哪种搜索算法失败最快
给定一个整数，我需要从一个小集合中找到一个匹配项。整数几乎总是，而不是在集合中。对于大多数搜索算法来说，这是最坏的情况(耗时最长)。但是对于这个应用程序，搜索时间将取决于搜索失败的速度。所以我想要一个算法最好的例子是“找不到”。
这样的东西存在吗？
整数不是随机的，而是数组索引--比如0..10k (15位)。集合将包含0..7整数，这对于一个简单的线性搜索来说是足够少的。但在几乎所有情况下，这都是最糟糕的情况。
我唯一能想到的就是布卢姆过滤器。它的工作方式如下:定义F(int) = Set位(i和1 1Fh) (即一个32位整数，设置一位)。对于每个集合，我将存储F(每个元素)的OR'd值(一个32位整数，最大n位设置为n个元素)。搜索的条件是(F(i)和F(set))>0，然后执行线性搜索。
因此，除非至少有一个set元素具有与测试整数i相同的低5位，否则将永远不会执行搜索。
谁有更好的主意？
回答 1
Stack Overflow用户
发布于 2012-11-23 01:21:19
我能想象到的最快的算法是一个巨大的布尔数组0..MaxInt，它会立即成功或失败，除了ArraySet成员的True之外，所有这些都是假的。搜索将是一个简单的数组查找：
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或一个集合成员，其中X不在集合范围内。(如果找不到一个完美的哈希，就会抛出一个异常，这种情况还没有发生。)在分析过程中，这些开销都不重要，因为它是在程序启动时完成的。
要在集合中找到测试整数，我调用Set.HashFunction(测试)，然后将测试与该Set.Array元素进行比较。最后的比较与线性搜索的每一步相同。要想更快，哈希函数必须比线性搜索的其余比较更快。因此，这个可以是一个更快的算法，但只适用于足够大的集合大小。
我还没试过要找出那套尺寸。无论如何，它将取决于每个散列函数的速度。
https://stackoverflow.com/questions/13506184
复制相似问题
腾讯云开发者
