पायथन जल्दी हैश म्यूटेबल ऑब्जेक्ट

Question

मेरे पास एक बाइटियर है जिसे मुझे एक शब्दकोश के लिए कुंजी के रूप में उपयोग करने की आवश्यकता है। आदर्श रूप से मैं इसे स्मृति की एक प्रतिलिपि के आकार के बिना ऐसा करना चाहता हूं। क्या इसे करने का कोई तरीका है? असल में,

b = some bytearray 
d[byte(b)] = x 

वहाँ यह करने के लिए किसी भी तेजी से रास्ता नहीं है? बाइट (बी) एक ओ (लेन (bytearray)) ऑपरेशन है जो अवांछनीय है।

Answer 1

कोई भी हैश एल्गोरिदम जो वास्तव में अपना काम सही ढंग से करता है ओ (लेन (बी)) समय का उपयोग करेगा। तो इसका उत्तर "ऐसा करने का कोई तेज़ तरीका है" नहीं है।

यदि आपकी वास्तविक चिंता मेमोरी उपयोग है, तो आप सिद्धांत रूप से, __hash__ विधि को बायटियर के उप-वर्ग में जोड़ सकते हैं। लेकिन यह एक बहुत बुरा विचार है। देखो क्या होता है:

>>> class HashableBytearray(bytearray): 
...  def __hash__(self): 
...   return hash(str(self)) 
... 
>>> h = HashableBytearray('abcd') 
>>> hash(h) 
-2835746963027601024 
>>> h[2] = 'z' 
>>> hash(h) 
-2835746963002600949 

तो एक ही वस्तु शब्दकोश में दो अलग-अलग धब्बे, जो नहीं होना है करने के लिए हैश सकता है। और यह बदतर हो जाता है:

>>> d = dict() 
>>> hb1 = HashableBytearray('abcd') 
>>> hb2 = HashableBytearray('abcd') 
>>> d[hb1] = 0 
>>> d[hb2] = 1 
>>> d 
{bytearray(b'abcd'): 1} 

ठीक है, अब तक, अच्छा है। मान बराबर हैं, इसलिए शब्दकोश में केवल एक ही वस्तु होनी चाहिए। सबकुछ अपेक्षित के रूप में काम कर रहा है।

देखें कि भले ही hb2 बिल्कुल नहीं बदला है, यह इस समय शब्दकोश में एक नया कुंजी-मान पेयर बनाया: अब जब हम hb1 बदलने देखते हैं क्या होता है?

हर बार जब मैंने d पर कुंजी पारित की, तो वह कुंजी 'abcd' के बराबर थी। लेकिन क्योंकि पहली कुंजी के मान को के बाद शब्दकोश में जोड़ा जा रहा है, इसलिए पाइथन यह नहीं बता सका कि नई कुंजी का मान वही था जब पुरानी कुंजी को जोड़ा गया था। अब शब्दकोश में दो कुंजी-मूल्य जोड़े हैं, जब केवल एक होना चाहिए।

यह केवल कई तरीकों में से एक है कि कुंजियों के रूप में परिवर्तनीय मानों का उपयोग करके अप्रत्याशित और बहुत गलत व्यवहार हो सकता है। बस bytearray को एक अपरिवर्तनीय प्रकार में परिवर्तित करें, या पहले स्थान पर अपरिवर्तनीय प्रकारों के साथ काम करें।

---

और जिज्ञासु के लिए: सुनिश्चित करें कि, buffer पहले हैश कैश, लेकिन यह बिल्कुल भी मदद नहीं करता है। है कि आप प्रयोग कर रहे हैं

>>> d 
{<read-only buffer for 0x1004a2300, size -1, offset 0 at 0x100499cb0>: 1, 
<read-only buffer for 0x1004a2420, size -1, offset 0 at 0x100499cf0>: 0, 
<read-only buffer for 0x1004a22d0, size -1, offset 0 at 0x100499c70>: 2} 

Answer 2

आप समय के बारे में चिंतित हैं, और कुंजी: केवल दो कुंजी मान रहे हैं, तो यह केवल दो dict प्रविष्टियों उत्पन्न करनी चाहिए:

>>> a, b, c = bytearray('abcd'), bytearray('abcd'), bytearray('abzd') 
>>> a_buf, b_buf, c_buf = buffer(a), buffer(b), buffer(c) 
>>> d = {b_buf:1, c_buf:2} 
>>> b[2] = 'z' 
>>> d[a_buf] = 0 

लेकिन यह तीन उत्पन्न करता है

b = some byte array 
d[id(b)] = x 

आप रहते हैं: हमेशा की तरह, आप अपने शब्दकोश में कुंजी के रूप में (स्मृति में स्थान) ने अपने id उपयोग कर सकते हैं एक ही वस्तु है स्मृति के बारे में चिंतित, आप अपने बाइट सरणी पर एक अच्छा क्रिप्टोग्राफ़िक हैश फ़ंक्शन का उपयोग कर सकते हैं, और शायद आपको टकराव कभी नहीं मिलेगा (उदाहरण के लिए, गिट, sha1 का उपयोग करता है, और somediscussionsinternet पर बाहर होने की संभावना है एक अनजान sha1 टकराव प्राप्त करें)।आपको लगता है कि छोटे से जोखिम के साथ ठीक कर रहे हैं, तो आप:

b = some byte array 
d[hashlib.sha1(b).hexdigest()] = x 

समय (हर बार जब आप हैश की गणना) में हे (एन) अपने बाइट सरणी के आकार में होने जा रहा है यही कारण है कि, लेकिन आप बाद में एक अलग बाइट सरणी पढ़ने में सक्षम हो सकता है, लेकिन बाइट्स के समान अनुक्रम का प्रतिनिधित्व करता है, जो एक ही शब्दकोश कुंजी के लिए हैश होगा।

और @ सेंडरल बिल्कुल सही है; आप किसी ऑब्जेक्ट का उपयोग नहीं करना चाहते हैं जो वास्तव में म्यूटेबल है, जब इसका उपयोग मूल्य के द्वारा किया जाता है (जैसा कि इसके अपरिवर्तनीय फ़ंक्शन के विपरीत है, जैसे id()) शब्दकोश के लिए कुंजी के रूप में। शब्दकोश कुंजी के रूप में उपयोग की जाने वाली ऑब्जेक्ट का हैश बदलना नहीं चाहिए; यह एक हैश फ़ंक्शन से डिक्शनरी ऑब्जेक्ट की अपेक्षाओं के आविष्कार का उल्लंघन करता है।

Answer 3

मुझे लगता है कि यह आपके इच्छित होने के करीब हो सकता है। यह अपेक्षाकृत तेज़ है और यह स्मृति को आकार के आकार की प्रतिलिपि नहीं बनाता है, हालांकि यह ओ (लेन (बाइटियर)) है - क्योंकि मैं इससे बचने के लिए किसी भी तरह से नहीं सोच सकता और हमेशा अद्वितीय मूल्य भी उत्पन्न करता हूं।

def byte(ba): 
    """ decode a bytearray as though it were a base 256 number """ 
    return reduce(lambda a,d: a*256 + d, ba, 0) 

ba = bytearray('this is a bytearray') 
d = {} 
d[byte(ba)] = 42 
ba[8] = 'X' # now 'this is X bytearray' 
d[byte(ba)] = 17 # accesses a separate entry in dict 
print d