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

contents

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

主要問題

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

基數排序降低常數

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

非負整數基數排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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;
}
}

浮點數基數排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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。如果算法屬於調整某些元素後,再對整體進行排序,這時候 sortstable_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_heappop_heap … 的接口。