我有一组小数字,需要不断搜索。
这个组是静态的,在一开始就已知。
通过观察,我知道大部分时间我要查找的数字不在这个组里。
我正在寻找的算法可以在一两步操作中实现:
- 从不说一个数字不在组内而实际上在
- 该算法大多数或全部时间都可以预测是否在组内
例如,如果数字是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)
但我不知道这如何帮助我确定元素是否在组内。
有什么想法吗?
谢谢,
Itay
更新
我发现使用类似于非常简单的布隆过滤器很有用:
我已经将x、y和z散列到一个位数组中(例如8位)。 然后,我将结果移动到正确的位:
uint8_t digest = (1 << (x % 8)) | (1 << (y % 8)) | (1 << (z % 8))
在搜索功能中,我使用了以下内容:
if ( (1 << (num % 8)) & digest )
我使用随机数进行了一些分析,发现使用8位时有大约30%的时间会给出错误的指示。使用16位则效果更好。