在元组列表中查找值的更快的方法是什么？

Question

我正在通过ip范围查找国家数千万行.我正在寻找一种更快速的查找方式.

我有这种形式的180K元组:

>>> data = ((0, 16777215, 'ZZ'),
...         (1000013824, 1000079359, 'CN'),
...         (1000079360, 1000210431, 'JP'),
...         (1000210432, 1000341503, 'JP'),
...         (1000341504, 1000603647, 'IN'))

(整数是将IP地址转换为普通数字.)

这样做的工作正确,但只需要太长时间:

>>> ip_to_lookup = 999
>>> country_result = [country
...                   for (from, to, country) in data
...                   if (ip_to_lookup >= from) and
...                      (ip_to_lookup <= to)][0]
>>> print country_result
ZZ

有人能指出我正确的方向来更快地进行这种查找吗？使用上述方法,100次查找需要3秒.我想,10M行意味着需要几天时间.

Answer 1

bisect排序数据集后,可以使用该模块执行二进制搜索:

from operator import itemgetter
import bisect

data = ((0, 16777215, 'ZZ'), (1000013824, 1000079359, 'CN'), (1000079360, 1000210431, 'JP'), (1000210432, 1000341503, 'JP'), (1000341504, 1000603647, 'IN'))
sorted_data = sorted(data, key=itemgetter(0))
lower_bounds = [lower for lower,_,_ in data]

def lookup_ip(ip):
    index = bisect.bisect(lower_bounds, ip) - 1
    if index < 0:
        return None
    _, upper, country = sorted_data[index]
    return country if ip <= upper else None

print(lookup_ip(-1))          # => None
print(lookup_ip(999))         # => 'ZZ'
print(lookup_ip(16777216))    # => None
print(lookup_ip(1000013824))  # => 'CN'
print(lookup_ip(1000400000))  # => 'IN'

查找的算法复杂性在O(log n)这里,而不是O(n)完整的列表行走.