c# - 如何在 C# 中实现列表的延迟改组？

Question

我正在寻找在 c# 中实现延迟洗牌。
我只关心处理前几个元素所需的时间。我不在乎原始列表是否被修改(即删除元素就可以了)。我不在乎处理时间是否随着迭代器到达列表的末尾而变长(当然，只要它保持在合理的范围内)。
上下文:我有一个很大的列表，我想从中获取相对较少的随机样本。在大多数情况下，我只需要第一个随机元素，但在同样罕见的情况下，我需要列表中的所有元素。
如果可能的话，我想将其作为扩展方法来实现，就像这样(但没有扩展方法的答案也很好):

public static class Program
{
    public static IEnumerable<T> lazy_shuffle<T>(this IEnumerable<T> input, Random r)
    {
        //do the magic
        return input;
    }
    static void Main(string[] args)
    {
        var start = DateTime.Now;
        var shuffled = Enumerable.Range(0, 1000000).lazy_shuffle(new Random(123));
        var enumerate = shuffled.GetEnumerator();
        foreach (var i in Enumerable.Range(0, 5))
        {
            enumerate.MoveNext();
            Console.WriteLine(enumerate.Current);
        }
        Console.WriteLine($"time for shuffling 1000000 elements was {(DateTime.Now - start).TotalMilliseconds}ms");
    }
}

笔记:

input.OrderBy(i => r.Next())还不够好，因为一旦为列表的每个元素生成一个随机数，它就需要遍历整个列表。

这不是 Lazy Shuffle Algorithms 的副本因为我的问题对算法的限制不那么严格，而是需要在 c#

中实现

这不是 Randomize a List<T> 的副本因为这个问题是关于常规洗牌而不是懒惰洗牌。

更新:

一个 Count存在。存在对元素的随机访问。它不是严格意义上的不可枚举，而只是一个大 List或 Array .我已将问题更新为“列表”而不是“可枚举”。只有惰性洗牌器的输出需要是可枚举的，源可以是一个实际的列表。

选择应该是公平的，即每个元素需要有相同的机会首先被选中。

源列表的突变/修改很好

最后我只需要从列表中随机抽取 N 个元素，但我事先不知道 N

Answer 1

由于原始列表可以修改，这里提供一个非常简单高效的解决方案，基于this answer :

public static IEnumerable<T> Shuffle<T>(this IList<T> list, Random rng)
{
    for(int i = list.Count - 1; i >= 0; i--)
    {
        int swapIndex = rng.Next(i + 1);
        yield return list[swapIndex];
        list[swapIndex] = list[i];
    }
}