部分的なキーの一致を最適化する

Question

私は4タプルをキーとして使用する辞書を持っています。部分的に他のタプルと一致する辞書内のすべてのキーを見つける必要があります。私はこれを行ういくつかのコードがありますが、それは遅く、最適化が必要です。ここで

は、私が後だものです：

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

現在のコード：

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 

• キーワード私は
• self.chainと一致する値を含むリストが辞書です
• self.orderはタプルのサイズです
• LEN（キーワード）は常に= LEN（K）
• 「なし」とみなされているワイルドカード
• 辞書は（〜800msを実行すると300メガバイトについては、この方法が取っている）かなり巨大であるため、スペースもあります考慮事項

私は基本的にこの方法の最適化、またはこのデータを保存するためのより良い方法を探しています。

Answer 1

を何単にデータベースを使用してはどうですか？

単純なプロジェクトでもSQLite + SQLAlchemyが好きですが、普通のsqlite3の方がやや習熟しているかもしれません。

各キー列にインデックスを設定すると、スピードの問題を処理する必要があります。

Answer 2

おそらく、あなたのキーのインデックスを維持することによってスピードを上げることができます。基本的に、このような何か：

self.indices[2][5] 

は、キーの第3の位置に5を持っているすべてのキーのsetを含んでいるでしょう。琥珀の答えにリフ

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

：

は、その後、あなたは、単にキーのセットを取得するために、関連するインデックス・エントリの間にセット交差を行うことができます

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

単純な辞書にデータを保存すると、これをさらに最適化することはできません。何も予測できない順序で辞書のすべての要素への順次アクセスを提供しないためです。これは、あなたの解がO(n)より速くないことを意味します。

今、データベース。データベースは、（複雑な）問題の普遍的な解決策ではありません。このようなデータベースのルックアップの速度/複雑さを確実に見積もることはできますか？この返信の最後までスクロールすると、大きなデータセットの場合、データベースのパフォーマンスがスマートなデータ構造よりもはるかに悪い可能性があります。

ここで必要なものは手作りのデータ構造です。多くの選択肢がありますが、このデータを使って他のものに強く依存しています。たとえば、Nのキーの並べ替えられたリストを、それぞれn番目のタプル要素でソートしておくことができます。次に、位置nにある1つのタプル要素にのみ一致する要素の並べ替えられたセットのNを素早く選択し、それらの交差を見つけて結果を得ることができます。これにより、平均パフォーマンスがO(log n)*O(m)になります。ここで、mは1つのサブセットの平均要素数です。

あなたはk-dツリーにアイテムを保存することができます。つまり、挿入価格はO(log n)でなければなりませんが、上記のようなクエリをO(log n)時間行うことができます。ここでscipyのダウンロードからkd木の実装を使用して、Pythonでの例です：

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) 

そして、テスト実行結果：

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

楽しみのためだけに、また、データベースベースのソリューションのベンチマークを追加しました。ベンチマークごと（キーのセット657720要素を結果として生じるため）

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) 

と試験結果、100回の実行のために低下：今

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

、「データベース」実装：初期化コードは、上からに変更しました：

$ 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 

このビルドツリーでは、このテストデータセットをデータベースに挿入するのに要する時間がほぼ2倍短縮されました。ここ

完全なソース：https://gist.github.com/1261449