Ottimizzazione corrispondenza chiave dizionario parziale

Question

Ho un dizionario che utilizza una tupla di 4 come chiave. Ho bisogno di trovare tutte le chiavi nel dizionario che corrispondono parzialmente ad altre tuple. Ho del codice che fa questo, ma è lento e ha bisogno di essere ottimizzato.

Ecco quello che sto cercando:

Keys: 
(1, 2, 3, 4) 
(1, 3, 5, 2) 
(2, 4, 8, 7) 
(1, 4, 3, 4) 
Match: 
(1, None, 3, None) 
Result: 
[(1, 2, 3, 4), (1, 4, 3, 4)] 

codice attuale:

def GetTuples(self, keyWords): 
    tuples = [] 
    for k in self.chain.iterkeys(): 
     match = True 
     for i in range(self.order): 
      if keyWords[i] is not None and keyWords[i] != k[i]: 
       match = False 
       break 
     if match is True: 
      tuples.append(k) 
    return tuples 

• parole chiave è una lista contenente i valori che voglio abbinare
• self.chain è il dizionario
• self.order è la dimensione della tupla
• len (parole chiave) sempre = len (k)
• 'Nessuno' è considerata la wild card
• Il dizionario è abbastanza grande (questo metodo sta prendendo ~ 800ms a correre e circa 300 MB), quindi lo spazio è anche un considerazione

Sono fondamentalmente alla ricerca di ottimizzazioni per questo metodo o un modo migliore per archiviare questi dati.

Answer 1

Che dire semplicemente utilizzando un database?

Preferisco SQLite + SQLAlchemy anche per progetti semplici, ma il semplice sqlite3 potrebbe avere una curva di apprendimento più delicata.

Inserire un indice su ogni colonna chiave dovrebbe occuparsi dei problemi di velocità.

Answer 2

Forse si potrebbe accelerare mantenendo gli indici per le chiavi. In sostanza, qualcosa di simile:

self.indices[2][5] 

conterrebbe un set di tutte le chiavi che hanno 5 nella terza posizione della chiave.

allora si potrebbe semplicemente fare insieme intersezione tra le voci di indice rilevanti per ottenere il set di chiavi:

matching_keys = None 

for i in range(self.order): 
    if keyWords[i] is not None: 
     if matching_keys is None: 
      matching_keys = self.indices[i][keyWords[i]] 
     else: 
      matching_keys &= self.indices[i][keyWords[i]] 

matching_keys = list(matching_keys) if matching_keys else [] 

Answer 3

riffing sulla risposta di Ambra:

>>> from collections import defaultdict 
>>> index = defaultdict(lambda:defaultdict(set)) 
>>> keys = [(1, 2, 3, 4), 
...   (1, 3, 5, 2), 
...   (2, 4, 8, 7), 
...   (1, 4, 3, 4), 
...   ] 
>>> for key in keys: 
...  for i, val in enumerate(key): 
...   index[i][val].add(key) 
... 
>>> def match(goal): 
...  res = [] 
...  for i, val in enumerate(goal): 
...   if val is not None: 
...    res.append(index[i][val]) 
...  return reduce(set.intersection, res) 
... 
>>> match((1, None, 3, None)) 
set([(1, 4, 3, 4), (1, 2, 3, 4)]) 

Answer 4

Non è possibile ottimizzare ulteriormente se si memorizzano i dati in un dizionario normale, poiché non fornisce nulla più veloce di un accesso sequenziale a tutti gli elementi del dizionario in un ordine imprevedibile. Ciò significa che la tua soluzione non è più veloce di O(n).

Ora, database. Il database non è una soluzione universale a qualsiasi problema (abbastanza complesso). Riesci a stimare in modo affidabile la velocità/complessità di tali ricerche per un database? Se scorri in fondo a questa risposta, vedrai che per le serie di dati di grandi dimensioni le prestazioni del database possono essere molto peggiori di una struttura dati intelligente.

