用面具搜索

Question

有大量条目具有以下类型:

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

我想根据提供的int key;速度尽可能快地在这个数组中找到一个条目.该条目是确保这一点(key & mask) == value.

这种阵列组织的最佳方法是什么,处理它的相应算法是什么？

编辑:阵列组织没有限制; 它是静态的,可以在查找之前准备好.该value和mask可以有任意值.

Edit2:value并且mask可以具有任意值,但是数组中的条目数约为10000.因此,可以预先计算某些"paterns".

查找次数很多.

Answer 1

每个位都是独立的，因此在预处理阶段[*]，您可以对每个条目分类 32（或者无论您int有多大）次。每个分类存储 2 组：当 0 时在该位匹配的组和当1key时匹配的组。key

也就是说，如果 value == 1 且 mask == 0 在该位，则该分类根本不存储该条目，因为它不匹配key(事实上，无论您使用什么方案，例如在任何预处理阶段都应该删除条目，因此任何分类都不应存储条目（即使有一位是这样的）。如果均为 0，则存储到两个集合中。否则存储到两个集合之一中。

然后，根据您的密钥，您希望找到 32 个集合的快速交集。

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

或者可能有更好的方法来进行交叉。

如果键倾向于重复使用，那么您应该将查找结果缓存在从键到条目的映射中。如果可能的键的数量相当小（也就是说，如果可能的输入明显少于 2^32 个键，和/或您有大量可用内存），那么您的预处理阶段可能是：

1. 依次获取每个条目
2. 找出它可能匹配的键
3. 将其添加到这些键的地图中

[*] 在没有任何预处理的情况下，显然您所能做的就是检查每个数组成员，直到找到匹配项或检查完所有内容。