इंट्रोसेलेक्ट: Difference between revisions
No edit summary |
No edit summary |
||
| Line 21: | Line 21: | ||
[[कंप्यूटर विज्ञान]] में, इंट्रोसेलेक्ट ("आत्मनिरीक्षण चयन" के लिए संक्षिप्त) एक चयन एल्गोरिदम है जो क्विकसेलेक्ट और मध्यस्थों के मध्य का एक [[हाइब्रिड एल्गोरिदम|हाइब्रिड]] है जिसमें तेज़ औसत प्रदर्शन और इष्टतम सबसे खराब स्थिति वाला प्रदर्शन होता है। इंट्रोसेलेक्ट, इंट्रोसॉर्ट सॉर्टिंग एल्गोरिदम से संबंधित है: ये बुनियादी क्विकसेलेक्ट और क्विकसॉर्ट एल्गोरिदम के अनुरूप परिशोधन हैं, जिसमें वे दोनों त्वरित एल्गोरिदम से शुरू होते हैं, जिसमें अच्छा औसत प्रदर्शन और कम ओवरहेड होता है, लेकिन एक इष्टतम सबसे खराब स्थिति वाले एल्गोरिदम पर वापस आते हैं। (उच्च ओवरहेड के साथ) यदि त्वरित एल्गोरिथ्म पर्याप्त तेज़ी से प्रगति नहीं करता है। दोनों एल्गोरिदम को [[डेविड मूसर|डेविड मुसर]] द्वारा (मुसर 1997) में पेश किया गया था, जिसका उद्देश्य C++ मानक लाइब्रेरी के लिए सामान्य एल्गोरिदम प्रदान करना था, जिसमें तेज़ औसत प्रदर्शन और इष्टतम सबसे खराब प्रदर्शन दोनों हैं, इस प्रकार प्रदर्शन आवश्यकताओं को कठोर किया जा सकता है।<ref>"[http://www.cs.rpi.edu/~musser/gp/algorithms.html Generic Algorithms]", [[David Musser]]</ref> | [[कंप्यूटर विज्ञान]] में, इंट्रोसेलेक्ट ("आत्मनिरीक्षण चयन" के लिए संक्षिप्त) एक चयन एल्गोरिदम है जो क्विकसेलेक्ट और मध्यस्थों के मध्य का एक [[हाइब्रिड एल्गोरिदम|हाइब्रिड]] है जिसमें तेज़ औसत प्रदर्शन और इष्टतम सबसे खराब स्थिति वाला प्रदर्शन होता है। इंट्रोसेलेक्ट, इंट्रोसॉर्ट सॉर्टिंग एल्गोरिदम से संबंधित है: ये बुनियादी क्विकसेलेक्ट और क्विकसॉर्ट एल्गोरिदम के अनुरूप परिशोधन हैं, जिसमें वे दोनों त्वरित एल्गोरिदम से शुरू होते हैं, जिसमें अच्छा औसत प्रदर्शन और कम ओवरहेड होता है, लेकिन एक इष्टतम सबसे खराब स्थिति वाले एल्गोरिदम पर वापस आते हैं। (उच्च ओवरहेड के साथ) यदि त्वरित एल्गोरिथ्म पर्याप्त तेज़ी से प्रगति नहीं करता है। दोनों एल्गोरिदम को [[डेविड मूसर|डेविड मुसर]] द्वारा (मुसर 1997) में पेश किया गया था, जिसका उद्देश्य C++ मानक लाइब्रेरी के लिए सामान्य एल्गोरिदम प्रदान करना था, जिसमें तेज़ औसत प्रदर्शन और इष्टतम सबसे खराब प्रदर्शन दोनों हैं, इस प्रकार प्रदर्शन आवश्यकताओं को कठोर किया जा सकता है।<ref>"[http://www.cs.rpi.edu/~musser/gp/algorithms.html Generic Algorithms]", [[David Musser]]</ref> | ||
हालाँकि, अधिकांश 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> | |||
हालाँकि, अधिकांश C++ मानक लाइब्रेरी कार्यान्वयन में, एक अलग इंट्रोसेलेक्ट | |||
== एल्गोरिदम == | == एल्गोरिदम == | ||
Revision as of 09:53, 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]
एल्गोरिदम
इंट्रोसॉर्ट क्विकॉर्ट और ढेर बनाएं और छांटें का एक हाइब्रिड बनाकर ओ (एन लॉग एन) सबसे खराब स्थिति वाले व्यवहार को संरक्षित करते हुए क्विकॉर्ट के तुलनीय व्यावहारिक प्रदर्शन को प्राप्त करता है। इंट्रोसॉर्ट क्विकॉर्ट से शुरू होता है, इसलिए यदि क्विकॉर्ट काम करता है तो यह क्विकॉर्ट के समान प्रदर्शन प्राप्त करता है, और यदि क्विकॉर्ट पर्याप्त तेज़ी से प्रगति नहीं करता है तो यह हेप्सॉर्ट (जिसमें इष्टतम सबसे खराब स्थिति वाला प्रदर्शन होता है) पर वापस आ जाता है। इसी तरह, इंट्रोसेलेक्ट, क्विकसेलेक्ट के समान प्रदर्शन के साथ सबसे खराब स्थिति वाले रैखिक चयन को प्राप्त करने के लिए क्विकसेलेक्ट को मध्यस्थों के माध्यिका के साथ जोड़ता है।
इंट्रोसेलेक्ट आशावादी रूप से क्विकसेलेक्ट के साथ शुरू करके काम करता है और केवल सबसे खराब स्थिति वाले रैखिक-समय चयन एल्गोरिदम (ब्लम-फ्लोयड-प्रैट-रिवेस्ट-टार्जन मीडियन ऑफ मीडियन एल्गोरिदम) पर स्विच करता है, अगर यह पर्याप्त प्रगति किए बिना कई बार पुनरावृत्ति करता है। स्विचिंग रणनीति एल्गोरिथम की मुख्य तकनीकी सामग्री है। केवल रिकर्सन को निरंतर गहराई तक सीमित करना पर्याप्त नहीं है, क्योंकि इससे एल्गोरिदम सभी पर्याप्त बड़ी सूचियों पर स्विच हो जाएगा। मुसर ने कुछ सरल तरीकों पर चर्चा की:
- अब तक संसाधित उपविभाजनों के आकारों की सूची पर नज़र रखें। यदि किसी भी बिंदु पर 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-#.
