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

Question

我有一个N 64位整数列表,其位代表小集.每个整数最多有k位设置为1.给定位掩码,我想找到列表中与掩码匹配的第一个元素,即element & mask == 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为数千.面具有很多1; 你可以假设它是从64位整数的空间中均匀绘制的.

更新:

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

简单的线性搜索比我预期的要快得多.这是因为k很小,因此对于随机掩码,平均发现匹配非常快.

Answer 1

构造一棵二叉树如下：

1. 每个级别对应一个位
2. 其对应位为向右走，否则向左

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

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

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

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

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