0

我们正在寻找计算上最简单的函数，该函数将使函数的索引查找能够由广泛分布的整数和整数范围的高频输入流确定。

如果哈希/映射函数选择本身根据特定的整数和范围要求而变化，则可以，并且与选择此算法的代码部分相关的性能并不重要。在大多数情况下，感兴趣的整数/范围的数量会很小（零到几千）。性能关键部分是处理传入的流并选择适当的函数。

作为一个简单的例子，请考虑以下伪代码：

switch (highFrequencyIntegerStream)
    case(2)      : func1();
    case(3)      : func2();
    case(8)      : func3();
    case(33-122) : func4();

    ...

    case(10,000) : func40();

在一个典型的例子中，上面显示的“案例”只有几千个，其中可能包括完整的 32 位整数值和范围。（在上面的伪代码中，33-122 代表了从 33 到 122 的所有整数。）会有大量的对象包含这些“switch 语句”。

（请注意，实际的实现不会包括 switch 语句。它将是一个跳转表（它是一个函数指针数组）或者可能是 Command 和 Observer 模式的组合等。实现细节与请求相切，但提供帮助可视化。）

许多对象将包含只有几个条目的“switch 语句”。感兴趣的值会受到实时变化的影响，但与管理这些变化相关的性能并不重要。哈希/映射算法可以根据特定整数和感兴趣的范围（对于给定时间的给定对象）在每次更新时缓慢重新生成。

我们在互联网上进行了搜索，查看了 Bloom 过滤器、维基百科的“哈希函数”页面和其他地方列出的各种哈希函数、相当多的 Stack Overflow 问题、抽象代数（主要是伽罗瓦理论，其计算简单的操作数很有吸引力）、各种密码等，但尚未找到似乎针对此问题的解决方案。（我们甚至找不到将这些类型的范围视为输入的哈希或映射函数，更不用说高效的了。也许我们没有在正确的地方寻找或使用正确的语言。）

目前的计划是创建一个自定义算法，预处理感兴趣的整数和范围列表（对于给定时间的给定对象），寻找可应用于输入流以帮助描绘范围的移位和掩码。请注意，大多数传入的整数将是无趣的，并且对尽可能大比例的流的那部分做出非常快速的决定至关重要（这就是为什么布隆过滤器一开始看起来很有趣（在我们开始之前）认为他们的实现比其他解决方案需要更多的计算复杂性））。

因为第一个决定非常重要，我们也在考虑拥有多个表，其中第一个是反掩码（用于选择不感兴趣的数字的掩码），以便于查找未包含在给定“switch 语句”中的大范围数据，后面的表格将扩大较小的范围。我们认为，对于大多数输入流的情况，这将比在范围边界上进行二分搜索快得多。

请注意，输入流可以被认为是随机分布的。

4

2 回答 2

1

我认为有一个非常广泛的最小完美哈希函数理论可以满足您的要求。最小完美哈希的想法是一组不同的输入以 1-1 的方式映射到一组密集的整数。在您的情况下，一组 N 个 32 位整数和范围将分别映射到大小为 N 的小倍数的范围内的唯一整数。 Gnu 有一个完美的散列函数生成器，称为gperf用于字符串但可能适用于你的数据。我一定会试一试的。只需添加一个长度字节，使整数为 5 字节字符串，范围为 9 字节。维基百科页面上有一些正式的参考资料。ACM 和 IEEE 文献中的文献搜索肯定会出现更多。

我刚刚跑过这个我以前没见过的图书馆。

添加

我现在看到您正在尝试将范围内的所有整数映射到相同的函数值。正如我在评论中所说，这与散列不太兼容，因为散列函数故意尝试“擦除”位位置的幅度信息，以便具有相似幅度的值不太可能映射到相同的散列值。

因此，我认为您不会比最佳二叉搜索树或等效的代码生成器做得更好，该代码生成器可以生成“if else”语句的最佳“树”。

如果我们想构建您要求的类型的函数，我们可以尝试使用实数，其中各个域值映射到共同域中的连续整数，范围映射到共同域中的单位间隔。因此，一个简单的地板操作将为您提供您正在寻找的跳跃表索引。

在您提供的示例中，您将具有以下映射：

2 -> 0.0
3 -> 1.0
8 -> 2.0
33 -> 3.0
122 -> 3.99999
...
10000 -> 42.0 (for example)

诀窍是找到对这些点进行插值的单调递增多项式。这当然是可能的，但我敢肯定，有数千分，你最终会得到比最佳搜索慢得多的评估结果。

于 2013-08-14T03:31:13.937 回答
0

也许我们对散列整数的想法会有所帮助。您还将找到一个基于 Bob Jenkins 工作的散列库 (hashlib.zip)，它以一种智能的方式处理整数。我建议在散列机制拒绝单个案例后处理更大的范围。

于 2015-11-17T12:41:35.737 回答