有效地找到与位掩码匹配的第一个元素

发布于 2025-01-04 17:09:49 字数 1385 浏览 1 评论 0原文

我有一个 N 64 位整数列表，其位代表小集合。每个整数最多有 k 位设置为 1。给定一个位掩码，我想找到列表中与掩码匹配的第一个元素，即 element &掩码==元素。

示例：

如果我的列表是：

index abcdef
  0   001100
  1   001010
  2   001000
  3   000100
  4   000010
  5   000001
  6   010000
  7   100000
  8   000000

并且我的掩码是111000，则与掩码匹配的第一个元素位于索引 2 处。

方法 1：

线性搜索浏览整个列表。这需要 O(N) 时间和 O(1) 空间。

方法 2：

预先计算所有可能掩码的树，并在每个节点保留该掩码的答案。这需要 O(1) 的查询时间，但占用 O(2^64) 的空间。

问题：

如何才能以比 O(N) 更快的速度找到与掩码匹配的第一个元素，同时仍使用合理的空间量？我可以在预计算上花费多项式时间，因为会有很多查询。关键是k很小。在我的应用程序中，k <= 5，N 为数千。 mask有很多1；您可以假设它是从 64 位整数空间中统一提取的。

更新：

以下是一个示例数据集和一个在 Linux 上运行的简单基准程序：http://up.thild.com/binmask.tar.gz。对于 large.in，N=3779 和 k=3。第一行是N，后面是代表元素的N无符号64位整数。使用 make 进行编译。使用 ./benchmark.e >large.out 运行以创建真实的输出，然后您可以对其进行比较。（掩码是随机生成的，但随机种子是固定的。）然后用您的实现替换 find_first() 函数。

简单的线性搜索比我预期的要快得多。这是因为k很小，因此对于随机掩码来说，平均很快就能找到匹配项。

原文

I have a list of N 64-bit integers whose bits represent small sets. Each integer has at most k bits set to 1. Given a bit mask, I would like to find the first element in the list that matches the mask, i.e. element & mask == element.

Example:

If my list is:

index abcdef
  0   001100
  1   001010
  2   001000
  3   000100
  4   000010
  5   000001
  6   010000
  7   100000
  8   000000

and my mask is 111000, the first element matching the mask is at index 2.

Method 1:

Linear search through the entire list. This takes O(N) time and O(1) space.

Method 2:

Precompute a tree of all possible masks, and at each node keep the answer for that mask. This takes O(1) time for the query, but takes O(2^64) space.

Question:

How can I find the first element matching the mask faster than O(N), while still using a reasonable amount of space? I can afford to spend polynomial time in precomputation, because there will be a lot of queries. The key is that k is small. In my application, k <= 5 and N is in the thousands. The mask has many 1s; you can assume that it is drawn uniformly from the space of 64-bit integers.

Update:

Here is an example data set and a simple benchmark program that runs on Linux: http://up.thirld.com/binmask.tar.gz. For large.in, N=3779 and k=3. The first line is N, followed by N unsigned 64-bit ints representing the elements. Compile with make. Run with ./benchmark.e >large.out to create the true output, which you can then diff against. (Masks are generated randomly, but the random seed is fixed.) Then replace the find_first() function with your implementation.

The simple linear search is much faster than I expected. This is because k is small, and so for a random mask, a match is found very quickly on average.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

听风念你 2025-01-11 17:09:49

后缀树（位）可以解决这个问题，原始优先级位于叶节点：

000000 -> 8
     1 -> 5
    10 -> 4
   100 -> 3
  1000 -> 2
    10 -> 1
   100 -> 0
 10000 -> 6
100000 -> 7

如果在掩码中设置了位，则搜索两个臂，如果没有，则仅搜索 0 个臂；你的答案是你在叶节点遇到的最小数字。

您可以通过不按顺序而是通过最大可辨别性遍历位来（稍微）改进这一点；在您的示例中，请注意 3 个元素设置了位 2，因此您将

2:0 0:0 1:0 3:0 4:0 5:0 -> 8
                    5:1 -> 5
                4:1 5:0 -> 4
            3:1 4:0 5:0 -> 3
        1:1 3:0 4:0 5:0 -> 6
    0:1 1:0 3:0 4:0 5:0 -> 7
