python - Python:按间隔高效查找
问题描述
我有一个大查找表,其中键是一个间隔:
| min | max | value |
|-----|-----|---------|
| 0 | 3 | "Hello" |
| 4 | 5 | "World" |
| 6 | 6 | "!" |
| ... | ... | ... |
目标是创建一个查找结构my_lookup
,该结构为每个整数返回一个值,具体取决于整数所在的范围。例如:2 -> "Hello"
、3 -> "Hello"
、4 -> "World"
。
这是一个实现我想要的实现:
d = {
(0, 3): "Hello",
(4, 5): "World",
(6, 6): "!"
}
def my_lookup(i: int) -> str:
for key, value in d.items():
if key[0] <= i <= key[1]:
return value
但是遍历所有条目似乎效率低下(实际查找表包含 400.000 行)。有更快的方法吗?
解决方案
如果您的时间间隔已排序(按升序),则可以使用bisect
模块(doc)。搜索是 O(log n) 而不是 O(n):
min_lst = [0, 4, 6]
max_lst = [3, 5, 6]
values = ['Hello', 'World', '!']
import bisect
val = 2
idx = bisect.bisect_left(max_lst, val)
if idx < len(max_lst) and min_lst[idx] <= val <= max_lst[idx]:
print('Value found ->', values[idx])
else:
print('Value not found')
印刷:
Value found -> Hello
推荐阅读
- heroku - 找不到该进程类型(网络)
- java - 为什么字节到字符的转换需要int加宽转换
- c - 为什么我的 scanf 不能正常工作,当我移动它时,它工作正常?
- python-3.x - 如何从python中的多次重定向url中获取目标url?
- javascript - 如何在“新”中少写
- android - DELETE 调用返回 415 不支持的媒体类型
- java - 在我的数据库 Java Derby 中插入新数据时生成的 ID 错误
- javascript - Brain.js GPU 慢速训练
- selenium - Selenium Webdriver Java-> 单击我想要的帖子的 Facebook 分享按钮
- java - 通过更新变量更改 LiveData 源