Какой более быстрый способ поиска значения в списке кортежей?

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 секунды. Я имею в виду, что на 10 миллионов строк уйдет несколько дней.

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) для полного просмотра списка.

Answer 2

Если ваша ситуация соответствует некоторым требованиям, существует способ довести сложность среды выполнения до O(1) в среднем, но пространственная сложность страдает.

1. Данные должны быть статическими;все данные должны быть обработаны перед любыми поисками.
2. Учитывая произвольный IP, должен быть способ определить его значимые октеты .
3. Должно быть достаточно места для добавленияключ для каждого значимого значения для каждой страны.

Ниже приведена очень наивная реализация.Он выбирает первые два октета IP как значимые независимо от того, что, затем объединяет значимые октеты в виде целых чисел и постепенно добавляет ключ для каждого значения между mininum и максимумом.Как вы, вероятно, можете сказать, есть много возможностей для улучшения.

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