|
 |
栏目导栏 |
|
| |
|
|
|
|
|
资料搜索 |
|
| |
|
|
|
|
|
热门文章 |
|
| |
|
|
|
|
|
最新文章 |
|
| |
|
|
|
| |
| |
|
|
|
|
1//位图排序法，时空高效的至高境界 tqfLinux联盟
2#include <cstdio> tqfLinux联盟
3 tqfLinux联盟
4#define BITSPERWORD 32 tqfLinux联盟
5#define SHIFT 5 tqfLinux联盟
6#define MASK 0x1F tqfLinux联盟
7#define N 10000000 tqfLinux联盟
8int a[1 + N/BITSPERWORD]; tqfLinux联盟
9 tqfLinux联盟
10void set(int i){ tqfLinux联盟
11 a[i >> SHIFT] |= (1<<(i & MASK)); tqfLinux联盟
12} tqfLinux联盟
13 tqfLinux联盟
14void clr(int i){ tqfLinux联盟
15 a[i >> SHIFT] &= ~(1<<(i & MASK)); tqfLinux联盟
16} tqfLinux联盟
17 tqfLinux联盟
18int test(int i){ tqfLinux联盟
19 return a[i >> SHIFT] & (1<<(i & MASK)); tqfLinux联盟
20} tqfLinux联盟
21 tqfLinux联盟
22int main(void) { tqfLinux联盟
23 int i; tqfLinux联盟
24 for (i = 0; i < N; i++) { tqfLinux联盟
25 clr(i); tqfLinux联盟
26 } tqfLinux联盟
27 //while (scanf("%d", &i) != EOF) { tqfLinux联盟
28 // set(i); tqfLinux联盟
29 //} tqfLinux联盟
30 for (int j = 0; j < 3; j++) { //供简单的正确性测试 tqfLinux联盟
31 scanf("%d", &i); //注意，输入的数不能重复 tqfLinux联盟
32 set(i); //否则当只输入一次 tqfLinux联盟
33 } tqfLinux联盟
34 for (i = 0; i < N; i++) { tqfLinux联盟
35 if (test(i)) tqfLinux联盟
36 printf("%d\n", i); tqfLinux联盟
37 } tqfLinux联盟
38 return 0; tqfLinux联盟
39} tqfLinux联盟
为什么说这个算法时空效率达到及致呢？我们对１００万个不重复的正整数（１００００００以内）的文件进行测试： tqfLinux联盟
tqfLinux联盟
系统排序 C++/STL.set C/qsort C/位图 tqfLinux联盟
总时间(s) 89 38 12.6 10.7 tqfLinux联盟
计算时间(s) 79 28 2.4 0.5 tqfLinux联盟
内存使用(MB) 0.8 70 4 1.25 tqfLinux联盟
（本测试数据是在较旧的电脑上测试的，但还是体现性能的差距） tqfLinux联盟
第一行是总时间，第二行的计算时间是总时间减去数据读取耗时１０.２秒。虽然通用C++程序使用内存和ＣＰＵ时间是专用Ｃ程序（C/位图）的５０倍，但是它的使用仅需要一半的代码，并能很容易扩展到其他问题上，这也是专用C程序最大的缺点吧。 tqfLinux联盟
下文回复还有网友提供的Bitmap排序的C#版，我还没有进行性能测试，估计性能也是很好的，而且那样的程序扩展性显然强很多。
Linux联盟收集整理 ,转贴请标明原始链接,如有任何疑问欢迎来本站Linux论坛讨论 |
|
|
|
|
|
