來自通過產生元素生成的IEnumerable的隨機樣本？

我有一個產生 的方法IEnumerable，但它yield在執行時使用關鍵字回傳元素。我并不總是知道總收藏有多大。當您嘗試使用 .NET時，它有點類似于標準Fibonacci示例，只是它會產生有限數量的元素。話雖這么說，因為沒有辦法事先知道它會回傳多少元素，所以如果有太多元素，它可能會永遠保持產量。

當我在這里尋找有關此主題的其他問題時，其中一個答案提供了一個干凈的 LINQ 查詢，可以從集合中隨機抽樣 N 個元素。但是，這里的假設是該集合是靜態的。如果您訪問 Try .NET 網站并修改代碼以使用該答案中的隨機抽樣實作，您將得到一個無限回圈。

public static void Main()
{
    foreach (var i in Fibonacci().OrderBy(f => Guid.NewGuid()).Take(20))
    {
        Console.WriteLine(i);
    }
}

查詢嘗試對回傳的所有IEnumerable元素進行排序，但要對所有元素進行排序，它必須首先計算所有元素，其中有無限多個，這意味著它將繼續下去，永遠不會回傳有序集合。

那么對于IEnumerable包含未知數量的元素進行隨機抽樣的好策略是什么？甚至可能嗎？

uj5u.com熱心網友回復：

如果一個序列的長度是無限的，那么您不能在少于無限的時間內從中選擇 N 個元素，其中選擇序列中每個元素的機會是相同的。

但是，可以從長度未知但有限的序列中選擇 N 個專案。您可以使用水庫采樣來做到這一點。

這是一個示例實作：

/// <summary>
/// This uses Reservoir Sampling to select <paramref name="n"/> items from a sequence of items of unknown length.
/// The sequence must contain at least <paramref name="n"/> items.
/// </summary>
/// <typeparam name="T">The type of items in the sequence from which to randomly choose.</typeparam>
/// <param name="items">The sequence of items from which to randomly choose.</param>
/// <param name="n">The number of items to randomly choose from <paramref name="items"/>.</param>
/// <param name="rng">A random number generator.</param>
/// <returns>The randomly chosen items.</returns>

public static T[] RandomlySelectedItems<T>(IEnumerable<T> items, int n, System.Random rng)
{
    // See http://en.wikipedia.org/wiki/Reservoir_sampling for details.

    var result = new T[n];
    int index = 0;
    int count = 0;

    foreach (var item in items)
    {
        if (index < n)
        {
            result[count  ] = item;
        }
        else
        {
            int r = rng.Next(0, index   1);

            if (r < n)
                result[r] = item;
        }

          index;
    }

    if (index < n)
        throw new ArgumentException("Input sequence too short");

    return result;
}

但是，這仍然必須遍歷整個序列，因此它不適用于無限長的序列。

如果您想支持超過 2^31 的輸入序列，您可以在實作中使用 longs，如下所示：

public static T[] RandomlySelectedItems<T>(IEnumerable<T> items, int n, System.Random rng)
{
    // See http://en.wikipedia.org/wiki/Reservoir_sampling for details.

    var  result = new T[n];
    long index  = 0;
    int  count  = 0;

    foreach (var item in items)
    {
        if (index < n)
        {
            result[count  ] = item;
        }
        else
        {
            long r = rng.NextInt64(0, index   1);

            if (r < n)
                result[r] = item;
        }

          index;
    }

    if (index < n)
        throw new ArgumentException("Input sequence too short");

    return result;
}

請注意，此實作需要 .Net 6.0 或更高版本，因為rng.NextInt64().

Also note that there's no point in making n long because you can't have an array that exceeds ~2^31 elements, so it wouldn't be possible to fill it. You could in theory fix that by returning multiple arrays, but I'll leave that as an exercise for the reader. ;)

uj5u.com熱心網友回復：

您需要指定要隨機選擇的專案數量。您可以通過Take移動OrderBy.

Fibonacci().Take(1000).OrderBy(f => Guid.NewGuid()).Take(20);

例如，將前 1k 個專案隨機化，然后從中挑選 20 個。

標籤：

上一篇：獲取具有重疊場景的日期持續時間的周數

下一篇：如何在c#中獲取資料表的多列的總和