Qual è un modo più rapido per cercare un valore in un elenco di tuple?

Question

Sto cercando paese per intervallo IP per decine di milioni di righe. Sto cercando un modo più veloce per fare la ricerca.

devo 180K tuple in questa forma:

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

(Gli interi sono indirizzi IP convertiti in numeri semplici.)

Questo fa il lavoro giusto, ma semplicemente vuole troppo tempo:

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

Qualcuno può indicarmi la direzione giusta per un modo più veloce di fare questa ricerca? Utilizzando il metodo sopra, 100 ricerche impiegano 3 secondi. Significa, credo, 10 milioni di righe richiederanno diversi giorni.

Answer 1

È possibile utilizzare il modulo bisect per effettuare una ricerca binaria dopo aver risolto il set di dati:

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 complessità algoritmica della ricerca è O(log n) qui, invece di O(n) per una passeggiata lista completa.

Answer 2

Supponendo che la propria situazione soddisfi alcuni requisiti, esiste un modo per ottenere la complessità di runtime su O(1) in media, ma la complessità dello spazio ne risente.

1. I dati devono essere statici; tutti i dati devono essere elaborati prima di qualsiasi ricerca.
2. Dato un IP arbitrario, ci deve essere un modo per determinare il suo significant octets.
3. Deve esserci spazio sufficiente per aggiungere una chiave per ogni valore significativo per ogni paese.

Di seguito è un'implementazione molto ingenuo. Seleziona i primi due ottetti dell'IP come significativi indipendentemente da cosa, quindi concatena gli ottetti significativi come numeri interi e aggiunge in modo incrementale una chiave per ogni valore compreso tra il minimo e il massimo. Come probabilmente puoi dire, c'è molto margine di miglioramento.

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