2:1 0:0 1:0 3:0 4:0 5:0 -> 2
                4:1 5:0 -> 1
            3:1 4:0 5:0 -> 0

在示例掩码中创建这没有帮助（因为您必须遍历 bit2==0 和 bit2==1 两侧，因为您的掩码设置为位 2），但平均而言，它将改善结果（但以设置和更复杂的数据结构为代价）。如果某些位比其他位更有可能被设置，那么这可能是一个巨大的胜利。如果它们在元素列表中非常接近随机，那么这根本没有帮助。

如果您坚持使用基本上随机的位集，您应该从后缀树方法中获得平均 (1-5/64)^32 的好处（加速 13 倍），这可能< /em> 优于由于使用更复杂的操作而导致的效率差异（但不要指望它 - 位掩码很快）。如果列表中的位是非随机分布的，那么您几乎可以做得很好。

A suffix tree (on bits) will do the trick, with the original priority at the leaf nodes:

000000 -> 8
     1 -> 5
    10 -> 4
   100 -> 3
  1000 -> 2
    10 -> 1
   100 -> 0
 10000 -> 6
100000 -> 7

where if the bit is set in the mask, you search both arms, and if not, you search only the 0 arm; your answer is the minimum number you encounter at a leaf node.

You can improve this (marginally) by traversing the bits not in order but by maximum discriminability; in your example, note that 3 elements have bit 2 set, so you would create

2:0 0:0 1:0 3:0 4:0 5:0 -> 8
                    5:1 -> 5
                4:1 5:0 -> 4
            3:1 4:0 5:0 -> 3
        1:1 3:0 4:0 5:0 -> 6
    0:1 1:0 3:0 4:0 5:0 -> 7
2:1 0:0 1:0 3:0 4:0 5:0 -> 2
                4:1 5:0 -> 1
            3:1 4:0 5:0 -> 0

In your example mask this doesn't help (since you have to traverse both the bit2==0 and bit2==1 sides since your mask is set in bit 2), but on average it will improve the results (but at a cost of setup and more complex data structure). If some bits are much more likely to be set than others, this could be a huge win. If they're pretty close to random within the element list, then this doesn't help at all.

If you're stuck with essentially random bits set, you should get about (1-5/64)^32 benefit from the suffix tree approach on average (13x speedup), which might be better than the difference in efficiency due to using more complex operations (but don't count on it--bit masks are fast). If you have a nonrandom distribution of bits in your list, then you could do almost arbitrarily well.

回复收藏 0 原文

回忆凄美了谁 2025-01-11 17:09:49

这就是按位 Kd 树。每次查找操作通常需要少于 64 次访问。目前，旋转位（维度）的选择是随机的。

#include <limits.h>
#include <time.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

typedef unsigned long long Thing;
typedef unsigned long Number;

unsigned thing_ffs(Thing mask);
Thing rand_mask(unsigned bitcnt);

#define WANT_RANDOM 31
#define WANT_BITS 3

#define BITSPERTHING (CHAR_BIT*sizeof(Thing))
#define NONUMBER ((Number)-1)

struct node {
        Thing value;
        Number num;
        Number nul;
        Number one;
        char pivot;
        } *nodes = NULL;
unsigned nodecount=0;
unsigned itercount=0;

struct node * nodes_read( unsigned *sizp, char *filename);
Number *find_ptr_to_insert(Number *ptr, Thing value, Thing mask);

unsigned grab_matches(Number *result, Number num, Thing mask);
void initialise_stuff(void);

