在排序固定長度的小陣列時,那些 big-O 優異的演算法往往討不到便宜,而且還很容易因為多餘的操作而拖慢速度。Sorting Network 就是為了排序固定長度的小陣列而發明的。Sorting Network 是一組事先規劃好的比較、交換操作,只要按照固定步驟操作就能將資料排序。

若一個 Sorting Network 滿足某些條件,就可以將操作步驟平行化或者實作成平行排序硬體,這是這類演算法最大的優勢,不過這不是本文的重點。即使在沒有平行化的情況下,Sorting Network 作為循序執行的排序法效能通常也不錯,至少可以狂電 Bubble、Insertion sort,而且所有的動作都是固定的,可以輕易寫成一連串無迴圈的 if-swap 串,這在「big-O不代表一切」的小資料世界裡具有實作優勢。

有一些演算法可以系統化產生 Sorting Network,例如 Bose-Nelson、Batcher's odd–even mergesort、Bitonic 等等。一般如果要寫 Sorting Network 程式,比較簡單的方法是 先用這些演算法產生比較序列 ,然後再手工刻出一堆 if-swap 串。例如:

void sort_int6(int* arr)
{
#define CMP_SWAP(i, j) \
        if (arr[j] < arr[i]) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }

    CMP_SWAP(1, 2);
    CMP_SWAP(0, 2);
    CMP_SWAP(0, 1);
    CMP_SWAP(4, 5);
    CMP_SWAP(3, 5);
    CMP_SWAP(3, 4);
    CMP_SWAP(0, 3);
    CMP_SWAP(1, 4);
    CMP_SWAP(2, 5);
    CMP_SWAP(2, 4);
    CMP_SWAP(1, 3);
    CMP_SWAP(2, 3);

#undef CMP_SWAP
}

這些系統化方法產生出來的步驟並非對所有輸入長度都是最佳,所以有一些人專門在尋找針對某個特定長度的最佳排序步驟,他們使用的方法包括暴力解、演化式演算法等等。至於斤斤計較幾個操作是否具有實用價值,我就不清楚了。

要證明某個 Sorting Network 是否是某個長度的最佳排序步驟其實並不是件容易的事,Knuth 在 《Art of Computer Programming》提過一個在輸入長度 16 時,depth 最優的演算法,Knuth 和 Floyd 在 1960 年代就已經做過部份證明,然而完整的證明直到 2014 年才出爐。

圓規正轉,我想到既然有系統化的生成演算法,那應該可以用 C++ template 實作,讓編譯器幫我們規劃比較與交換的序列,於是就寫了個小程式來玩玩看。使用的方法大概是這樣:

std::array<int, 8> intArray = {...};
std::array<string, 8> strArray = {...};

FixedSort<8> sort8;     // sorting network for size 8.
sort8(intArray.data());
sort8(strArray.data());

以下只是概念驗證的實作,並沒有考慮太多細節:

// Generate sorting network using Bose-Nelson algorithm.

template <int J, int K>
struct CompareSwap
{
    template <typename T>
    inline static void apply(T* array)
    {
        if (array[J] > array[K]) {
            std::swap(array[J], array[K]);
        }
    }
};

template <int J, int LenJ, int K, int LenK>
struct Merge
{
    enum {
        MidJ = LenJ / 2,
        MidK = (LenJ & 1) ? LenK / 2 : (LenK + 1) / 2
    };

    template <typename T>
    inline static void apply(T* array)
    {
        Merge<J, MidJ, K, MidK>::apply(array);
        Merge<J + MidJ, LenJ - MidJ, K + MidK, LenK - MidK>::apply(array);
        Merge<J + MidJ, LenJ - MidJ, K, MidK>::apply(array);
    }
};

template <int J, int K>
struct Merge<J, 1, K, 1>
{
    template <typename T>
    inline static void apply(T* array)
    {
        CompareSwap<J, K>::apply(array);
    }
};

template <int J, int K>
struct Merge<J, 1, K, 2>
{
    template <typename T>
    inline static void apply(T* array)
    {
        CompareSwap<J, K+1>::apply(array);
        CompareSwap<J, K>::apply(array);
    }
};

template <int J, int K>
struct Merge<J, 2, K, 1>
{
    template <typename T>
    inline static void apply(T* array)
    {
        CompareSwap<J, K>::apply(array);
        CompareSwap<J+1, K>::apply(array);
    }
};

template <int Start, int Len>
struct Split
{
    enum { Mid = Len / 2 };

    template <typename T>
    inline static void apply(T* array)
    {
        Split<Start, Mid>::apply(array);
        Split<Start + Mid, Len - Mid> ::apply(array);
        Merge<Start, Mid, Start + Mid, Len - Mid>::apply(array);
    }
};

template <int Start>
struct Split<Start, 1>
{
    inline static void apply(void* array) {}
};

template <int Len>
struct FixedSort
{
    // static_assert(Len >= 2 && Len <= 16, "Len must between [2, 16]");

    template <typename T>
    inline void operator()(T* array)
    {
        Split<0, Len>::apply(array);
    }
};

然後我用 6 ~ 16 長度的整數陣列測試執行時間,雖然事先已經預期會比 std::sort() 還快,但我完全沒想到在長度 8 的時候 FixedSort 耗時竟然只有 g++ 內建 std::sort() 的 1/15,在其他長度大概都比 std::sort() 快個 4 ~ 10 倍。(這裡有個有趣的錯誤,見補充)

實際觀察 FixedSort 用 g++ -O2 所生成的 x86 和 x86_64 組合語言,所有的函數全部被 inline,因此等效於一連串無迴圈的 if-swap。(組合語言這裡就不附了,有興趣的讀者可以自己玩玩看。)

我個人沒有根據的胡亂猜測,FixedSort 之所以比 g++ 內建的 std::sort() 還快,可能之一是 libstdc++ 在小陣列優化不足。而 FixedSort 則因迴圈攤平得到許多好處,特別是現代的處理器的分支預測、指令層級平行能力。這只是猜想,實際原因我沒有去追蹤。

Bitonic 看起來似乎比 Bose-Nelson 更快一點點,或許可以找個時間來實作看看。

2016-mar-06 補充:

由於效能差距太可疑了,我今天重新做了實驗,奇怪的是將 array 改成 vector 之後,差距變得合理多了,FixedSort 耗時大約是 std::sort 的 60%~90% 左右。

不確定之前的差距所在,不太像是邏輯錯誤,因為我也只是把之前的程式碼改 type 而已,而且我有用 std::is_sorted() 檢查過排序正確性。

再補充:找到原因了,其實還蠻好笑的。我在測試正確性的時候用的是完整的 std::is_sorted(),但是測效能時為了減少干擾,只檢查首末兩項的 checksum。

好玩的地方在於當 g++ 把所有的東西 inline 進來後發現我們只關心首末兩項,所以就只把首末兩項排好,與首末兩項無關的程式碼都被丟棄。


參考資料:

, ,

novus 發表在 痞客邦 PIXNET 留言(0) 人氣()