集合关系运算符,集合关系的表示方法
包含关系的快速算法——模拟博客花园
包含关系的快速算法
2012-10-05 22:18 by simcity,751阅读,0评论,收藏,编辑
#1每行数据代表一个集合。怎样才能判断集合的包含关系?-收集的数据仅在有限的范围内。
0 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23a-24元素
1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24b-24元素
最容易想到的就是蛮力操作。在计算之前,你也应该知道谁的元素多吧?还好,我耍了一招。在读取数据时,我已经将数组元素的个数存储到了数组的第0个元素中。
对于a中的每个元素x为1
2如果(!setContain(b,x))
3返回假;
四
5返回true
#2数据在31以内,所以考虑用无符号数编码数组。
比如1 2 3 4用0x 000000000000000000000000000000111编码,即1用第一位,2用第二位,依此类推。
但是数据中有0,可以这么说,0用第一位,1用第二位,依此类推.
1 2 3 4最终形式是0x 00000000000000000000000000000000000000000001110
所以判断起来就容易多了,就
复制代码
1无符号src //表示更多元素数组的编码。
2 unsigned dst //表示较少元素的数组的编码。
3如果(src dst==dst)
4返回true
五
6返回假;
复制代码
但是等一下,如何将1 2 3 4这样的元素存储到src这样的变量中呢?
于是,手工加工的桌子出现了。
复制代码
1无符号整数表[32]={
20x00000001、0x00000002、0x00000004、0x00000008、
30x00000010、0x00000020、0x00000040、0x00000080、
40x00000100、0x00000200、0x00000400、0x00000800、
50x00001000、0x00002000、0x00004000、0x00008000、
60x00010000、0x00020000、0x00040000、0x00080000、
70x00100000、0x00200000、0x00400000、0x00800000、
80x01000000、0x02000000、0x04000000、0x08000000、
90x10000000、0x20000000、0x40000000、0x80000000
10 };
复制代码
您只需要对每个阵列扫描一次就可以实现目标。
1 src=0;
2
对于a中的每个元素x为3
4 src=src表[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
按照下图来考虑。
复制代码
数字位
0 1。。
31 32
32 - 0 1。。
63 - 31 32
复制代码
重建数组
1 int cache={0,32 };
2未签名的int cache manager[2][2];
3 //二维数组用来维护两个数组的代码,每行编码一个数组。
方法如下,分别以16和63为例。
操作(160x00000020) 5产生0,然后16-cache[0]产生16,存储在cacheManager[?][ 0 ]
操作(630x00000020) 5产生1,然后63-cache[1]产生31,存储在cacheManager[?][ 1 ]
#4实际代码,使用这种方法,程序的运行时间缩短到原来的1/3。
复制代码
1 int fillCacheManager(normalInt * index,Element (* dt)[ElementNumber],unsigned int (*cm)[cacheLine],unsigned int * table){
2 int元素;
3 int cache[2]={0,32 };
4 int串行;
五
6 for(归一化m=1;m=索引[0];m ){
7归一化t=指数[m];
8cm[t][0]=0;
9cm[t][1]=0;
10 for(归一化n=1;n=dt[t][0];n ){
11元素=dt[t][n];
12 serial=(element0x 00000020)5;
13 element=element-cache[serial];
14 cm[t][serial]=cm[t][serial]表[元素];
15 }
16 }
17
18返回0;
19 }
20
21
22 int quicktablereduction(normalInt * index,Element (* dt)[ElementNumber],unsigned int (*cm)[cacheLine]){
23正规子集=索引[0];
24 if (subset==0)返回-1;
25
26 for(归一化m=1;m子集;m ){
27 if (index[m] 0)继续;
28
29 for(规格化n=m ^ 1;n子集1;n ){
30 if(index[n] 0)继续;
31如果(n==m)继续;
32
33归一化src=指数[m];
34 normal int 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如果(交换)t=n;
45 index[t]=-2;
46索引[0]=索引[0]-1;
47 if(swapped==false)break;
48 }
49 }
50 }
51
52 normal int idx[索引计数];//索引结束
53归一化len=1;
54为(归一化m=1;索引[m]!=indexOverm)//m=索引[0]
55如果(索引[m] -1){
56 idx[len]=index[m];
57 len
58 }
59
60为(归一化m=1;m m)index[m]=idx[m];
61 index[len]=indexOver;
62
63返回0;
64 }
复制代码
#5 STL位集:更好的选择?
分类:C/C
郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。