क्या शब्दकोश में प्रविष्टियों की कोई सीमा है <>?

Question

मेरे पास लगभग 3000 विभिन्न फाइलें हैं जिन्हें मुझे व्यवस्थित करने की आवश्यकता है, और गेम के दौरान अलग-अलग समय पर पुनर्प्राप्त करें।

मैंने चर की अपनी संरचना बनाई है। मैं अपने आवेदन की शुरुआत में "शब्दकोश" बनाने के बारे में सोच रहा था, और गेम शुरू होने से पहले बस अपनी सभी फाइलें लोड कर रहा था।

मैं प्रदर्शन के बारे में सोच रहा हूं: क्या इस प्रविष्टि के साथ एक शब्दकोश मेरे आवेदन को धीमा कर देगा? क्या एक बड़ा शब्दकोश "TryGetValue" और "ContainsKey" धीमा चलाएगा?

सलाह के लिए धन्यवाद!

Answer 1

TryGetValue और ContainsKey उस आकार पर बहुत तेज होना चाहिए, जब तक कि कुंजी अच्छी तरह से वितरित हैश हो।

एक शब्दकोश में "बाल्टी" की एक सूचकांक संख्या है। जब यह किसी कुंजी द्वारा मूल्य जोड़ता है या देखता है तो यह GetHashCode() द्वारा लौटाए गए मान को ले जाएगा, यह बाल्टी की संख्या से कम होने के लिए फिर से नीचे है (आमतौर पर मॉड्यूलो की तरह कुछ सरल है, लेकिन कार्यान्वयन परिभाषित नहीं किया गया है) और प्रासंगिक बाल्टी में देखो।

बाल्टी में वर्तमान में शून्य या अधिक आइटम होंगे। शब्दकोश प्रत्येक आइटम की तुलना कुंजी के साथ करेगा .quals()।

सही बाल्टी खोजने का पहला बिट निरंतर समय ओ (1) में होने वाला है। बाल्टी में चाबियों के साथ कुंजी की तुलना करने का दूसरा बिट रैखिक समय ओ (एन) में होगा जहां एन केवल उस बाल्टी में वस्तुओं की संख्या से संबंधित है, पूरे संग्रह में नहीं।

आम तौर पर प्रत्येक बाल्टी में बहुत कम आइटम होना चाहिए (बाल्टी की संख्या इस मामले को रखने की कोशिश करने के लिए बढ़ेगी) ताकि ऑपरेशन अनिवार्य रूप से निरंतर समय हो।

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

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

यदि आपको लगता है कि शब्दकोश को एक्सेस करना धीमा है, तो आप इस पर ध्यान देना चाहते हैं और या तो GetHashCode() विधि को ठीक करना चाहते हैं या एक IqualityComparer (जो आपको GetHashCode() और बराबर के लिए बाहरी नियमों को परिभाषित करने देता है () शब्दकोश, हैशसेट, आदि के साथ उपयोग के लिए)।

सबसे अधिक संभावना है, 3000 कुछ भी नहीं है, यह ठीक रहेगा।

Answer 2

3000 प्रविष्टियां Dictionary<> के लिए पिडलिंग कर रही हैं। यह मंदी का स्रोत नहीं होगा।

दूसरी तरफ स्टार्टअप पर स्मृति में 3000 अलग-अलग फ़ाइलों को पढ़ना, धीमा हो जाएगा। फ़ाइलों को केवल उस समय मेमोरी में पढ़ने से बेहतर होगा, जब उन्हें आवश्यकता हो, लेकिन बाद में पहुंच के लिए उन्हें स्मृति में रखा जाए।

Answer 3

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

Answer 4

नहीं, यह नहीं होगा। यह स्मृति का उपभोग करेगा लेकिन TryGetValue और ContainKey बहुत तेज़ होना चाहिए क्योंकि एक शब्दकोश एक हैशटेबल है और कुंजी के तत्वों तक पहुंच निरंतर है और यह तत्वों की संख्या पर निर्भर नहीं होगी।

Answer 5

शब्दकोश कुंजी प्रकार के लिए हैशकोड एल्गोरिदम प्रदान करना Int32 स्पेस में अपेक्षाकृत समान रूप से हैशकोड फैलाता है, हैशकोड लुकअप शब्दकोश आकार से अप्रभावित है। अधिक जानकारी के लिए

http://en.wikipedia.org/wiki/Hashtable#Performance_analysis देखें।

Answer 6

आपकी बाधा शब्दकोश का प्रदर्शन नहीं बल्कि 3000 फाइलों के पढ़ने के बजाय होगी।

Answer 7

कंप्यूटर (और प्रदर्शन के साथ विशेष रूप से) के साथ सबसे चीजों के साथ के रूप में,

"यह (टीएम) निर्भर करता है" यह सब शब्दकोश के अंतर्गत प्रयोग पर निर्भर करता है।

यह एक बाइनरी पेड़ के रूप में किया जा सकता है, जिस स्थिति में ओ (लॉग 2 एन) होना चाहिए, जिसका मतलब है कि लुकअप का समय धीरे-धीरे बढ़ता है क्योंकि शब्दकोश का आकार बढ़ता है।

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

हालांकि, आपको ध्यान देने योग्य अंतर देखने से पहले शब्दकोश को परिमाण के कई क्रम से 3000 से अधिक बढ़ना होगा।

Answer 8

एक सीमा है, लेकिन 3000 इसके पास कहीं भी नहीं है। Dictionary<>Object.GetHashCode() का उपयोग अपनी चाबियों को व्यवस्थित करने के लिए करता है, जो int देता है।इसलिए आप टक्कर से पहले अधिकतम 2^32 (4,294,967,296) कुंजी स्टोर कर सकते हैं। हालांकि, जिस तरह से नेट के हैश कोड आमतौर पर गणना की जाती हैं, वैसे ही आप इस जादू संख्या के करीब पहुंचने पर कई टकराव होंगे।

अधिक कुंजी जोड़ना TryGetValue और ContainsKey धीमा नहीं होगा - वे O(1) संचालन हैं।