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

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 处。

方法一:

在整个列表中进行线性搜索。这需要 O(N) 时间和 O(1) 空间。

方法二:

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

问题:

我怎样才能比 O(N) 更快地找到与掩码匹配的第一个元素，同时仍然使用合理的空间量？我有能力在预计算上花费多项式时间，因为会有很多查询。关键是k要小。在我的应用程序中，k <= 5 并且 N 以千为单位。 mask 有很多个 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

后缀树(按位)可以解决问题，叶节点具有原始优先级:

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 的平均 yield (13 倍加速)，可能比由于使用更复杂的操作而导致的效率差异更好(但不要指望它——位掩码很快)。如果您的列表中的位是非随机分布的，那么您几乎可以做得很好。