Optymalizacja częściowego słownika kluczowego dopasowania

Question

Mam słownik, który używa 4-tki, jak to jest klucz. Muszę znaleźć wszystkie klucze w słowniku, które częściowo pasują do innej krotki. Mam kod, który to robi, ale jest wolny i wymaga optymalizacji.

Oto co jestem po:

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

Aktualny kod:

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 

• słów kluczowych znajduje się lista zawierająca wartości, które chcę, aby dopasować
• self.chain jest słownik
• self.order jest wielkości krotki
• len (słów kluczowych) zawsze = Len (k)
• „Brak” jest uważane za dzikie karty
• Słownik jest dość ogromny (ta metoda jest podejmowanie ~ 800ms do uruchomienia i około 300MB), więc przestrzeń jest również rozważenie:

Poszukuję optymalizacji tej metody lub lepszego sposobu przechowywania tych danych.

Answer 1

co właśnie przy użyciu bazy danych?

Preferuję SQLite + SQLAlchemy nawet dla prostych projektów, ale zwykły sqlite3 może mieć łagodniejszą krzywą uczenia się.

Umieszczenie indeksu na każdej kolumnie klucza powinno uwzględniać problemy z szybkością.

Answer 2

Być może możesz przyspieszyć, utrzymując indeksy dla swoich kluczy. Zasadniczo coś takiego:

self.indices[2][5] 

zawierałby set wszystkich klawiszy, które mają 5 w trzeciej pozycji klucza.

Następnie można po prostu zrobić przecięcie między właściwymi wpisów indeksu, aby uzyskać zestaw kluczy:

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

riffy na odpowiedź Amber:

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

Nie można zoptymalizować tego dalej, jeśli przechowujesz dane w zwykłym słowniku, ponieważ nie zapewnia niczego szybciej niż sekwencyjny dostęp do wszystkich elementów słownika w nieprzewidywalnej kolejności. Oznacza to, że twoje rozwiązanie nie jest szybsze niż O(n).

Teraz, bazy danych. Baza danych nie jest uniwersalnym rozwiązaniem jakiegokolwiek (wystarczająco złożonego) problemu. Czy możesz wiarygodnie oszacować szybkość/złożoność takich wyszukiwań dla bazy danych? Jeśli przewiniesz na dół tej odpowiedzi, zobaczysz, że w przypadku dużych zbiorów danych wydajność bazy danych może być znacznie gorsza niż w przypadku inteligentnej struktury danych.

Potrzebna jest ręcznie opracowana struktura danych. Istnieje wiele możliwości wyboru, bardzo zależy to od innych rzeczy, które robisz z tymi danymi.Na przykład: możesz przechowywać N zestawów posortowanych list kluczy, każdy posortowany według n -ty element krotki. Następnie możesz szybko wybrać N posortowane zestawy elementów pasujących do jednego elementu krotki na pozycji n i znaleźć ich przecięcie, aby uzyskać wyniki. Dałoby to średnią wydajność O(log n)*O(m), gdzie m jest średnią liczbą elementów w jednym podzbiorze.

Możesz też przechowywać przedmioty w drzewie k-d, co oznacza, że ​​musisz zapłacić O(log n) cenę wstawki, ale możesz wykonywać zapytania podobne do tych wymienionych powyżej w O(log n). Oto przykład w Pythonie, używając k-d realizację drzewo z 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) 

i uruchomić testy Wyniki:

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

Tylko dla zabawy, również dodaje odniesienia rozwiązanie oparte na bazie danych. Kod inicjalizacji zmieniło od góry do:

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

Teraz „bazy” realizacji:

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) 

i wyniki testów, zmniejszonej o 100 działa za punkt odniesienia (dla wynikające 657720-elementowy zestaw kluczy) :

$ 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 

Warto również wspomnieć, że tworzenie drzewa zajęło prawie dwa razy mniej czasu, a następnie wstawienie tego zestawu danych testowych do bazy danych.

Kompletna źródło tutaj: https://gist.github.com/1261449