条目的种类繁多,具有以下类型:
typedef struct {
int value;
int mask;
int otherData;
} Entry;
我想尽可能快地根据提供的
int key;
在此数组中找到一个条目。该条目是确保(key & mask) == value
所必需的。这种阵列组织的最佳方法是什么,相应的算法将对其进行处理?
编辑:对阵列组织没有限制;它是静态的,可以在查找之前进行准备。
value
和mask
可以具有任意值。Edit2:
value
和mask
可以具有任意值,但是数组中的条目数约为10000。因此,可以预先计算某些“模式”。查找次数很多。
最佳答案
每个位都是独立的,因此在预处理阶段[*]中,您可以将每个条目分类32次(或int
很大)。每个分类存储2组:当key
为0时在该位匹配的那些和当key
为1时匹配的那些。
也就是说,如果该位的值== 1和mask == 0,则该分类根本不会存储该条目,因为它与key
的任何值都不匹配(实际上,无论您使用哪种方案,此类条目应在任何预处理阶段中删除,因此,即使只有一位,此类也不应存储任何分类。如果两者均为0,则存储到两组中。否则,存储到两组中的一组中。
然后,给定您的 key ,您想要找到32个集合的快速交集。
根据原始数组的大小,存储每个集合的最佳方法可能是巨型位数组,该数组指示数组中的每个条目是否在集合中。然后可以一次找到一个单词找到交集-&
总共32个单词,每个位数组一个。如果结果为0,请继续。如果结果非零,则说明您有一个匹配项,结果中设置的位会告诉您哪个条目是匹配项。当然,数组的大小仍然是线性的,实际上,您正在执行31 &
操作来检查32个条目是否匹配,这与对原始数组的简单线性搜索大致相同。但是比较和分支较少,并且正在查看的数据得到了更多压缩,因此您可能会获得更好的性能。
否则可能会有更好的方法进行相交。
如果倾向于重用键,则应将查找结果缓存在从键到条目的映射中。如果可能的键的数量相当少(也就是说,如果可能的输入少于2 ^ 32个键,并且/或者您有很多可用的内存),那么预处理阶段可能就是:
[*]无需任何预处理,显然您所能做的就是检查每个数组成员,直到找到匹配项,否则就检查了所有内容。
关于c++ - 戴着面具搜索,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/6583835/