我有一小组数字,我经常需要搜索它们。
群体是静态的并且在时间开始时已知。
我从观察中知道,大多数时候我要搜索的号码不在该组中。
我正在寻找的是一种算法,在一条或两条指令中将:
- 永远不要说一个号码不在组中,而它在组中
- 算法大部分时间或所有时间都预测它是否是
例如,
如果数字是 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 位使它变得更好。
最佳答案
只有七个数字,你应该在你的集合中进行暴力搜索;它会比任何其他方法都快。如果您的值是 16 位或更少,您可以在单个 SIMD 相等性测试中完成;如果它们是 32 位,则可以分两次完成。
关于c++ - 快速排除成员是否在集合中,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22303057/