इतने सारे परिचालनों के लिए ओके (एन) में सबसे खराब मामला क्यों है?

Question

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

http://www.google.com/search?sourceid=chrome&ie=UTF-8&q=python+complexity

Answer 1

Dict हे है (1) सबसे संचालन, संचालन कि इस तरह की यात्रा और कॉपी के रूप में सभी तत्वों, स्पर्श के अलावा के लिए (में:

इस के लिए मेरे स्रोत, वैसे, यह है जो मामला है, यह स्पष्ट रूप से ओ (एन)) है।

देखें: http://wiki.python.org/moin/TimeComplexity

यह हे (एन) सबसे खराब स्थिति है, क्योंकि आप हमेशा एक रोग उदाहरण है, जहां सभी कुंजियों ही हैश मान है ईजाद कर सकते हैं।

Answer 2

आकाशगंगा में सबसे अच्छा हैश फ़ंक्शन पर भी विचार करें। अभी भी एक मौका है कि आप एक दिन उन मूल्यों की सूची के साथ चल सकते हैं जिनके सर्वोत्तम हैश फ़ंक्शन मान समान होते हैं। यदि आप उन्हें एक निर्देश में डालते हैं, तो सिस्टम में रैखिक खोज करने के अलावा कोई विकल्प नहीं है।

एक संतुलित पेड़ का उपयोग करना ओ (लॉग एन) पर सबसे खराब स्थिति का समय रखेगा, लेकिन रखरखाव लागत बहुत अधिक है। आमतौर पर, हैश टेबल बहुत अच्छी तरह से प्रदर्शन करते हैं।

Answer 3

मुझे लगता है कि एक बेहतर कार्यान्वयन ओ (लॉग (एन)) के बजाय तालिका को वापस करने के लिए एक पेड़ का उपयोग करके विभिन्न परिचालनों के लिए होगा।

पेड़ और हैश तालिकाओं में बहुत अलग आवश्यकताएं और प्रदर्शन विशेषताएं हैं।

• पेड़ को आदेशित प्रकार की आवश्यकता होती है।
• पेड़ वस्तु को खोजने के लिए आदेश तुलना करने की आवश्यकता है। तारों की तरह कुछ वस्तुओं के लिए, यह कुछ महत्वपूर्ण अनुकूलन को रोकता है: आपको हमेशा एक स्ट्रिंग तुलना करने की आवश्यकता होती है, जो कि बेहद महंगा है। यह ओ (लॉग एन) का निरंतर कारक काफी ऊंचा बनाता है।
• हैश तालिकाओं को एक हैशबल प्रकार की आवश्यकता होती है, और आप समानता के लिए परीक्षण कर सकते हैं, लेकिन उन्हें आदेशित प्रकार की आवश्यकता नहीं है।
• समानता के लिए परीक्षण महत्वपूर्ण रूप से अनुकूलित किया जा सकता है। यदि दो तारों को प्रशिक्षित किया जाता है, तो आप परीक्षण कर सकते हैं कि क्या वे ओ (एन) के बराबर हैं, ताकि वे पूरे स्ट्रिंग की तुलना करके ओ (एन) के बजाय अपने पॉइंटर की तुलना कर सकें। यह भारी अनुकूलन है: प्रत्येक foo.bar लुकअप में जो foo.__dict__["bar"], "bar" पर अनुवादित हो जाता है एक आंतरिक स्ट्रिंग है।
• हैश टेबल सबसे खराब मामले में ओ (एन) हैं, लेकिन जांचें कि सबसे बुरे मामले में क्या होता है: एक बहुत बुरा हैश टेबल कार्यान्वयन (उदाहरण के लिए, आपके पास केवल एक बाल्टी है), या एक टूटा हुआ हैश फ़ंक्शन जो हमेशा एक ही देता है मूल्य। जब आपके पास उचित हैश फ़ंक्शन और उचित बाल्टीिंग एल्गोरिदम होता है, तो लुकअप बहुत सस्ते होते हैं - अक्सर लगातार समय तक पहुंचते हैं।

पेड़ महत्वपूर्ण लाभ की क्या ज़रूरत है:

• वे कम स्मृति आवश्यकताओं हो जाते हैं, क्योंकि वे बाल्टी preallocate की जरूरत नहीं है।छोटी से छोटी पेड़ 12 बाइट्स (नोड सूचक और दो बच्चे संकेत), जहां एक हैश तालिका 128 बाइट्स या उससे अधिक हो जाता है हो सकता है - sys.getsizeof ({}) अपने सिस्टम पर 136.
• वे आदेश दिया ट्रेवर्सल अनुमति देते हैं; इस पर पुनरावृति करने के लिए [सक्षम होने के लिए अत्यंत उपयोगी है क, ख) एक आदेश दिया सेट है, जो हैश तालिकाओं की अनुमति नहीं है में।

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

Answer 4

किसी अन्य पर एक कार्यान्वयन चुनने का बिंदु upper-bound के बारे में आवश्यक नहीं है, बल्कि अपेक्षाकृत amortized performance है। जबकि अलग एल्गोरिदम कर सकते हैं पतित मामलों है यह आम तौर पर "व्यवहार में बेहतर" एक साध्य कम ऊपरी बाध्य के साथ एक दृष्टिकोण का उपयोग करने से है। कुछ मामलों में, हालांकि, संरचनाओं को रोगजनक रूप से खराब इनपुट से बचाने के लिए डिज़ाइन किया जाना चाहिए।

इसके अलावा, कुछ भाषाएं/पुस्तकालय - पायथन के बारे में निश्चित नहीं हैं - वास्तव में अंतर्निहित कार्यान्वयन को बदलते हैं, जैसे कि आइटम की संख्या कम एन से अधिक हो जाती है। यह परिशोधित प्रदर्शन (कुछ मामलों में) को प्रभावित करता है, लेकिन जरूरी नहीं कि big O।

और अंत में: "यह निर्भर करता है"।

हैप्पी कोडिंग।

Answer 5

हैश फंक्शन और टक्कर संकल्प रणनीति है कि वास्तव में उपयोग किया जाता है के बारे में जानकारी के विश्वसनीय सूत्रों स्रोत फ़ाइल dictobject.c में टिप्पणियों और फ़ाइल के पूरे शामिल dictnotes.txt