शब्दकोश लुकअप (ओ (1)) बनाम लिंक जहां

Question

तेजी से क्या है और मुझे गति प्राप्त करने के लिए लिंक मानक का त्याग करना चाहिए (माना जाता है कि शब्दकोश लुकअप वास्तव में तेज़ है)? तो मुझे विस्तृत करते हैं:

मैं निम्नलिखित है:

List<Product> products = GetProductList(); 

मैं सीरियल नंबर एक, एक उत्पाद कुछ विशेषता के आधार पर खोज करने के लिए उदाहरण के लिए की जरूरत है, की है। मैं पहली बार एक शब्दकोश बना सकते हैं, और उसके बाद इस प्रकार पॉप्युलेट:

Dictionary<string, Product> dict = new Dictionary<string, Product>(); 
foreach(Product p in products) 
{ 
    dict.Add(p.serial, p); 
} 

जब यह एक उत्पाद को खोजने की, हे का लाभ लेने के समय आ गया है (1) शब्दकोश लुक-अप द्वारा की पेशकश की:

string some_serial = ...; 
try { Product p = dict[some_serial]; } catch(KeyNotFoundException) { } 

वैकल्पिक रूप से, LINQ का उपयोग:

Product p = products.Where(p => p.serial.Equals(some_serial)).FirstOrDefault(); 

Dict दृष्टिकोण के साथ दोष यह निश्चित रूप से है इस स्मृति में और अधिक स्थान, लिखने के लिए और अधिक कोड, कम सुरुचिपूर्ण, आदि (हालांकि इस का सबसे बहस का मुद्दा है) की आवश्यकता है। मान लें कि यह गैर-कारक है। क्या मुझे पहला दृष्टिकोण लेना चाहिए?

निष्कर्ष निकालने के लिए, मैं पुष्टि करना चाहता हूं कि उपरोक्त लिंक दृष्टिकोण की जटिलता वास्तव में ओ (एन) है और मुझे नहीं लगता कि यह उससे बेहतर कैसे हो सकता है।

Answer 1

मान लिया जाये कि आप वस्तुओं का एक गणन के साथ शुरू कर रहे हैं और केवल एक बार ऐसा कर रहे हैं ...

यह के रूप में एक Dictionary<TKey,TValue> को जोड़ने और फिर इसे देख वापस ऊपर करने के लिए विरोध Where विधि करने के लिए तेजी से हो जाएगा। कारण यह है कि शब्दकोश विधि ओ (1) नहीं है। इस परिदृश्य में आप शब्दकोश में आइटम जोड़ रहे हैं और फिर इसे देख रहे हैं। जोड़ना हिस्सा ओ (एन) है जो अतिरिक्त मेमोरी ओवरहेड के साथ Where विधि के रूप में महंगा है।

एक और मामूली बात यह जानना है कि Dictionary<TKey,TValue> वास्तव में ओ (1) नहीं है। यह इसके बजाय ओ (1) तक पहुंचता है लेकिन कुछ परिस्थितियों में कम प्रदर्शन में कमी कर सकता है (उदाहरण के लिए कई प्रकार की टक्कर कुंजी)।