गिनती टकराव

Question

मेरी पहली बार यहाँ पोस्टिंग, तो मैं रास्ते से सही तरह में मेरे सवाल का,

पूछा है उम्मीद एक अजगर शब्दकोश में एक तत्व जोड़ने के बाद, यह करने के लिए अजगर पाने के लिए संभव है आपको बताते हैं कि उस तत्व को जोड़ने से टकराव हुआ? (और तत्व को रखने के लिए जगह खोजने से पहले टक्कर रिज़ॉल्यूशन रणनीति की कितनी जगहों की जांच की गई?)

मेरी समस्या यह है कि: मैं एक बड़ी परियोजना के हिस्से के रूप में शब्दकोश का उपयोग कर रहा हूं, और व्यापक प्रोफाइलिंग के बाद, मैंने पाया है कि सबसे धीमा कोड का हिस्सा शब्दकोशों का उपयोग करके लागू एक स्पैस दूरी मैट्रिक्स से निपट रहा है।

मैं जिन चाबियों का उपयोग कर रहा हूं वे पाइथन ऑब्जेक्ट्स की आईडी हैं, जो अद्वितीय पूर्णांक हैं, इसलिए मुझे पता है कि वे सभी हैंश अलग-अलग मानों के लिए हैं। लेकिन उन्हें एक शब्दकोश में डालने से सिद्धांत में टकराव हो सकता है। मुझे विश्वास नहीं है कि शब्दकोश टकराव ऐसी चीज है जो मेरे कार्यक्रम को धीमा कर रही है, लेकिन मैं उन्हें अपनी पूछताछ से खत्म करना चाहता हूं।

तो, उदाहरण के लिए, यह देखते हुए निम्नलिखित शब्दकोश:

d = {} 
for i in xrange(15000): 
    d[random.randint(15000000, 18000000)] = 0 

आप अजगर कितने टकराव हुआ यह बनाते समय आपको बताने के लिए मिल सकता है?

मेरा वास्तविक कोड एप्लिकेशन के साथ उलझ गया है, लेकिन उपर्युक्त कोड एक शब्दकोश बनाता है जो मैं उपयोग कर रहा हूं।

दोहराने के लिए: मुझे नहीं लगता कि टकराव मेरे कोड को धीमा कर रहा है, मैं बस यह दिखाकर संभावना को खत्म करना चाहता हूं कि मेरे शब्दकोशों में कई टकराव नहीं हैं।

आपकी मदद के लिए धन्यवाद।

संपादित करें:

n = 1500 
global collision_count 
collision_count = 0 

class Foo(): 

    def __eq__(self, other): 
     global collision_count 
     collision_count += 1 
     return id(self) == id(other) 

    def __hash__(self): 
     #return id(self) # @John Machin: yes, I know! 
     return 1 

objects = [Foo() for i in xrange(n)] 

d = {} 
for o in objects: 
    d[o] = 1 

print collision_count 

ध्यान दें कि जब आप एक वर्ग पर __eq__ परिभाषित करते हैं, अजगर आप एक TypeError: unhashable instance अगर आप भी एक __hash__ समारोह परिभाषित नहीं करते देता है: कुछ कोड @Winston Ewert के समाधान को लागू करने।

यह अपेक्षा करता है कि यह काफी नहीं चलता है। यदि आपके पास __hash__ फ़ंक्शन return 1 है, तो आपको उम्मीद के अनुसार टकराव का भार मिलता है (1125560 मेरे सिस्टम पर एन = 1500 के लिए टकराव)। लेकिन return id(self) के साथ, 0 टकराव हैं।

कोई भी जानता है कि यह 0 टकराव क्यों कह रहा है?

संपादित करें: मैंने इसे समझ लिया होगा।

क्या ऐसा इसलिए है क्योंकि __eq__ केवल तभी कहा जाता है जब __hash__ दो ऑब्जेक्ट्स के मान समान हैं, न कि उनके "क्रंच किए गए संस्करण" (जैसा कि जॉन जॉनिन ने इसे रखा है)?

Answer 1

लघु जवाब:

आप dict कुंजी के रूप में यादृच्छिक पूर्णांकों का उपयोग करके dict कुंजी के रूप में वस्तु आईडी का उपयोग कर अनुकरण नहीं कर सकते। उनके पास विभिन्न हैश फ़ंक्शन हैं।

टक्कर होती है। "अनोखी चीज़ों का मतलब है कि कोई टकराव नहीं है" "चीज़" के कई मूल्यों के लिए गलत है।

आपको टक्कर के बारे में चिंता नहीं करना चाहिए।

लांग जवाब:

कुछ स्पष्टीकरण, reading the source code से ली गई:

एक dict 2 ** मैं प्रविष्टियों, जहां मैं एक पूर्णांक है की एक तालिका के रूप में कार्यान्वित किया जाता है।

डिक्ट्स 2/3 से अधिक पूर्ण नहीं हैं। नतीजतन 15000 चाबी के लिए, मैं 15 और 2 होना चाहिए ** मैं 32768.

है जब ओ एक वर्ग के एक मनमाना आवृत्ति __hash__(), परिभाषित नहीं करता है यह सच नहीं है यह है कि हैश (ओ) == आईडी (ओ)। चूंकि पते में निम्न-आदेश 3 या 4 बिट्स में शून्य होने की संभावना है, इसलिए हैश का निर्माण 4 बिट्स द्वारा पते को घुमाकर बनाया गया है; देख source file Objects/object.c, समारोह _Py_HashPointer

