.NET शब्दकोश, प्रभावशाली तेज़ लेकिन यह कैसे काम करता है?

Question

ठीक है, मैं कबूल करूंगा कि मैंने यहां क्या हो रहा है, यह देखने के लिए परावर्तक को खोला नहीं है, लेकिन मुझे उम्मीद है कि कोई मुझे बता सकता है।

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

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

मैं जादू को समझने और उससे सीखने की कोशिश कर रहा हूं!

Answer 1

dictionary<T,T> नेट में एक डेटा संरचना एक हैश तालिका कहा जाता है:

हैश तालिका और नेट शब्दकोश में:

http://en.wikipedia.org/wiki/Hash_table

http://msdn.microsoft.com/en-us/library/4yh14awz.aspx

http://www.cs.auckland.ac.nz/~jmor159/PLDS210/hash_tables.html

पर बाइनरी खोज:

http://en.wikipedia.org/wiki/Binary_search

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

Answer 2

यह व्यावहारिक रूप से हर दूसरे शब्दकोश कार्यान्वयन की तरह hash का उपयोग करता है।

Answer 3

बुनियादी सिद्धांत है:

1. खाली सरणी सेट करें।
2. हैश कोड प्राप्त करें।
3. री-हैश हैश सरणी के आकार को फिट करने के लिए है (उदाहरण के लिए यदि सरणी आकार में 31 आइटम है, तो हम hash % 31 कर सकते हैं) और इसे इंडेक्स के रूप में उपयोग करें।

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

यहां स्पष्ट मुद्दा यह है कि यदि एक ही सूचकांक में दो आइटम हैं तो क्या करना है। एक दृष्टिकोण यह है कि आप कुंजी-मूल्य जोड़ी के बजाय सरणी में एक सूची या समान संग्रह करते हैं, दूसरा एक अलग इंडेक्स में "reprobing" है। दोनों दृष्टिकोणों के फायदे और नुकसान हैं, और माइक्रोसॉफ्ट एक सूची reprobing का उपयोग करें।

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

जाहिर है, हालांकि, एक बहुत गरीब हैश एल्गोरिथ्म इस नष्ट कर सकते हैं, तो आप इस अपने आप से वस्तुओं की एक शब्दकोश का निर्माण करके जहां hashCode विधि निम्नलिखित है प्रदर्शित कर सकते हैं:

public override int GetHashCode() 
{ 
    return 0; 
} 

यह वैध है, लेकिन भयानक है, और अपने पास-ओ (1) हे में व्यवहार (एन) (और बुरे के रूप में भी हे (एन) चला जाता है बदल जाता है।

अन्य विवरण और अनुकूलन के बहुत सारे हैं, लेकिन इसके बाद के संस्करण बुनियादी सिद्धांत है।

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

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

Answer 4

यह सवाल मुझे उत्सुक हो गया है, इसलिए मैं thats एक शब्दकोश देखने के अल्ट्रा तेजी से, अनुकूलित संस्करण लिखा 5x (पाँच बार) तेजी से डिफ़ॉल्ट नेट शब्दकोश कार्यान्वयन से।

मैंने ब्रेवटी के लिए त्रुटि जांच छोड़ दी है, हालांकि, यह जोड़ने के लिए तुच्छ होगा। मैंने इसे समझने में आसान बनाने के लिए इसे गैर-टेम्पलेट भी छोड़ा है।

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

/// <summary> 
/// Ultra fast dictionary, optimized for retrieval of keys consisting of 3-letter uppercase strings, where each string is 'A' to 'Z'. 
/// This is 5 times faster than the default Dictionary<> implementation, but not as flexible. 
/// ----start output from tester--- 
/// Ultra Fast Dictionary. 
/// Total time for 2,000,000,000 key retrievals: 19,892 milliseconds. 0.00994600 nanoseconds per retrieval. Sum -1958822656. 
/// Normal Dictionary. 
/// Total time for 2,000,000,000 key retrievals: 98,397 milliseconds. 0.04919850 nanoseconds per retrieval. Sum -1958822656. 
/// ----end output from tester--- 
/// </summary> 
public class DictionaryUltraFast 
{ 
    string[][][] dictionary; 

    /// <summary> 
    /// Add a string to the dictionary. 
    /// </summary> 
    public void Add(string key, string value) 
    { 
     key = key.ToUpper(); 
     if (dictionary == null) 
     { 
      dictionary = new string['Z' - 'A' + 1][][]; 
     } 
     if (dictionary[key[0] - 'A'] == null) 
     { 
      dictionary[key[0] - 'A'] = new string['Z' - 'A' + 1][]; 
     } 
     if (dictionary[key[0] - 'A'][key[1] - 'A'] == null) 
     { 
      dictionary[key[0] - 'A'][key[1] - 'A'] = new string['Z' - 'A' + 1]; 
     } 
     dictionary[key[0] - 'A'][key[1] - 'A'][key[2] - 'A'] = value; 
    } 

    public string Get(string key) 
    { 
     return dictionary[key[0] - 'A'][key[1] - 'A'][key[2] - 'A']; 
    } 
}