實現快速又穩定的排序法 (2. 以Array.Sort為基礎，實踐部分OrderBy功能)

2012-09-14 置頂文章

6484
0
C#
2012-09-15

上次分析了比較了Linq.OrderBy( )與Array.Sort( )，發現Array.Sort( )的速度快很多。

但是我想要的是Linq.OrderBy()的特性－－穩定 + 不改變原始資料順序。

那麼，能不能將兩者特性結合，變得(快+省記憶體+穩定+不改變原始資料)呢？

讓我們動手試試吧！

首先，為了將問題簡化，將演算核心做成傳入Key、Value的陣列與Key的比較實作，但要符合穩定排序+不改變原始資料的Order原則；傳回值則是IEnumerable<TValue>。

而其他多載則先將資料轉換成陣列形式，再傳遞給核心函式。

關於核心，我的想法很簡單：

1. 如果來源資料需要轉換的話，先將其複製為陣列結構。

2. 建立一個相同大小的索引表。

3. 利用Array.Sort<TKey, TValue> 方法 (TKey[], TValue[], IComparer<TKey>)將索引表依照比較鍵值排序。

4. 掃描比較鍵值，將鍵值相等的區塊對應的索引區塊，利用Array.Sort<T> 方法 (T[], Int32, Int32)將索引表的每部分作子排序。

5. 依索引表，yield return每個TValue。


internal class Sorter1<T, TKey>
{
    public IEnumerable<T> OrderBy(T[] items, TKey[] keys, Comparer<TKey> comparer)
    {
        // 注意這裡的傳入keys會被排序
        return OrderByCore(items, keys, comparer);
    }

    public IEnumerable<T> OrderBy(T[] items, Func<T, TKey> keySelector, Comparer<TKey> comparer)
    {
        return this.OrderBy(items, computeKeys(items, keySelector, items.Length), comparer);
    }

    public IEnumerable<T> OrderBy(IEnumerable<T> items, Func<T, TKey> keySelector, Comparer<TKey> comparer)
    {
        T[] _items;
        TKey[] _keys;
        computeValuesAndKeys(items, keySelector, out _items, out _keys);
        return OrderBy(_items, _keys, comparer);
    }

    private IEnumerable<T> OrderByCore(T[] items, TKey[] keys, Comparer<TKey> comparer)
    {
        if (keys.Length > items.Length)
            throw new ArgumentException("keys 的長度大於 items 的長度。");
        int count = keys.Length;
        // 建立索引表
        int[] indexTable = new int[count];
        for (int i = 0; i < count; i++)
            indexTable[i] = i;
        // 將索引表依照比較鍵值排序。
        Array.Sort(keys, indexTable, comparer);
        // 為了穩定排序而做的子排序
        TKey keyLeft = keys[0];
        int indexLeft = 0;
        for (int i = 1; i < count; i++)
        {
            if (comparer.Compare(keys[i], keyLeft) == 0)
                continue;
            // 掃到不相等的部分時, 將之前相等的部分以索引自身重新排序
            if (i - 1 > indexLeft)
                Array.Sort(indexTable, indexLeft, i - indexLeft);
            indexLeft = i;
            keyLeft = keys[i];
        }
        // 注意邊界
        if (count - 1 > indexLeft)
            Array.Sort(indexTable, indexLeft, count - indexLeft);
        // 依索引順序將元素返回
        foreach (int i in indexTable)
            yield return items[i];
    }

    private TKey[] computeKeys(IEnumerable<T> items, Func<T, TKey> keySelector, int count)
    {
        TKey[] keys = new TKey[count];
        int i = 0;
        foreach (var item in items)
            keys[i++] = keySelector(item);
        return keys;
    }

    private void computeValuesAndKeys(IEnumerable<T> items, Func<T, TKey> keySelector, out T[] values, out TKey[] keys)
    {
        int count = items.Count();
        values = new T[count];
        keys = new TKey[count];
        int i = 0;
        foreach (var item in items)
        {
            values[i] = item;
            keys[i] = keySelector(item);
            i++;
        }
    }
}

或許大家對需要做兩步驟的排序有疑問，為什麼不利用自訂比較方法(Comparison)或是實作排序法，一次排序就能解決問題呢？

關於Comparison，其實我測試過了，把32行、第一個Array.Sort()改掉變成如下：


private IEnumerable<T> OrderByCore(T[] items, TKey[] keys, Comparer<TKey> comparer)
{
    if (keys.Length > items.Length)
        throw new ArgumentException("keys 的長度大於 items 的長度。");
    int count = keys.Length;
    // 建立索引表
    int[] indexTable = new int[count];
    for (int i = 0; i < count; i++)
        indexTable[i] = i;
    // 使用自訂Comparison排序
    Array.Sort(indexTable, new Comparison<int>((i, j) => {
        int result = comparer.Compare(keys[i], keys[j]);
        if (result == 0) return i - j;
        return result;
    }));
    // 子排序可以全數省略
    foreach (int i in indexTable)
        yield return items[i];
}

的確省了很多程式碼，可惜效能卻也大幅降低。

至於自己寫演算法，這我當然也考慮過。但一來一開始先以最少的code去實驗可行性；二來若寫出不怎樣的快速排序~~會被笑~~速度會差framkwork內建許多(大家可以自己試試看)；最後則是我寫blog喜歡~~歹戲拖棚~~好酒沉甕底。

當然因為是實驗性作品所以bug不少，這也是拖戲的竅門之一？

最後當然要驗收一下成果，加上新的測試方法，由於使用相同的亂數種子，得到的陣列會與上次一樣：


static void Main(string[] args)
{
    MyData[] items = MyData.getRandomMyData(10, 10000000, 0, 4000000);

    GC.Collect();
    GC.WaitForPendingFinalizers();
    GC.Collect();
    Sorter1Order(items);

    Console.ReadKey();
}

static void Sorter1Order(MyData[] arr)
{
    var comparer = Comparer<int>.Default;
    Func<MyData, int> keySelector = item => item.Value;
    Sorter2.Sorter1<MyData, int> sorter = new Sorter2.Sorter1<MyData, int>();
    var memBefore = System.Environment.WorkingSet;
    var watch = System.Diagnostics.Stopwatch.StartNew();
    IEnumerable<MyData> result = sorter.OrderBy(arr, keySelector, comparer);
    PrintResult(result, 10);
    //foreach (var item in result) break;
    var memAfter = System.Environment.WorkingSet;
    GC.KeepAlive(result);
    Console.WriteLine("Sorter1.Order use: {0}ms", watch.ElapsedMilliseconds);
    Console.WriteLine("mem usage: {0:###,###,###}", memAfter - memBefore);
    //PrintResult(result, 10);
}

新的結果：