快速判断成员是否在集合中的方法

Question

我有一组小数字，需要不断搜索。

这个组是静态的，在一开始就已知。

通过观察，我知道大部分时间我要查找的数字不在这个组里。

我正在寻找的算法可以在一两步操作中实现：

1. 从不说一个数字不在组内而实际上在
2. 该算法大多数或全部时间都可以预测是否在组内

例如，如果数字是x、y、z，我可以这样做：

保存：

tmp = (x | y | z)

当我搜索一个数字时，我可以进行如下操作：

if ((num & tmp) == (num))
    do the real search

如果数字是x、y或z，当使用AND时保证返回num。如果不是，我可能会搜索到空，但基本上没问题。

这个测试的主要问题在于，对于超过5个数字的组，大多数情况下即使num不在组中，我仍然会得到TRUE。

我考虑使用XOR魔法：

tmp = (x ^ y ^ z)

当搜索时，可以执行以下操作：

(num ^ tmp)

但我不知道这如何帮助我确定元素是否在组内。

有什么想法吗？

谢谢，

Itay

更新

我发现使用类似于非常简单的布隆过滤器很有用：

我已经将x、y和z散列到一个位数组中（例如8位）。 然后，我将结果移动到正确的位：

uint8_t digest = (1 << (x % 8)) | (1 << (y % 8)) | (1 << (z % 8))

在搜索功能中，我使用了以下内容：

if ( (1 << (num % 8)) & digest )

我使用随机数进行了一些分析，发现使用8位时有大约30%的时间会给出错误的指示。使用16位则效果更好。

- Itay Marom

---

你应该提供一个或多个需要表示的群体的例子，这可以帮助我们找到有趣的模式。 - user1196549

为什么不使用布尔数组查找？如果数字范围太大，可以考虑使用一些原始哈希技术。 - hivert

我没有对它们进行排序的原因是该组非常小（最多7个数字），而且程序非常注重性能。这就是为什么我试图找到最快的规则排除检查。 - Itay Marom

如hivert所建议，布尔数组可能是最快的。对于32位数字，您可以使用528兆字节内存中存储的位数组。只需要一个索引（由值>> 3索引）读取字节，然后测试字节中是否设置了任何位，因此对于非命中只需两个操作。如果设置了任何位，则需要通过移位（移位为（value＆7））和布尔与（&）测试特定位是否设置。 - rcgldr

@rcgldr 分配528兆字节的零，整个过程中只设置了七个位，这是通过缓存抖动来降低性能的好方法，也可能是最慢的方法。 - Sneftel

Answer 1

对于只有七个数字的集合，您应该使用暴力搜索方法来查找；这比任何其他方法都要快。如果您的值为16位或更少，则可以在单个SIMD相等性测试中完成；如果它们是32位，则可以在两个测试中完成。

- Sneftel

---

对集合进行排序仍应该给出较好的结果，因为一旦找到一个大于搜索项的数字，你就可以退出搜索。 - erik258

@DanFarrell 可能会因为分支预测失败而导致性能下降，因此提前退出可能不是一个好的选择。 - Sneftel

@ItayMarom 大多数与高效执行任务相关的好主意都依赖于特定的平台。 - Sneftel

实际上，你之前的回答（你已经删除了）帮助我找到了解决方案：一个简单的布隆过滤器。 http://billmill.org/bloomfilter-tutorial/ - Itay Marom

我认为在这里布隆过滤器并不是一个好主意。由于集合中元素数量较少，计算哈希函数的成本可能比简单搜索更高。 - Sneftel

Answer 2

如果“静态和时间开始”意味着编译时，您可以使用开关。

bool inGroup(int i) {
switch(i) {
case X1: return true;
case X2: return true;
// ...
case X7: return true;
default: return false;
}

如果整数范围内的数字不是广泛分布的，那么将导致跳转表。如果数字范围广泛分布，则可以使用gperf计算出最佳哈希函数。

如果数字不是编译时常量，则应考虑将它们存储在数组中，对其进行排序并使用二分查找。排序只需要做一次，搜索最多需要三次比较。

- Jens

Answer 3

使用一个简单的哈希函数将您的域映射到一个常量范围（例如a.x mod b或类似）和一个包含b个布尔值的数组。如果你足够幸运/小心，你可能会避免哈希冲突并得到一个精确的测试结果。

- user1196549

Answer 4

数据结构

设 min 为目标集合中的最小值。 设 max 为目标集合中的最大值。

设 bset 为一个比特向量，大小为 max - min 所需的总比特数。

对于目标集合中的每个数字 x，令 n = x - min。设置集合中的第 n 位。

谓词

对于给定的数字 x，令 n = x - min，如果第 n 位被设置，则它是一个成员。

每次测试的成本应该是 1 次减法、2 次位移、1 次数组访问和 1 次逻辑与。如果您的比特向量由一组 32 位或 64 位值表示，并在屏蔽比特之前首先测试值是否非零，则可能能够概率性地节省更多。

内存成本取决于 max 和 min 之间的差异。

根据输入集合的大小，我也倾向于即时编译您拥有的数字的比较器。如果您动态编写二分搜索，最坏情况下需要 log2(n) 次比较，这与二进制向量相当，适用于 ~32 个数字。

- plinth