2018-07-22

優化技巧 - 排序/優先隊列

1. 主要問題
2. 基數排序降低常數
1. 2.1. 非負整數基數排序
2. 2.2. 浮點數基數排序
3. 慎選內建排序
4. 優先隊列

主要問題

在算法問題中，時常結合到排序，而排序的常數也大大影響到我們整體的效能。

基數排序降低常數

若是一般原始型別的排序，可以透過基數排序 (radix sort)。從排序的範圍來決定是否要劃分 8-bit 一組一組。若範圍介於可容忍的 $[0, v]$，當 $v < n$ 時，直接開 $n$ 個 bucket 的方式更好。因為大多數的複雜度都大於線性 $O(n)$

非負整數基數排序

void _radix_sort(Pt *A, int n) {
    static Pt _tmp[MAXN];
    const int CHUNK = 256;
    static int C[CHUNK];
    Pt *B = _tmp, *T;
    for (int x = 0; x < 8; x++) {
        const int d = x*8;
        memset(C, 0, sizeof(C));
        for (int i = 0; i < n; i++)
            C[(A[i].x>>d)&(CHUNK-1)]++;
        for (int i = 1; i < CHUNK; i++)
            C[i] += C[i-1];
        for (int i = n-1; i >= 0; i--)
            B[--C[(A[i].x>>d)&(CHUNK-1)]] = A[i];
        T = A, A = B, B = T;
    }
}

浮點數基數排序

void radix_sort(Pt *A, int n) {
    for (int i = 0; i < n; i++) {
        int32_t &v = *((int32_t *) &(A[i].s));
        if ((v>>31)&1)
            v = ~v;
        else
            v = v | 0x80000000;
    }
    static Pt _tmp[MAXN*2];
    static const int CHUNK = 256;
    static int C[1<<8];
    Pt *B = _tmp, *T;
    for (int x = 0; x < 4; x++) {
        const int d = x*8;
        memset(C, 0, sizeof(C));
        for (int i = 0; i < n; i++)
            C[((*((int32_t *) &(A[i].s)))>>d)&(CHUNK-1)]++;
        for (int i = 1; i < CHUNK; i++)
            C[i] += C[i-1];
        for (int i = n-1; i >= 0; i--)
            B[--C[((*((int32_t *) &(A[i].s)))>>d)&(CHUNK-1)]] = A[i];
        T = A, A = B, B = T;
    }
    for (int i = 0; i < n; i++) {
        int32_t &v = *((int32_t *) &(A[i].s));
        if ((v>>31)&1)
            v = v & 0x7fffffff;
        else
            v = ~v;
    }
}

慎選內建排序

內建排序常見的有 qsort, sort, stable_sort，我不推薦使用 qsort，因為它在很久以前找到了一個退化情況 A Killer Adversary for Quicksort - 1995，有些題目的測資會出這種特別案例，導致當年的萌新內心受創。除非只有 C 的情況，否則請避開 qsort。如果算法屬於調整某些元素後，再對整體進行排序，這時候 sort 比 stable_sort 慢很多。當情況非常接近已經排序的時候，就使用 stable_sort。

優先隊列

使用 priority queue 的方法通常有三種 set, priority_queue, heap。

功能最多的 set、次少的 priority_queue，最少的 heap。
效能方面則是 heap 最快、次著 priority_queue、最後 set。
代碼維護最容易的 set、最差的 heap。

之前很排斥使用 priority_queue，原因在於撰寫 operator< 與我的邏輯相反，因此都偏愛使用 set，但是效能被拉出來的時候，又必須退回類似 C 的 make_heap、pop_heap … 的接口。

Morris' Blog