int main (int argc, char **argv)
{
Thing mask;
Number num;
unsigned idx;

srand (time(NULL));
nodes = nodes_read( &nodecount, argv[1]);
fprintf( stdout, "Nodecount=%u\n", nodecount );
initialise_stuff();

#if WANT_RANDOM
mask = nodes[nodecount/2].value | nodes[nodecount/3].value ;
#else
mask = 0x38;
#endif

fprintf( stdout, "\n#### Search mask=%llx\n", (unsigned long long) mask );

itercount = 0;
num = NONUMBER;
idx = grab_matches(&num,0, mask);
fprintf( stdout, "Itercount=%u\n", itercount );

fprintf(stdout, "KdTree search  %16llx\n", (unsigned long long) mask );
fprintf(stdout, "Count=%u Result:\n", idx);
idx = num;
if (idx >= nodecount) idx = nodecount-1;
fprintf( stdout, "num=%4u Value=%16llx\n"
        ,(unsigned) nodes[idx].num
        ,(unsigned long long) nodes[idx].value
        );

fprintf( stdout, "\nLinear search  %16llx\n", (unsigned long long) mask );
for (idx = 0; idx < nodecount; idx++) {
        if ((nodes[idx].value & mask) == nodes[idx].value) break;
        }
fprintf(stdout, "Cnt=%u\n", idx);
if (idx >= nodecount) idx = nodecount-1;
fprintf(stdout, "Num=%4u Value=%16llx\n"
        , (unsigned) nodes[idx].num
        , (unsigned long long) nodes[idx].value );

return 0;
}

void initialise_stuff(void)
{
unsigned num;
Number root, *ptr;
root = 0;

for (num=0; num < nodecount; num++) {
        nodes[num].num = num;
        nodes[num].one = NONUMBER;
        nodes[num].nul = NONUMBER;
        nodes[num].pivot = -1;
        }
nodes[num-1].value = 0; /* last node is guaranteed to match anything */

root = 0;
for (num=1; num < nodecount; num++) {
        ptr = find_ptr_to_insert (&root, nodes[num].value, 0ull );
        if (*ptr == NONUMBER) *ptr = num;
        else fprintf(stderr, "Found %u for %u\n"
                , (unsigned)*ptr, (unsigned) num );
        }
}

Thing rand_mask(unsigned bitcnt)
{struct node * nodes_read( unsigned *sizp, char *filename)
{
struct node *ptr;
unsigned size,used;
FILE *fp;

if (!filename) {
        size = (WANT_RANDOM+0) ? WANT_RANDOM : 9;
        ptr = malloc (size * sizeof *ptr);
#if (!WANT_RANDOM)
        ptr[0].value = 0x0c;
        ptr[1].value = 0x0a;
        ptr[2].value = 0x08;
        ptr[3].value = 0x04;
        ptr[4].value = 0x02;
        ptr[5].value = 0x01;
        ptr[6].value = 0x10;
        ptr[7].value = 0x20;
        ptr[8].value = 0x00;
#else
        for (used=0; used < size; used++) {
                ptr[used].value = rand_mask(WANT_BITS);
                }
#endif /* WANT_RANDOM */
        *sizp = size;
        return ptr;
        }

fp = fopen( filename, "r" );
if (!fp) return NULL;
fscanf(fp,"%u\n",  &size );
fprintf(stderr, "Size=%u\n", size);
ptr = malloc (size * sizeof *ptr);
for (used = 0; used < size; used++) {
        fscanf(fp,"%llu\n",  &ptr[used].value );
        }

fclose( fp );
*sizp = used;
return ptr;
}

Thing value = 0;
unsigned bit, cnt;

for (cnt=0; cnt < bitcnt; cnt++) {
        bit = 54321*rand();
        bit %= BITSPERTHING;
        value |= 1ull << bit;
        }
return value;
}

Number *find_ptr_to_insert(Number *ptr, Thing value, Thing done)
{
Number num=NONUMBER;

while ( *ptr != NONUMBER) {
        Thing wrong;

        num = *ptr;
        wrong = (nodes[num].value ^ value) & ~done;
        if (nodes[num].pivot < 0) { /* This node is terminal */
                /* choose one of the wrong bits for a pivot .
                ** For this bit (nodevalue==1 && searchmask==0 )
                */
                if (!wrong) wrong = ~done ;
                nodes[num].pivot  = thing_ffs( wrong );
                }
        ptr = (wrong & 1ull << nodes[num].pivot) ? &nodes[num].nul : &nodes[num].one;
        /* Once this bit has been tested, it can be masked off. */
        done |= 1ull << nodes[num].pivot ;
        }
return ptr;
}

