इंट्रोसेलेक्ट: Difference between revisions
No edit summary |
|||
| Line 24: | Line 24: | ||
== एल्गोरिदम == | == एल्गोरिदम == | ||
इंट्रोसॉर्ट | इंट्रोसॉर्ट क्विकशार्ट और हीपसॉर्ट का एक हाइब्रिड बनाकर ''O''(''n'' log ''n'') सबसे खराब स्थिति वाले व्यवहार को संरक्षित करते हुए क्विकशार्ट के बराबर व्यावहारिक प्रदर्शन प्राप्त करता है। इंट्रोसॉर्ट क्विकशार्ट से शुरू होता है, इसलिए यदि क्विकशार्ट काम करता है तो यह क्विकशार्ट के समान प्रदर्शन प्राप्त करता है, और यदि क्विकशार्ट पर्याप्त रूप से तेजी से प्रगति नहीं करता है तो यह हेप्सॉर्ट (जिसका सबसे खराब स्थिति वाला प्रदर्शन होता है) पर वापस आ जाता है। इसी प्रकार, इंट्रोसेलेक्ट, क्विकसेलेक्ट के समान प्रदर्शन के साथ सबसे खराब स्थिति वाले रैखिक चयन को प्राप्त करने के लिए क्विकसेलेक्ट को मध्यस्थों के मध्यिका के साथ जोड़ता है। | ||
इंट्रोसेलेक्ट क्विकसेलेक्ट के साथ आशावादी रूप से शुरुआत करके काम करता है और केवल सबसे खराब स्थिति वाले रैखिक-समय चयन एल्गोरिदम (ब्लम-फ्लोयड-प्रैट-रिवेस्ट-टार्जन मीडियन ऑफ मीडियन्स एल्गोरिदम) पर स्विच करता है, अगर यह पर्याप्त प्रगति किए बिना कई बार पुनरावृत्ति करता है। स्विचिंग रणनीति एल्गोरिदम की मुख्य तकनीकी सामग्री है। रिकर्सन को केवल निरंतर गहराई तक सीमित करना पर्याप्त नहीं है, क्योंकि इससे एल्गोरिदम सभी पर्याप्त बड़ी सूचियों पर स्विच हो जाएगा। मुसर कुछ सरल दृष्टिकोणों पर चर्चा करते हैं: | |||
* अब तक संसाधित उपविभागों के आकारों की सूची पर नज़र रखें। यदि किसी बिंदु पर k पुनरावर्ती कॉल सूची आकार को आधा किए बिना की गई है, तो कुछ छोटे धनात्मक k के लिए, सबसे खराब स्थिति वाले रैखिक एल्गोरिदम पर स्विच करें। | |||
* अब तक उत्पन्न सभी विभाजनों के आकार का योग करें। यदि यह सूची आकार से कुछ छोटे धनात्मक स्थिरांक k से गुना अधिक है, तो सबसे खराब स्थिति वाले रैखिक एल्गोरिदम पर स्विच करें। यह योग एकल अदिश चर में ट्रैक करना आसान है। | |||
दोनों दृष्टिकोण रिकर्सन गहराई को k ⌈log n⌉ = O(log n) और कुल चलने का समय O(n) तक सीमित करते हैं। | दोनों दृष्टिकोण रिकर्सन गहराई को k ⌈log n⌉ = O(log n) और कुल चलने का समय O(n) तक सीमित करते हैं। | ||
Revision as of 09:59, 2 August 2023
| 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) |
कंप्यूटर विज्ञान में, इंट्रोसेलेक्ट ("आत्मनिरीक्षण चयन" के लिए संक्षिप्त) एक चयन एल्गोरिदम है जो क्विकसेलेक्ट और मध्यस्थों के मध्य का एक हाइब्रिड है जिसमें तेज़ औसत प्रदर्शन और इष्टतम सबसे खराब स्थिति वाला प्रदर्शन होता है। इंट्रोसेलेक्ट, इंट्रोसॉर्ट सॉर्टिंग एल्गोरिदम से संबंधित है: ये बुनियादी क्विकसेलेक्ट और क्विकसॉर्ट एल्गोरिदम के अनुरूप परिशोधन हैं, जिसमें वे दोनों त्वरित एल्गोरिदम से शुरू होते हैं, जिसमें अच्छा औसत प्रदर्शन और कम ओवरहेड होता है, लेकिन एक इष्टतम सबसे खराब स्थिति वाले एल्गोरिदम पर वापस आते हैं। (उच्च ओवरहेड के साथ) यदि त्वरित एल्गोरिथ्म पर्याप्त तेज़ी से प्रगति नहीं करता है। दोनों एल्गोरिदम को डेविड मुसर द्वारा (मुसर 1997) में पेश किया गया था, जिसका उद्देश्य C++ मानक लाइब्रेरी के लिए सामान्य एल्गोरिदम प्रदान करना था, जिसमें तेज़ औसत प्रदर्शन और इष्टतम सबसे खराब प्रदर्शन दोनों हैं, इस प्रकार प्रदर्शन आवश्यकताओं को कठोर किया जा सकता है।[1]
हालाँकि, अधिकांश C++ मानक लाइब्रेरी कार्यान्वयन में, एक अलग "इंट्रोसेलेक्ट" एल्गोरिथ्म का उपयोग किया जाता है, जो क्विकसेलेक्ट और हेप्सेलेक्ट को जोड़ता है, और इसमें O(n log n) का सबसे खराब स्थिति वाला रनिंग समय होता है।[2] 2022 तक C++ ड्राफ्ट मानक में सबसे खराब स्थिति के प्रदर्शन की आवश्यकता नहीं है, इसलिए इस तरह के विकल्प की अनुमति है।[3]
एल्गोरिदम
इंट्रोसॉर्ट क्विकशार्ट और हीपसॉर्ट का एक हाइब्रिड बनाकर O(n log n) सबसे खराब स्थिति वाले व्यवहार को संरक्षित करते हुए क्विकशार्ट के बराबर व्यावहारिक प्रदर्शन प्राप्त करता है। इंट्रोसॉर्ट क्विकशार्ट से शुरू होता है, इसलिए यदि क्विकशार्ट काम करता है तो यह क्विकशार्ट के समान प्रदर्शन प्राप्त करता है, और यदि क्विकशार्ट पर्याप्त रूप से तेजी से प्रगति नहीं करता है तो यह हेप्सॉर्ट (जिसका सबसे खराब स्थिति वाला प्रदर्शन होता है) पर वापस आ जाता है। इसी प्रकार, इंट्रोसेलेक्ट, क्विकसेलेक्ट के समान प्रदर्शन के साथ सबसे खराब स्थिति वाले रैखिक चयन को प्राप्त करने के लिए क्विकसेलेक्ट को मध्यस्थों के मध्यिका के साथ जोड़ता है।
इंट्रोसेलेक्ट क्विकसेलेक्ट के साथ आशावादी रूप से शुरुआत करके काम करता है और केवल सबसे खराब स्थिति वाले रैखिक-समय चयन एल्गोरिदम (ब्लम-फ्लोयड-प्रैट-रिवेस्ट-टार्जन मीडियन ऑफ मीडियन्स एल्गोरिदम) पर स्विच करता है, अगर यह पर्याप्त प्रगति किए बिना कई बार पुनरावृत्ति करता है। स्विचिंग रणनीति एल्गोरिदम की मुख्य तकनीकी सामग्री है। रिकर्सन को केवल निरंतर गहराई तक सीमित करना पर्याप्त नहीं है, क्योंकि इससे एल्गोरिदम सभी पर्याप्त बड़ी सूचियों पर स्विच हो जाएगा। मुसर कुछ सरल दृष्टिकोणों पर चर्चा करते हैं:
- अब तक संसाधित उपविभागों के आकारों की सूची पर नज़र रखें। यदि किसी बिंदु पर 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-#.
