इंट्रोसेलेक्ट: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(8 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{Short description|Selection algorithm}}
{{Short description|Selection algorithm}}
{{Infobox Algorithm
{{Infobox Algorithm
|name=Introselect (Musser)
|name=इंट्रोसेलेक्ट (मुसेर)
|class='''Selection algorithm'''
|class="सिलेक्शन एल्गोरिथम"
|image=
|image=
|data=[[Array data structure|Array]]
|data=[[ऐरे डेटा संरचना|ऐरे]]
|best-time=O(''n'')
|best-time=O(''n'')
|time=O(''n'')
|time=O(''n'')
Line 10: Line 10:
}}
}}
{{Infobox Algorithm
{{Infobox Algorithm
|name=Introselect (Quickselect–Heapselect)
|name=इंट्रोसेलेक्ट (क्विकसेलेक्ट-हीपसलेक्ट)
|class='''Selection algorithm'''
|class="''सलेक्शन एल्गोरिदम'''
|image=
|image=
|data=[[Array data structure|Array]]
|data=[[ऐरे डेटा संरचना|ऐरे]]
|best-time=O(''n'')
|best-time=O(''n'')
|time=O(''n'' log ''n'')
|time=O(''n'' log ''n'')
Line 19: Line 19:
}}
}}


[[कंप्यूटर विज्ञान]] में, इंट्रोसेलेक्ट ("आत्मनिरीक्षण चयन" के लिए संक्षिप्त) एक चयन एल्गोरिदम है जो क्विकसेलेक्ट और मध्यस्थों के मध्य का एक [[हाइब्रिड एल्गोरिदम|हाइब्रिड]] है जिसमें तेज़ औसत प्रदर्शन और इष्टतम सबसे खराब स्थिति वाला प्रदर्शन होता है। इंट्रोसेलेक्ट, इंट्रोसॉर्ट सॉर्टिंग एल्गोरिदम से संबंधित है: ये बुनियादी क्विकसेलेक्ट और क्विकसॉर्ट एल्गोरिदम के अनुरूप परिशोधन हैं, जिसमें वे दोनों त्वरित एल्गोरिदम से शुरू होते हैं, जिसमें अच्छा औसत प्रदर्शन और कम ओवरहेड होता है, लेकिन एक इष्टतम सबसे खराब स्थिति वाले एल्गोरिदम पर वापस आते हैं। (उच्च ओवरहेड के साथ) यदि त्वरित एल्गोरिथ्म पर्याप्त तेज़ी से प्रगति नहीं करता है। दोनों एल्गोरिदम को [[डेविड मूसर|डेविड मुसर]] द्वारा (मुसर 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++ मानक लाइब्रेरी कार्यान्वयन में, एक अलग "इंट्रोसेलेक्ट" एल्गोरिथ्म का उपयोग किया जाता है, जो क्विकसेलेक्ट और हेप्सेलेक्ट को जोड़ता है, और इसमें ''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 ⌈log n⌉ = O(log n) और कुल चलने का समय O(n) तक सीमित करते हैं।
* अब तक उत्पन्न सभी विभाजनों के आकार का योग करें। यदि यह सूची आकार से कुछ छोटे धनात्मक स्थिरांक k से गुना अधिक है, तो निकृष्ट स्थिति वाले रैखिक एल्गोरिदम पर स्विच करें। यह योग एकल स्केलर वेरिएबल में ट्रैक करना आसान है।
 
दोनों दृष्टिकोण पुनरावृत्ति गहराई को ''k'' ⌈log ''n''⌉ = ''O''(log ''n'') और कुल चलने का समय ''O''(''n)'' तक सीमित करते हैं।


पेपर ने सुझाव दिया कि इंट्रोसेलेक्ट पर और अधिक शोध आने वाला है, लेकिन लेखक ऐसे किसी भी अन्य शोध को प्रकाशित किए बिना 2007 में सेवानिवृत्त हो गए।
पेपर ने सुझाव दिया कि इंट्रोसेलेक्ट पर और अधिक शोध आने वाला है, लेकिन लेखक ऐसे किसी भी अन्य शोध को प्रकाशित किए बिना 2007 में सेवानिवृत्त हो गए।
Line 41: Line 43:
* {{Cite journal | last = Musser | first = David R. | author-link = David Musser | title = Introspective Sorting and Selection Algorithms | url = http://www.cs.rpi.edu/~musser/gp/introsort.ps| doi = 10.1002/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-# | journal = Software: Practice and Experience | volume = 27 | issue = 8 | pages = 983–993 | year = 1997 }}
* {{Cite journal | last = Musser | first = David R. | author-link = David Musser | title = Introspective Sorting and Selection Algorithms | url = http://www.cs.rpi.edu/~musser/gp/introsort.ps| doi = 10.1002/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-# | journal = Software: Practice and Experience | volume = 27 | issue = 8 | pages = 983–993 | year = 1997 }}
{{refend}}
{{refend}}
[[Category: चयन एल्गोरिदम]]


[[Category: Machine Translated Page]]
[[Category:Created On 26/07/2023]]
[[Category:Created On 26/07/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Short description with empty Wikidata description]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:चयन एल्गोरिदम]]

Latest revision as of 09:53, 11 August 2023

इंट्रोसेलेक्ट (मुसेर)
Class"सिलेक्शन एल्गोरिथम"
Data structureऐरे
Worst-case performanceO(n)
Best-case performanceO(n)
इंट्रोसेलेक्ट (क्विकसेलेक्ट-हीपसलेक्ट)
Class"सलेक्शन एल्गोरिदम'
Data structureऐरे
Worst-case performanceO(n log n)
Best-case performanceO(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 में सेवानिवृत्त हो गए।

यह भी देखें

  • फ्लोयड-रिवेस्ट एल्गोरिदम

संदर्भ

  1. "Generic Algorithms", David Musser
  2. "35968 – nth_element fails to meet its complexity requirements".
  3. "27.8.3 Nth element [alg.nth.element]". Working Draft, Standard for Programming Language C++, eel.is.