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

Question

这两个问题给出了洗牌 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 时间相同，如果快几倍，也会产生明显的差异。

Answer 1

由于 RemoveAt，第二个版本可能会慢一点。列表实际上是数组，当您向它们添加元素时它会增长，因此，中间的插入和删除很慢(事实上，MSDN 指出 RemoveAt 的复杂度为 O(n))。

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