c# शनर कुंजी ओ(1) द्वारा शब्दकोश के तत्व का उपयोग क्यों कर रहा है भले ही हैश फ़ंक्शन ओ(1) न हो?




शब्दकोश हिन्दी से अंग्रेजी (7)

O(1) तत्काल मतलब नहीं है। O(1) डेटा के आकार के संबंध में निरंतर मतलब है। हैश फ़ंक्शन में निश्चित समय लगता है, लेकिन उस समय की मात्रा संग्रह के आकार के साथ स्केल नहीं होती है।

मैं देखता हूं कि आप अपने संग्रह को कुंजी से कैसे एक्सेस कर सकते हैं। हालांकि, हैश फ़ंक्शन में दृश्यों के पीछे बहुत सारे ऑपरेशन हैं, है ना?

मान लें कि आपके पास एक अच्छा हैश फ़ंक्शन है जो बहुत ही कुशल है, फिर भी यह कई संचालन कर सकता है।

क्या यह समझाया जा सकता है?


HashFunc के दृश्यों के पीछे बहुत सारे ऑपरेशन हैं

यह निश्चित रूप से सच है। हालांकि, इन परिचालनों की संख्या कुंजी के आकार पर निर्भर करती है, हैश तालिका के आकार पर नहीं जिसमें कुंजी डाली जाती है: हैश फ़ंक्शन की गणना करने के लिए संचालन की संख्या दस या दस के साथ तालिका में एक कुंजी के लिए समान होती है। दस हजार प्रविष्टियों के साथ।

यही कारण है कि हैश फ़ंक्शन का कॉल अक्सर ओ (1) माना जाता है। यह निश्चित-आकार कुंजी (अभिन्न मान और निश्चित-लंबाई तार) के लिए ठीक काम करता है। यह एक व्यावहारिक ऊपरी सीमा के साथ परिवर्तनीय आकार की चाबियों के लिए एक सभ्य अनुमान प्रदान करता है।

आम तौर पर, हालांकि, हैश तालिका का एक्सेस समय ओ (के) है, जहां हैश कुंजी के आकार पर ऊपरी सीमा है।


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

एक हैश-मैप में O(n) की सबसे बुरी स्थिति रनटाइम जटिलता हो सकती है यदि आपके पास बहुत सारे महत्वपूर्ण टकराव हैं या बहुत खराब हैश फ़ंक्शन है, क्योंकि इस मामले में यह पूरे सरणी के रैखिक स्कैन में घट जाता है जिसमें डेटा होता है ।

इसके अलावा, O(1) तात्पर्य मतलब नहीं है, इसका मतलब है कि इसकी निरंतर राशि है। तो एक शब्दकोश के लिए सही कार्यान्वयन का चयन करना संग्रह में तत्वों की संख्या पर निर्भर करता है, क्योंकि फ़ंक्शन के लिए बहुत अधिक निरंतर लागत होने पर केवल कुछ प्रविष्टियां होती हैं।

यही कारण है कि विभिन्न परिदृश्यों के लिए शब्दकोश / मानचित्र अलग-अलग लागू किए जाते हैं। जावा के लिए कई अलग-अलग कार्यान्वयन होते हैं, सी ++ लाल / काले पेड़ आदि का उपयोग करता है। आपने उन्हें डेटा की संख्या और उनके सर्वोत्तम / औसत / सबसे खराब-मामले रनटाइम-दक्षता के आधार पर चुना है।


एक बार जब आप इस तथ्य की अनुमति देते हैं कि बड़े और बड़े शब्दकोश अधिक मेमोरी लेते हैं, तो कैश पदानुक्रम को आगे बढ़ाते हैं और अंततः डिस्क पर स्वैप स्थान धीमा करने के लिए बाहर निकलना मुश्किल होता है, यह सच है कि यह वास्तव में ओ (1) है। शब्दकोश का प्रदर्शन धीमा हो जाएगा क्योंकि यह बड़ा हो जाता है, शायद ओ (लॉग एन) समय जटिलता दे रहा है। मेरा विश्वास मत करो? 1, 100, 1000, 10000 के साथ अपने आप को आजमाएं, 100 बिलियन कहने के लिए, और तत्व को देखने के लिए अभ्यास में कितना समय लगता है।

हालांकि यदि आप सरलीकृत धारणा करते हैं कि आपके सिस्टम में सभी मेमोरी यादृच्छिक एक्सेस मेमोरी है, और निरंतर समय में पहुंचा जा सकता है, तो आप दावा कर सकते हैं कि शब्दकोश ओ (1) है। यह धारणा आम है, भले ही यह डिस्क स्वैप स्पेस वाली किसी भी मशीन के लिए वास्तव में सच नहीं है, और फिर भी सीपीयू कैश के विभिन्न स्तरों को देखते हुए किसी भी मामले में काफी बहस योग्य है।


सैद्धांतिक रूप से यह अभी भी ओ (एन) है, क्योंकि सबसे खराब स्थिति में आपका सभी डेटा समान हैश होने के साथ समाप्त हो सकता है और एक साथ बंडल किया जा सकता है, इस मामले में आपको रैखिक रूप से इसे सभी के माध्यम से जाना होगा।


इसका मतलब यह है कि इससे कोई फर्क नहीं पड़ता कि आपका संग्रह कितना आकार हो सकता है, फिर भी इसके किसी भी सदस्य को पुनः प्राप्त करने के लिए लगभग उतना ही समय लगेगा।

तो दूसरे शब्दों में 5 सदस्यों के साथ डिक्शनरी का कहना है कि उनमें से एक को एक्सेस करने के लिए कैड को लगभग 0.002 एमएस लेना चाहिए, साथ ही 25 सदस्यों के शब्दकोश को कुछ समान लेना चाहिए। बिग ओ का मतलब वास्तविक बयान या निष्पादित कार्यों के बजाय संग्रह आकार पर एल्गोरिदमिक जटिलता है


दस्तावेज़ों से:

इसकी कुंजी का उपयोग कर एक मूल्य प्राप्त करना बहुत तेज़ है, ओ (1) के करीब, क्योंकि टी: System.Collections.Generic.Dictionary`2 कक्षा को हैश तालिका के रूप में लागू किया गया है।

तो यह ओ (1) हो सकता है लेकिन धीमा हो सकता है। यहां आप हैशटेबल प्रदर्शन के बारे में एक और धागा पा सकते हैं: हैश टेबल - यह सरणी से तेज क्यों है?







big-o