Cách nhanh hơn để tra cứu giá trị trong danh sách bộ dữ liệu là gì?

Question

Tôi đang tìm quốc gia theo dải ip cho hàng chục triệu hàng. Tôi đang tìm cách tìm kiếm nhanh hơn.

Tôi có 180K bản ghi trong mẫu đơn này:

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

(Các số nguyên được địa chỉ ip chuyển đổi thành số đơn giản.)

này không được công việc đúng, nhưng chỉ mất quá lâu:

>>> 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 

Có ai có thể chỉ cho tôi đúng hướng để có cách nhanh hơn để thực hiện tra cứu này không? Sử dụng phương pháp trên, 100 lần tra cứu mất 3 giây. Có nghĩa là, tôi nghĩ, 10 triệu hàng sẽ mất vài ngày.

Answer 1

Bạn có thể sử dụng các mô-đun bisect để thực hiện tìm kiếm nhị phân sau khi bạn sắp xếp các dữ liệu:

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' 

Sự phức tạp thuật toán của việc tra cứu là O(log n) đây, thay vì O(n) cho một danh sách đi bộ hoàn chỉnh.

Answer 2

Giả sử tình huống của bạn đáp ứng một số yêu cầu, có một cách để tăng độ phức tạp của thời gian chạy lên O(1), nhưng độ phức tạp của không gian bị ảnh hưởng.

1. Dữ liệu phải tĩnh; tất cả dữ liệu phải được xử lý trước bất kỳ lần tra cứu nào.
2. Với IP tùy ý, phải có cách xác định significant octets.
3. Phải có đủ không gian để thêm khóa cho mọi giá trị quan trọng cho mỗi quốc gia.

Dưới đây là triển khai rất ngây thơ. Nó chọn hai octet đầu tiên của IP là quan trọng không có vấn đề gì, sau đó ghép các octet quan trọng thành các số nguyên và gia tăng thêm một khóa cho mỗi giá trị giữa mininum và maximum. Như bạn có thể nói, có nhiều chỗ để cải thiện.

from socket import inet_ntoa 
from struct import pack 

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

def makedict(minip, maxip, country): 
    d = {} 
    for i in xrange(key(minip), key(maxip)+1): 
     d[i] = country 
    return d 

def key(ip): 
    octets = inet_ntoa(pack('>L', ip)).split('.') 
    return int("".join(octets[0:2])); 

lookup = {} 
for lo, hi, cnt in data: 
    lookup.update(makedict(lo, hi, cnt)) 

print lookup[key(999)]   # ZZ 
print lookup[key(1000215555)] # JP