क्योंकि आकार 2 की एक तालिका का उपयोग करने की यह एक समस्या हो सकता है अगर वहाँ कम आदेश बिट में शून्य की बहुत थे, ** मैं (जैसे 32768), हैश मान (अक्सर ज्यादा उस से बड़ा) फिट करने के लिए crunched किया जाना चाहिए, और यह हैश मूल्य के कम आदेश i (उदाहरण के लिए 15) बिट्स ले कर बहुत आसानी से और जल्दी किया जाता है।

परिणामस्वरूप टक्कर अनिवार्य हैं।

हालांकि यह आतंक के कारण नहीं है। हैश वैल्यू के शेष बिट्स की गणना की जाती है जहां अगली जांच होगी। तीसरी आदि जांच की संभावना की आवश्यकता बहुत छोटी होनी चाहिए, खासतौर पर क्योंकि यह नियम कभी भी 2/3 से अधिक नहीं होता है। पहली और बाद की जांच के लिए स्लॉट की गणना करने की सस्ती लागत से कई जांचों की लागत कम हो जाती है।

नीचे दिया गया कोड उपरोक्त चर्चा में से अधिकांश को चित्रित करने वाला एक सरल प्रयोग है।यह अपने अधिकतम आकार तक पहुंचने के बाद dict की यादृच्छिक पहुंच मानता है। पायथन 2.7.1 के साथ, यह 15000 ऑब्जेक्ट्स (13.3%) के लिए 2000 टकराव दिखाता है।

किसी भी मामले में नीचे की रेखा यह है कि आपको वास्तव में कहीं और अपना ध्यान बदलना चाहिए। टकराव आपकी समस्या नहीं है जब तक कि आप अपनी वस्तुओं के लिए स्मृति प्राप्त करने के कुछ असामान्य तरीके से हासिल नहीं कर लेते हैं। आपको देखना चाहिए कि आप डिक्ट्स का उपयोग कैसे कर रहे हैं उदा। k in d का उपयोग करें या d.has_key(k) पर कोशिश करें/छोड़कर। d[x][y] के रूप में उपयोग किए गए दो स्तरों के बजाय d[(x, y)] के रूप में उपयोग किए गए एक निर्देश पर विचार करें। अगर आपको इसके साथ मदद की ज़रूरत है, तो एक अलग सवाल पूछें।

अद्यतन अजगर 2.6 पर परीक्षण के बाद:

पते के घूर्णन अजगर 2.7 जब तक पेश नहीं किया गया था; व्यापक चर्चा और बेंचमार्क के लिए this bug report देखें। बुनियादी निष्कर्ष आईएमएचओ अभी भी वैध हैं, और "यदि आप कर सकते हैं तो अपडेट करें" द्वारा बढ़ाया जा सकता है।

>>> n = 15000 
>>> i = 0 
>>> while 2 ** i/1.5 < n: 
... i += 1 
... 
>>> print i, 2 ** i, int(2 ** i/1.5) 
15 32768 21845 
>>> probe_mask = 2 ** i - 1 
>>> print hex(probe_mask) 
0x7fff 
>>> class Foo(object): 
...  pass 
... 
>>> olist = [Foo() for j in xrange(n)] 
>>> hashes = [hash(o) for o in olist] 
>>> print len(set(hashes)) 
15000 
>>> probes = [h & probe_mask for h in hashes] 
>>> print len(set(probes)) 
12997 
>>> 

Answer 2

अपनी चाबी गारंटी अद्वितीय पूर्णांक है, और अजगर कुंजी पर hash() का उपयोग करता है के बाद से कर रहे हैं, तो आप किसी भी टकराव के लिए नहीं की गारंटी दी जानी चाहिए।

Answer 3

यह विचार वास्तव में काम नहीं करता है, प्रश्न में चर्चा देखें।

पायथन के सी कार्यान्वयन पर एक त्वरित रूप से पता चलता है कि टकराव को हल करने के लिए कोड टकराव की संख्या की गणना या संग्रह नहीं करता है।

हालांकि, यह जांचने के लिए कि क्या वे मेल खाते हैं, यह PyObject_RichCompareBool पर चाबियाँ लगाएंगे। इसका मतलब है कि कुंजी पर __eq__ प्रत्येक टक्कर के लिए बुलाया जाएगा।

तो:

वस्तुओं कि __eq__ को परिभाषित करने और एक काउंटर को बढ़ा देते हैं जब यह कहा जाता है के साथ अपनी चाबी बदलें। तुलना के लिए पाइथन में कूदने में शामिल ओवरहेड की वजह से यह धीमा हो जाएगा। हालांकि, यह आपको एक विचार देना चाहिए कि कितने टकराव हो रहे हैं।

सुनिश्चित करें कि आप कुंजी के रूप में विभिन्न ऑब्जेक्ट्स का उपयोग करते हैं, अन्यथा पाइथन शॉर्टकट लेगा क्योंकि ऑब्जेक्ट हमेशा अपने बराबर होता है। साथ ही, सुनिश्चित करें कि ऑब्जेक्ट्स मूल कुंजी के समान मान के हैंश है।