unsigned grab_matches(Number *result, Number num, Thing mask)
{
Thing wrong;
unsigned count;

for (count=0; num < *result; ) {
        itercount++;
        wrong = nodes[num].value & ~mask;
        if (!wrong) { /* we have a match */
                if (num < *result) { *result = num; count++; }
                /* This is cheap pruning: the break will omit both subtrees from the results.
                ** But because we already have a result, and the subtrees have higher numbers
                ** than our current num, we can ignore them. */
                break;
                }
        if (nodes[num].pivot < 0) { /* This node is terminal */
                break;
                }
        if (mask & 1ull << nodes[num].pivot) {
                /* avoid recursion if there is only one non-empty subtree */
                if (nodes[num].nul >= *result) { num = nodes[num].one; continue; }
                if (nodes[num].one >= *result) { num = nodes[num].nul; continue; }
                count += grab_matches(result, nodes[num].nul, mask);
                count += grab_matches(result, nodes[num].one, mask);
                break;
                }
        mask |= 1ull << nodes[num].pivot;
        num = (wrong & 1ull << nodes[num].pivot) ? nodes[num].nul : nodes[num].one;
        }
return count;
}

unsigned thing_ffs(Thing mask)
{
unsigned bit;

#if 1
if (!mask) return (unsigned)-1;
for ( bit=random() % BITSPERTHING; 1 ; bit += 5, bit %= BITSPERTHING) {
        if (mask & 1ull << bit ) return bit;
        }
#elif 0
for (bit =0; bit < BITSPERTHING; bit++ ) {
        if (mask & 1ull <<bit) return bit;
        }
#else
mask &= (mask-1); // Kernighan-trick
for (bit =0; bit < BITSPERTHING; bit++ ) {
        mask >>=1;
        if (!mask) return bit;
        }
#endif

return 0xffffffff;
}

struct node * nodes_read( unsigned *sizp, char *filename)
{
struct node *ptr;
unsigned size,used;
FILE *fp;

if (!filename) {
        size = (WANT_RANDOM+0) ? WANT_RANDOM : 9;
        ptr = malloc (size * sizeof *ptr);
#if (!WANT_RANDOM)
        ptr[0].value = 0x0c;
        ptr[1].value = 0x0a;
        ptr[2].value = 0x08;
        ptr[3].value = 0x04;
        ptr[4].value = 0x02;
        ptr[5].value = 0x01;
        ptr[6].value = 0x10;
        ptr[7].value = 0x20;
        ptr[8].value = 0x00;
#else
        for (used=0; used < size; used++) {
                ptr[used].value = rand_mask(WANT_BITS);
                }
#endif /* WANT_RANDOM */
        *sizp = size;
        return ptr;
        }

fp = fopen( filename, "r" );
if (!fp) return NULL;
fscanf(fp,"%u\n",  &size );
fprintf(stderr, "Size=%u\n", size);
ptr = malloc (size * sizeof *ptr);
for (used = 0; used < size; used++) {
        fscanf(fp,"%llu\n",  &ptr[used].value );
        }

fclose( fp );
*sizp = used;
return ptr;
}

更新：

我对枢轴选择进行了一些实验，倾向于具有最高辨别值（“信息内容”）的位。这涉及到：

在构建树时制作位使用情况的直方图（可以在初始化时完成）
：在剩余子树中选择频率最接近 1/2 的一个。

结果：随机主元选择表现更好。

This is the bitwise Kd-tree. It typically needs less than 64 visits per lookup operation. Currently, the selection of the bit (dimension) to pivot on is random.

#include <limits.h>
#include <time.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

typedef unsigned long long Thing;
typedef unsigned long Number;

unsigned thing_ffs(Thing mask);
Thing rand_mask(unsigned bitcnt);

#define WANT_RANDOM 31
#define WANT_BITS 3

#define BITSPERTHING (CHAR_BIT*sizeof(Thing))
#define NONUMBER ((Number)-1)

struct node {
        Thing value;
        Number num;
        Number nul;
        Number one;
        char pivot;
        } *nodes = NULL;
unsigned nodecount=0;
unsigned itercount=0;

struct node * nodes_read( unsigned *sizp, char *filename);
Number *find_ptr_to_insert(Number *ptr, Thing value, Thing mask);

unsigned grab_matches(Number *result, Number num, Thing mask);
void initialise_stuff(void);

