इंट्रोसेलेक्ट: Difference between revisions
No edit summary |
|||
| Line 19: | Line 19: | ||
}} | }} | ||
[[कंप्यूटर विज्ञान]] में, इंट्रोसेलेक्ट ("आत्मनिरीक्षण चयन" के लिए संक्षिप्त) एक चयन एल्गोरिदम है जो क्विकसेलेक्ट और मध्यस्थों के मध्य का | [[कंप्यूटर विज्ञान]] में, इंट्रोसेलेक्ट ("आत्मनिरीक्षण चयन" के लिए संक्षिप्त) एक चयन एल्गोरिदम है जो क्विकसेलेक्ट और मध्यस्थों के मध्य का [[हाइब्रिड एल्गोरिदम|हाइब्रिड]] है जिसमें तेज़ औसत प्रदर्शन और इष्टतम निकृष्ट स्थिति वाला प्रदर्शन होता है। इंट्रोसेलेक्ट, इंट्रोसॉर्ट सॉर्टिंग एल्गोरिदम से संबंधित है: ये बुनियादी क्विकसेलेक्ट और क्विकसॉर्ट एल्गोरिदम के अनुरूप परिशोधन हैं, जिसमें वे दोनों त्वरित एल्गोरिदम से शुरू होते हैं, जिसमें अच्छा औसत प्रदर्शन और कम ओवरहेड होता है, लेकिन एक इष्टतम निकृष्ट स्थिति वाले एल्गोरिदम पर वापस आते हैं। (उच्च ओवरहेड के साथ) यदि त्वरित एल्गोरिथ्म पर्याप्त तेज़ी से प्रगति नहीं करता है। दोनों एल्गोरिदम को [[डेविड मूसर|डेविड मुसर]] द्वारा (मुसर 1997) में पेश किया गया था, जिसका उद्देश्य C++ मानक लाइब्रेरी के लिए सामान्य एल्गोरिदम प्रदान करना था, जिसमें तेज़ औसत प्रदर्शन और इष्टतम सबसे खराब प्रदर्शन दोनों हैं, इस प्रकार प्रदर्शन आवश्यकताओं को कठोर किया जा सकता है।<ref>"[http://www.cs.rpi.edu/~musser/gp/algorithms.html Generic Algorithms]", [[David Musser]]</ref> | ||
हालाँकि, अधिकांश C++ मानक लाइब्रेरी कार्यान्वयन में, एक अलग "इंट्रोसेलेक्ट" एल्गोरिथ्म का उपयोग किया जाता है, जो क्विकसेलेक्ट और हेप्सेलेक्ट को जोड़ता है, और इसमें ''O''(''n'' log ''n'') का | हालाँकि, अधिकांश C++ मानक लाइब्रेरी कार्यान्वयन में, एक अलग "इंट्रोसेलेक्ट" एल्गोरिथ्म का उपयोग किया जाता है, जो क्विकसेलेक्ट और हेप्सेलेक्ट को जोड़ता है, और इसमें ''O''(''n'' log ''n'') का निकृष्ट स्थिति वाला रनिंग समय होता है।<ref>{{Cite web|url=https://gcc.gnu.org/bugzilla/show_bug.cgi?id=35968|title = 35968 – nth_element fails to meet its complexity requirements}}</ref> 2022 तक C++ ड्राफ्ट मानक में निकृष्ट स्थिति के प्रदर्शन की आवश्यकता नहीं है, इसलिए इस तरह के विकल्प की अनुमति है।<ref>{{cite web |title=27.8.3 Nth element [alg.nth.element] |url=https://eel.is/c++draft/alg.nth.element |website=Working Draft, Standard for Programming Language C++, eel.is}}</ref> | ||
== एल्गोरिदम == | == एल्गोरिदम == | ||
इंट्रोसॉर्ट क्विकशार्ट और हीपसॉर्ट का | इंट्रोसॉर्ट क्विकशार्ट और हीपसॉर्ट का हाइब्रिड बनाकर ''O''(''n'' log ''n'') निकृष्ट स्थिति वाले व्यवहार को संरक्षित करते हुए क्विकशार्ट के बराबर व्यावहारिक प्रदर्शन प्राप्त करता है। इंट्रोसॉर्ट क्विकशार्ट से शुरू होता है, इसलिए यदि क्विकशार्ट काम करता है तो यह क्विकशार्ट के समान प्रदर्शन प्राप्त करता है, और यदि क्विकशार्ट पर्याप्त रूप से तेजी से प्रगति नहीं करता है तो यह हेप्सॉर्ट (जिसका निकृष्ट स्थिति वाला प्रदर्शन होता है) पर वापस आ जाता है। इसी प्रकार, इंट्रोसेलेक्ट, क्विकसेलेक्ट के समान प्रदर्शन के साथ निकृष्ट स्थिति वाले रैखिक चयन को प्राप्त करने के लिए क्विकसेलेक्ट को मध्यस्थों के मध्यिका के साथ जोड़ता है। | ||
इंट्रोसेलेक्ट क्विकसेलेक्ट के साथ आशावादी रूप से | इंट्रोसेलेक्ट क्विकसेलेक्ट के साथ आशावादी रूप से प्रारम्भ करके काम करता है और केवल निकृष्ट स्थिति वाले रैखिक-समय चयन एल्गोरिदम (ब्लम-फ्लोयड-प्रैट-रिवेस्ट-टार्जन मीडियन ऑफ मीडियन्स एल्गोरिदम) पर स्विच करता है, अगर यह पर्याप्त प्रगति किए बिना कई बार पुनरावृत्ति करता है। स्विचिंग रणनीति एल्गोरिदम की मुख्य तकनीकी सामग्री है। रिकर्सन को केवल निरंतर गहराई तक सीमित करना पर्याप्त नहीं है, क्योंकि इससे एल्गोरिदम सभी पर्याप्त बड़ी सूचियों पर स्विच हो जाएगा। मुसर कुछ सरल दृष्टिकोणों पर चर्चा करते हैं: | ||
* अब तक संसाधित उपविभागों के आकारों की सूची पर नज़र रखें। यदि किसी बिंदु पर k पुनरावर्ती कॉल सूची आकार को आधा किए बिना की गई है, तो कुछ छोटे धनात्मक k के लिए, | * अब तक संसाधित उपविभागों के आकारों की सूची पर नज़र रखें। यदि किसी बिंदु पर k पुनरावर्ती कॉल सूची आकार को आधा किए बिना की गई है, तो कुछ छोटे धनात्मक k के लिए, निकृष्ट स्थिति वाले रैखिक एल्गोरिदम पर स्विच करें। | ||
* अब तक उत्पन्न सभी विभाजनों के आकार का योग करें। यदि यह सूची आकार से कुछ छोटे धनात्मक स्थिरांक k से गुना अधिक है, तो | * अब तक उत्पन्न सभी विभाजनों के आकार का योग करें। यदि यह सूची आकार से कुछ छोटे धनात्मक स्थिरांक k से गुना अधिक है, तो निकृष्ट स्थिति वाले रैखिक एल्गोरिदम पर स्विच करें। यह योग एकल अदिश चर में ट्रैक करना आसान है। | ||
दोनों दृष्टिकोण पुनरावृत्ति गहराई को ''k'' ⌈log ''n''⌉ = ''O''(log ''n'') और कुल चलने का समय ''O''(''n)'' तक सीमित करते हैं। | दोनों दृष्टिकोण पुनरावृत्ति गहराई को ''k'' ⌈log ''n''⌉ = ''O''(log ''n'') और कुल चलने का समय ''O''(''n)'' तक सीमित करते हैं। | ||
Revision as of 10:09, 2 August 2023
| Class | "सिलेक्शन एल्गोरिथम" |
|---|---|
| Data structure | ऐरे |
| Worst-case performance | O(n) |
| Best-case performance | O(n) |
| Class | "सलेक्शन एल्गोरिदम' |
|---|---|
| Data structure | ऐरे |
| 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-#.
