¿Cuál es una forma más rápida de buscar un valor en una lista de tuplas?

Question

Estoy buscando país por rango de IP para decenas de millones de filas. Estoy buscando una forma más rápida de hacer la búsqueda.

que tienen 180K tuplas de esta forma:

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

(Los números enteros son direcciones IP convertidos en números sin formato.)

Esto hace bien su trabajo, pero sólo se necesita demasiado tiempo:

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

¿Alguien puede indicarme la dirección correcta para una forma más rápida de hacer esta búsqueda? Usando el método anterior, 100 búsquedas toman 3 segundos. Es decir, creo que las filas de 10M demorarán varios días.

Answer 1

Usted puede utilizar el módulo bisect para realizar una búsqueda binaria después de que ordenara el conjunto de datos:

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' 

La complejidad algorítmica de la búsqueda es O(log n) aquí, en lugar de O(n) para obtener una lista completa paseo.

Answer 2

Suponiendo que su situación cumpla con algunos requisitos, existe una forma de obtener la complejidad del tiempo de ejecución a O(1) en promedio, pero la complejidad del espacio sufre.

1. Los datos deben ser estáticos; todos los datos deben procesarse antes de cualquier búsqueda.
2. Dada una dirección IP arbitraria, debe haber una manera de determinar su significant octets.
3. Debe haber suficiente espacio para agregar una clave para cada valor significativo para cada país.

A continuación se presenta una implementación muy ingenua. Selecciona los primeros dos octetos de la IP como significativo sin importar qué, luego concatena los octetos significativos como números enteros y agrega incrementalmente una clave para cada valor entre el mínimo y el máximo. Como probablemente pueda decir, hay mucho margen de mejora.

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