c++ - 带着面具搜索

Question

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

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

我想根据提供的 int key; 尽可能快地在这个数组中找到一个条目。需要输入以确保 (key & mask) == value。

这种数组组织的最佳方式是什么，相应的算法是什么？

编辑:数组组织没有限制；它是静态的，可以在查找之前准备好。 value 和 mask 可以有任意值。

Edit2:value 和mask 可能有任意值，但数组中的条目数约为 10000。因此，可以提前计算某些“模式”。

查找次数多。

Answer 1

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

也就是说，如果该位的值 == 1 和掩码 == 0，则该分类根本不存储该条目，因为它不匹配 key 的任何值(事实上，无论你使用什么方案，这些条目都应该在任何预处理阶段被删除，所以没有分类应该存储一个条目，即使是这样的一位)。如果两者都为 0，则存储到两个集合中。否则存储到两个集合中的一个。

然后，根据您的 key ，您想要找到 32 个集合的快速交集。

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

或者可能有更好的交叉方式。

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

1. 依次输入每个条目
2. 找出它可能匹配的键
3. 将它添加到那些键的映射中

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