क्या .NET संग्रह सबसे तेज़ खोज

119

प्रदान करता है मेरे पास 60k आइटम हैं जिन्हें 20k लुकअप सूची के विरुद्ध चेक करने की आवश्यकता है। क्या कोई संग्रह वस्तु है (जैसे List, HashTable) जो एक असाधारण तेज़ Contains() विधि प्रदान करता है? या मुझे अपना खुद लिखना होगा? अन्य शब्दों में, डिफ़ॉल्ट Contains() विधि केवल प्रत्येक आइटम को स्कैन करें या यह बेहतर खोज एल्गोरिदम का उपयोग करता है।क्या .NET संग्रह सबसे तेज़ खोज

foreach (Record item in LargeCollection) 
{ 
    if (LookupCollection.Contains(item.Key)) 
    { 
     // Do something 
    } 
}

नोट। लुकअप सूची पहले से ही क्रमबद्ध है।

स्रोत

2009-06-17 Anonymous

सूची के लिए सूची वस्तुओं की सूची के लिए काम नहीं करती है क्योंकि यह संदर्भों की तुलना कर रही है। – Fiur

क्रमबद्ध डेटा? बाइनरी खोज - @ मार्क का जवाब देखें। –

हैशटेबल मेरे अनुभव में 2 एम आइटम तक कुछ भी धड़कता है –

111

सबसे सामान्य मामले में, System.Collections.Generic.HashSet पर अपने डिफ़ॉल्ट "कंटेनर" डेटा संरचना के रूप में विचार करें, क्योंकि Contains का मूल्यांकन करने में लगातार समय लगता है।

"सबसे तेज़ खोज योग्य संग्रह क्या है" का वास्तविक उत्तर आपके विशिष्ट डेटा आकार, ऑर्डर-नेस, लागत-की-हैशिंग और खोज आवृत्ति पर निर्भर करता है।

स्रोत

2009-06-17 19:38:51 Jimmy

+23

नोट: हैशकोड फ़ंक्शन को ओवरराइड करना न भूलें। अतिरिक्त प्रदर्शन के लिए, अपने कंस्ट्रक्टर में अपने हैशकोड को पूर्वनिर्धारित करें। – Brian

@ ब्रायन: अच्छा बिंदु। मैं मान रहा था (आधारहीन) रिकॉर्ड। के कुछ प्रकार का एक अंतर्निहित प्रकार था। – Jimmy

रिकॉर्ड.केई सिर्फ एक लंबा –

आप आदेश देने की जरूरत नहीं है, कोशिश HashSet<Record>

आप एक List<Record> का उपयोग करें और BinarySearch फोन करते हैं (3.5 नेट के लिए नया)।

स्रोत

2009-06-17 19:40:04 SLaks

या, .NET> = 4 में, [SortedSet] (http://msdn.microsoft.com/en-us/library/dd412070.aspx का उपयोग करें)) – StriplingWarrior

क्या आपने List.BinarySearch(item) पर विचार किया है?

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

स्रोत

2009-06-17 19:44:08 Mark

आप सही हैं, एक हैश एक कुंजी के रूप में mutable वस्तुओं का उपयोग करते समय कुछ अवांछित समस्याएं ला सकता है। – jmservera

यदि आप प्रदर्शन के हर अंतिम बिट को स्कोक करने के बारे में चिंतित नहीं हैं तो हैशसेट या बाइनरी खोज का उपयोग करने के सुझाव ठोस हैं। आपके डेटासेट बस इतने बड़े नहीं हैं कि यह 99% समय की समस्या होगी।

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

स्रोत

2009-06-17 19:48:22

यदि आपके आइटम को सॉर्ट करना संभव है तो ऐसा करने के लिए एक तेज़ तरीका है, फिर हैशटेबल या बी-पेड़ में मुख्य लुकअप करना। यद्यपि यदि आप आइटम क्रमबद्ध नहीं हैं, तो आप वास्तव में उन्हें बी-पेड़ में नहीं डाल सकते हैं।

वैसे भी, यदि दोनों सूचियों को सॉर्ट करने योग्य सॉर्ट करें तो यह केवल लुकअप सूची को चलने का मामला है।

Walk lookup list 
    While items in check list <= lookup list item 
    if check list item = lookup list item do something 
    Move to next lookup list item

स्रोत

2009-06-17 19:51:28 Qberticus

हां, तो सच है। यदि आपके पास दो क्रमबद्ध सूचियां हैं तो आपको केवल एक बार पार करने की आवश्यकता है। अधिक कुशल एल्गोरिदम के लिए – denver

आप नेट 3.5 का उपयोग कर रहे हैं, तो आप का उपयोग कर क्लीनर कोड बना सकते हैं:

foreach (Record item in LookupCollection.Intersect(LargeCollection)) 
{ 
    //dostuff 
}

मैं यहाँ नेट 3.5 की जरूरत नहीं है और इसलिए इस अपरीक्षित है। यह एक विस्तार विधि पर निर्भर करता है। यह नहीं कि LookupCollection.Intersect(LargeCollection) शायद LargeCollection.Intersect(LookupCollection) जैसा नहीं है ... बाद वाला शायद बहुत धीमा है।

इसमें यह माना जाता LookupCollection एक HashSet

स्रोत

2009-06-17 19:57:38 Brian

क्रमबद्ध क्रम में रखें दोनों सूचियों x और y है।

यदि x = y, तो अपनी क्रिया करें, यदि x < y, अग्रिम x, यदि y < x, अग्रिम y जब तक कोई सूची खाली न हो।

इस चौराहे के रन टाइम मिनट (आकार (x), आकार (y)) के लिए आनुपातिक है

नहीं एक .Contains() पाश चलाते हैं, इस x * y के लिए आनुपातिक है जो बहुत बुरा है।

स्रोत

2009-06-17 20:10:50 clemahieu

+1। भले ही सूचियों को वर्तमान में छोड़ा गया हो, फिर भी उन्हें पहले क्रमबद्ध करने के लिए और फिर यह एल्गोरिदम चलाने के लिए अधिक कुशल होगा। –

हालांकि रनटाइम सबसे खराब केस परिदृश्य में अधिकतम (आकार (एक्स), आकार (वाई)) के आनुपातिक नहीं होगा? उदाहरण: int [] x = {99,100}; int [] y = {0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}; –

नहीं क्योंकि एक बार जब आप छोटे सेट को पूरा कर लेते हैं, तो आप शेष तत्वों को बड़े सेट से जोड़ सकते हैं क्योंकि वे पहले ही सॉर्ट किए गए हैं। मुझे लगता है कि यह प्रक्रिया मर्ज सॉर्ट के समान है। –

आपको this blog पढ़ना चाहिए कि गति ने एकल और बहु-थ्रेडेड तकनीकों का उपयोग करके प्रत्येक के लिए कई अलग-अलग प्रकार के संग्रह और विधियों का परीक्षण किया।

परिणामों के मुताबिक, एक सूची और सॉर्टेडलिस्ट पर एक बाइनरीशर्च शीर्ष कलाकारों को "मूल्य" के रूप में कुछ देखते समय लगातार गर्दन में गर्दन चला रहा था।

"कुंजी" के लिए अनुमति देने वाले संग्रह का उपयोग करते समय, डिक्शनरी, कंसूरेंट डिक्शनरी, हैशसेट और हैशटेबल्स ने सबसे अच्छा प्रदर्शन किया।

स्रोत

2014-11-27 07:23:35

क्या .NET संग्रह सबसे तेज़ खोज

उत्तर

संबंधित मुद्दे