प्रतिवर्ती शब्दकोश अजगर

Question

के लिए मैं एक शब्दकोश में एक समान रूप में अजगर में कुछ डेटा स्टोर करना चाहते हैं: {1:'a', 2:'b'}। प्रत्येक मूल्य अद्वितीय होगा, न केवल अन्य मूल्यों के बीच, बल्कि कुंजी के बीच भी।

वहाँ एक सरल डेटा संरचना है कि मैं अगर मैं 'कुंजी' या 'मूल्य' का उपयोग कर पूछना इसी वस्तु कोई बात नहीं प्राप्त करने के लिए उपयोग कर सकते हैं है? उदाहरण के लिए:

>>> a = {1:'a', 2:'b'} 
>>> a[1] 
'a' 
>>> a['b'] 
2 
>>> a[3] 
KeyError 

'कुंजी', मानक अजगर ints हैं एक मूल्यों कम (< 256char) तार कर रहे हैं।

मेरे वर्तमान समाधान एक उलट शब्दकोश बनाने और अगर मैं मूल शब्दकोश में एक परिणाम नहीं मिल सकता है यह खोज कर रहा है: मेरे शब्दकोशों

pointsreversed = dict((v, k) for k, v in points.iteritems()) 
def lookup(key): 
    return points.get(key) or pointsreversed.key() 

यह दो बार के रूप में ज्यादा स्थान का उपयोग करता है, जो महान नहीं है (कुछ सौ मेग्स तक हो सकता है) और औसतन 50% धीमी है।

संपादित करें: के रूप में कुछ जवाब में उल्लेख किया है, दो dicts, नहीं डबल स्मृति उपयोग करता है, क्योंकि यह केवल शब्दकोश, उसके अंदर के आइटम है, कि दोहराव है।

वहाँ एक समाधान है कि इस पर सुधार है?

Answer 1

संबंधित पोस्ट:

Python mapping inverse

Python 1:1 mappings

बेशक

, अगर सभी मूल्यों और चाबी अद्वितीय हैं, तो आप सिर्फ एक शब्दकोश का उपयोग नहीं कर सकता है, और सम्मिलित दोनों कुंजी: मूल्य और मूल्य प्रारंभ में कुंजी?

a = {1:'a', 2:'b'} 
a.update(dict((v, k) for k, v in a.iteritems())) 

तो फिर तुम, दोनों ऐसा करने में सक्षम हो जाएगा के रूप में आप की आवश्यकता:

print a[1] 
print a['a'] 

Answer 2

सम्मिलित ही dict में (कुंजी, मूल्य) की जोड़ी उलट गैर-ओवरलैपिंग, एक स्पष्ट दृष्टिकोण उन्हें एक ही नियम में स्टोर करना है। अर्थात्:

class BidirectionalDict(dict): 
    def __setitem__(self, key, val): 
     dict.__setitem__(self, key, val) 
     dict.__setitem__(self, val, key) 

    def __delitem__(self, key): 
     dict.__delitem__(self, self[key]) 
     dict.__delitem__(self, key) 

d = BidirectionalDict() 
d['foo'] = 4 
print d[4] # Prints 'foo' 

(आप भी शायद __init__, update और iter* तरीकों तरह बातें कोई वास्तविक dict की तरह काम करने के लिए, आप कितना कार्यक्षमता की जरूरत पर निर्भर करता है को लागू करना चाहते हैं)।

इसमें केवल एक लुकअप शामिल होना चाहिए, हालांकि आपको स्मृति में बहुत अधिक बचत नहीं हो सकती है (आपके पास अभी भी दो बार प्रविष्टियों की संख्या दो बार है)। नोट हालांकि कि यह और न ही अपने मूल न दुगनी हो जाती स्थान का उपयोग होगा: dict केवल संदर्भ (प्रभावी रूप से सूचक मात्र), प्लस एक overallocation भूमि के ऊपर के लिए जगह लेता है। आपके डेटा द्वारा उठाई गई जगह को दो बार दोहराया नहीं जाएगा क्योंकि उसी ऑब्जेक्ट की ओर इशारा किया जाता है।

