集合关系运算符,集合关系的表示方法
包含关系的快速算法——模拟博客花园
包含关系的快速算法
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
