在排序的静态数组中进行最快的搜索方式

Question

在排序的静态数组中进行最快的搜索方式

3

我正在寻找在一个已排序的固定32位键数组中进行最快搜索的方法。该数组的大小和数据是静态的，永远不会改变。这个数组的大小大约是1000到10000个唯一元素。搜索范围显著较广（大约为100000），因此很多搜索值将无法找到。我只对完全匹配感兴趣。

搜索过程如下：

1. 生成大约100个键。这些键按相关性排序，因此不能简单地排序。 2. 在静态数组集合中搜索这组大约100个键（通常在50到300个数组之间）。 3. 在找到足够的匹配结果时停止搜索（因此不对键进行排序以获取最相关的结果非常重要）。

键的可能有趣的属性是，即使它们在整数值方面不接近，大多数键与其最接近的邻居之间仅有几个不同的位（约为1-4个位）。

我发现的大部分答案都指向二分查找，但没有处理静态数组的情况，这可能打开了一些优化可能性。

我完全控制数据结构，现在它是一个固定的排序数组，但如果不是最优的话，我可以进行更改。如果数据不发生变化，则我也可以添加预计算信息，前提是不需要使用过多的内存。

目标是在CPU和内存方面都高效，尽管CPU是首要考虑因素。

使用C++，但这可能不会对答案产生太大的影响。

- user2413068

2

如果您对数据结构有控制权，为什么要将搜索空间分成“50-300”个不同的数组，而不是一个排好序的单一数组中？ - Tyler Durden

2

二分查找可能仍然是最快的，特别是如果静态数据已经排序（并且不需要对数据进行任何操作）。除非您想将数据加载到一堆哈希容器中（如果您只寻找精确匹配），如果您有正确的哈希算法，则可能表现更好。 - Joe

3

静态数组通常使用(完美)哈希搜索是一个不错的想法。您所说的足够匹配的结果是什么意思？ - Jon Chesterfield

可能需要使用 Trie 数据结构，每个层级的键长为 5 或 6 位，总共有 5 或 4 层，最后一层只是一个位列表（128 或 256），其中包含要搜索的数组中的 ID。不确定这需要多少空间，或者是否比直接进行二进制搜索更快（由于内存缓存和局部性）。 - 1201ProgramAlarm

一个包含10,000个32位键的数组大小为40,000字节。将整个100,000范围表示为位（键存在/不存在）仅需要12,500字节。为什么不以这种方式存储数组呢？查找时间将几乎是瞬间的。 - m69 ''snarky and unwelcoming''

显示剩余5条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user3707125 · Accepted Answer

考虑到您的静态数组永远不会改变，并且您拥有无限的预处理能力，我认为最好的方法是为每个数组创建一个特定的哈希函数。

我的方法 - 定义一个参数化哈希函数（Java代码）：

private static Function<Long, Integer> createHashFunction(int sz) {
    int mvLeft = ThreadLocalRandom.current().nextInt(30);
    int mvRight = ThreadLocalRandom.current().nextInt(16);
    int mvLeft2 = ThreadLocalRandom.current().nextInt(10);
    int mvRight2 = ThreadLocalRandom.current().nextInt(16);
    int mvLeft3 = ThreadLocalRandom.current().nextInt(16);
    int mvRight3 = ThreadLocalRandom.current().nextInt(20);
    return (key) -> {
        // These operations are totally random, and has no mathematical background beneath them!
        key = ~key + (key << mvLeft);
        key = key ^ (key >>> mvRight);
        key = key + (key << mvLeft2);
        key = key ^ (key >>> mvRight2);
        key = key + (key << mvLeft3);
        key = key ^ (key >>> mvRight3);
        return (int) (Math.abs(key) % sz); // sz is the size of target array
    };
}

对于每个测试数组，请找到一组参数，使得最大桶大小最小。

一些测试（输入数组大小为10k，填充随机元素）：

哈希映射到[0..262k]会导致最多2个项的桶。测试了5k个随机数组，单线程版本以约100个数组/秒的速度找到哈希函数。

考虑到最大桶大小为2，可以将两个值映射到一个64位整数中，这种方法只需要进行一次内存跳转和最简单的CPU操作——哈希是通过xor、加和移位来完成的，应该非常快，位比较也是如此。

但是，您的数据可能不是很好，可能需要3个桶大小，这会破坏long long用于桶项的使用可能性。在这种情况下，您可以尝试找到一些体面的哈希函数，而不是我写的随机混乱。