0

就像标题所说,我试图找到存在于大型常量数组 N 中的 M 的元素。大多数时候,N 中不会存在 M 的元素,所以对 M 进行的绝大多数搜索都是浪费时间。

我正在寻找某种方法来创建索引以在对 M 进行全面搜索之前进行检查。类似于我的项目从 M 的每个元素的前几个字节创建一个位数组,据我所知,利用位级并行性以快速搜索它。我不完全理解这是如何工作的。

那么我可以使用什么技巧来减少不必要地搜索 M 的机会呢?

这是一个主要与语言无关的问题,但为了尽可能完整,我使用的是 C++。

4

3 回答 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 回答