c++ - 快速排除成员是否在集合中

Question

我有一小组数字，我经常需要搜索它们。

群体是静态的并且在时间开始时已知。

我从观察中知道，大多数时候我要搜索的号码不在该组中。

我正在寻找的是一种算法，在一条或两条指令中将:

1. 永远不要说一个号码不在组中，而它在组中
2. 算法大部分时间或所有时间都预测它是否是

例如，

如果数字是 x,y,z 我可以执行以下操作:

保存:

tmp = (x | y | z)

当我搜索一个号码时，我可以这样做:

if ((num & tmp) == (num))
    do the real search

如果数字是 x、y 或 z，则保证在对其执行 AND 时返回 num。如果不是，我可能什么都不搜索 - 但基本上没问题。

此测试的主要问题是，大多数情况下，组中超过 5 个数字时，即使 num 不在组中，我也会得到 TRUE。

我在考虑使用 XOR 魔法:

tmp = (x ^ y ^ z)

并且在搜索时做类似的事情:

(num ^ tmp)

但我看不出这如何帮助我确定元素是否在组中。

有什么想法吗？

谢谢，

义泰

更新

我发现有用的是使用类似非常简单的布隆过滤器的东西:

我已将 x、y 和 z 散列为位数组(例如 8 位)。然后，我将结果转移到正确的位:

uint8_t digest = (1 << (x % 8)) | (1 << (y % 8)) | (1 << (z % 8))

关于我使用的搜索功能:

if ( (1 << (num % 8)) & digest )

我使用随机数进行了一些分析，结果发现使用 8 位随机数在大约 30% 的时间内给出了错误指示。使用 16 位使它变得更好。

Answer 1

只有七个数字，你应该在你的集合中进行暴力搜索；它会比任何其他方法都快。如果您的值是 16 位或更少，您可以在单个 SIMD 相等性测试中完成；如果它们是 32 位，则可以分两次完成。