假设我有一个 M 32 位整数的大数组，其中每个值的设置不超过 N 位。现在我想返回与查询 Target AND Value == Target 匹配的子集，即目标位出现在数组值中设置的值。
暴力破解很简单，只需迭代数组并提取其中 target&value == target 即可。如果 M 变得很大，这会变得太慢。有人知道如何将数组转换为更适合搜索的数据结构吗？
一种方法是存储每个位的数组或值（因此对于 32 位数组，您需要 32 个），然后仅搜索与目标值中的每个位匹配的值。除非 N 接近 32 或者目标设置接近 N 位，否则这会有一点帮助。由于我正在寻找的本质上是部分匹配，因此散列或排序似乎没有帮助。
精确正确的结果是必要条件。这必须在不访问并行硬件（例如 GPU 或使用 SIMD）的情况下工作。
我将使用 C++，但只要一些算法或想法的指针就可以了。最可能的情况是 M=100000 且 N=8 并且被频繁调用。
只是重申一下：我需要部分匹配（例如 item = 011000 匹配 target = 001000）而不是完全匹配。尽管M项是提前已知的，但目标的可能值可以是任何值。
我最终决定坚持使用蛮力。对于 80,000 件物品，不值得做任何其他事情。我想如果数据集的大小更像 800,000,000 它可能是值得的。
你可以建立一个按位特里树 http://en.wikipedia.org/wiki/Trie#Bitwise_tries.
遍历 trie 时，对于目标中的每个 0，您需要遍历两个分支。
Edit在测试了快速实现之后，我不会推荐这种方法。蛮力方法比这个方法快约 100 倍。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