int main (int argc, char **argv)
{
Thing mask;
Number num;
unsigned idx;

srand (time(NULL));
nodes = nodes_read( &nodecount, argv[1]);
fprintf( stdout, "Nodecount=%u\n", nodecount );
initialise_stuff();

#if WANT_RANDOM
mask = nodes[nodecount/2].value | nodes[nodecount/3].value ;
#else
mask = 0x38;
#endif

fprintf( stdout, "\n#### Search mask=%llx\n", (unsigned long long) mask );

itercount = 0;
num = NONUMBER;
idx = grab_matches(&num,0, mask);
fprintf( stdout, "Itercount=%u\n", itercount );

fprintf(stdout, "KdTree search  %16llx\n", (unsigned long long) mask );
fprintf(stdout, "Count=%u Result:\n", idx);
idx = num;
if (idx >= nodecount) idx = nodecount-1;
fprintf( stdout, "num=%4u Value=%16llx\n"
        ,(unsigned) nodes[idx].num
        ,(unsigned long long) nodes[idx].value
        );

fprintf( stdout, "\nLinear search  %16llx\n", (unsigned long long) mask );
for (idx = 0; idx < nodecount; idx++) {
        if ((nodes[idx].value & mask) == nodes[idx].value) break;
        }
fprintf(stdout, "Cnt=%u\n", idx);
if (idx >= nodecount) idx = nodecount-1;
fprintf(stdout, "Num=%4u Value=%16llx\n"
        , (unsigned) nodes[idx].num
        , (unsigned long long) nodes[idx].value );

return 0;
}

void initialise_stuff(void)
{
unsigned num;
Number root, *ptr;
root = 0;

for (num=0; num < nodecount; num++) {
        nodes[num].num = num;
        nodes[num].one = NONUMBER;
        nodes[num].nul = NONUMBER;
        nodes[num].pivot = -1;
        }
nodes[num-1].value = 0; /* last node is guaranteed to match anything */

root = 0;
for (num=1; num < nodecount; num++) {
        ptr = find_ptr_to_insert (&root, nodes[num].value, 0ull );
        if (*ptr == NONUMBER) *ptr = num;
        else fprintf(stderr, "Found %u for %u\n"
                , (unsigned)*ptr, (unsigned) num );
        }
}

Thing rand_mask(unsigned bitcnt)
{struct node * nodes_read( unsigned *sizp, char *filename)
{
struct node *ptr;
unsigned size,used;
FILE *fp;

if (!filename) {
        size = (WANT_RANDOM+0) ? WANT_RANDOM : 9;
        ptr = malloc (size * sizeof *ptr);
#if (!WANT_RANDOM)
        ptr[0].value = 0x0c;
        ptr[1].value = 0x0a;
        ptr[2].value = 0x08;
        ptr[3].value = 0x04;
        ptr[4].value = 0x02;
        ptr[5].value = 0x01;
        ptr[6].value = 0x10;
        ptr[7].value = 0x20;
        ptr[8].value = 0x00;
#else
        for (used=0; used < size; used++) {
                ptr[used].value = rand_mask(WANT_BITS);
                }
#endif /* WANT_RANDOM */
        *sizp = size;
        return ptr;
        }

fp = fopen( filename, "r" );
if (!fp) return NULL;
fscanf(fp,"%u\n",  &size );
fprintf(stderr, "Size=%u\n", size);
ptr = malloc (size * sizeof *ptr);
for (used = 0; used < size; used++) {
        fscanf(fp,"%llu\n",  &ptr[used].value );
        }

fclose( fp );
*sizp = used;
return ptr;
}

Thing value = 0;
unsigned bit, cnt;

for (cnt=0; cnt < bitcnt; cnt++) {
        bit = 54321*rand();
        bit %= BITSPERTHING;
        value |= 1ull << bit;
        }
return value;
}

