मैं सूची देख रहा हूं और मुझे कुछ ओवरलोड के साथ एक बाइनरीशर्च विधि दिखाई दे रही है, और मैं इस बात की सोच में मदद नहीं कर सकता कि क्या सूची में ऐसा तरीका है?एक सूची <T> क्यों है? चिकित्सा खोज (...)?
सूची को सॉर्ट किए जाने तक मैं बाइनरी खोज क्यों करना चाहूंगा? और यदि सूची को सॉर्ट नहीं किया गया था, तो विधि को कॉल करना केवल CPU समय का अपशिष्ट होगा। सूची पर उस विधि को रखने का क्या मतलब है?
सॉर्टिंग और खोज सूचियों पर दो बहुत ही सामान्य संचालन हैं। एक नियमित सूची में बाइनरी खोज की पेशकश न करके डेवलपर के विकल्पों को सीमित करना असभ्य होगा।
लाइब्रेरी डिज़ाइन समझौता की आवश्यकता है - .NET डिजाइनरों ने दोनों सरणी पर बाइनरी सर्च फ़ंक्शन को सी # में एक सूचियां प्रदान करने का विकल्प चुना क्योंकि वे शायद महसूस करते थे (जैसा कि मैं करता हूं) कि ये उपयोगी और सामान्य संचालन हैं, और प्रोग्रामर जो चुनते हैं उन्हें बुलाए जाने से पहले उनकी पूर्व शर्त (अर्थात् सूची का आदेश दिया गया है) को समझें।
Sort() ओवरलोड में से किसी एक का उपयोग करके List<T> को सॉर्ट करना काफी आसान है। यदि आपको लगता है कि आपको एक आविष्कार की आवश्यकता है जो गोरंटियों को सॉर्ट कर रहा है, तो आप हमेशा SortedList<TKey,TValue> या SortedSet<T> का उपयोग कर सकते हैं।
हां लेकिन सूची में सॉर्ट() विधि भी है ताकि आप इसे बाइनरीशर्च से पहले कॉल कर सकें।
मैं मानता हूं कि यह एक अनर्जित सूची पर बाइनरीशर्च को कॉल करने के लिए पूरी तरह से गूंगा है, लेकिन अगर आप जानते हैं कि आपकी बड़ी सूची सॉर्ट की गई है तो यह सही है।
मैंने यह जांचते समय इसका उपयोग किया है कि किसी स्ट्रीम से आइटम 100,000 आइटम या उससे अधिक की स्थिर सूची में मौजूद हैं या नहीं।
सूची खोजना बाइनरी सूची की तुलना में तीव्रता के ऑर्डर है। ढूँढें, डेटाबेस की तुलना में तीव्रता के कई आदेश कितने तेज़ हैं।
मुझे समझ में आता है, और मुझे वहां खुशी है (यह नहीं कि यह लागू करने के लिए रॉकेट विज्ञान होगा यदि यह नहीं था)।
अन्य ने इंगित किया है कि BinarySearch क्रमबद्ध List<T> पर काफी उपयोगी है। यह वास्तव में List<T> पर नहीं है, हालांकि, सी ++ एसटीएल अनुभव वाला कोई भी व्यक्ति तुरंत पहचान लेगा।
हाल ही में सी # भाषा के विकास के साथ, यह एक क्रमबद्ध सूची (उदा। ISortedList<T> : IList<T>) की धारणा को परिभाषित करने और BinarySearch (et। Al।) को उस इंटरफ़ेस के विस्तार विधियों के रूप में परिभाषित करने के लिए अधिक समझ में आता है। यह एक क्लीनर, अधिक ऑर्थोगोनल प्रकार का डिज़ाइन है।
मैंने Nito.Linq लाइब्रेरी के हिस्से के रूप में बस ऐसा करना शुरू कर दिया है। मैं उम्मीद करता हूं कि पहली स्थिर रिलीज कुछ महीनों में होगी।
मुझे यकीन नहीं है कि आप इसे C++ STL से तुलना करते समय क्या प्राप्त कर रहे हैं। std :: list <> एक लिंक-सूची है, लेकिन सूची <> वास्तव में एक सरणी के रूप में लागू की गई है और std :: vector <> के करीब है। –
बिंदु यह है कि सी ++ एसटीएल समर्थित * ऑर्थोगोनलिटी *। 'वेक्टर' में 'binary_search' नामक विधि नहीं थी; बल्कि, 'binary_search' को किसी भी यादृच्छिक-पहुंच इटरेटर पर लागू किया जा सकता है, जैसे 'वेक्टर' द्वारा प्रदान किए गए। सी # बीसीएल को एक ही अवधारणा लागू करें: 'सूची
मेरे उत्तर (और लाइब्रेरी) में, मैं इससे आगे एक कदम आगे जाता हूं और 'ISortedList
BinarySearch केवल एक List<T> कि सॉर्ट हो जाता है पर समझ में आता है, IList<T>.Add केवल IsReadOnly = false के साथ एक IList<T> के लिए समझ में आता है वैसे ही जैसे। यह गन्दा है, लेकिन यह केवल कुछ करने के लिए है: कभी-कभी कार्यक्षमता एक्स मानदंड पर निर्भर करता है वाई। तथ्य यह है कि वाई हमेशा सत्य नहीं होता है, एक्स को बेकार नहीं बनाता है।
अब, मेरी राय में, यह निराशा होती है कि नेट किसी भीIList<T> कार्यान्वयन के लिए सामान्यSort और BinarySearch विधियां नहीं है (उदाहरण के लिए, एक्सटेंशन विधियों के रूप में)। अगर ऐसा होता है, तो हम आसानी से और आसानी से सॉर्ट कर सकते हैं किसी भी गैर-पढ़ने-संग्रह संग्रह में यादृच्छिक पहुंच प्रदान करने वाले आइटमों की खोज कर सकते हैं।
फिर फिर, आप हमेशा अपना स्वयं का (या copy someone else's) लिख सकते हैं।
मैं अन्य सही उत्तरों के अलावा नोट करता हूं कि द्विआधारी खोज सही ढंग से लिखने के लिए आश्चर्यजनक रूप से कठिन है। बहुत से कोने के मामले और कुछ मुश्किल पूर्णांक अंकगणित हैं। चूंकि बाइनरी खोज स्पष्ट रूप से क्रमबद्ध सूचियों पर एक आम ऑपरेशन है, इसलिए बीसीएल टीम ने दुनिया को बाइनरी खोज एल्गोरिदम सही ढंग से लिखकर लिखकर सेवा प्रदान की है ताकि ग्राहकों को अपनी बाइनरी खोज एल्गोरिदम लिखने के लिए प्रोत्साहित किया जा सके; उन ग्राहक-लेखक एल्गोरिदम की एक महत्वपूर्ण संख्या गलत होगी।
यहां तक कि महान पुस्तकालय डिजाइनरों को यह भी गलत लगता है: http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html –
धन्यवाद, एरिक। –
@ रॉन वॉरहोलिक: तथ्य यह है कि एक विशेष कार्यान्वयन लगभग दो बिलियन तत्वों की सूचियों तक सीमित है, आमतौर पर बग के बजाय सीमा के रूप में वर्णित किया जाएगा। मुझे लगता है कि अगर किसी के पास दो बिलियन से अधिक तत्वों के साथ एक मोनोलिथिक डेटा संरचना हो सकती है, तो इसका मतलब यह नहीं है कि किसी को चाहिए। – supercat
खोज और सॉर्टिंग एल्गोरिदमिक प्राइमेटिव हैं। मानक पुस्तकालय के लिए तेजी से विश्वसनीय कार्यान्वयन के लिए यह सहायक है। अन्यथा, डेवलपर्स पहिया को फिर से शुरू करने में समय बर्बाद करते हैं।
हालांकि, .NET Framework के मामले में, यह दुर्भाग्यपूर्ण है कि एल्गोरिदम के विशिष्ट विकल्प उन्हें कम से कम उपयोगी बनाने के लिए होते हैं। कुछ मामलों में, उनके व्यवहार परिभाषित किया गया है नहीं: सूची में एक ही मूल्य के साथ एक से अधिक तत्व शामिल
List<T>.BinarySearch हैं, तो विधि घटनाओं का केवल एक ही देता है, और यह घटनाओं में से किसी एक वापस कर सकती है, जरूरी नहीं कि पहले एक।
List<T> यह कार्यान्वयन एक अस्थिर प्रकार का प्रदर्शन करता है; यानी, यदि दो तत्व बराबर हैं, उनका ऑर्डर संरक्षित नहीं किया जा सकता है। इसके विपरीत, एक स्थिर प्रकार बराबर तत्वों के क्रम को संरक्षित करता है।
यह शर्म की बात है, क्योंकि निर्धारक एल्गोरिदम हैं जो कि तेज़ी से हैं, और ये ब्लॉक बनाने के रूप में अधिक उपयोगी होंगे। यह ध्यान देने योग्य है कि पाइथन, रूबी और गो में बाइनरी खोज एल्गोरिदम सभी मिलान करने वाले तत्व को ढूंढते हैं।
अंत में किसी ने यह कहा। मैं पूरी तरह से आपके साथ पहली बार हूँ। मेरा मानना है कि 'सूची
बिंदु 2 पर, मैं दो दिमाग में हूं। ** कई बार ** मुझे लगता है कि यह ठीक था, कारण के लिए: सूची
शायद एक और बिंदु यह है कि एक सरणी समान रूप से अपरिवर्तित हो सकती है। तो सिद्धांत रूप में, एक सरणी पर एक बाइनरी खोज होने पर भी अमान्य हो सकता है।
हालांकि, उच्च स्तर की भाषा की सभी सुविधाओं के साथ, उन्हें डेटा के कारण और समझ के साथ किसी व्यक्ति द्वारा लागू करने की आवश्यकता है, या वे असफल हो जाएंगे। बेशक, कुछ क्रॉस-चेक के लिए लागू किया जा सकता है, और हम एक ध्वज है कि ने कहा कि "IsSorted" हो सकता है और यह अन्यथा द्विआधारी खोज पर विफल हो जाएगा, लेकिन .....
कुछ छद्म कोड:
if List is sorted
use the BinarySearch method
else if List is not sorted and you think sorting it is "waste of CPU time"
use a different algorithm that is more suitable and efficient
यह साबित करने के लिए कि यह उत्तर गलत है, मैं हिट और रन डरपोक सहित किसी को चुनौती नहीं देता हूं। केवल साहसी लोगों को आमंत्रित किया जाता है। – usefulBee
असल में यह एक अच्छा सवाल है। लेकिन क्या किसी भी प्रकार की प्रणाली (केवल सी #/एनईटी) के लिए यह संभव है कि किसी विधि को "क्रमबद्ध" वस्तुओं पर काम करने की अनुमति दें? यदि आप किसी प्रकार की प्रणाली पर सॉर्ट किए जाते हैं तो आपको कैसे पता चलेगा? –