快速排序LINQ的性能优势通过T []对的IEnumerable <T>

Question

只是为了好玩我建在C＃中的快速排序实现使用LINQ：

public static IEnumerable<T> quicksort<T>(IEnumerable<T> input) where T : IComparable<T>{ 
    if (input.Count() <= 1) return input; 
    var pivot = input.FirstOrDefault(); 
    var lesser = quicksort(input.Skip(1).Where(i => i.CompareTo(pivot) <= 0)); 
    var greater = quicksort(input.Where(i => i.CompareTo(pivot) > 0)); 
    return lesser.Append(pivot).Concat(greater); 
} 

它在大约13秒10000个排序随机整数。

将其更改为使用int []而不是List结果的性能会提高约700倍！对相同的10000个随机整数只需要21ms。

public static T[] quicksortArray<T>(T[] input) where T : IComparable<T>{ 
    if (input.Count() <= 1) return input; 
    var pivot = input.FirstOrDefault(); 
    var lesser = quicksortArray(input.Skip(1).Where(i => i.CompareTo(pivot) <= 0).ToArray()); 
    var greater = quicksortArray(input.Where(i => i.CompareTo(pivot) > 0).ToArray()); 
    return lesser.Append(pivot).Concat(greater).ToArray(); 
} 

只看我会认为这将有更坏 性能的代码。我认为.ToArray（）会在内存中创建一个额外的数组，并在那里复制所有整数。 我认为传递数组与传递列表应该大致相同。

那么这个巨大的性能差异从哪里来？

Answer 1

这就是为什么你应该很小心迭代IEnumerable多次。

您第一次打电话给quicksort时，您通过List。它再次调用quicksort两次，在每种情况下，您传递的IEnumerable代表一个查询，它将跳过第一个项目，然后对每个项目执行比较。然后，您将该查询传递给两个更多quicksort的实例，但使查询不仅会跳过第一个项目并比较其后的每个项目，但会跳过该查询结果的第一个项目，然后比较每个项目即之后的东西。这意味着当你最终达到一个值时，你有一个代表log（n）跳过的查询，并将序列中的每个项目与值log（n）次进行比较。

在你你不传递秒执行查询到quicksort，你正在评估这些查询自己的价值观和传递值来操作，然后可以使用这些值的两倍，而不是不断地执行一个非常复杂的查询多次。

Answer 2

关于linq查询的事情是懒惰的，他们不会被评估，直到你调用像ToArray或ToList这样的方法。在例如你的第一个代码，这个查询：

input.Skip(1).Where(i => i.CompareTo(pivot)) 

将至少两次每次调用quicksort，一旦Count()，一次用于FirstOrDefault时间进行评估。这意味着过滤操作将重复为每个呼叫一遍又一遍。另一方面，如果您使用ToArray，由于您已经在数组中过滤了元素，因此Where将不会每次都执行，只有在您拨打ToArray后才会执行，就是这样。这是代码之间的差异，基于此你可以为其他部分做数学运算。