使用掩码进行搜索

Question

这里有一个包含以下类型的大型数组：

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

我想根据提供的 int key; 尽快在此数组中找到一个条目。 要确保(key & mask) == value。

对于这样的数组组织方式，什么是最好的方法以及相应的处理算法是什么？

编辑：对于数组组织没有限制；它是静态的，并且可以在查找之前准备。 value 和 mask 可能具有任意值。

编辑2：虽然value 和 mask 可能具有任意值，但数组中的条目数约为10000。 因此，某些“模式”可以提前计算。

查找次数很多。

- Serge C

---

在给定的键中，数组中只有一个条目的保证吗？ - SirDarius

密钥和掩码有任何限制吗？如果没有某种限制，那么只有线性搜索才有意义。 - Karoly Horvath

附加说明：数组的组织没有限制。因此，它可以进行排序，例如。<br>只需找到适用的第一个条目即可。 - Serge C

请添加一些额外的约束条件，或者告诉我们是否没有任何约束条件。您使用有限的掩码集吗？您经常搜索相同的掩码吗？找到匹配元素的概率很高吗？... - Karoly Horvath

首先，将数组中不符合(value & mask) == value条件的条目丢弃，因为它们永远不会匹配。 - SF.

Answer 1

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

也就是说，如果值等于1且掩码在该位上等于0，则该分类根本不存储该条目，因为它不与任何key的值匹配（实际上，无论使用什么方案，在任何预处理阶段中都应删除这样的条目，因此没有分类应存储一个条目，即使只有一位是这样的情况）。如果两个都是0，则存储到两个集合中。否则，存储到两个集合中的一个。

然后，给定您的键，您希望快速查找32个集合的交集。

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

或者可能有更好的方法来执行交集。

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

1. 逐个获取每个条目 2. 确定它与哪些可能的键匹配 3. 将其添加到这些键的映射中

[*] 没有任何预处理，显然您只能检查每个数组成员，直到找到匹配项或检查了所有内容。

- Steve Jessop

---

你不需要将32个集合分别分配给每个密钥位，你可以对密钥位进行分组。例如，如果你将密钥位分成2组，则每组2个密钥位对应4个集合，因此你只需要计算16个集合的交集。将密钥位分成8组可能是最好的折衷方案 - 总共有1024个集合，每个密钥字节选择256个集合之一，然后计算4个集合的交集。 - caf

Answer 2

由于您没有额外的信息（例如，数组是否已排序），因此需要进行线性搜索-遍历数组并检查条件-伪代码：

for( size_t index = 0; index < arraySize; index++ ) {
   if( ( array[index].mask & key ) == array[index].value ) ) {
      return index;
   }
}
return -1;

- sharptooth

Answer 3

• 如果您有一个键到条目的映射，那么这将非常容易。

• 如果您的数组按键排序，则可以进行词典二分搜索并付出一些努力。 【实际上，也许不行！】

• 由于现在没有，您只需要遍历数组，直到找到您要查找的内容。也就是说，从头到尾迭代并在找到后停止。

_{顺便说一句，这是一个很好的例子，它展示了数据结构选择如何影响随后可用的算法。如果您在第一次选择中选择了错误的数据结构，则不能仅仅将算法应用于问题！}

- Lightness Races in Orbit

---

我不明白你的意思，使用像 b101 这样的位掩码应该怎么工作？ - Karoly Horvath

@yi_H：你知道如何进行比较，因为你在问题中已经展示了！将比较应用于每个数组元素，直到它揭示出巨大的成功。 - Lightness Races in Orbit

那是Serge..我问你如何使用位掩码来进行词典二分查找的工作 - Karoly Horvath

@yi_H：哦，抱歉，我误以为你是原帖作者。回想起来，也许二分查找并不那么容易。 - Lightness Races in Orbit

Answer 4

线性搜索当然可以工作，但如果您需要使用相同的关键字进行多次查找，则可以尝试根据(key & mask)首先对范围进行排序。如果您只有少量固定的关键字，则可以尝试使用boost.multi_index，每个关键值都有一个索引。

- Kerrek SB

Answer 5

如果每个条目的掩码都随意变化，我看不到除了线性搜索之外的其他选择。如果对掩码有重要的限制，例如只有几个值是可能的，那么最好为每个掩码值使用某种映射，通过线性搜索找到包含您要查找的值的第一个映射。或者，如果掩码仅涉及几个位，那么值与所有掩码的and掩码排序的multimap可能更好，并使用相同的方式处理键，然后使用完整的键进行线性搜索以找到精确匹配。

- James Kanze

Answer 6

如果掩码中零位的数量很少，您可以为掩码中的每个“不关心”位重复条目。例如，如果value=0和mask=0xfffe，则应该为key=0和key=1在表中放置一个条目。对于value=0和mask=0xfeef，请在表中放置4个条目：key=0x0000、key=0x0010、key=0x0100和key=0x0110。现在，您可以对条目进行排序并使用二进制搜索，或者使用二进制搜索结构，如std::map。

- Mark Ransom