条目的种类繁多,具有以下类型:

typedef struct {
    int value;
    int mask;
    int otherData;
} Entry;

我想尽可能快地根据提供的int key;在此数组中找到一个条目。该条目是确保(key & mask) == value所必需的。

这种阵列组织的最佳方法是什么,相应的算法将对其进行处理?

编辑:对阵列组织没有限制;它是静态的,可以在查找之前进行准备。 valuemask可以具有任意值。

Edit2:valuemask可以具有任意值,但是数组中的条目数约为10000。因此,可以预先计算某些“模式”。

查找次数很多。

最佳答案

每个位都是独立的,因此在预处理阶段[*]中,您可以将每个条目分类32次(或int很大)。每个分类存储2组:当key为0时在该位匹配的那些和当key为1时匹配的那些。

也就是说,如果该位的值== 1和mask == 0,则该分类根本不会存储该条目,因为它与key的任何值都不匹配(实际上,无论您使用哪种方案,此类条目应在任何预处理阶段中删除,因此,即使只有一位,此类也不应存储任何分类。如果两者均为0,则存储到两组中。否则,存储到两组中的一组中。

然后,给定您的 key ,您想要找到32个集合的快速交集。

根据原始数组的大小,存储每个集合的最佳方法可能是巨型位数组,该数组指示数组中的每个条目是否在集合中。然后可以一次找到一个单词找到交集-&总共32个单词,每个位数组一个。如果结果为0,请继续。如果结果非零,则说明您有一个匹配项,结果中设置的位会告诉您哪个条目是匹配项。当然,数组的大小仍然是线性的,实际上,您正在执行31 &操作来检查32个条目是否匹配,这与对原始数组的简单线性搜索大致相同。但是比较和分支较少,并且正在查看的数据得到了更多压缩,因此您可能会获得更好的性能。

否则可能会有更好的方法进行相交。

如果倾向于重用键,则应将查找结果缓存在从键到条目的映射中。如果可能的键的数量相当少(也就是说,如果可能的输入少于2 ^ 32个键,并且/或者您有很多可用的内存),那么预处理阶段可能就是:

  • 依次输入每个条目
  • 找出与
  • 匹配的可能键
  • 将这些键添加到 map 中

  • [*]无需任何预处理,显然您所能做的就是检查每个数组成员,直到找到匹配项,否则就检查了所有内容。

    关于c++ - 戴着面具搜索,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/6583835/

    10-09 08:08
    查看更多