散列一系列价值观

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是一些float任意精度的参数.

我能想到的最快的方法是散列,但问题在于:我可以(0.1, 0.2)用作键,但这仍然会花费我O(n)运行时间,并且最终并不比elifs的更好(我必须迭代键并检查是否key[0] <= x <= key[1]).

有没有办法散列一系列值,以便我可以检查哈希表0.15,仍然得到#execute B？

如果无法进行这样的散列,我还能如何改善其运行时间？我正在使用足够大的数据集,线性运行时不够快.

编辑:在回答cheeken的回答时,我必须注意,不能假设间隔是规则的.事实上,我几乎可以保证他们不是

为了回应评论中的要求,我应该提到我这样做是为了尝试在遗传算法中实现基于适应度的选择.算法本身用于作业,但具体实现仅用于改善生成实验数据的运行时间.

Answer 1

正如其他人已经注意到的那样,你要获得的最佳算法是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列表,列表中包含较低阈值列表,然后就可以了.