Quello che ti serve qui è una struttura di dati realizzata a mano. C'è una serie di scelte, dipende fortemente da altre cose che stai facendo con questi dati.Ad esempio: puoi mantenere N serie di elenchi ordinati delle tue chiavi, ciascuna ordinata per n -esimo elemento tupla. Quindi è possibile selezionare rapidamente N gruppi ordinati di elementi corrispondenti a un solo elemento tuple nella posizione n e trovare l'intersezione per ottenere i risultati. Ciò fornirebbe una prestazione media di O(log n)*O(m) dove m è un numero medio di elementi in un sottoinsieme.

Oppure è possibile memorizzare gli elementi in un albero k-d, ciò significa che è necessario pagare il prezzo di inserzione O(log n), ma è possibile eseguire query come quella sopra nel tempo O(log n). Ecco un esempio in Python, usando k-d implementazione albero dal SciPy:

from scipy.spatial import kdtree 
import itertools 
import random 

random.seed(1) 
data = list(itertools.permutations(range(10), 4)) 
random.shuffle(data) 
data = data[:(len(data)/2)] 

tree = kdtree.KDTree(data) 

def match(a, b): 
    assert len(a) == len(b) 
    for i, v in enumerate(a): 
     if v != b[i] and (v is not None) and (b[i] is not None): 
      return False 
    return True 

def find_like(kdtree, needle): 
    assert len(needle) == kdtree.m 
    def do_find(tree, needle): 
     if hasattr(tree, 'idx'): 
      return list(itertools.ifilter(lambda x: match(needle, x), 
              kdtree.data[tree.idx])) 
     if needle[tree.split_dim] is None: 
      return do_find(tree.less, needle) + do_find(tree.greater, needle) 
     if needle[tree.split_dim] <= tree.split: 
      return do_find(tree.less, needle) 
     else: 
      return do_find(tree.greater, needle) 
    return do_find(kdtree.tree, needle) 

def find_like_bf(kdtree, needle): 
    assert len(needle) == kdtree.m 
    return list(itertools.ifilter(lambda x: match(needle, x), 
            kdtree.data)) 

import timeit 
print "k-d tree:" 
print "%.2f sec" % timeit.timeit("find_like(tree, (1, None, 2, None))", 
           "from __main__ import find_like, tree", 
           number=1000) 
print "brute force:" 
print "%.2f sec" % timeit.timeit("find_like_bf(tree, (1, None, 2, None))", 
           "from __main__ import find_like_bf, tree", 
           number=1000) 

ed eseguire test di risultati:

$ python lookup.py 
k-d tree: 
0.89 sec 
brute force: 
6.92 sec 

Solo per divertimento, ha anche aggiunto di riferimento soluzione di database-based. Il codice di inizializzazione cambiato da sopra a:

random.seed(1) 
data = list(itertools.permutations(range(30), 4)) 
random.shuffle(data) 

Ora, il "database" implementazione:

import sqlite3 

db = sqlite3.connect(":memory:") 
db.execute("CREATE TABLE a (x1 INTEGER, x2 INTEGER, x3 INTEGER, x4 INTEGER)") 
db.execute("CREATE INDEX x1 ON a(x1)") 
db.execute("CREATE INDEX x2 ON a(x2)") 
db.execute("CREATE INDEX x3 ON a(x3)") 
db.execute("CREATE INDEX x4 ON a(x4)") 

db.executemany("INSERT INTO a VALUES (?, ?, ?, ?)", 
       [[int(x) for x in value] for value in tree.data]) 

def db_test(): 
    cur = db.cursor() 
    cur.execute("SELECT * FROM a WHERE x1=? AND x3=?", (1, 2)) 
    return cur.fetchall() 

print "sqlite db:" 
print "%.2f sec" % timeit.timeit("db_test()", 
           "from __main__ import db_test", 
           number=100) 

E i risultati dei test, ridotto per 100 corse al punto di riferimento (per eventuali 657.720-element set di chiavi) :

$ python lookup.py 
building tree 
done in 6.97 sec 
building db 
done in 11.59 sec 
k-d tree: 
1.90 sec 
sqlite db: 
2.31 sec 

E 'anche opportuno ricordare che l'albero edificio ha preso quasi il doppio meno tempo poi l'inserimento di questi dati di prova stabiliti nel database.

sorgente completo qui: https://gist.github.com/1261449