सैंपलसॉर्ट: Difference between revisions
From Vigyanwiki
No edit summary |
|||
| (12 intermediate revisions by 4 users not shown) | |||
| Line 33: | Line 33: | ||
स्यूडोकोड मूल फ्रेज़र और मैककेलर एल्गोरिदम से भिन्न है।<ref name=Frazer70>{{cite journal | last1=Frazer|first1=W. D.| last2=McKellar|first2=A. C.| title=Samplesort: A Sampling Approach to Minimal Storage Tree Sorting| journal=Journal of the ACM| date=1970-07-01| volume=17| issue=3| pages=496–507| doi=10.1145/321592.321600| s2cid=16958223 }}</ref> स्यूडोकोड में, सैंपलसॉर्ट को पुनरावर्ती रूप से कार्यवान्वित किया जाता है। फ़्रेज़र और मैककेलर ने केवल एक बार सैंपलसॉर्ट को कार्यान्वित किया और निम्नलिखित सभी पुनरावृत्तियों में क्विकसॉर्ट का उपयोग किया। | स्यूडोकोड मूल फ्रेज़र और मैककेलर एल्गोरिदम से भिन्न है।<ref name=Frazer70>{{cite journal | last1=Frazer|first1=W. D.| last2=McKellar|first2=A. C.| title=Samplesort: A Sampling Approach to Minimal Storage Tree Sorting| journal=Journal of the ACM| date=1970-07-01| volume=17| issue=3| pages=496–507| doi=10.1145/321592.321600| s2cid=16958223 }}</ref> स्यूडोकोड में, सैंपलसॉर्ट को पुनरावर्ती रूप से कार्यवान्वित किया जाता है। फ़्रेज़र और मैककेलर ने केवल एक बार सैंपलसॉर्ट को कार्यान्वित किया और निम्नलिखित सभी पुनरावृत्तियों में क्विकसॉर्ट का उपयोग किया। | ||
=== कम्प्लेक्सिटी === | === कम्प्लेक्सिटी === | ||
| Line 85: | Line 85: | ||
<math display="block">P_\text{fail} = n \cdot P(X < S) \le n \cdot \exp\left(\dfrac{-\epsilon^2 \cdot S}{2}\right) \le n \cdot \dfrac{1}{n^2} \text{ for } S \ge \dfrac{4}{\epsilon^2}\ln n</math> | <math display="block">P_\text{fail} = n \cdot P(X < S) \le n \cdot \exp\left(\dfrac{-\epsilon^2 \cdot S}{2}\right) \le n \cdot \dfrac{1}{n^2} \text{ for } S \ge \dfrac{4}{\epsilon^2}\ln n</math> | ||
== कई इडेंटिकल 'की'(key) == | == कई इडेंटिकल 'की'(key) == | ||
| Line 110: | Line 110: | ||
1990 के दशक में [[कनेक्शन मशीन]] सुपरकंप्यूटर पर किए गए प्रयोग ने दिखाया कि सैंपलसॉर्ट बड़े डेटासेट को सॉर्ट करने में विशेष रूप से अच्छा है, क्योंकि इसका इंटरप्रोसेसर संचार ओवरहेड कम होता है।<ref>{{cite conference |title=A Comparison of Sorting Algorithms for the Connection Machine CM-2 |first1=Guy E. |last1=Blelloch |authorlink1=Guy Blelloch |first2=Charles E. |last2=Leiserson |authorlink2=Charles E. Leiserson |first3=Bruce M. |last3=Maggs |first4=C. Gregory |last4=Plaxton |first5=Stephen J. |last5=Smith |first6=Marco |last6=Zagha |conference=ACM Symp. on Parallel Algorithms and Architectures |year=1991 |url=https://www.cs.cmu.edu/~scandal/papers/cm-sort-SPAA91.html |citeseerx=10.1.1.131.1835}}</ref> हाल के [[GPGPU|GPUs]] पर, इस एल्गोरिदम का प्रयोग उसके विकल्पों की तुलना में कम प्रभावी हो सकता है।<ref>{{cite conference |first1=Nadathur |last1=Satish |first2=Mark |last2=Harris |first3=Michael |last3=Garland |title=Designing Efficient Sorting Algorithms for Manycore GPUs |conference=Proc. IEEE Int'l Parallel and Distributed Processing Symp. |citeseerx=10.1.1.190.9846}}</ref> | 1990 के दशक में [[कनेक्शन मशीन]] सुपरकंप्यूटर पर किए गए प्रयोग ने दिखाया कि सैंपलसॉर्ट बड़े डेटासेट को सॉर्ट करने में विशेष रूप से अच्छा है, क्योंकि इसका इंटरप्रोसेसर संचार ओवरहेड कम होता है।<ref>{{cite conference |title=A Comparison of Sorting Algorithms for the Connection Machine CM-2 |first1=Guy E. |last1=Blelloch |authorlink1=Guy Blelloch |first2=Charles E. |last2=Leiserson |authorlink2=Charles E. Leiserson |first3=Bruce M. |last3=Maggs |first4=C. Gregory |last4=Plaxton |first5=Stephen J. |last5=Smith |first6=Marco |last6=Zagha |conference=ACM Symp. on Parallel Algorithms and Architectures |year=1991 |url=https://www.cs.cmu.edu/~scandal/papers/cm-sort-SPAA91.html |citeseerx=10.1.1.131.1835}}</ref> हाल के [[GPGPU|GPUs]] पर, इस एल्गोरिदम का प्रयोग उसके विकल्पों की तुलना में कम प्रभावी हो सकता है।<ref>{{cite conference |first1=Nadathur |last1=Satish |first2=Mark |last2=Harris |first3=Michael |last3=Garland |title=Designing Efficient Sorting Algorithms for Manycore GPUs |conference=Proc. IEEE Int'l Parallel and Distributed Processing Symp. |citeseerx=10.1.1.190.9846}}</ref> | ||
== सैम्पल सॉर्ट का एफीसिएंट कार्यान्वयन == | == सैम्पल सॉर्ट का एफीसिएंट कार्यान्वयन == | ||
[[File:Animation.png|thumb|सुपर स्केलर सैंपलसॉर्ट का एनिमेटेड उदाहरण। प्रत्येक चरण में, जिन संख्याओं की तुलना की जाती है उन्हें नीले रंग से चिह्नित किया जाता है और जो संख्याएं अन्यथा | [[File:Animation.png|thumb|सुपर स्केलर सैंपलसॉर्ट का एनिमेटेड उदाहरण। प्रत्येक चरण में, जिन संख्याओं की तुलना की जाती है उन्हें नीले रंग से चिह्नित किया जाता है और जो संख्याएं अन्यथा रीड या राइट कीजाती हैं उन्हें लाल रंग से चिह्नित किया जाता है।]]जैसा कि ऊपर बताया गया है, सैंपलसॉर्ट एल्गोरिदम चयनित स्प्लिटर्स के अनुसार एलमेंट को विभाजित करता है। पेपर सुपर स्केलर सैंपल सॉर्ट में एक एफीसिएंट कार्यान्वयन रणनीति प्रस्तावित है।<ref name=":0"/>पेपर में प्रस्तावित कार्यान्वयन <math>n</math> एफीसिएंट कार्यान्वयन के लिए (इनपुट डेटा युक्त मूल ऐरे और एक अस्थायी) आकार की दो ऐरे का उपयोग करता है । इसलिए, कार्यान्वयन का यह संस्करण इन-प्लेस एल्गोरिदम नहीं है। | ||
प्रत्येक रिकर्सन चरण में, डेटा को डिवाइड विधि से अन्य ऐरे में कॉपी किया जाता है। यदि डेटा अंतिम रिकर्सन चरण में अस्थायी ऐरे में है, तो डेटा को मूल ऐरे में वापस कॉपी किया जाता है। | प्रत्येक रिकर्सन चरण में, डेटा को डिवाइड विधि से अन्य ऐरे में कॉपी किया जाता है। यदि डेटा अंतिम रिकर्सन चरण में अस्थायी ऐरे में है, तो डेटा को मूल ऐरे में वापस कॉपी किया जाता है। | ||
=== बकेट का निर्धारण === | === बकेट का निर्धारण === | ||
तुलना आधारित सॉर्टिंग एल्गोरिदम में तुलना ऑपरेशन सबसे | किसी तुलना-आधारित सॉर्टिंग एल्गोरिदम में तुलना की संचार ऑपरेशन सबसे प्रदर्शन-मुख्य भाग होती है। सैंपलसॉर्ट में यह तत्व के लिए बकेट निर्धारित करने के लिए होती है। इसमें प्रत्येक तत्व के लिए <math>\log k</math> समय लगता है। | ||
सुपर स्केलर सैंपल सॉर्ट एक बैलन्स सर्च ट्री का उपयोग करता है जो स्वतः में एक एरे {{mvar|t}} में रखा गया होता है। रूट ट्री 0 पर रखा जाता है, <math>t_i</math> का बाईं उत्तरधारी <math>t_{2i}</math> पर रखा जाता है और दाईं उत्तरधारी <math>t_{2i+1}</math> पर रखा जाता है। ट्री {{mvar|t}} को दिया गया है, एल्गोरिदम एलमेंट <math>a_i</math> का बकेट नंबर {{mvar|j}} निम्नलिखित विधि से निर्धारित करता है (यहां स्वीकृति है कि <math>a_i>t_j</math> का मूल्य 1 होगा यदि यह सत्य है और 0 होगा यदि यह सत्य नहीं है): | |||
''j'' := 1 | |||
repeat log<sub>2</sub>(''p'') times | |||
''j'' := 2''j'' + (''a'' > ''t''<sub>''j''</sub>) | |||
''j'' := ''j'' − ''p'' + 1 | |||
बकेटों की संख्या {{mvar|k}} कंपाइल समय पर ज्ञात होती है, इसलिए कंपाइलर इस लूप को [[लूप अनरोलिंग|अनरोल कर]] सकता है। तुलना ऑपरेशन को [[प्रेडिकेशन (कंप्यूटर विज्ञान)|प्रेडिकेटेड इंस्ट्रक्शन्स]] के साथ लागू किया जाता है। इससे [[ब्रांच मिसप्रिडिक्शन]] नहीं होती है, जो तुलना ऑपरेशन को काफी धीमा बना सकता है। | |||
=== विभाजन === | === विभाजन === | ||
एक प्रभावशील विभाजन के लिए, एल्गोरिदम को अग्रिम बकेटों का आकार जानने की जरूरत होती है। अनुक्रम के एलमेंट को विभाजित करने और उन्हें एक एरे में रखने के लिए, हमें अग्रिम बकेटों के आकार को जानने की आवश्यकता होती है। एक साधारण एल्गोरिदम में हर बकेट के एलमेंट की संख्या को गिन सकता है। फिर एलमेंट को सही स्थान पर दूसरे एरे में डाला जा सकता है। इससे, हमें प्रत्येक तत्व के लिए दो बार बकेट का निर्धारण करने की आवश्यकता होगी (एक बार बकेट में एलमेंट की संख्या को गिनने के लिए और एक बार उन्हें इन्सर्ट करने के लिए)। | |||
इस दोहराने वाले तुलना को टालने के लिए, सुपर स्केलर सैंपल सॉर्ट एक अतिरिक्त एरे <math>o</math> (जिसे ऑरेकल कहा जाता है) का उपयोग करता है जो प्रत्येक तत्व के एक बकेट से सम्बंधित होता है। पहले, एल्गोरिदम <math>o</math> के संदर्भ को निर्धारित करके यह निर्धारित करता है, फिर बकेट का आकार निर्धारित करके एलमेंट को <math>o</math> द्वारा निर्धारित बकेट में रखता है। एरे <math>o</math> भी संग्रह स्थान में खर्च करता है, परंतु क्योंकि इसमें केवल <math>n\cdot \log k</math> बिट संभावित होते हैं, इन खर्चों को इनपुट एरे के अनुपात में छोटा माना जा सकता है। | |||
== इन-प्लेस सैंपलसॉर्ट == | == इन-प्लेस सैंपलसॉर्ट == | ||
ऊपर दिखाए गए एफीसिएंट सैंपलसॉर्ट कार्यान्वयन | ऊपर दिखाए गए एफीसिएंट सैंपलसॉर्ट कार्यान्वयन की एक मुख्य हानि यह है कि यह इन-प्लेस नहीं है और सॉर्टिंग के समय इनपुट अनुक्रम के समान आकार की दूसरी अस्थायी ऐरे की आवश्यकता होती है। उदाहरण के लिए एफीसिएंट कार्यान्वयन क्विकसॉर्ट इन-प्लेस हैं और इस प्रकार अधिक प्लेस एफीसिएंट हैं। यद्यपि, सैंपलसॉर्ट को इन-प्लेस पर भी लागू किया जा सकता है।<ref>{{cite journal|last1=Axtmann|first1=Michael|last2=Witt|first2=Sascha|last3=Ferizovic|first3=Daniel|last4=Sanders|first4=Peter|title=इन-प्लेस पैरेलल सुपर स्केलर सैंपलसॉर्ट (IPSSSSo)|journal=25th Annual European Symposium on Algorithms (ESA 2017)|date=2017|volume=87|issue=Leibniz International Proceedings in Informatics (LIPIcs)|pages=9:1–9:14|doi=10.4230/LIPIcs.ESA.2017.9}}</ref> | ||
इन-प्लेस एल्गोरिदम को चार चरणों में विभाजित किया गया है: | इन-प्लेस एल्गोरिदम को चार चरणों में विभाजित किया गया है: | ||
# सैम्पलिंग जो उपरोक्त एफीसिएंट कार्यान्वयन में सैम्पलिंग के समतुल्य है। | # सैम्पलिंग जो उपरोक्त एफीसिएंट कार्यान्वयन में सैम्पलिंग के समतुल्य है। | ||
# प्रत्येक प्रोसेसर पर स्थानीय वर्गीकरण, जो इनपुट को ब्लॉकों में समूहित करता है जैसे कि प्रत्येक ब्लॉक में सभी तत्व एक ही बकेट से संबंधित होते हैं, | # प्रत्येक प्रोसेसर पर स्थानीय वर्गीकरण, जो इनपुट को ब्लॉकों में समूहित करता है जैसे कि प्रत्येक ब्लॉक में सभी तत्व एक ही बकेट से संबंधित होते हैं, परंतु बकेट आवश्यक रूप से मेमोरी में निरंतर नहीं होते हैं। | ||
# ब्लॉक क्रमपरिवर्तन ब्लॉकों को विश्व स्तर पर सही क्रम में लाता है। | # ब्लॉक क्रमपरिवर्तन ब्लॉकों को विश्व स्तर पर सही क्रम में लाता है। | ||
# क्लीनअप कुछ एलमेंट को | # क्लीनअप कुछ एलमेंट को बकेट के साइड पर ले जाता है। | ||
इस एल्गोरिदम | इस एल्गोरिदम की एक स्पष्ट हानि यह है कि यह प्रत्येक तत्व को दो बार रीड और राइट करता है, एक बार वर्गीकरण चरण में और एक बार ब्लॉक क्रमपरिवर्तन चरण में। यद्यपि, एल्गोरिथ्म अन्य अत्याधुनिक इन-प्लेस प्रतिस्पर्धियों की तुलना में तीन गुना तेज और अन्य अत्याधुनिक अनुक्रमिक प्रतिस्पर्धियों की तुलना में 1.5 गुना तेज प्रदर्शन करता है। जैसा कि सैम्पल के बारे में पहले ही ऊपर चर्चा की जा चुकी है, बाद के तीन चरणों के बारे में आगे विस्तार से बताया जाएगा। | ||
=== स्थानीय वर्गीकरण === | === स्थानीय वर्गीकरण === | ||
पहले चरण में, इनपुट | पहले चरण में, इनपुट एरे को <math>p</math> समान आकार के ब्लॉकों के <math>p</math> स्ट्राइप्स में विभाजित किया जाता है, प्रत्येक प्रोसेसर के लिए एक। प्रत्येक प्रोसेसर अतिरिक्त रूप से <math>k</math> बफर्स का आवंटन करता है जो ब्लॉकों के समान आकार के होते हैं, प्रत्येक बकेट के लिए एक। उसके बाद, प्रत्येक प्रोसेसर अपने स्ट्राइप को स्कैन करता है और एलमेंट को उस अनुसार बफर में ले जाता है। यदि बफर भर गया है, तो बफर को प्रोसेसर के स्ट्राइप में लिखा जाता है, फ्रंट से प्रारंभ करके। हमेशा कम से कम एक बफर के आकार का खाली स्थान होता है, क्योंकि बफर को लिखने के लिए (अर्थात बफर भर गया है), लिखे गए एलमेंट से कम से कम एक बफर के आकार के एलमेंट की जांच करने की आवश्यकता होती है। इसलिए, प्रत्येक भरा हुआ ब्लॉक एक ही बकेट के एलमेंट को सम्मिलित करता है। स्कैन करते समय, प्रत्येक बकेट के आकार को ट्रैक किया जाता है। | ||
=== ब्लॉक | === ब्लॉक पर्म्यूटैशन === | ||
सबसे पहले, | सबसे पहले, प्रीफिक्स सम आपरेशन किया जाता है जो बकेटों की सीमाओं को निर्धारित करता है। हालांकि, इस चरण में केवल पूर्ण ब्लॉक ही ले जाए जाते हैं, इसलिए सीमाएं ब्लॉक आकार की गुणा के लिए बढ़ा दी जाती हैं और एक एकल ओवरफ्लो बफर आवंटित की जाती है। ब्लॉक परिवर्तन प्रारंभ करने से पहले, कुछ खाली ब्लॉक बकेट के अंत में ले जाए जाने की आवश्यकता हो सकती है। इसके बाद, प्रत्येक बकेट के लिए एक लेखन सूचकांक <math>w_i</math> सेट किया जाता है जो बकेट <math>b_i</math> उपसूचकांश के प्रारंभ पर सेट किया जाता है और प्रत्येक बकेट के लिए एक पठन सूचकांक <math>r_i</math> सेट किया जाता है जो बकेट <math>b_i</math> उपसूचकांश के अंतिम खाली ब्लॉक में सेट किया जाता है। | ||
वर्क कन्टेन्शन की सीमा निर्धारित करने के लिए, प्रत्येक प्रोसेसर को एक अलग-अलग प्राथमिक बकेट <math>b_{prim}</math> और दो स्वैप बफर दिए जाते हैं, जो प्रत्येक में एक ब्लॉक हो सकता है। प्रत्येक चरण में, यदि दोनों स्वैप बफर खाली होते हैं, तो प्रोसेसर अपने प्राथमिक बकेट के पठन सूचकांक <math>r_{prim}</math> को कम करता है और एक ब्लॉक को <math>r_{prim - 1}</math> पर पढ़ता है और इसे अपने स्वैप बफर में स्थानांतरित करता है। ब्लॉक का गंतव्य बकेट <math>b_{dest}</math> तय करने के बाद, प्रारंभ में ब्लॉक का वर्तमान स्थानांतरित करते समय प्रोसेसर ब्लॉक के पहले तत्व की श्रेणीबद्धता से गंतव्य बकेट को निर्धारित करता है। फिर वह लेखन सूचकांक <math>w_{dest}</math> को बढ़ाता है, <math>w_{dest - 1}</math> पर ब्लॉक पढ़ता है और ब्लॉक को अपने गंतव्य बकेट में लिखता है। यदि <math>w_{dest} > r_{dest}</math> है, तो स्वैप बफर्स फिर से खाली हो जाते हैं। अन्यथा, स्वैप बफर्स में बचे रहे ब्लॉक को अपने गंतव्य बकेट में डालना अवश्यक होता है। | |||
यदि किसी प्रोसेसर की प्राथमिक बकेट की उपऐरे में सभी ब्लॉक सही बकेट में हैं, तो अगली बकेट को प्राथमिक बकेट के रूप में चुना जाता है। यदि कोई प्रोसेसर एक बार सभी बकेट को प्राथमिक बकेट के रूप में चुनता है, तो प्रोसेसर समाप्त हो जाता है। | यदि किसी प्रोसेसर की प्राथमिक बकेट की उपऐरे में सभी ब्लॉक सही बकेट में हैं, तो अगली बकेट को प्राथमिक बकेट के रूप में चुना जाता है। यदि कोई प्रोसेसर एक बार सभी बकेट को प्राथमिक बकेट के रूप में चुनता है, तो प्रोसेसर समाप्त हो जाता है। | ||
=== | |||
चूँकि ब्लॉक क्रमपरिवर्तन चरण में केवल पूरे ब्लॉकों को स्थानांतरित किया गया था, कुछ तत्व अभी भी गलत | |||
=== क्लीनअप === | |||
चूँकि ब्लॉक क्रमपरिवर्तन चरण में केवल पूरे ब्लॉकों को स्थानांतरित किया गया था, कुछ तत्व अभी भी गलत विधि से बकेट सीमाओं के निकट रखे जा सकते हैं। चूंकि प्रत्येक तत्व के लिए ऐरे में पर्याप्त स्पेस होना चाहिए, उन गलत विधि से रखे गए एलमेंट को बाएं से दाएं खाली स्थानों पर ले जाया जा सकता है, अंत में ओवरफ्लो बफर पर विचार किया जा सकता है। | |||
== यह भी देखें == | == यह भी देखें == | ||
* [[फ्लैशसॉर्ट]] | * [[फ्लैशसॉर्ट]] | ||
* | * क्विकसॉर्ट | ||
==संदर्भ== | ==संदर्भ== | ||
| Line 184: | Line 229: | ||
{{sorting}} | {{sorting}} | ||
[[Category:All articles with unsourced statements]] | |||
[[Category:Articles with invalid date parameter in template]] | |||
[[Category: | [[Category:Articles with unsourced statements from January 2018]] | ||
[[Category:Collapse templates]] | |||
[[Category:Created On 26/07/2023]] | [[Category:Created On 26/07/2023]] | ||
[[Category:Machine Translated Page]] | |||
[[Category:Navigational boxes| ]] | |||
[[Category:Navigational boxes without horizontal lists]] | |||
[[Category:Pages with script errors]] | |||
[[Category:Sidebars with styles needing conversion]] | |||
[[Category:Template documentation pages|Documentation/doc]] | |||
[[Category:Templates Vigyan Ready]] | |||
[[Category:Templates generating microformats]] | |||
[[Category:Templates that are not mobile friendly]] | |||
[[Category:Templates using TemplateData]] | |||
[[Category:Wikipedia metatemplates]] | |||
[[Category:छँटाई एल्गोरिदम]] | |||
[[Category:वितरित एल्गोरिदम]] | |||
Latest revision as of 13:52, 14 August 2023
सैंपलसॉर्ट, डिवाइड एंड कंकर एल्गोरिथ्म पर आधारित एक सॉर्टिंग एल्गोरिथ्म है, जिसका उपयोग प्रायः पैरलेल प्रोसेसिंग सिस्टम में किया जाता है।[1] पारंपरिक डिवाइड एंड कंकर एल्गोरिथ्म, ऐरे को सब-इंटरवल या बकेट में विभाजित करता है। फिर इस बकेट को अलग-अलग क्रमबद्ध किया जाता है और एक साथ जोड़ दिया जाता है। यद्यपि, यदि ये ऐरे गैर-समान रूप से वितरित किए गए है, तो इन सॉर्टिंग एल्गोरिदम का प्रदर्शन अत्यधिक सीमा तक कम हो सकता है। सैंपलसॉर्ट इस समस्या का समाधान करने में सक्षम है जिसमें n-एलिमेंट सीक्वन्स के लिए एक s आकार का सैम्पल चुनकर तथा उस सैंपल को सॉर्ट करने के उपरांत p-1 < s एलेमेन्ट को परिणाम से चुनकर बकेट की रेंज निर्धारित की जाती है। ये एलमेंट (जिन्हें स्प्लिटर्स कहा जाता है) फिर ऐरे को लगभग p समान बकेट में विभाजित करते हैं।[2] सैंपलसॉर्ट का वर्णन 1970 के लेख, सैंपलसॉर्ट: ए सैंपलिंग अप्रोच टू मिनिमल स्टोरेज ट्री सॉर्टिंग में डब्ल्यू. डी. फ्रेज़र और ए. सी. मैककेलर द्वारा किया गया है।[3]