快速排序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後纔會執行，就是這樣。這是代碼之間的差異，基於此你可以爲其他部分做數學運算。