1

给定一个整数，我需要从一个小集合中找到一个匹配项。整数几乎总是不在集合中。对于大多数搜索算法，这是最坏的情况（花费时间最长）。但是对于这个应用程序，搜索时间将取决于搜索失败的速度。所以我想要一个最好的情况是“找不到”的算法。

这样的事情存在吗？

整数远非随机，是数组索引——比如 0..10k（15 位）。这些集合将包含 0..7 个整数，这对于简单的线性搜索来说是足够少的。但这在几乎所有情况下都是最坏的情况。

我唯一能想到的就是布隆过滤器。它会像这样工作：定义 F(int) = Set Bit (i AND 1Fh)（即，一个 32 位整数，一个位被设置）。对于每个集合，我会将 F（每个元素）的 OR'd 值存储在一起（一个 32 位整数，为 n 个元素设置最大 n 位）。然后搜索将是 IF (F(i) AND F(set))>0 然后执行线性搜索。

因此，除非至少一个集合元素具有与测试整数 i 相同的低 5 位，否则永远不会执行搜索。可以根据下一个最低 5 位添加第二个测试。

有更好的想法吗？

4

1 回答 1

0

我能想象到的最快的算法，它会立即成功或失败，是一个巨大的布尔数组 0..MaxInt，除了 Array[Set Member] 处的 True 之外，所有的都是 False。搜索将是一个简单的数组查找：

Found = Array[Test]

但是内存占用是荒谬的。一个常见的优化是哈希数组。

作为测试，我使用 Set Members 的位实现了 Perfect Hash。函数 PHash(int) 返回一个整数 0..15，它是数组索引，如果存在匹配项，将在其中找到匹配项。那么搜索是：

IF Array[PHash(Test)] = Test 
  THEN Found at Index PHash(Test) 
  ELSE Not Found

分析表明这比线性搜索慢，这可能不会让任何人感到惊讶。（叹）

当然，没有单个 Hash 可以将 15 位整数减少为不同的 4 位整数。我使用许多不同的哈希函数。为了生成 Set，我找出哪个函数为该 Set 生成不同的 4 位散列，然后将 Set 存储为散列函数指针加上一个 16 元素数组。每个数组元素是 X 或一个集合成员，其中 X 不在集合范围内。（未能找到完美哈希会引发异常，这还没有发生。）这些开销在分析中都不重要，因为它在程序启动时完成一次。

要在 Set 中查找 Test 整数，我调用 Set.HashFunction(Test)，然后将 Test 与该 Set.Array 元素进行比较。最后的比较与线性搜索的每个步骤相同。为了更快，哈希函数必须比线性搜索的剩余比较更快。所以这可能是一个更快的算法，但只适用于足够大的集合大小。

我还没有尝试找到那个集合大小。无论如何，这取决于每个散列函数的速度。

于 2012-11-23T01:21:19.813 回答