我正在按ip范围查找国家(地区)数千万行。我正在寻找一种更快的查找方法。

我有18万个元组以这种形式:

>>> 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秒钟。我认为,这意味着1000万行将需要几天的时间。

最佳答案

排序数据集后,可以使用 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)

关于python - 在元组列表中查找值的更快方法是什么?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/9752308/

10-11 22:51
查看更多