集合包含关系的快速算法simcity博客园

集合包含关系的快速算法 - 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++