对一系列值进行哈希处理

Question

我知道我可以把单个值当作键放进一个 dict 里进行哈希。例如，我可以把 5 作为 dict 中的一个键。

现在我遇到了一个问题，需要对一系列值进行哈希。

基本上，我需要一个更快的方法来做到这一点：

if 0 <= x <= 0.1:
    # f(A)
elif 0.1 <= x <= 0.2:
    # f(B)
elif 0.2 <= x <= 0.3:
    # f(C)
elif 0.3 <= x <= 0.4:
    # f(D)
elif 0.4 <= x <= 0.5:
    # f(E)
elif 0.5 <= x <= 0.6:
    # f(F)

这里的 x 是一个可以有任意精度的小数参数。

我能想到的最快的方法就是哈希，但问题是：我可以用 (0.1, 0.2) 作为一个键，但这样做的时间复杂度还是 O(n)，最终效果和一堆 elif 没什么区别（我得遍历所有键，检查 key[0] <= x <= key[1]）。

有没有办法对一系列值进行哈希，这样我就可以在哈希表中查找 0.15 还能够得到 #execute B 呢？

如果这样的哈希方法不可行，那我还有什么其他办法可以提高运行速度呢？因为我处理的数据集比较大，线性时间复杂度的速度实在不够快。

编辑：针对 cheeken 的回答，我必须说明这些区间不能假设是规则的。实际上，我几乎可以保证它们不是。

回应评论中的请求，我应该提到我这样做是为了在一个 遗传算法中实现基于适应度的选择。这个算法是为了作业，但具体的实现只是为了提高生成实验数据的运行速度。

Answer 1

如果你的区间是规则的，你可以先对你的操作数进行缩放，然后用floor函数把它们取整到每个范围的最小值，然后把这个结果直接放入一个dict字典中，把这些最小值和相应的处理器对应起来。

下面是一个示例实现，使用了你提供的范围。

# Integerize our 0.1 width intervals; scale by x10
handlerDict = {}
handlerDict[0] = lambda x: ... # 0.1
handlerDict[1] = lambda x: ... # 0.2
handlerDict[2] = lambda x: ... # 0.3
...

# Get the right handler, scaling x by x10; handle
handlerDict[int(10*x)](x, ...)

Answer 2

你不一定需要对所有的值进行哈希处理。比如，在上面提到的范围中，如果你得到了0.15，你可以把它四舍五入到0.2（小数点后面的第一个数字），然后对0.2进行哈希处理。

那么，这个过程需要多高的效率呢？你可以尝试另一种方法，就是二分查找。把区间值按顺序存放在一个列表中，然后在这个列表上进行二分查找。例如：

sorted_list = [ (0.1, function1), (0.2, function2), ....(0.6, function6) ] 

接着，你只需要进行二分查找，找到比x大的最小元素。这种方法的效率是O(log(n))。

Answer 3

正如其他人提到的，最好的算法其实是O(log N)的，而不是O(1)。这意味着你可以通过一种叫做二分查找的方法，在一个已经排好序的列表中进行查找。

在Python中，最简单的方法就是使用bisect这个标准模块，具体可以参考这个链接：http://docs.python.org/library/bisect.html。特别要注意的是，在8.5.2节中有一个关于数字表查找的例子——这正是你要做的事情：

>>> def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
...     i = bisect(breakpoints, score)
...     return grades[i]
...
>>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
['F', 'A', 'C', 'C', 'B', 'A', 'A']

把grades这个字符串替换成一个函数的列表，把breakpoints这个列表替换成你的下限阈值列表，这样就可以了。