Answer 3

यदि आपका कुंजी और मूल्यों हैं

Answer 4

यहां उपयोगकर्ता परिभाषित वर्ग का उपयोग कर another solution है।

और कोड ...

# search a dictionary for key or value 
# using named functions or a class 
# tested with Python25 by Ene Uran 01/19/2008 

def find_key(dic, val): 
    """return the key of dictionary dic given the value""" 
    return [k for k, v in symbol_dic.iteritems() if v == val][0] 

def find_value(dic, key): 
    """return the value of dictionary dic given the key""" 
    return dic[key] 

class Lookup(dict): 
    """ 
    a dictionary which can lookup value by key, or keys by value 
    """ 
    def __init__(self, items=[]): 
     """items can be a list of pair_lists or a dictionary""" 
     dict.__init__(self, items) 

    def get_key(self, value): 
     """find the key(s) as a list given a value""" 
     return [item[0] for item in self.items() if item[1] == value] 

    def get_value(self, key): 
     """find the value given a key""" 
     return self[key] 

Answer 5

कंप्यूटर प्रोग्रामिंग की कला में, वोक्यूम 3 Knuth में द्वितीयक कुंजी के लुकअप पर एक अनुभाग है। आपके प्रश्न के प्रयोजनों के लिए, मूल्य को द्वितीयक कुंजी माना जा सकता है।

पहला सुझाव यह है कि आपने जो किया है वह करना है: मूल्य के अनुसार चाबियों का एक कुशल अनुक्रमणिका बनाएं।

दूसरा सुझाव क्लस्टर डेटा का एक समग्र सूचकांक है, जहां शाखा नोड्स में मूल्य होते हैं और पत्तियों में बड़े डेटा (यदि कोई है तो) में महत्वपूर्ण डेटा और पॉइंटर्स होते हैं।

यदि डेटा ज्यामितीय है (जैसा कि आपका प्रतीत होता है) वहां पोस्ट ऑफिस पेड़ कहलाते हैं। यह प्रश्नों का उत्तर दे सकता है, एक्स को इंगित करने के लिए निकटतम वस्तु क्या है। कुछ उदाहरण यहां हैं: http://simsearch.yury.name/russir/01nncourse-hand.pdf इस तरह की क्वेरी के लिए एक और आसान विकल्प क्वाड्री और के-डी पेड़ है। http://en.wikipedia.org/wiki/Quadtree

एक और अंतिम विकल्प संयोजक हैशिंग है, जहां आप कुंजी और मूल्य को एक विशेष प्रकार के हैश में जोड़ते हैं जो आपको हैश पर कुशल लुकअप करने देता है, भले ही आपके पास दोनों मान न हों। मुझे ऑनलाइन एक अच्छा संयोजक हैश स्पष्टीकरण नहीं मिला, लेकिन यह पृष्ठ 573 पर वॉल्यूम 3 द्वितीय संस्करण में टीओओसीपी,

माना जाता है, इनमें से कुछ के लिए आपको अपना कोड लिखना पड़ सकता है। लेकिन अगर स्मृति या प्रदर्शन वास्तव में महत्वपूर्ण है, तो आप समय लेना चाहेंगे।

Answer 6

इसे "दो बार अंतरिक्ष" का उपयोग नहीं करना चाहिए। शब्दकोश केवल डेटा के संदर्भों को संग्रहीत करते हैं, डेटा नहीं। इसलिए, यदि आपके पास एक अरब बाइट्स लेने वाले लाखों तार हैं, तो प्रत्येक शब्दकोष में अतिरिक्त 10-20 मिलियन बाइट्स लगते हैं - कुल भंडारण का एक छोटा सा अंश। दो शब्दकोशों का उपयोग करना सही काम है।