我正在按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/