Optimizar la coincidencia parcial de la clave del diccionario

Question

Tengo un diccionario que usa una tupla de 4 como su clave. Necesito encontrar todas las claves del diccionario que coincidan parcialmente con alguna otra tupla. Tengo un código que hace esto pero es lento y necesita optimización.

Esto es lo que busco:

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

código actual:

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 

• palabras clave es una lista que contiene los valores que desea hacer coincidir
• self.chain es el diccionario
• self.order es el tamaño de la tupla
• len (palabras clave) siempre = len (k)
• 'Ninguno' se considera el comodín
• El diccionario es bastante grande (este método se está llevando ~ 800 ms para correr y aproximadamente 300 MB), por lo que el espacio es también una consideración

Básicamente estoy buscando ya sea optimizaciones para este método, o una mejor manera de almacenar estos datos.

Answer 1

¿Qué pasa con sólo usar una base de datos?

Prefiero SQLite + SQLAlchemy incluso para proyectos simples, pero el sqlite3 simple puede tener una curva de aprendizaje más suave.

Poner un índice en cada columna clave debe ocuparse de los problemas de velocidad.

Answer 2

Quizás podría acelerarlo manteniendo índices para sus claves. En esencia, algo como esto:

self.indices[2][5] 

contendría una set de todas las teclas que tienen 5 en la tercera posición de la llave.

entonces se podría simplemente hacer juego de intersección entre las entradas de índice pertinentes para obtener el juego de llaves:

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

riffs sobre la respuesta de Ámbar:

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

No puede optimizar esto más si almacena sus datos en un diccionario simple, ya que no proporciona nada más rápido que un acceso secuencial a todos los elementos de su diccionario en un orden impredecible. Esto significa que su solución no es más rápida que O(n).

Ahora, bases de datos. La base de datos no es una solución universal para ningún problema (lo suficientemente complejo). ¿Puede estimar de manera confiable la velocidad/complejidad de tales búsquedas para una base de datos? Si se desplaza hasta el final de esta respuesta, verá que, para grandes conjuntos de datos, el rendimiento de la base de datos puede ser mucho peor que una estructura de datos inteligente.

Lo que necesita aquí es una estructura de datos hecha a mano. Hay una serie de opciones, depende en gran medida de otras cosas que esté haciendo con estos datos.Por ejemplo: puede mantener N conjuntos de listas ordenadas de sus claves, cada una clasificada por n -cinco elemento de tupla. A continuación, puede seleccionar rápidamente N conjuntos ordenados de elementos que coinciden solo con un elemento de tupla en la posición n, y encuentre su intersección para obtener los resultados. Esto daría un rendimiento promedio de O(log n)*O(m) donde m es un número promedio de elementos en un subconjunto.

O puede almacenar sus artículos en un árbol k-d, esto significa que tiene que pagar O(log n) precio de inserción, pero puede hacer consultas como la de arriba en O(log n) vez. He aquí un ejemplo en Python, usando k-d implementación árbol de 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) 

Y prueba Resultados de ejecución:

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

Sólo por diversión, también añadido basados ​​en la base de datos solución de referencia. El código de inicialización cambiado de arriba a:

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

Ahora, la "base de datos" aplicación:

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) 

y resultados de pruebas, la reducción de 100 carreras por referencia (por resultante 657720-elemento de un conjunto de teclas) :

$ 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 

también vale la pena mencionar que el árbol de la construcción llevó casi dos veces menos tiempo que la inserción de estos datos de prueba establecidos en la base de datos.

fuente completo aquí: https://gist.github.com/1261449