0

我正在寻找一种将一系列“范围”“投影”到一系列值中的方法。应用程序将是具有不均匀 bin 的直方图或创建查找表。

一个例子：

0 到 14 => 0

15 到 234 => 1

235 => 2

236 到 255 => 3

右边的“结果”值（0、1、2、3）的实际顺序并不重要，只要它们在 0 和 3 之间，这样我就可以使用一个小的查找表。如果我可以在浮点值（左侧）上进行这项工作，那就更好了。

我知道我可以在这里使用一个 8 位查找表并重复值，但我想找到一种“完美哈希”的方法：通过一系列系统操作（尽可能小，没有分支）从左边的值，以获得最小的结果空间。

我似乎无法为这种算法找到正确的一系列神奇的 Google 咒语。

如果需要，这个“哈希”或“投影”函数的计算持续时间可以是天。

4

1 回答 1

1

如果您的n范围没有重叠或间隙，您可以使用O(log2(n))此查找的指令生成一些简单的代码。我将使用一些 Python 代码进行演示。

# Must be a power of two, extend with zeros on the right if needed.
lookup = [0, 15, 235, 236]

def index(x):
    i = 0
    # ceil(log2(len(lookup))) iterations in the following pattern.
    # We only need 2 iterations here.
    # ...
    # i += (x >= lookup[i+8]) << 4
    # i += (x >= lookup[i+4]) << 3
    i += (x >= lookup[i+2]) << 2
    i += (x >= lookup[i+1]) << 1
    return i

这被称为无分支二进制搜索。例如，即使您有 2 16 个范围，也只需要 32 次加法和 16 次表查找、比较和位移来计算准确的索引。

于 2021-06-22T23:00:30.177 回答