集合包含关系的快速算法 - simcity - 博客园
集合包含关系的快速算法
2012-10-05 22:18 by simcity, 751 阅读, 0 评论, 收藏, 编辑
#1 每行数据代表一个集合，如何判断集合的包含关系？ -- 集合的数据仅在有限范围内。
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 a --24个元素
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 b --24个元素
最容易想到的是蛮力运算，计算前还应该知道谁元素多，对吧？不过还好，我耍了个花招，在读取数据时已经把数组元素数目存入数组第0号元素。
1 for each element x in a
2 if (!setContain(b , x))
3 return false;
4
5 return true;
#2 数据在31以内，考虑用无符号数编码数组
例如 1 2 3 4 用 0x00000000 00000000 00000000 00001111编码，也就是1用第一个bit，2用第二个bit，依此类推...
但是数据里面有0，也好说，0用第一个bit，1用第二个bit，依此类推...
这样1 2 3 4 最终形式 0x00000000 00000000 00000000 00011110
这么一来要判断要简单多了，只需要
复制代码
1 unsigned src //代表较多元素数组的编码
2 unsigned dst //代表较少元素数组的编码
3 if (src & dst == dst)
4 return true;
5
6 return false;
复制代码
但是且慢，如何将1 2 3 4等元素存入 src 之类变量？
So, 手工加工的 table登场
复制代码
1 unsigned int table[32] = {
2 0x00000001, 0x00000002, 0x00000004, 0x00000008,
3 0x00000010, 0x00000020, 0x00000040, 0x00000080,
4 0x00000100, 0x00000200, 0x00000400, 0x00000800,
5 0x00001000, 0x00002000, 0x00004000, 0x00008000,
6 0x00010000, 0x00020000, 0x00040000, 0x00080000,
7 0x00100000, 0x00200000, 0x00400000, 0x00800000,
8 0x01000000, 0x02000000, 0x04000000, 0x08000000,
9 0x10000000, 0x20000000, 0x40000000, 0x80000000
10 };
复制代码
只需要每数组扫描一遍即可实现目标。
1 src = 0;
2
3 for each element x in a
4 src = src + table[x];
问题基本解决。
#3 考虑如下数组：如何扩展至64位
25 26 27 28 29 30 31 32 33 34 35 36 37 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
26 27 28 29 30 31 32 33 34 35 36 37 38 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
可按下图来考虑
复制代码
number bit
0 1
. .
. .
. .
31 32
32 -- 0 1
. .
. .
. .
63 -- 31 32
复制代码
再构造数组
1 int cache = {0, 32};
2 unsigned int cacheManager[2][2];
3 //用二维数组维护两个数组的编码，每行编码一数组
方法如下，分别以16 ， 63为例
运算 (16 & 0x00000020) >> 5 得出 0， 然后 16 - cache[0] 得出 16, 16 存入cacheManager[?][ 0 ]
运算 (63 & 0x00000020) >> 5 得出 1， 然后 63 - cache[1] 得出 31, 31存入cacheManager[?][ 1 ]
#4 实际代码，利用此方法，程序运行时间缩短到原来1/3.
复制代码
1 int fillCacheManager(normalInt * index, Element (* dt)[ElementNumber], unsigned int (*cm)[cacheLine], unsigned int * table){
2 int element;
3 int cache[2] = {0 , 32};
4 int serial;
5
6 for( normalInt m=1; m<=index[0]; m++ ){
7 normalInt t = index[m];
8 cm[t][0] = 0;
9 cm[t][1] = 0;
10 for ( normalInt n=1; n<=dt[t][0]; n++ ){
11 element = dt[t][n];
12 serial = (element & 0x00000020) >>5;
13 element = element - cache[serial];
14 cm[t][serial] = cm[t][serial] + table[element] ;
15 }
16 }
17
18 return 0;
19 }
20
21
22 int quickTableReducton(normalInt * index, Element (* dt)[ElementNumber], unsigned int (*cm)[cacheLine]){
23 normalInt subset = index[0];
24 if (subset == 0) return -1;
25
26 for (normalInt m=1; m<subset; m++ ){
27 if (index[m] < 0) continue;
28
29 for(normalInt n=m+1; n<subset+1; n++){
30 if(index[n] < 0) continue;
31 if(n == m) continue;
32
33 normalInt src = index[m];
34 normalInt dst = index[n];
35 normalInt QQ = dst;
36 bool swaped = false;
37 if (dt[src][0] < dt[dst][0]){
38 swaped = true;
39 QQ = src;
40 }
41
42 if ( (cm[src][0] & cm[dst][0]) == cm[QQ][0] && (cm[src][1] & cm[dst][1]) == cm[QQ][1] ){
43 int t = m;
44 if (swaped) t = n;
45 index[t] = -2;
46 index[0] = index[0]-1;
47 if (swaped == false) break;
48 }
49 }
50 }
51
52 normalInt idx[indexCount];//indexOver
53 normalInt len=1;
54 for (normalInt m=1; index[m]!=indexOver; m++)//m<=index[0]
55 if (index[m] > -1){
56 idx[len] = index[m];
57 len++;
58 }
59
60 for (normalInt m=1; m<len; m++) index[m] = idx[m];
61 index[len] = indexOver;
62
63 return 0;
64 }
复制代码
#5 STL bitset : better choice?
分类: C/C++