Number *find_ptr_to_insert(Number *ptr, Thing value, Thing done)
{
Number num=NONUMBER;

while ( *ptr != NONUMBER) {
        Thing wrong;

        num = *ptr;
        wrong = (nodes[num].value ^ value) & ~done;
        if (nodes[num].pivot < 0) { /* This node is terminal */
                /* choose one of the wrong bits for a pivot .
                ** For this bit (nodevalue==1 && searchmask==0 )
                */
                if (!wrong) wrong = ~done ;
                nodes[num].pivot  = thing_ffs( wrong );
                }
        ptr = (wrong & 1ull << nodes[num].pivot) ? &nodes[num].nul : &nodes[num].one;
        /* Once this bit has been tested, it can be masked off. */
        done |= 1ull << nodes[num].pivot ;
        }
return ptr;
}

unsigned grab_matches(Number *result, Number num, Thing mask)
{
Thing wrong;
unsigned count;

for (count=0; num < *result; ) {
        itercount++;
        wrong = nodes[num].value & ~mask;
        if (!wrong) { /* we have a match */
                if (num < *result) { *result = num; count++; }
                /* This is cheap pruning: the break will omit both subtrees from the results.
                ** But because we already have a result, and the subtrees have higher numbers
                ** than our current num, we can ignore them. */
                break;
                }
        if (nodes[num].pivot < 0) { /* This node is terminal */
                break;
                }
        if (mask & 1ull << nodes[num].pivot) {
                /* avoid recursion if there is only one non-empty subtree */
                if (nodes[num].nul >= *result) { num = nodes[num].one; continue; }
                if (nodes[num].one >= *result) { num = nodes[num].nul; continue; }
                count += grab_matches(result, nodes[num].nul, mask);
                count += grab_matches(result, nodes[num].one, mask);
                break;
                }
        mask |= 1ull << nodes[num].pivot;
        num = (wrong & 1ull << nodes[num].pivot) ? nodes[num].nul : nodes[num].one;
        }
return count;
}

unsigned thing_ffs(Thing mask)
{
unsigned bit;

#if 1
if (!mask) return (unsigned)-1;
for ( bit=random() % BITSPERTHING; 1 ; bit += 5, bit %= BITSPERTHING) {
        if (mask & 1ull << bit ) return bit;
        }
#elif 0
for (bit =0; bit < BITSPERTHING; bit++ ) {
        if (mask & 1ull <<bit) return bit;
        }
#else
mask &= (mask-1); // Kernighan-trick
for (bit =0; bit < BITSPERTHING; bit++ ) {
        mask >>=1;
        if (!mask) return bit;
        }
#endif

return 0xffffffff;
}

struct node * nodes_read( unsigned *sizp, char *filename)
{
struct node *ptr;
unsigned size,used;
FILE *fp;

if (!filename) {
        size = (WANT_RANDOM+0) ? WANT_RANDOM : 9;
        ptr = malloc (size * sizeof *ptr);
#if (!WANT_RANDOM)
        ptr[0].value = 0x0c;
        ptr[1].value = 0x0a;
        ptr[2].value = 0x08;
        ptr[3].value = 0x04;
        ptr[4].value = 0x02;
        ptr[5].value = 0x01;
        ptr[6].value = 0x10;
        ptr[7].value = 0x20;
        ptr[8].value = 0x00;
#else
        for (used=0; used < size; used++) {
                ptr[used].value = rand_mask(WANT_BITS);
                }
#endif /* WANT_RANDOM */
        *sizp = size;
        return ptr;
        }

fp = fopen( filename, "r" );
if (!fp) return NULL;
fscanf(fp,"%u\n",  &size );
fprintf(stderr, "Size=%u\n", size);
ptr = malloc (size * sizeof *ptr);
for (used = 0; used < size; used++) {
        fscanf(fp,"%llu\n",  &ptr[used].value );
        }

fclose( fp );
*sizp = used;
return ptr;
}

UPDATE:

I experimented a bit with the pivot-selection, favouring bits with the highest discriminatory value ("information content"). This involves:

making a histogram of the usage of bits (can be done while initialising)
while building the tree: choosing the one with frequency closest to 1/2 in the remaining subtrees.

The result: the random pivot selection performed better.

回复收藏 0 原文

时光沙漏 2025-01-11 17:09:49

构造一棵二叉树如下：

每一层对应一个位
对应的位向右，否则向左

这样就将每个数字插入到数据库中。

现在，进行搜索：如果掩码中的相应位为 1，则遍历两个子节点。如果为0，则只遍历左节点。本质上继续遍历树，直到到达叶节点（顺便说一句，0 是每个掩码的命中！）。

