通过产生元素生成的 IEnumerable 中的随机样本？

Question

我有一个生成 IEnumerable 的方法，但它使用 yield keyword to return elements when executed. I don't always know how big the total collection is. It's kind of similar to the standard Fibonacci example when you go to Try .NET 除了它会生成有限数量的元素。话虽这么说，因为事先无法知道它会 return 多少元素，如果元素太多，它可能会永远保持屈服。

当我在这里查找有关此主题的其他问题时，one of the answers 提供了一个干净的 LINQ 查询，可以从集合中随机抽取 N 个元素。但是，这里的假设是集合是静态的。如果您转到 Try .NET 网站并修改代码以使用该答案中的随机采样实现，您将得到一个无限循环。

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

查询尝试对所有 returned IEnumerable 中的元素进行排序，但要对所有元素进行排序，它必须首先计算所有元素，其中有无数个，这意味着它会一直持续下去，永远不会 return 一个有序的集合。

那么，对于包含元素数量未知的 IEnumerable 随机抽样的好策略是什么？有可能吗？

Answer 1

如果一个序列的长度是无限的，你不能在小于无限的时间内从它 select N 个元素，其中序列中每个元素被 selected 的机会是相同的.

然而，有可能 select N 项来自未知的序列，但有限，长度。您可以使用 reservoir sampling.

来做到这一点

这是一个示例实现：

/// <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 的输入序列，你可以像这样在实现中使用长整数：

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()。

另请注意，使 n 变长没有意义，因为您不能拥有超过 ~2^31 个元素的数组，因此无法填充它。理论上您可以通过返回多个数组来解决这个问题，但我将把它留作 reader 的练习。 ;)

通过产生元素生成的 IEnumerable 中的随机样本？

Random sample from an IEnumerable generated by yielding elements?

c#

linq

random

.net-core