Python：通过区间实现高效查找

Question

我有一个大型的查找表，其中键是一个区间：

| 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行）。有更快的方法吗？

- Elias Strehle

---

通常情况下，您将间隔存储在区间树中。 - chepner

这些区间是否保证不相交？ - chepner

是的，这些区间是不相交的。在查找表被初始化之后，将会有数百万次的查找...所以如果排序能增加查找效率，那肯定是值得的。 - Elias Strehle

为了给您一些背景：实际问题是从 Web 服务器上的 IP 地址确定用户所在的国家。 - Elias Strehle

等等，那么实际的间隔是什么：IP地址范围？你可能需要一个Patricia trie，因为这些范围很可能是网络前缀。 - chepner

Answer 1

如果你的间隔已经按照升序排列，你可以使用 bisect 模块（文档）。这样搜索的时间复杂度为 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

- Andrej Kesely