该树的空间要求为 O(N)。

例如 1 (001)、2(010) 和 5 (101) 的树

         root
        /    \
       0      1
      / \     |
     0   1    0
     |   |    |
     1   0    1
    (1) (2)  (5)

Construct a a binary tree as follows:

Every level corresponds to a bit
It corresponding bit is on go right, otherwise left

This way insert every number in the database.

Now, for searching: if the corresponding bit in the mask is 1, traverse both children. If it is 0, traverse only the left node. Essentially keep traversing the tree until you hit the leaf node (BTW, 0 is a hit for every mask!).

This tree will have O(N) space requirements.

Eg of tree for 1 (001), 2(010) and 5 (101)

         root
        /    \
       0      1
      / \     |
     0   1    0
     |   |    |
     1   0    1
    (1) (2)  (5)

回复收藏 0 原文

燕归巢 2025-01-11 17:09:49

使用预先计算的位掩码。形式上仍然是 O(N)，因为与掩码操作是 O(N)。最后一遍也是 O(N)，因为它需要找到最低的位集，但这也可以加快。

#include <limits.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

  /* For demonstration purposes.
  ** In reality, this should be an unsigned long long */
typedef unsigned char Thing;

#define BITSPERTHING (CHAR_BIT*sizeof (Thing))
#define COUNTOF(a) (sizeof a / sizeof a[0])

Thing data[] =
/****** index abcdef */
{ 0x0c /* 0   001100 */
, 0x0a /* 1   001010 */
, 0x08 /* 2   001000 */
, 0x04 /* 3   000100 */
, 0x02 /* 4   000010 */
, 0x01 /* 5   000001 */
, 0x10 /* 6   010000 */
, 0x20 /* 7   100000 */
, 0x00 /* 8   000000 */
};

        /* Note: this is for demonstration purposes.
        ** Normally, one should choose a machine wide unsigned int
        ** for bitmask arrays.
        */
struct bitmap {
        char data[ 1+COUNTOF (data)/ CHAR_BIT ];
        } nulmaps [ BITSPERTHING ];

#define BITSET(a,i) (a)[(i) / CHAR_BIT ] |= (1u <<  ((i)%CHAR_BIT) )
#define BITTEST(a,i) ((a)[(i) / CHAR_BIT ] & (1u <<  ((i)%CHAR_BIT) ))

void init_tabs(void);
void map_empty(struct bitmap *dst);
void map_full(struct bitmap *dst);
void map_and2(struct bitmap *dst, struct bitmap *src);

int main (void)
{
Thing mask;
struct bitmap result;
unsigned ibit;

mask = 0x38;
init_tabs();
map_full(&result);

for (ibit = 0; ibit < BITSPERTHING; ibit++) {
        /* bit in mask is 1, so bit at this position is in fact a don't care */
        if (mask & (1u <<ibit))  continue;
        /* bit in mask is 0, so we can only select items with a 0 at this bitpos */
        map_and2(&result, &nulmaps[ibit] );
        }

        /* This is not the fastest way to find the lowest 1 bit */
for (ibit = 0; ibit < COUNTOF (data); ibit++) {
        if (!BITTEST(result.data, ibit) ) continue;
        fprintf(stdout, " %u", ibit);
        }
fprintf( stdout, "\n" );
return 0;
}

void init_tabs(void)
{
unsigned ibit, ithing;

        /* 1 bits in data that dont overlap with 1 bits in the searchmask are showstoppers.
        ** So, for each bitpos, we precompute a bitmask of all *entrynumbers* from data[], that contain 0 in bitpos.
        */
memset(nulmaps, 0 , sizeof nulmaps);
for (ithing=0; ithing < COUNTOF(data); ithing++) {
        for (ibit=0; ibit < BITSPERTHING; ibit++) {
                if ( data[ithing] & (1u << ibit) ) continue;
                BITSET(nulmaps[ibit].data, ithing);
                }
        }
}

        /* Logical And of two bitmask arrays; simular to dst &= src */
void map_and2(struct bitmap *dst, struct bitmap *src)
{
unsigned idx;
for (idx = 0; idx < COUNTOF(dst->data); idx++) {
        dst->data[idx] &= src->data[idx] ;
        }
}

