1//位圖排序法，時(shí)空高效的至高境界
2#include <cstdio>
3
4#define BITSPERWORD 32
5#define SHIFT 5
6#define MASK 0x1F
7#define N 10000000
8int a[1 + N/BITSPERWORD];
9
10void set(int i){
11 a[i >> SHIFT] |= (1<<(i & MASK));
12}
13
14void clr(int i){
15 a[i >> SHIFT] &= ~(1<<(i & MASK));
16}
17
18int test(int i){
19 return a[i >> SHIFT] & (1<<(i & MASK));
20}
21
22int main(void) {
23 int i;
24 for (i = 0; i < N; i++) {
25 clr(i);
26 }
27 //while (scanf("%d", &i) != EOF) {
28 // set(i);
29 //}
30 for (int j = 0; j < 3; j++) { //供簡(jiǎn)單的正確性測(cè)試
31 scanf("%d", &i); //注意，輸入的數(shù)不能重復(fù)
32 set(i); //否則當(dāng)只輸入一次
33 }
34 for (i = 0; i < N; i++) {
35 if (test(i))
36 printf("%d\n", i);
37 }
38 return 0;
39}
為什么說這個(gè)算法時(shí)空效率達(dá)到及致呢？我們對(duì)１００萬個(gè)不重復(fù)的正整數(shù)（１００００００以內(nèi)）的文件進(jìn)行測(cè)試：
系統(tǒng)排序 C++/STL.set C/qsort C/位圖
總時(shí)間(s) 89 38 12.6 10.7
計(jì)算時(shí)間(s) 79 28 2.4 0.5
內(nèi)存使用(MB) 0.8 70 4 1.25
（本測(cè)試數(shù)據(jù)是在較舊的電腦上測(cè)試的，但還是體現(xiàn)性能的差距）
第一行是總時(shí)間，第二行的計(jì)算時(shí)間是總時(shí)間減去數(shù)據(jù)讀取耗時(shí)１０.２秒。雖然通用C++程序使用內(nèi)存和ＣＰＵ時(shí)間是專用Ｃ程序（C/位圖）的５０倍，但是它的使用僅需要一半的代碼，并能很容易擴(kuò)展到其他問題上，這也是專用C程序最大的缺點(diǎn)吧。
|
