實現快速又穩定的排序法 (1.比較內建排序)
上次提到了LINQ的OrderBy是最慢的一塊。大略來說，有90%的運算時間都是用在它上面。
如果想要優化，自然是對這部分下手了。
在開始之前，先讓我來比較一下.net framework內建的排序功能－－Linq.OrderBy( )與Array.Sort( )。
前者是對所有實作IEnumerable介面的物件都可以使用的擴充方法、也是我在分錢那篇用到的功能。
後者則是僅對一微陣列物件有用的靜態排序方法。
其他的比較我晚點再提，現在先來一點測試用的程式碼：
struct MyData : IComparable<MyData>
{
public int Index;
public int Value;
public MyData(int index, int value)
{
this.Index = index;
this.Value = value;
}
public int CompareTo(MyData other)
{
// 小技巧: 對兩個int或short比較, 用減法比調用比較子更快, 尤其在x64編譯環境下
return this.Value - other.Value;
//return this.Value.CompareTo(other.Value);
}
public override string ToString()
{
return string.Format("MyData: {0}\t{1}", this.Value, this.Index);
}
static public MyData[] getRandomMyData(int count, int minValue, int maxValue)
{
return getRandomMyData(new Random(), count, minValue, maxValue);
}
static public MyData[] getRandomMyData(int seed, int count, int minValue, int maxValue)
{
return getRandomMyData(new Random(seed), count, minValue, maxValue);
}
static public MyData[] getRandomMyData(Random rnd, int count, int minValue, int maxValue)
{
MyData[] arr = new MyData[count];
for (int i = 0; i < count; i++)
arr[i] = new MyData(i, rnd.Next(minValue, maxValue));
return arr;
}
}以上是比較用的簡單結構。
以下則進行測試：
static void Main(string[] args)
{
MyData[] items = MyData.getRandomMyData(10000000, 0, 4000000);
GC.Collect();
GC.WaitForPendingFinalizers();
GC.Collect();
LinqOrder(items);
GC.Collect();
GC.WaitForPendingFinalizers();
GC.Collect();
ArraySort(items);
Console.ReadKey();
}
static void ArraySort(MyData[] items)
{
var memBefore = System.Environment.WorkingSet;
var watch = System.Diagnostics.Stopwatch.StartNew();
Array.Sort(items);
var memAfter = System.Environment.WorkingSet;
Console.WriteLine("{0} use: {1}ms", "ArraySort", watch.ElapsedMilliseconds);
Console.WriteLine("mem usage: {0:###,###,##0}", memAfter - memBefore);
PrintResult(items, 10);
}
static void LinqOrder<T>(T[] items)
{
var memBefore = System.Environment.WorkingSet;
var watch = System.Diagnostics.Stopwatch.StartNew();
var result = items.OrderBy(item => item);
foreach (var item in result) break; // 使延遲的排序工作真的執行
var memAfter = System.Environment.WorkingSet;
GC.KeepAlive(result);
Console.WriteLine("{0} use: {1}ms", "LinqOrder", watch.ElapsedMilliseconds);
Console.WriteLine("mem usage: {0:###,###,##0}", memAfter - memBefore);
PrintResult(result, 10);
}
static void PrintResult(System.Collections.IEnumerable ienumerable, int count)
{
Console.WriteLine("\tValue\tIndex");
int i = 0;
foreach (var item in ienumerable)
{
Console.WriteLine(item);
if (++i > count) return;
}
}最後是結果：
從這兩張圖來看，速度與記憶體均是Array.Sort大勝。
再來看看印出來前10項結果，因為我使用Random的範圍比count小，故一定會有重複的值。
縮小範圍看Value=3的部分，Array.Sort的Index沒有固定順序，而Linq.Order則是維持原本的順序(由小到大)。
這個結果代表Linq.Order是穩定的(stable)、而Array.Sort則是不穩定的。
其實這不用特別做測試，MSDN裡面就有寫了：
Array.Sort<T> 方法 (T[])：這個方法使用 QuickSort 演算法。這個實作會執行不穩定的排序；換言之，如果兩個項目相等，其順序可能不會被保留。對照之下，穩定的排序會保留相等項目的順序。
(我：Array.Sort似乎是使用改良的Introsort，而非純正的Quicksort)
Enumerable.OrderBy<TSource, TKey> 方法：這個方法會執行穩定的排序，也就是說，如果兩個項目的索引鍵相等，就會保留項目的順序。 相反地，不穩定的排序並不會保留具有相同索引鍵之項目的排序。
除此之外，兩者不同點還有許多，做個簡單的表格列舉一下：
|
Array.Sort |
Linq.Order |
|
|
速度 |
快 |
慢 |
|
使用記憶體 |
少 |
多 |
|
穩定排序法 |
不穩定 |
穩定 |
|
影響原始資料 |
是，會將傳入陣列作排序 |
否，只傳回已排序的列舉結果 |
|
適用類別 |
低，只能排序陣列 |
高，可對所有實作IEnumerable的資料做排序，包含陣列 |
|
Keys指定 |
傳入另一個索引鍵陣列做比較。該索引鍵陣列亦會被排序。 |
使用Func<TSource, TKey> keySelector的delegate取得鍵值 |
|
指定範圍 |
可指定陣列開始排序的起點與長度。 |
可用Take方法指定排序長度，但未排序的部分不會在結果中 |
|
子排序 |
較麻煩 |
簡單，使用ThenBy方法即可。 |