c# - 这两种用于改组 IEnumerable 的算法之间是否存在性能差异？

这两个问题给出了用于改组 IEnumerable 的类似算法:

C#: Is using Random and OrderBy a good shuffle algorithm?

Can you enumerate a collection in C# out of order?

以下是并排的两种方法:

public static IEnumerable<T> Shuffle1<T> (this IEnumerable<T> source)
{
    Random random = new Random ();
    T [] copy = source.ToArray ();

    for (int i = copy.Length - 1; i >= 0; i--) {
        int index = random.Next (i + 1);
        yield return copy [index];
        copy [index] = copy [i];
    }
}


public static IEnumerable<T> Shuffle2<T> (this IEnumerable<T> source)
{
    Random random = new Random ();
    List<T> copy = source.ToList ();

    while (copy.Count > 0) {
        int index = random.Next (copy.Count);
        yield return copy [index];
        copy.RemoveAt (index);
    }
}

它们基本上是相同的，除了一个使用 List ，一个使用数组。从概念上讲，第二个对我来说似乎更清楚。但是使用数组是否可以获得实质性的性能优势？即使 Big-O 时间相同，如果它快几倍，它也会产生显着的差异。

最佳答案

由于 RemoveAt，第二个版本可能会慢一点。列表实际上是在向其中添加元素时会增长的数组，因此，中间的插入和删除很慢(实际上，MSDN 声明 RemoveAt 具有 O(n) 复杂度)。

无论如何，最好的方法是简单地使用分析器来比较这两种方法。

关于c# - 这两种用于改组 IEnumerable 的算法之间是否存在性能差异？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4412405/