void map_empty(struct bitmap *dst)
{
memset(dst->data, 0 , sizeof dst->data);
}

void map_full(struct bitmap *dst)
{
unsigned idx;
        /* NOTE this loop sets too many bits to the left of COUNTOF(data) */
for (idx = 0; idx < COUNTOF(dst->data); idx++) {
        dst->data[idx] = ~0;
        }
}

With precomputed bitmasks. Formally is is still O(N), since the and-mask operations are O(N). The final pass is also O(N), because it needs to find the lowest bit set, but that could be sped up, too.

#include <limits.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

  /* For demonstration purposes.
  ** In reality, this should be an unsigned long long */
typedef unsigned char Thing;

#define BITSPERTHING (CHAR_BIT*sizeof (Thing))
#define COUNTOF(a) (sizeof a / sizeof a[0])

Thing data[] =
/****** index abcdef */
{ 0x0c /* 0   001100 */
, 0x0a /* 1   001010 */
, 0x08 /* 2   001000 */
, 0x04 /* 3   000100 */
, 0x02 /* 4   000010 */
, 0x01 /* 5   000001 */
, 0x10 /* 6   010000 */
, 0x20 /* 7   100000 */
, 0x00 /* 8   000000 */
};

        /* Note: this is for demonstration purposes.
        ** Normally, one should choose a machine wide unsigned int
        ** for bitmask arrays.
        */
struct bitmap {
        char data[ 1+COUNTOF (data)/ CHAR_BIT ];
        } nulmaps [ BITSPERTHING ];

#define BITSET(a,i) (a)[(i) / CHAR_BIT ] |= (1u <<  ((i)%CHAR_BIT) )
#define BITTEST(a,i) ((a)[(i) / CHAR_BIT ] & (1u <<  ((i)%CHAR_BIT) ))

void init_tabs(void);
void map_empty(struct bitmap *dst);
void map_full(struct bitmap *dst);
void map_and2(struct bitmap *dst, struct bitmap *src);

int main (void)
{
Thing mask;
struct bitmap result;
unsigned ibit;

mask = 0x38;
init_tabs();
map_full(&result);

for (ibit = 0; ibit < BITSPERTHING; ibit++) {
        /* bit in mask is 1, so bit at this position is in fact a don't care */
        if (mask & (1u <<ibit))  continue;
        /* bit in mask is 0, so we can only select items with a 0 at this bitpos */
        map_and2(&result, &nulmaps[ibit] );
        }

        /* This is not the fastest way to find the lowest 1 bit */
for (ibit = 0; ibit < COUNTOF (data); ibit++) {
        if (!BITTEST(result.data, ibit) ) continue;
        fprintf(stdout, " %u", ibit);
        }
fprintf( stdout, "\n" );
return 0;
}

void init_tabs(void)
{
unsigned ibit, ithing;

        /* 1 bits in data that dont overlap with 1 bits in the searchmask are showstoppers.
        ** So, for each bitpos, we precompute a bitmask of all *entrynumbers* from data[], that contain 0 in bitpos.
        */
memset(nulmaps, 0 , sizeof nulmaps);
for (ithing=0; ithing < COUNTOF(data); ithing++) {
        for (ibit=0; ibit < BITSPERTHING; ibit++) {
                if ( data[ithing] & (1u << ibit) ) continue;
                BITSET(nulmaps[ibit].data, ithing);
                }
        }
}

        /* Logical And of two bitmask arrays; simular to dst &= src */
void map_and2(struct bitmap *dst, struct bitmap *src)
{
unsigned idx;
for (idx = 0; idx < COUNTOF(dst->data); idx++) {
        dst->data[idx] &= src->data[idx] ;
        }
}

void map_empty(struct bitmap *dst)
{
memset(dst->data, 0 , sizeof dst->data);
}

void map_full(struct bitmap *dst)
{
unsigned idx;
        /* NOTE this loop sets too many bits to the left of COUNTOF(data) */
for (idx = 0; idx < COUNTOF(dst->data); idx++) {
        dst->data[idx] = ~0;
        }
}

回复收藏 0 原文

~没有更多了~