这两种算法之间是否存在改变IEnumerable的性能差异？

Question

这两个问题为洗刷IEnumerable提供了类似的算法:

• C#:使用Random和OrderBy是一个很好的shuffle算法吗？
• 你可以在C#中乱序列举一个集合吗？

以下是两种方法并排:

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);
    }
}

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

Answer 1

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

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