algorithm - 哪种搜索算法失败最快

Question

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

有这样的东西吗？

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

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

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

有人有更好的想法吗？

Answer 1

我能想象到的最快的算法是一个巨大的 bool 数组 0..MaxInt，除了 Array[Set Member] 处的 True 之外都是 False。搜索将是一个简单的数组查找:

Found = Array[Test]  

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

作为测试，我使用集合成员的位实现了完美哈希。函数 PHash(int) 返回一个整数 0..15，它是数组索引，如果存在匹配项将在其中找到匹配项。然后搜索是:

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

分析显示这比线性搜索慢，这可能不会让人感到惊讶。(叹气)

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

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

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