इंट्रोसेलेक्ट
| Class | Selection algorithm |
|---|---|
| Data structure | Array |
| Worst-case performance | O(n) |
| Best-case performance | O(n) |
| Class | Selection algorithm |
|---|---|
| Data structure | Array |
| Worst-case performance | O(n log n) |
| Best-case performance | O(n) |
कंप्यूटर विज्ञान में, इंट्रोसेलेक्ट (आत्मनिरीक्षण चयन के लिए संक्षिप्त) एक चयन एल्गोरिदम है जो त्वरित चयन और मध्यस्थों के मध्य का एक हाइब्रिड एल्गोरिदम है जिसमें तेज़ औसत प्रदर्शन और इष्टतम सबसे खराब स्थिति वाला प्रदर्शन होता है। इंट्रोसेलेक्ट, परिचय छँटाई एल्गोरिथ्म से संबंधित है: ये बुनियादी तुरंत चयन और जल्दी से सुलझाएं एल्गोरिदम के अनुरूप परिशोधन हैं, जिसमें वे दोनों त्वरित एल्गोरिदम से शुरू होते हैं, जिसमें अच्छा औसत प्रदर्शन और कम ओवरहेड होता है, लेकिन यदि त्वरित एल्गोरिदम पर्याप्त तेजी से प्रगति नहीं करता है तो एक इष्टतम सबसे खराब स्थिति वाले एल्गोरिदम (उच्च ओवरहेड के साथ) पर वापस आ जाता है। दोनों एल्गोरिदम डेविड मूसर द्वारा पेश किए गए थे (Musser 1997), C++ मानक लाइब्रेरी के लिए सामान्य एल्गोरिदम प्रदान करने के उद्देश्य से, जिसमें तेज़ औसत प्रदर्शन और इष्टतम सबसे खराब प्रदर्शन दोनों हैं, जिससे प्रदर्शन आवश्यकताओं को कड़ा किया जा सकता है।[1] हालाँकि, अधिकांश C++ मानक लाइब्रेरी कार्यान्वयन में, एक अलग इंट्रोसेलेक्ट एल्गोरिदम का उपयोग किया जाता है, जो क्विकसेलेक्ट और heapselect को जोड़ता है, और इसमें O(n log n) का सबसे खराब स्थिति वाला रनिंग टाइम होता है।[2] 2022 तक C++ ड्राफ्ट मानक में सबसे खराब स्थिति के प्रदर्शन की आवश्यकता नहीं है, इसलिए इस तरह के विकल्प की अनुमति है।[3]
एल्गोरिदम
इंट्रोसॉर्ट क्विकॉर्ट और ढेर बनाएं और छांटें का एक हाइब्रिड बनाकर ओ (एन लॉग एन) सबसे खराब स्थिति वाले व्यवहार को संरक्षित करते हुए क्विकॉर्ट के तुलनीय व्यावहारिक प्रदर्शन को प्राप्त करता है। इंट्रोसॉर्ट क्विकॉर्ट से शुरू होता है, इसलिए यदि क्विकॉर्ट काम करता है तो यह क्विकॉर्ट के समान प्रदर्शन प्राप्त करता है, और यदि क्विकॉर्ट पर्याप्त तेज़ी से प्रगति नहीं करता है तो यह हेप्सॉर्ट (जिसमें इष्टतम सबसे खराब स्थिति वाला प्रदर्शन होता है) पर वापस आ जाता है। इसी तरह, इंट्रोसेलेक्ट, क्विकसेलेक्ट के समान प्रदर्शन के साथ सबसे खराब स्थिति वाले रैखिक चयन को प्राप्त करने के लिए क्विकसेलेक्ट को मध्यस्थों के माध्यिका के साथ जोड़ता है।
इंट्रोसेलेक्ट आशावादी रूप से क्विकसेलेक्ट के साथ शुरू करके काम करता है और केवल सबसे खराब स्थिति वाले रैखिक-समय चयन एल्गोरिदम (ब्लम-फ्लोयड-प्रैट-रिवेस्ट-टार्जन मीडियन ऑफ मीडियन एल्गोरिदम) पर स्विच करता है, अगर यह पर्याप्त प्रगति किए बिना कई बार पुनरावृत्ति करता है। स्विचिंग रणनीति एल्गोरिथम की मुख्य तकनीकी सामग्री है। केवल रिकर्सन को निरंतर गहराई तक सीमित करना पर्याप्त नहीं है, क्योंकि इससे एल्गोरिदम सभी पर्याप्त बड़ी सूचियों पर स्विच हो जाएगा। मुसर ने कुछ सरल तरीकों पर चर्चा की:
- अब तक संसाधित उपविभाजनों के आकारों की सूची पर नज़र रखें। यदि किसी भी बिंदु पर k पुनरावर्ती कॉल सूची के आकार को आधा किए बिना की गई है, तो कुछ छोटे सकारात्मक k के लिए, सबसे खराब स्थिति वाले रैखिक एल्गोरिदम पर स्विच करें।
- अब तक उत्पन्न सभी विभाजनों के आकार का योग करें। यदि यह सूची के आकार से कुछ छोटे सकारात्मक स्थिरांक k से गुना अधिक है, तो सबसे खराब स्थिति वाले रैखिक एल्गोरिदम पर स्विच करें। इस योग को एकल अदिश चर में ट्रैक करना आसान है।
दोनों दृष्टिकोण रिकर्सन गहराई को k ⌈log n⌉ = O(log n) और कुल चलने का समय O(n) तक सीमित करते हैं।
पेपर ने सुझाव दिया कि इंट्रोसेलेक्ट पर और अधिक शोध आने वाला है, लेकिन लेखक ऐसे किसी भी अन्य शोध को प्रकाशित किए बिना 2007 में सेवानिवृत्त हो गए।
यह भी देखें
- फ्लोयड-रिवेस्ट एल्गोरिदम
संदर्भ
- ↑ "Generic Algorithms", David Musser
- ↑ "35968 – nth_element fails to meet its complexity requirements".
- ↑ "27.8.3 Nth element [alg.nth.element]". Working Draft, Standard for Programming Language C++, eel.is.
- Musser, David R. (1997). "Introspective Sorting and Selection Algorithms". Software: Practice and Experience. 27 (8): 983–993. doi:10.1002/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-#.
