1//位图排序法,时空高效的至高境界 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++) { //供简单的正确性测试 31 scanf("%d", &i); //注意,输入的数不能重复 32 set(i); //否则当只输入一次 33 } 34 for (i = 0; i < N; i++) { 35 if (test(i)) 36 printf("%d\n", i); 37 } 38 return 0; 39} 为什么说这个算法时空效率达到及致呢?我们对100万个不重复的正整数(1000000以内)的文件进行测试:
系统排序 C++/STL.set C/qsort C/位图 总时间(s) 89 38 12.6 10.7 计算时间(s) 79 28 2.4 0.5 内存使用(MB) 0.8 70 4 1.25 (本测试数据是在较旧的电脑上测试的,但还是体现性能的差距) 第一行是总时间,第二行的计算时间是总时间减去数据读取耗时10.2秒。虽然通用C++程序使用内存和CPU时间是专用C程序(C/位图)的50倍,但是它的使用仅需要一半的代码,并能很容易扩展到其他问题上,这也是专用C程序最大的缺点吧。
|