Ita*_*rom 3 c c++ algorithm performance
我有一小组数字,我经常需要搜索.
这个群体是静止的,并且在开始时就已知道了.
我从观察中得知,我搜索的数字大部分时间都不属于小组.
我正在寻找的是一个算法,在一两条指令中:
例如,
如果数字是x,y,zi可以执行以下操作:
保存:
tmp = (x | y | z)
当我搜索一个我可以做的数字时:
if ((num & tmp) == (num))
do the real search
如果数字是x,y或z,则保证在执行AND时返回num.如果不是我可能会搜索什么 - 但那基本上没问题.
这个测试的主要问题是,即使num不在组中,组i中超过5个数字的大部分时间也会变为TRUE.
我在考虑使用XOR魔法:
tmp = (x ^ y ^ z)
当搜索时做类似的事情:
(num ^ tmp)
但我不明白这是如何帮助我确定元素是否在组中.
有任何想法吗 ？
谢谢,
伊泰
UPDATE
我发现有用的是使用像一个非常简单的布隆过滤器:
我将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位,你可以用两个.