अनुकूलन आंशिक शब्दकोश कुंजी मैच

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 टपल के आकार है
• लेन (कीवर्ड्स) हमेशा = लेन (के)
• 'कोई नहीं' माना जाता है वाइल्ड कार्ड
• शब्दकोश सुंदर विशाल (इस विधि ले जा रहा है ~ 800ms चलाने के लिए और 300MB के बारे में) है, इसलिए अंतरिक्ष भी एक है विचार

मैं मूल रूप से इस विधि के अनुकूलन या इस डेटा को संग्रहीत करने का एक बेहतर तरीका ढूंढ रहा हूं।

Answer 1

क्या सिर्फ एक डेटाबेस का उपयोग कर के बारे में?

मैं सरल परियोजनाओं के लिए SQLite + SQLAlchemy पसंद करता हूं, लेकिन सादा sqlite3 में एक gentler सीखने की वक्र हो सकती है।

प्रत्येक कुंजी स्तंभ पर एक सूचकांक लाना गति मुद्दों का ध्यान रखना चाहिए।

Answer 2

शायद आप इसे अपने चाबी के लिए अनुक्रमित बनाए रखने के द्वारा तेजी लाने सकता है। अनिवार्य रूप से, कुछ इस तरह:

self.indices[2][5] 

कुंजी जो कुंजी का तीसरे स्थान पर 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

एम्बर के जवाब पर riffing:

तो फिर तुम बस कुंजियों का सेट प्राप्त करने के लिए सम्बंधित सूचकांक प्रविष्टियों के बीच सेट चौराहे कर सकता है

>>> 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 -th tuple तत्व द्वारा क्रमबद्ध किया गया है। फिर आप N स्थिति n पर केवल एक ट्यूपल तत्व से मेल खाने वाले तत्वों के क्रमबद्ध सेट का चयन कर सकते हैं, और परिणाम प्राप्त करने के लिए अपने चौराहे को ढूंढ सकते हैं। यह O(log n)*O(m) का औसत प्रदर्शन करेगा जहां मी एक सबसेट में तत्वों की औसत संख्या है।

या आप अपने आइटम को के-डी पेड़ में स्टोर कर सकते हैं, इसका मतलब है कि आपको O(log n) सम्मिलन मूल्य का भुगतान करना होगा, लेकिन आप O(log n) समय में उपरोक्त प्रश्नों को कर सकते हैं। यहाँ अजगर में एक उदाहरण है, वह SciPy k-घ पेड़ कार्यान्वयन का उपयोग:

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 

बस मस्ती के लिए, डेटाबेस के आधार पर समाधान बेंचमार्क यह भी कहा। बेंचमार्क प्रति (657,720 तत्व चाबियों का सेट जिसके परिणामस्वरूप के लिए)

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 

यह भी उल्लेखनीय है कि निर्माण पेड़ लगभग दो बार कम समय लेता है और फिर डेटाबेस में इस परीक्षण डेटा को सेट करता है।

पूरा यहाँ स्रोत: https://gist.github.com/1261449