集合关系运算符,集合关系的表示方法

  集合关系运算符,集合关系的表示方法

  包含关系的快速算法——模拟博客花园

  包含关系的快速算法

  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的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。

留言与评论(共有 条评论)
   
验证码: