就像标题所说，我试图找到存在于大型常量数组 N 中的 M 的元素。大多数时候，N 中不会存在 M 的元素，所以对 M 进行的绝大多数搜索都是浪费时间。
我正在寻找某种方法来创建索引以在对 M 进行全面搜索之前进行检查。类似于我的项目从 M 的每个元素的前几个字节创建一个位数组，据我所知，利用位级并行性以快速搜索它。我不完全理解这是如何工作的。
那么我可以使用什么技巧来减少不必要地搜索 M 的机会呢？
这是一个主要与语言无关的问题，但为了尽可能完整，我使用的是 C++。
问问题
86 次
3 回答
4
您可能会想到Bloom 过滤器，它正是用于这种情况。他们可能会给您误报，在这种情况下，您必须在真实表中进行搜索，但在大多数情况下，如果您没有存储该项目，它们会从一开始就告诉您。
哈希表通常是存储的最佳选择；但是如果您的密钥空间远远大于目标的数量，您将有大量的哈希冲突，您必须检查存储在那里的目标是否真的是您正在寻找的密钥。如果密钥比较很昂贵，它很快就会成为一个因素。
于 2010-06-24T22:17:26.790 回答
2
您可以使用 N 的值作为键来构建哈希表。
然后你尝试访问 hash[M[i]]，如果它返回一个值则它存在，即 O(1)（忽略冲突。）
于 2010-06-24T22:11:24.283 回答
1
由于 N 是静态的，您可能会考虑为 N 创建一个完美哈希函数。这将使您的搜索保证O(1) 时间。
CLR 关于算法的书对此有一个章节，上面的 wiki 页面有您可能会发现有用的链接。不过，它可能太复杂了，您可能很难找到有用的实现。. 查看Gperf的实现。
不过，您始终可以使用具有预期 O(1) 的常用哈希表。
我想您正在存储一些您想检索的额外信息，知道它在那里？你是如何存储这些的？
您可能会发现B-Tree在这种情况下很有用（行业标准数据库通常使用其中的一些变体），它甚至可以用作索引！所以，你搜索，如果你找到它，你就有了指向它的数据/指针。您会在网络上找到许多这些的实现。
于 2010-06-24T22:16:13.513 回答