और अधिक प्रकार के बारे में

मैं इस विषय को फिर से उठाने के लिए उद्यम करूंगा। मैं मिखाइल ओपानासेंको (oms7) के एक लेख के लिंक के साथ शुरू करूंगा , जो कि किए गए काम की मात्रा के साथ-साथ लिंक की संख्या के संदर्भ में बहुत प्रभावशाली है। उन्होंने इस प्रकाशन के बारे में न जानते हुए, अपनी सामग्री तैयार करना शुरू कर दिया, जो बाद में, परिचित होने के बाद, इसके पर्याप्त प्रसंस्करण की आवश्यकता के कारण हुआ। जिन लोगों ने पहले से ही इस लेख को पढ़ा है, मैं आपको सूचित करता हूं कि मेरी सामग्री में, अधिक विविध प्रकार के डेटा का अध्ययन किया जाता है, विशेष रूप से, तार और वास्तविक संख्याओं में, बूस्ट और बीएसडी पुस्तकालयों का उपयोग किया जाता है, और लेख से गायब कुछ अन्य विषयों का उल्लेख किया गया है।

डेटा आइटम को व्यवस्थित करने के लिए दर्जनों अलग-अलग तरीके हैं। उनमें से, वे हैं जो तेजी से काम करते हैं, जैसे कि, उदाहरण के लिए, वे अधिकतम मिनटों में कंप्यूटर की रैम में स्थित किसी भी डेटा ऐरे को सॉर्ट कर सकते हैं। अधिक विशेष रूप से, यह कहा जा सकता है कि त्वरित छँटाई एक सौ सेकंड से भी कम समय में एक अच्छे आधुनिक व्यक्तिगत कंप्यूटर में एक अरब पूर्णांक का आयोजन करती है। यदि आप आदिम, धीमी विधियों का उपयोग करते हैं, उदाहरण के लिए, बबल सॉर्टिंग या चयन छँटाई, तत्वों की एक बड़ी संख्या को सॉर्ट करने के लिए, तो इस तरह के डेटा प्रोसेसिंग पर खर्च किया गया समय किसी भी अपेक्षा से अधिक हो सकता है - ऐसे "प्रसंस्करण" वास्तव में कई दिन, सप्ताह और साल भी ले सकते हैं। यह बड़ा अंतर इस तथ्य के कारण है कि त्वरित तरीकों से छंटाई का समय एन लॉग एन और आदिम - एन ^{2 के} लिए लगभग आनुपातिक लगता है। बढ़ते एन के साथ , दो मूल्यों के बीच का अंतर बहुत ध्यान देने योग्य हो जाता है। इसलिए, केवल छोटे डेटा के साथ काम करने के लिए आदिम तरीकों का उपयोग करना उचित है, उदाहरण के लिए, आधुनिक कंप्यूटरों पर, कई हजार तत्वों तक। प्रोग्रामिंग और तार्किक सोच की मूल बातें सिखाने के लिए उनका उपयोग करना भी स्वाभाविक है, क्योंकि वे तेज़ विधियों की तुलना में बहुत सरल हैं।

मैं मौजूदा मानक पुस्तकालयों में मौजूद छंटाई के तरीकों को समझना चाहूंगा। पता लगाएं कि उनकी मुख्य विशेषताओं, काम की गति और उनकी विशिष्ट विशेषताओं के संदर्भ में उनके बीच का अंतर कितना बड़ा है। इसके अलावा, हम मन के लिए तुलना और अभ्यास के लिए कुछ तरीकों पर विचार करेंगे जिन्हें लागू करना मुश्किल नहीं है। यह भी ध्यान देने योग्य है कि जीसीसी संकलक और संभवतः अन्य अच्छे संकलक का अनुकूलन बहुत अच्छी तरह से काम करता है, कई बार कोड को गति देता है (कभी-कभी 5 से अधिक बार भी)।

आइए सबसे सरल और धीमे के रूप में बुलबुला सॉर्ट विधि के साथ शुरू करें। इस विधि के अनुसार, आपको पड़ोसी तत्वों की तुलना करने और उनके बीच के क्रम को तोड़ने पर उनके स्थानों को बदलने की जरूरत है। प्रत्येक पास के बाद, कम से कम एक तत्व (सबसे बड़ा या सबसे छोटा - चयनित क्रम पर निर्भर करता है) अपनी जगह पर है। सादगी के अलावा, इस विधि का एक और लाभ है, इसके लिए अतिरिक्त मेमोरी की आवश्यकता नहीं है। बुलबुला विधि की एक और विशेषता को नोट किया जा सकता है - यह बहुत जल्दी से पहले से ही ऑर्डर किए गए डेटा को संसाधित करता है और कुछ मामलों में इसे सबसे तेज़ तरीकों में से एक बनाता है। यदि डेटा केवल आंशिक रूप से ऑर्डर किया जाता है, तो यह विधि उनके साथ तेजी से काम करती है, लेकिन ज्यादातर मामलों में बहुत कम ही। परीक्षणों के लिए, मैंने निम्नलिखित कार्यान्वयन का उपयोग किया ।

एक और धीमी विधि चयन प्रकार है। यहां, प्रत्येक पास पर, डेटा में सबसे बड़े और सबसे छोटे तत्व पहले पाए जाते हैं और फिर इन तत्वों को चयनित क्रम के अनुरूप चरम स्थिति में रखा जाता है। अगले पास पर, हम इन चरम तत्वों के बिना डेटा को सॉर्ट करते हैं। यह विधि बुलबुला छंटाई के रूप में सरल है, और अतिरिक्त मेमोरी की भी आवश्यकता नहीं है, लेकिन यह काफी तेज है। इसके अलावा, इस विधि द्वारा छंटनी डेटा तत्वों के क्रमपरिवर्तन की रिकॉर्ड न्यूनतम संख्या करती है। इसलिए, जब क्रमचय तुलना की तुलना में बहुत धीमा है, तो चयन विधि द्वारा आदेश देना स्वीकार्य हो सकता है यदि डेटा तत्वों की संख्या छोटी है। यहाँ मेरा कार्यान्वयन है । अधिक बार इस छंटाई का एहसास होता है, प्रति मार्ग केवल एक तत्व को जगह देना। हीप सॉर्टिंग (या पिरामिडल), जिसे बाद में चर्चा की जाएगी, प्रश्न में छंटाई का सबसे उन्नत संस्करण है।

अंतिम मानी गई धीमी विधि, सम्मिलन प्रकार के लिए कोड, संभवतः सभी कोडों में से सबसे कम है जो छंटनी को लागू करते हैं, इसलिए इस पद्धति का उपयोग कभी-कभी जटिल त्वरित प्रकार के मामलों के लिए किया जाता है जहां छंटनी की जाने वाली वस्तुओं की संख्या छोटी (कई दसियों) होती है। यह कुछ हद तक एक बुलबुले द्वारा छंटाई के समान है, क्योंकि यहां और वहां के पड़ोसी तत्वों की तुलना क्रमिक रूप से की जाती है। लेकिन आवेषण द्वारा छंटनी डेटा के पहले से ही सॉर्ट किए गए हिस्से में सही स्थिति के लिए अगले तत्व की तलाश करती है, और न केवल चरम तत्व को चरम स्थिति में धकेलती है। इस दृष्टिकोण के साथ, अतिरिक्त मेमोरी की भी आवश्यकता नहीं है। बबल सॉर्टिंग की तरह, आर्डर सॉर्टिंग ऑर्डर किए गए डेटा पर बहुत तेज़ है और आंशिक रूप से ऑर्डर किए गए डेटा पर तेज़ है। बाद के मामले में, बुलबुले की तुलना में काफी तेज। आमतौर पर आवेषण द्वारा छांटना चयन द्वारा छंटाई की तुलना में कुछ तेज होता है। और बाद के विपरीत, यह, बुलबुला छंटाई की तरह, स्थिर है। सबसे खराब, सम्मिलन सॉर्टिंग रिवर्स ऑर्डर में डेटा के साथ काम करता है, जिसके साथ यह कभी-कभी सबसे धीमा सबसे धीमा हो जाता है। परीक्षणों के लिए, निम्नलिखित कार्यान्वयन का उपयोग किया गया था। यदि आप रैखिक नहीं, बल्कि बाइनरी खोज का उपयोग करते हैं, तो इसे थोड़ा तेज किया जा सकता है, उदाहरण के लिए, std :: bsearch फ़ंक्शन का उपयोग करना। एक सूची प्रकार संरचना का उपयोग करके महत्वपूर्ण त्वरण प्राप्त किया जा सकता है, एक तत्व का सम्मिलन जिसमें बहुत तेज है। आप यह भी देख सकते हैं कि यह सबसे प्राकृतिक छँटाई है - यह, उदाहरण के लिए, कार्ड खेलते समय आमतौर पर सहजता से उपयोग किया जाता है।

शेल छांटना तेज विधियों में सबसे सरल है और छात्रों के लिए प्रोग्रामिंग सीखने की शुरुआत के लिए काफी उपयुक्त है। यह बबल सॉर्टिंग का केवल कुछ संशोधन है। उनके बीच एकमात्र अंतर यह है कि शेल छँटाई में, तुलना तत्वों के बीच की दूरी को गलियारे से गलियारे तक ले जाया जाता है, पहले पास में बड़े से, अंतिम में 1 तक, इसलिए शैल विधि इन अंतिम पासिंग में आदिम बुलबुला में पतित हो जाती है। डोनाल्ड शेल ने बुनियादी सॉर्टिंग एल्गोरिथ्म प्रकाशित किया, जिसे 1959 में उनका नाम मिला। इस प्रकार, यह पहले सार्वभौमिक सॉर्टिंग में से एक है जो तेजी से काम करता है। तुलना के लिए, त्वरित सॉर्ट एल्गोरिथ्म दो साल बाद प्रकाशित किया गया था, और टिम की लोकप्रिय सॉर्टिंग या आत्मनिरीक्षण सॉर्टिंग केवल 90 के दशक में ज्ञात हुई। कई दिलचस्प अनसुलझी गणितीय समस्याएं शेल छँटाई के साथ जुड़ी हुई हैं, जिनमें से एक मुख्य है कि कैसे तुलनात्मक तत्वों के बीच विस्थापन का चयन करें। कुछ रिकॉर्ड अनुक्रम पाए गए, उदाहरण के लिए, A102549 । इस तरह के अनुक्रम कोलोसल गणना के माध्यम से पाए जाते हैं, इसलिए उनकी लंबाई बहुत कम है, ए 102549 केवल 8 तत्व हैं, जो केवल लगभग 3,000 तत्वों तक के डेटा के लिए पर्याप्त है। बड़े डेटा के लिए, सीक्वेल को लगभग यादृच्छिक रूप से देखा जाना चाहिए। 2, ई , 2.25 और 3. की ​​शक्तियों के करीब इस्तेमाल किए गए मान। 2 की शक्तियों के करीब अभाज्य संख्या ने सबसे खराब परिणाम दिखाए, जो कि सबसे अच्छे से हीन हैं। लेकिन अन्य तीन विकल्प प्रदर्शन पर प्रभाव के संदर्भ में लगभग समान थे और शायद इष्टतम के बहुत करीब थे। इसके अलावा, इन तीन मामलों में, primes के उपयोग ने मूर्त फायदे नहीं दिए। यह उत्सुक है कि संबंधित कार्यों के संदर्भ में विकिपीडिया (2.25 के आधार के साथ) पर प्रस्तावित पूर्वाग्रह परीक्षणों पर सर्वोत्तम परिणाम नहीं दिखाते हैं, हालांकि सर्वश्रेष्ठ से उनके मतभेद बहुत ही तुच्छ थे (5-10% से अधिक नहीं)। प्रारंभिक बिंदु के रूप में A102549 का उपयोग करना भी कोई ध्यान देने योग्य परिणाम नहीं देता है। मिखाइल ओपानासेंको ने भी शेल छंटाई की कोशिश की और एक दिलचस्प परिणाम मिला कि सूत्र द्वारा चुना गया विस्थापन s _{n + 1} = 10 s _n / 3 एक बहुत अच्छा प्रभाव देता है और शायद आदर्श के करीब भी। मेरे परिणाम इसकी पुष्टि करते हैं। कई मामलों में, यह ऐसे पूर्वाग्रह थे जिन्होंने सबसे अच्छा परिणाम दिया, हालांकि यह हमेशा मामला नहीं था और निकटतम परिणाम से अंतराल काफी छोटा था (लगभग 5%)। शेल सॉर्टिंग को लागू करने के लिए मेरा कोड ऑफ़सेट्स के साथ छोटे तालिकाओं का उपयोग करता है, हालांकि यदि आप अभाज्य संख्याओं का उपयोग नहीं करते हैं, तो तालिकाओं के लिए इन ऑफ़सेट्स की गणना लगभग तुरंत की जा सकती है, जैसा कि इस सॉर्टिंग के दिए गए वेरिएंट में से एक के कार्यान्वयन में किया गया था।

यह दिलचस्प है कि अगर हम तीन अलग-अलग तरीकों से तीनों की शक्तियों के करीब से उतारते हैं और थोड़ा अलग एल्गोरिथ्म ( कार्यान्वयन देखें) का उपयोग करते हैं, तो 32-बिट संख्याओं पर हमें सबसे अच्छी गति के करीब मिलेगा, लेकिन लंबी संख्या और लाइनों पर हमें एक महत्वपूर्ण मंदी मिलेगी, कभी-कभी। 100% से अधिक। Oms7 द्वारा उपयोग किए जाने वाले सर्वश्रेष्ठ एल्गोरिदम के परिणाम भी नीचे दी गई तालिका में हैं, लेकिन यद्यपि यह क्रम में अच्छे परिणाम दिखाता है, यह पूर्ण मूल्यों के मामले में नेताओं से काफी पीछे है।

क्या कभी भी सबसे अच्छा ऑफ़सेट खोजने का एक तरीका होगा? शायद, लेकिन मैं यह सुझाव देने की हिम्मत करता हूं कि यह जल्द ही नहीं है। लिनक्स कर्नेल में शेल छँटाई का उपयोग किया जाता है, और कम से कम एक सी लाइब्रेरी में इसका कोड मानक qsort () फ़ंक्शन के लिए उपयोग किया जाता है। यह सैद्धांतिक रूप से साबित हो चुका है कि शैल इष्टतम क्रमबद्ध गति केवल "वास्तविक" तेज़ लॉगरिदमिक विधियों की तुलना में थोड़ी धीमी है। दरअसल, इष्टतम शेल छँटाई के लिए उनके आकार पर औसत डेटा प्रोसेसिंग समय की निर्भरता सूत्र ( एन (लॉग एन / लॉग लॉग एन ) ² द्वारा वर्णित है, जो कि बहुत बड़े एन के लिए भी फार्मूला fast एन लॉग एन के लिए बहुत करीब है। आमतौर पर, शेल छँटाई अक्सर क्रम में सैद्धांतिक रूप से तेज़ विधियों की तुलना में अधिक तेज़ होती है और केवल बड़े एरेज़ (10 मिलियन तत्वों के आदेश) के प्रसंस्करण के दौरान उनके लिए थोड़ी उपज शुरू होती है। इस छँटाई को पूरी तरह से अतिरिक्त मेमोरी की आवश्यकता नहीं होती है और यह डेटा को भरने के लिए विभिन्न प्रकार के विकल्पों के लिए महत्वपूर्ण रूप से व्यवहार करता है, अनुकूलतम तुलनाओं के साथ तुलना करता है। शेल विधि में स्थिरता गुण नहीं होता है।

त्वरित सॉर्ट शेल एल्गोरिथ्म की तुलना में केवल थोड़ा अधिक जटिल है और अभी भी बेतरतीब ढंग से बिखरे हुए डेटा को व्यवस्थित करने का सबसे तेज़ तरीका है। हालाँकि, इस छँटाई में कई कमियाँ हैं। द्विघात निर्भरता के अनुसार उसे अतिरिक्त स्मृति की आवश्यकता होती है और बहुत कम मामलों में यह बहुत धीरे-धीरे काम करता है। इस पद्धति का मुख्य विचार डेटा को दो भागों में विभाजित करना है: एक भाग में डेटा दूसरे की तुलना में कम या ज्यादा (चयनित क्रम पर निर्भर करता है) होना चाहिए। इस अलगाव के लिए कई तरीके हैं। आदर्श रूप से, प्रत्येक विभाजन के साथ, दोनों भागों का आकार लगभग समान होना चाहिए, और सभी में से सबसे खराब, जब विभाजन में से कोई एक भाग केवल एक तत्व से बना हो। आइए, त्वरित सॉर्टिंग एल्गोरिदम के कई कार्यान्वयन पर विचार करें, विशेष रूप से, होर विधि , जिसमें डेटा को दो भागों में विभाजित करने वाले एक संदर्भ तत्व को सॉर्ट किए गए डेटा के बीच से चुना जाता है।

हम बेहद कॉम्पैक्ट लोमुटो एल्गोरिदम पर भी विचार करते हैं, जो कभी-कभी माना जाने वाले होरे विधि की तुलना में थोड़ा (लगभग 1%) तेज होता है। हालांकि, विशिष्ट विशेष मामलों पर, उदाहरण के लिए, आदेशित, उलटा या मैलोवेरिएंट डेटा पर, लोमुटो विधि चरम मंदी दिखाती है। इसके अलावा, त्वरित छंटाई के लिए विचार किए गए विकल्पों में से, यह व्यावहारिक रन के दौरान स्टैक के आकार के लिए सबसे लालची निकला: अपेक्षाकृत छोटे सरणियों को छांटने पर, केवल इस तरह के स्टैक के लिए पर्याप्त 8 मेगाबाइट नहीं थे, मुझे अपने आकार को ulimit के माध्यम से अधिक सेट करना पड़ा। स्टैक के लिए इस तरह का लालच बड़े डेटा (लाखों लाइनों का दसवां) प्रसंस्करण करते समय बड़ी मंदी की ओर जाता है, और मुझे इसकी प्रकृति को कॉल करने में कठिनाई हो रही है। मैं केवल यह बता सकता हूं कि इस तरह के डेटा के साथ अगले पैराग्राफ से इस छंटाई का उपयोग न करना बेहतर है।

लोमुटो विधि अंतिम तत्व को संदर्भ एक के रूप में चुनती है, लेकिन किसी भी सहायक तत्व के बिना त्वरित छंटाई को लागू करना संभव है, अधिक सटीक रूप से, यहां पहले से ही डेटा बिसनेस के परिणामस्वरूप ऐसे तत्व का चयन होता है। गति विशेषताओं द्वारा छँटाई यह लोमुटो विधि के करीब है, हालांकि यह आमतौर पर थोड़ा तेज़ होता है, और अत्यधिक मामलों में यह लोमुटो की तुलना में काफी तेज़ है, लेकिन होर की तुलना में धीमा है।

2009 में, दो-एंकर क्विक-सॉर्ट एल्गोरिथ्म प्रकाशित किया गया था, जो जावा भाषा के लिए मानक बन गया। यह एल्गोरिथ्म सबसे अच्छे ठेठ लोगों की तुलना में क्रमपरिवर्तन की संख्या को 20% कम कर देता है, लेकिन तुलनाओं की संख्या में बदलाव नहीं होता है। इसके लेखक व्लादिमीर यारोस्लावस्की हैं। यह वास्तव में, एक नियम के रूप में, अन्य त्वरित प्रकारों की तुलना में तेजी से काम करता है। मैंने इसे थोड़ा अनुकूलित किया, लंबे समय से ज्ञात तथ्य का उपयोग करते हुए कि x86 आर्किटेक्चर पर, स्वैप आमतौर पर असाइनमेंट की तुलना में तेजी से काम करता है, और सी ++ स्ट्रिंग्स के लिए यह बहुत, बहुत तेज है। अब तक मानी गई सभी त्वरित छंटाई के पास स्थिरता संपत्ति नहीं है।

त्वरित छँटाई के लिए अतिरिक्त मेमोरी को पुनरावर्ती कॉल को व्यवस्थित करने की आवश्यकता है। हालांकि, दूसरी ऐसी कॉल को लूप द्वारा प्रतिस्थापित किया जा सकता है, पूंछ की पुनरावृत्ति का अनुकूलन करके, जो गति के मामले में कोई लाभ नहीं दे सकता है, लेकिन उपयोग किए गए अतिरिक्त डेटा के आकार को काफी कम कर देता है। मैंने इस अनुकूलन के साथ Hoar सॉर्ट विकल्प को लागू किया। इसके अलावा, सिस्टम प्रोग्राम में, आप स्टैक पॉइंटर की जांच कर सकते हैं और यदि यह एक महत्वपूर्ण मूल्य पर पहुंचता है, तो आप बस सभी पुनरावर्ती कॉल को रीसेट कर सकते हैं और फिर से छंटनी शुरू कर सकते हैं - इस मामले के लिए यह स्पष्ट है कि आपको त्वरित सॉर्ट विकल्प का उपयोग करने की आवश्यकता है जो लगभग ऑर्डर किए गए डेटा को धीमा नहीं करता है, उदाहरण के लिए। , होर के उपरोक्त प्रस्तावित संस्करण। अतिरिक्त मेमोरी के उपयोग से लड़ना जीसीसी में मानक सी भाषा पुस्तकालय से त्वरित छंटाई का मुख्य विचार माना जा सकता है। यह आमतौर पर पुनरावृत्ति को छोड़ देता है। इसके बजाय, वे उसके अनुकरण का उपयोग करते हैं, जो तीसरे को स्टैक पर लोड को कम करने की अनुमति देता है। कोड लगभग 150 लाइनों के बजाय बड़ा हो गया। इस छँटाई के बारे में अभी भी नीचे कुछ सामग्री होगी।

हैश छांटना बहुत तेज हो सकता है,। N के करीब । हालांकि, कभी-कभी यह द्विघात निर्भरता पर काम कर सकता है। इस छँटाई विधि की गति इनपुट पर बहुत निर्भर है। यदि सहायक सरणी पर डेटा हैश फ़ंक्शन द्वारा समान रूप से वितरित किया जाता है, तो हमें सबसे तेज रैखिक संबंध प्राप्त होता है। और यदि सभी डेटा को अलग-अलग "बड़े पैमाने पर" केंद्रों के पास रखा जाता है या जब कई समान डेटा तत्व होते हैं, अर्थात जब बहुत से हैश टकराव होते हैं, तो हमें सबसे खराब प्रकार ² N ² निर्भरता मिलती है। जैसे पेड़ की छंटाई के साथ, हैश को सॉर्ट करने के लिए, आपको बहुत अतिरिक्त डेटा की आवश्यकता होती है, नीचे दी गई कोड सूची में , उदाहरण के लिए, प्रत्येक छंटनी वाले पूर्णांक (int32, x86-64) के लिए 12 अतिरिक्त बाइट्स। हैश छँटाई का एक दिलचस्प गुण डेटा तत्वों के बीच तुलना संचालन की अनुपस्थिति है, जो इस छंटाई को उन सभी लोगों से अलग करता है जो ऊपर माना जाता है। अधिक सटीक रूप से, ये ऑपरेशन केवल टकरावों के लिए आवश्यक हैं। डेटा को सॉर्ट करते समय जहां कुंजी पूरे डेटा तत्व से मेल खाती है, आप समान तत्वों की संख्या के लिए एक अतिरिक्त काउंटर का उपयोग कर सकते हैं, लेकिन यह एक संदिग्ध अनुकूलन है। आप हैश टक्कर डेटा को संग्रहीत करने के लिए सूची के बजाय बाइनरी ट्री का उपयोग कर सकते हैं, यह बहुत विशेष रूप से व्यक्तिगत मामलों के लिए काम करता है जब कई टकराव होते हैं, लेकिन सामान्य तौर पर, बाइनरी ट्री का उपयोग करते समय, कई मामलों में यह धीमा हो जाता है और इस तथ्य के बावजूद कि इस मामले में तत्व डेटा में लगभग 100 बाइट्स को अतिरिक्त जानकारी संग्रहीत करनी होती है। मैंने बाइनरी ट्री का उपयोग करके हैश छांटने के लिए तीन विकल्प लागू किए हैं : एक अनट्रेडर्ड ट्री का उपयोग करता है, और दूसरे दो मानक स्टैड और स्टेंडर्ड लाइब्रेरी से मानक पेड़ों का उपयोग करते हैं। हैश छँटाई पाठ स्ट्रिंग को छांटने के लिए व्यावहारिक रूप से अनुपयुक्त है, बहुत कम लोगों को छोड़कर, क्योंकि इस तरह के डेटा के लिए एक अच्छा हैश फ़ंक्शन करना असंभव है। मैं छँटाई के लिए मानक C ++ हैश (unordered_multiset) को अनुकूलित नहीं कर सका: मैंने मोनोटोन हैश फ़ंक्शंस का उपयोग करने और समानता के बजाय संबंधों का आदेश देने की कोशिश की - यह काम नहीं किया।

एरियर छंटाई पिछले एक के समान है। एक सहायक सरणी का भी उपयोग किया जाता है, जहां हैश फ़ंक्शन द्वारा मान दर्ज किए जाते हैं। टक्कर की स्थिति में, कब्जे वाले तत्वों के निरंतर टुकड़े को बाएं या दाएं स्थान पर स्थानांतरित करना आवश्यक है, नए तत्व के लिए हैश फ़ंक्शन द्वारा इंगित की गई स्थिति को मुक्त करना। अच्छी गति प्राप्त करने के लिए, यह आवश्यक है कि सहायक सरणी मूल से कई गुना (2-3 से) अधिक हो। सहायक सरणी के आकार में वृद्धि के साथ, गति केवल एक निश्चित सीमा तक बढ़ जाती है, सॉर्ट किए गए डेटा और उनके साथ जुड़े हैश फ़ंक्शन पर निर्भर करता है, और फिर (आमतौर पर 4-5 से) घट जाती है। ऑपरेशन की गति लगभग हैश के समान है, लेकिन अच्छे डेटा पर थोड़ा तेज है, और खराब डेटा पर यह काफी धीमा है। इस तरह की भी अतिरिक्त मेमोरी की आवश्यकता होती है।यदि आप सॉर्ट किए गए एरे में तत्वों की संख्या को चार बिलियन से थोड़ा अधिक तक सीमित करते हैं, तो एक ट्रिपल असिस्टेंट ऐरे को हैश के साथ सॉर्ट करने के लिए उतने ही अतिरिक्त डेटा की आवश्यकता होगी, और एक ट्राइएप्ड को 28 बाइट्स की आवश्यकता होगी, जो एक पेड़ से छांटने के लिए काफी कम है, या एक हैश से बहुत कम है पेड़ों के साथ। तार के साथ काम करने के लिए यह छंटाई भी लगभग अनुपयुक्त है। इस तरह के एक एल्गोरिथ्म के बारे में कोई विकिपीडिया लेख नहीं है, लेकिन यहां मेरा कार्यान्वयन है ।

दिलचस्प रूप से, विकिपीडिया में, एक अच्छे अवलोकन लेख में, सरणी छँटाई और हैश जैसे ऐसे मध्यवर्ती तरीकों का उल्लेख नहीं है, जो स्वाभाविक रूप से तत्वों और तत्वों के पूर्ण मूल्य के आधार पर तुलना करने के तरीकों के बीच रखा जा सकता है।

सबसे तेज़ छँटाई में से एक, जो कभी भी तुलना का उपयोग नहीं करता है, वह है 19 वीं शताब्दी के बाद से ज्ञात बिटवार छँटाई ।(मूलांक क्रमांक)। उसका विचार बहुत सरल है - आपको डेटा प्रतिनिधित्व के बिट्स के समूहों के साथ काम करने की आवश्यकता है (परीक्षणों के लिए मैंने 8, 11 और 16 बिट्स के समूह लिए)। प्रत्येक समूह के लिए तालिकाओं का निर्माण किया जाता है, और फिर परिणामों को अपेक्षाकृत सरल तरीके से संयोजित किया जाता है। बिटवाइज़ छँटाई का उपयोग करने के दो मुख्य तरीके हैं। अंकों को दाएं से बाएं (यह LSD - कम से कम महत्वपूर्ण अंक है) के लिए अंकों को छांटना और बाएं से दाएं तार को छांटना अधिक सुविधाजनक है (यह MSD - सबसे महत्वपूर्ण अंक विकल्प है)। बिटवाइज़ छँटाई अक्सर किसी अन्य डेटा ऑर्डर करने की विधि की तुलना में काफी तेज होती है। हैरानी की बात है, बिटवाइज़ छँटाई के लिए समर्थन अभी भी बहुत महत्वपूर्ण नहीं है: यह न तो बढ़ावा देने में है और न ही मानक सी ++ लाइब्रेरी में, मुझे सी ++ नंबर या तार के साथ काम करने के लिए किसी भी प्रसिद्ध पुस्तकालय के लिए इसके संस्करण के बारे में भी पता नहीं है। इस प्रकार हैबेशक, और नुकसान। यह सॉर्टिंग के लिए डेटा के प्रकार के प्रति बहुत संवेदनशील है, उदाहरण के लिए, आपके पास प्रत्येक आकार के डेटा के लिए इस तरह के सॉर्टिंग का अपना संस्करण होना चाहिए, आपको अहस्ताक्षरित और हस्ताक्षरित पूर्णांक के लिए विशेष विकल्प बनाने की आवश्यकता है, और वास्तविक संख्याओं के साथ काम करने के लिए समर्थन के लिए काफी प्रयास की आवश्यकता हो सकती है। ऑर्डर को कम से कम महत्वपूर्ण बाइट से सबसे महत्वपूर्ण में उपयोग करते समय, इसके संस्करण को आमतौर पर अतिरिक्त मेमोरी की आवश्यकता होती है, प्रारंभिक डेटा के लिए थोड़ा अधिक (यह हैश या एरे द्वारा छंटाई की तुलना में काफी कम है, और एक पेड़ द्वारा और भी अधिक)। इसके अलावा, यह विकल्प लंबे तार छांटने के लिए बहुत कम उपयोग है। इस तरह के लिए मेरा कोडआपको अहस्ताक्षरित और हस्ताक्षरित पूर्णांक के लिए विशेष विकल्प बनाने की आवश्यकता है, और वास्तविक संख्याओं के साथ काम करने के लिए समर्थन के लिए काफी प्रयास की आवश्यकता हो सकती है। ऑर्डर को कम से कम महत्वपूर्ण बाइट से सबसे महत्वपूर्ण में उपयोग करते समय, इसके संस्करण को आमतौर पर अतिरिक्त मेमोरी की आवश्यकता होती है, प्रारंभिक डेटा के लिए थोड़ा अधिक (यह हैश या एरे द्वारा छंटाई की तुलना में काफी कम है, और एक पेड़ द्वारा और भी अधिक)। इसके अलावा, यह विकल्प लंबे तार छांटने के लिए बहुत कम उपयोग है। इस तरह के लिए मेरा कोडआपको अहस्ताक्षरित और हस्ताक्षरित पूर्णांक के लिए विशेष विकल्प बनाने की आवश्यकता है, और वास्तविक संख्याओं के साथ काम करने के लिए समर्थन के लिए काफी प्रयास की आवश्यकता हो सकती है। सबसे महत्वपूर्ण बाइट से ऑर्डर का सबसे महत्वपूर्ण उपयोग करते समय, इसके संस्करण को आमतौर पर अतिरिक्त मेमोरी की आवश्यकता होती है, मूल डेटा की तुलना में थोड़ा बड़ा (यह हैश या एरे द्वारा छांटने के लिए काफी कम है, और एक पेड़ द्वारा और भी अधिक)। इसके अलावा, यह विकल्प लंबे तार छांटने के लिए बहुत कम उपयोग है। इस तरह के लिए मेरा कोडयह विकल्प लंबे तारों को छांटने के लिए उपयुक्त नहीं है। इस तरह के लिए मेरा कोडयह विकल्प लंबे तारों को छांटने के लिए उपयुक्त नहीं है। इस तरह के लिए मेरा कोडयहां , यह उल्लिखित oms7 लेख के कोड पर आधारित है। रिवर्स बाइट ऑर्डर विकल्प अधिक बहुमुखी और बहुत अच्छी तरह से तार छांटने के लिए उपयुक्त है। यह विकल्प अतिरिक्त मेमोरी के उपयोग के बिना लागू किया जा सकता है (इसके लिए कीमत स्थिरता संपत्ति का नुकसान है), जैसा कि bsd लाइब्रेरी के रेडिक्सॉर्ट () फ़ंक्शन में किया जाता है। मेरा कोडइस विकल्प के लिए यह oms7 कोड पर भी आधारित है, यह अतिरिक्त मेमोरी का उपयोग करता है, थोड़ा बड़ा स्रोत डेटा है, इसमें स्थिरता गुण है, लेकिन स्ट्रिंग्स के लिए अनुकूलित नहीं है और इसलिए पहले से उल्लेख किए गए bsd लाइब्रेरी से समान फ़ंक्शन sradixsort () की तुलना में काफी खराब प्रदर्शन विशेषताओं को दर्शाता है। । यह छँटाई छोटे संख्यात्मक सरणियों के साथ काम करते समय आश्चर्यजनक रूप से खराब परिणाम दिखा सकती है, यहां तक ​​कि बुलबुले की तुलना में धीमी गति के कई आदेश काम कर रहे हैं, हालांकि हम कुछ मिलीसेकंड से अधिक नहीं के बहुत छोटे मूल्यों के बारे में बात कर रहे हैं और यह अंतर नोटिस करना आसान नहीं है। यह इस तथ्य के कारण है कि यह छोटे आकार के सहायक सरणियों का उपयोग करता है, लेकिन छोटे आकार के डेटा को सॉर्ट करते समय, ये छोटे आकार सॉर्ट किए गए डेटा से बड़े हो सकते हैं।मंदी से बचने के लिए, "बाएं से दाएं" विकल्प ऐसे मामलों में मुख्य एक के बजाय सम्मिलन छँटाई का उपयोग करता है। अंत में, यह ध्यान देने योग्य है कि यह मेरे लिए एकमात्र अपेक्षाकृत लोकप्रिय छँटाई है जो हमेशा मज़बूती से worth की गति से काम करता हैएन , लेकिन यहां अनुपातिक गुणांक डेटा तत्वों के आकार पर निर्भर करता है और तार या लंबी संख्या के लिए यह काफी ध्यान देने योग्य हो सकता है।

बिटवाइज़ एमएसडी छँटाई के लिए एक विकल्प बीम छँटाई है , एक डेटा संरचना जो आपको कुशलता से एक साहचर्य सरणी की चाबियाँ रखने की अनुमति देती है। मेरा कार्यान्वयन , स्मृति के उपयोग को अनुकूलित करने के बावजूद, फिर भी इसके लिए बहुत लालची निकला। गति द्वारा, लंबी रेखाओं को छांटते समय सर्वोत्तम परिणाम प्राप्त किए गए।

आगे हम कुछ छंटाई पर विचार करेंगे जो मानक पुस्तकालयों में पाई जा सकती हैं।

आइए मानक सी लाइब्रेरी (क्वॉर्ट, जीसीसी का एक प्रकार) से तेजी से एक के साथ शुरू करें, मैंने पहले ही इसके बारे में लिखा था। मैं केवल यहां जोड़ सकता हूं कि यह छंटाई और साथ ही अन्य सी-सॉर्टिंग (उदाहरण के लिए, बीएसडी लाइब्रेरी से निम्नलिखित) ऑब्जेक्ट डेटा के साथ काम करने के लिए अनुपयुक्त हैं, विशेष रूप से, सी ++ स्ट्रिंग्स, जो इस तथ्य के कारण होता है कि ऐसा डेटा POD नहीं है। स्रोत होने पर, नियमित असाइनमेंट के साथ मेम्ची संचालन को प्रतिस्थापित करके समस्या को आसानी से हल किया जा सकता है। आप यह भी देख सकते हैं कि कुछ मानक C पुस्तकालयों में, यह छँटाई आवश्यक रूप से तेज़ नहीं हो सकती है, इसे दूसरों के साथ बदला जा सकता है। जीसीसी के लिए वर्तमान संस्करण में, इस छंटाई में स्थिरता की संपत्ति भी है। डेटा एकत्र करते समय उल्लिखित सी-सॉर्टिंग के साथ कभी-कभी आश्चर्य होता था, उदाहरण के लिए, जब एक कार्यात्मक वस्तु के माध्यम से एसटीडी :: वेक्टर प्रकार के साथ काम करते हैं, तो वे कठिनाइयों का निर्माण कर सकते हैं - मैं सावधानी के साथ ऑब्जेक्ट डेटा के साथ इसका उपयोग करने की सिफारिश कर सकता हूं। रनों के अनुसार, यह छंटाई कभी-कभी अपेक्षाकृत धीमी होती है: यह संख्याओं के साथ काम करते समय तेजी से छंटनी के अन्य कार्यान्वयन के लिए गति में काफी कम है, लेकिन जब सी-स्ट्रिंग्स के साथ काम करना बेहतर होता है, तो केवल दो नियंत्रण बिंदुओं के साथ छंटाई कभी-कभी आगे करनी चाहिए,लेकिन लंबी लाइनों पर, मानक qsort लगभग हमेशा इसे ओवरटेक करता है। सबसे दिलचस्प बात तब पता चली जब मैंने इसकी मदद से एक बिलियन पूर्णांक को सॉर्ट करने की कोशिश की - यह पता चला कि टाइप 7 में भरने से एक द्विघात कानून के करीब समय निर्भरता होती है, यानी कई वर्षों तक चलने वाले संभावित "प्रसंस्करण" के लिए (मैंने अंत की प्रतीक्षा नहीं की और इसे रोक दिया। 21 घंटे की दौड़ में)। कम डेटा के साथ, यह छँटाई आमतौर पर लंगर बिंदुओं का चयन कर सकती है जिसके साथ यह जल्दी से काम करता है।कम डेटा के साथ, यह छँटाई आमतौर पर लंगर बिंदुओं का चयन कर सकती है जिसके साथ यह जल्दी से काम करता है।कम डेटा के साथ, यह छँटाई आमतौर पर लंगर बिंदुओं का चयन कर सकती है जिसके साथ यह जल्दी से काम करता है।

इंट्रोस्पेक्टिव छंटाई का उपयोग C ++ मानक पुस्तकालय में किया जाता है, हालांकि std :: सॉर्ट में उपयोग की जाने वाली सटीक विधि कार्यान्वयन पर निर्भर करती है, केवल GCC पर जानकारी प्रदान की जाती है। रनों के अनुसार, संख्याओं के साथ काम करते समय प्रसार छँटाई के बाद यह दूसरा सबसे तेज़ है, और प्रसार छँटाई का लाभ छोटा है (लगभग 0 से 30% तक), लेकिन स्ट्रिंग छँटाई के साथ सब कुछ बहुत बुरा है - यह नेताओं की तुलना में 3-4 गुना कम हो सकता है । यह वास्तव में एक त्वरित सॉर्ट है, जिसमें दो विशेष मामलों को ध्यान में रखा जाता है: 1) यदि रिकर्स की संख्या बहुत बड़ी हो गई है, तो हीप द्वारा छांटने पर स्विचिंग होती है; 2) यदि छँटाई के लिए तत्वों की संख्या छोटी है, तो आवेषण द्वारा छंटनी पर स्विच करना होता है।

C ++ मानक लाइब्रेरी ( std :: स्थिर_sort) से स्थिर छँटाई), जैसा कि नाम से पता चलता है, स्थिरता की संपत्ति है - यह एक ही कुंजी के साथ तत्वों के बीच सापेक्ष आदेश को संरक्षित करता है। यह संपत्ति अपेक्षाकृत दुर्लभ रूप से आवश्यक है, हालांकि मैं इसके बारे में लिखता हूं बल्कि निराधार हूं, केवल अपने अनुभव के आधार पर। यह अतिरिक्त मेमोरी का उपयोग कर सकता है, जो इसे तेज बनाता है। हैरानी की बात है कि यह छँटाई अक्सर std :: sort की तुलना में तेज़ होती है।

सुपर-लोकप्रिय भाषा अजगर में, टिम की छंटाई मानक के रूप में उपयोग की जाती है । परीक्षणों के लिए, मैंने इसके संस्करण का उपयोग जीथब रिपॉजिटरी से किया। यह आंशिक रूप से ऑर्डर किए गए डेटा पर रिकॉर्ड-ब्रेकिंग अच्छे परिणाम दिखाता है, लेकिन औसतन यह अभी भी नेताओं की तुलना में धीमा है। आमतौर पर इसकी गति तेज छंटाई और शैल छंटाई के बीच औसत होती है, हालांकि तर्ज पर यह कभी-कभी नेताओं के करीब होती है। इसमें स्थिरता का गुण होता है। यह एक अपेक्षाकृत जटिल एल्गोरिथ्म को लागू करता है, जिसके मानक कार्यान्वयन में 2015 में एक त्रुटि की खोज की गई थी, जिसे हालांकि, इसके प्रकटन के लिए एक अवास्तविक स्थिति की आवश्यकता होती है।

BSD C लाइब्रेरी में बिटवाइज़ सॉर्टिंग ( मूलांक) है) और इसका स्थिर संस्करण (sradixsort)। दुर्भाग्य से, इन दोनों प्रकारों का उपयोग केवल सी-स्ट्रिंग्स के लिए किया जा सकता है। जैसा कि परीक्षण डेटा से देखा जाएगा, यह आज स्ट्रिंग्स को सॉर्ट करने का सबसे तेज़ तरीका है, और इसलिए यह आश्चर्यजनक है कि सी ++ स्ट्रिंग्स के लिए कोई मानक विकल्प नहीं है।

बीएसडी सी पुस्तकालय अधिक प्रकार है मर्ज ( mergesort)। यह सॉर्टिंग अनुक्रमिक एक्सेस डेटा (फ़ाइलों, सूचियों) के लिए सबसे तेज़ में से एक के रूप में जाना जाता है और संभवतः सी ++ मानक लाइब्रेरी में छंटनी सूचियों (एसटीडी :: सूची और एसटीडी :: फॉरवर्ड_लिस्ट) के लिए उपयोग किया जाता है। वैसे, वह 1948 से जानी जाती थी और इसके डेवलपर्स में से एक पहले कंप्यूटर सिस्टम वॉन न्यूमैन में एक बहुत ही प्रसिद्ध गणितज्ञ और विशेषज्ञ थे। त्वरित तरीकों में से, यह छंटाई सर्वोत्तम विशेषताओं द्वारा प्रतिष्ठित नहीं है, हालांकि, एक नियम के रूप में, यह शेल विधियों की तुलना में कुछ तेज है। इसके लिए अतिरिक्त मेमोरी की आवश्यकता होती है और इसे आमतौर पर टिकाऊ रूप से लागू किया जाता है।

इसके अलावा, वहाँ अभी भी एक गुच्छा द्वारा छँटाई है (heapsort). , . , . ( 3-6 ) , , , ( ) .

C++. : (std::make_heap) ( std::sort_heap)। यहाँ, bsd लाइब्रेरी के विपरीत, छँटाई केवल संचालन के लिए ढेर में से एक है। आमतौर पर, यह छंटनी विकल्प पिछले एक की तुलना में थोड़ा तेज होता है (bsd विकल्प केवल कम संख्या और लंबी एस-लाइनों पर बेहतर परिणाम दिखाता है)।

मानक C ++ लाइब्रेरी का उपयोग करके, आप बाइनरी संतुलित पेड़ (std :: multiset) को सॉर्ट कर सकते हैं - बस पेड़ को भरें और फिर चारों ओर जाएं। इस पद्धति को गैर-पुनरावर्ती त्वरित प्रकार माना जा सकता है। कुछ समस्या इस तथ्य में उत्पन्न होती है कि मानक स्मृति आवंटन धीमी होने के लिए उल्लेखनीय है, इसलिए सर्वोत्तम परिणामों के लिए आपको अपने स्वयं के आवंटनकर्ता का उपयोग करने की आवश्यकता होती है, जो लगभग 10-30% की गति देता है। यह भी ध्यान दिया जा सकता है कि इस तरह की विधि के लिए प्रत्येक डेटा तत्व के लिए जी ++ के साथ बहुत अधिक अतिरिक्त मेमोरी की आवश्यकता होती है, इसके अलावा, आपको 32 बाइट्स (x86-64 आर्किटेक्चर पर) को स्टोर करने की भी आवश्यकता है - ऐसे पेड़ को एक गुच्छा के रूप में संग्रहीत करने की कोशिश करना दिलचस्प होगा, अर्थात बिना अतिरिक्त। बाइट्स। यदि आप बढ़ावा :: कंटेनर :: मल्टीसेट का उपयोग करते हैं, तो आपको कम मेमोरी की आवश्यकता होती है: प्रति डेटा तत्व केवल 24 अतिरिक्त बाइट्स। हालांकि, बढ़ावा की तरह,और मानक पुस्तकालय ने एक अप्रिय आश्चर्य दिखाया - इस प्रक्रिया में उन्हें कभी-कभी अधिक स्मृति की आवश्यकता होती थी। शायद यह बाइनरी पेड़ों के संतुलन के कारण है। कोड -यहाँ ।

बूस्ट लाइब्रेरी का फैलाव है , एक एल्गोरिथ्म जो 21 वीं सदी में आविष्कार किया गया था। यह सबसे प्रसिद्ध समग्र विधि है जो आज भी प्रसिद्ध पुस्तकालयों में उपलब्ध है। यह सॉर्टिंग कुछ बिटवाइज़ विचारों का उपयोग करता है और जैसे, यह तर्क के प्रकार के बारे में काफी मूडी हो सकता है। आमतौर पर यह छँटाई रिकॉर्ड परिणाम दिखाती है, कभी-कभी निकटतम प्रतियोगियों की तुलना में काफी बेहतर होती है। एकमात्र अपवाद सी-लाइनों की छंटाई है, जहां यह bsd लाइब्रेरी से बिटवाइज़ विधियों के लिए काफी नीच है। लंबी सी-लाइनों को सॉर्ट करते समय, यह अन्य तरीकों से नीच हो सकता है, उदाहरण के लिए, दो एंकर बिंदुओं के साथ स्पिन-सॉर्टिंग या त्वरित सॉर्टिंग। फैल छँटाई (बूस्ट v1.62) एक बहुत बुरा समस्या दिखाया- छोटे (1000 तत्वों तक) सी-स्ट्रिंग सरणियों को छांटने पर, यह त्रुटियों के साथ काम करता है।

एक नया pdqsort एल्गोरिथ्म भी है जो लेखक द्वारा बताई गई, आत्मनिरीक्षण छँटाई में सुधार करता है। यह नया एल्गोरिथम, जिसका विकिपीडिया पर अभी तक वर्णन नहीं किया गया है। इसके परिणाम - यद्यपि बुरा नहीं है, लेकिन विशेष रूप से प्रभावशाली नहीं है। यह std की तुलना में धीमा है: छोटे पूर्णांकों पर क्रमबद्ध, लेकिन तार और लंबे पूर्णांकों पर तेजी से। दोनों मामलों में, अंतर नगण्य है। इस छँटाई के लिए सबसे अच्छा परिणाम लंबे सी ++ स्ट्रिंग्स के लिए प्राप्त किया गया था - यहाँ यह हीन है, हालांकि ध्यान देने योग्य है, केवल नेता के लिए, प्रसार-छँटाई।

बढ़ावा देने में आप अभी भी Spinsort पा सकते हैं। यह भी एक नया एल्गोरिथ्म है, जो पिछले एक के विपरीत, स्थिरता की संपत्ति है और जिसे विकिपीडिया पर अभी तक वर्णित नहीं किया गया है। आमतौर पर वह नेता के करीब होता है, लेकिन उसके पीछे ध्यान देने योग्य अंतराल के साथ। इसकी आवश्यकता है, हालांकि बहुत अधिक नहीं, अतिरिक्त मेमोरी। चलो उसी बढ़ावा पुस्तकालय से flat_stable_sort के

साथ समाप्त होते हैं । यह एक और नया मजबूत एल्गोरिथ्म है जो अभी तक विकिपीडिया पर वर्णित नहीं है। यह अब तक का सबसे तेज़ तरीका है, लेकिन अधिकांश अन्य तेज़ लाइब्रेरी तरीकों से थोड़ा कम है। यह बहुत कम अतिरिक्त मेमोरी का उपयोग करता है (हालांकि, इसे हमेशा 8 केबी के एक निश्चित आकार की तालिका की आवश्यकता होती है) और शेल विधि की तुलना में अक्सर उल्लेखनीय है। तालिका

पर विचार करेंसमय (ms में) एक AMD Phenom ™ II X4 955 @ 3.214 मेगाहर्ट्ज प्रोसेसर के साथ 8 जीबी रैम वाले कंप्यूटर पर इन एल्गोरिदम के संचालन के लिए। कंप्यूटर ने कई महीनों तक काम किया, और तालिकाओं के साथ भरी हुई दो जोंस फाइलों में एकत्रित डेटा का कुल आकार लगभग 400 KB है। टाइमिंग को रनों की संख्या के औसत से दिया जाता है; छोटे आकार के लिए, ये रन बड़े थे। अधिक जटिल तरीके से कैश के साथ काम करने से गणना की गति में परिवर्तन होता है, इसलिए प्राप्त किए गए परिणाम केवल लगभग अनुमानित होते हैं (मैं मान सकता हूं कि समय की अशुद्धि 20% तक पहुंच सकती है)। मेरा मानना ​​है कि पीसी के लिए सर्वश्रेष्ठ आधुनिक प्रोसेसर पर, परिणाम 2-3 गुना तेजी से प्राप्त किया जा सकता है, लेकिन ध्यान रखें कि कई और आधुनिक प्रोसेसर विभिन्न आवृत्तियों के बीच स्विच करके काम करते हैं और उनके साथ प्राप्त परिणाम,और भी अधिक अनुमानित होगा।

यह और निम्न तालिका इंटरैक्टिव हैं। समय के पूर्ण मूल्यों के अलावा, आप औसत, औसत, न्यूनतम और अधिकतम के सापेक्ष उनके मूल्यों को भी देख सकते हैं। आप वर्णों में सटीकता बदल सकते हैं। आप विभिन्न प्रकार के भरावों और डेटा प्रकारों के लिए समयबद्ध संबंध भी प्राप्त कर सकते हैं। उदाहरण के लिए, बाद वाला, यह दिखा सकता है कि सी-स्ट्रिंग्स को क्रमबद्ध करना सी ++ स्ट्रिंग्स की तुलना में काफी तेज है। छंटाई के तरीकों से, आप विभिन्न प्रकार के सबसेट का चयन और संयोजन भी कर सकते हैं। आप निश्चित रूप से, किसी भी कॉलम के अनुसार सेट कर सकते हैं। दुर्भाग्य से, मैं हब पर लेख में जावास्क्रिप्ट का उपयोग करने का तरीका नहीं जानता, इसलिए तालिकाओं केवल संदर्भ द्वारा उपलब्ध हैं। मामले के लिए अगर imtqy.com ओवरलोडेड है, तो मैं पहली और दूसरी टेबल पर बैकअप लिंक भी देता हूं ।

समय को मिलीसेकेंड में मापा जाता है, लेकिन समय की निर्भरता के कानून में, बहुत छोटे गुणांक से बचने के लिए, माइक्रोसेकंड के लिए सूत्र दिए जाते हैं। इस प्रकार, यदि हम सूत्र में एन के लिए मान को प्रतिस्थापित करते हैं , तो परिणाम को तालिका से संबंधित एक के करीब संख्या प्राप्त करने के लिए 1000 से भी विभाजित किया जाना चाहिए। समय पर निर्भरता का नियम प्राप्त परिणामों के आधार पर दो परिणामों की तुलना से लिया जाता है (आमतौर पर चरम लोगों को लिया जाता है)। आप आउटपुट से वास्तविक मूल्य के सापेक्ष विचलन के विकल्प का उपयोग करके व्युत्पन्न कानून की गुणवत्ता की जांच कर सकते हैं।

इस तालिका के परिणामों से कुछ सामान्य निष्कर्ष:

• 10 मिलियन तत्वों तक के डेटा पर सबसे अच्छा शेल प्रकार टिमर्ट और यहां तक ​​कि कुछ त्वरित प्रकारों से आगे निकल सकता है;
• टाइमसॉर्ट गति क्सोर्ट (क्लिब) में बहुत करीब है, कभी-कभी कुछ आगे निकल जाता है, और कभी-कभी इसके विपरीत;
• हीप्सोर्ट और विशेष रूप से ट्रीसॉर्ट अक्सर ध्यान से धीमा हो जाते हैं, लेकिन एक बुलबुले या यहां तक ​​कि एक विकल्प की पृष्ठभूमि के खिलाफ, यह स्पष्ट है कि ये अभी भी त्वरित तरीके हैं। दिलचस्प है, इन दोनों तरीकों में अक्सर बहुत समान विशेषताएं होती हैं - वे दोनों पेड़ बनाते हैं। यह नोटिस करना आसान है कि हीप्सोर्ट और ट्रीसॉर्ट के लिए निर्भरता, हालांकि स्पष्ट रूप से द्विघात नहीं है, स्पष्ट रूप से एन लॉग एन नहीं हैं , लेकिन बहुत बुरा है - शेल छंटाई के साथ तुलना करें, जो हेप्सोर्ट या ट्रीसॉर्ट की तुलना में डेटा की मात्रा बढ़ाने के साथ बेहतर व्यवहार करता है, जबकि कि वह स्वयं N लॉग एन से धीमी है । इस प्रकार, ढेर और पेड़ों की छँटाई के व्यावहारिक कार्यान्वयन उनके सैद्धांतिक विनिर्देशों से मेल नहीं खाते हैं;
• तार छँटाई पर डेटा से पता चलता है कि यहाँ समय निर्भरता के नियम संख्याओं के लिए समान नहीं हैं - छंटनी की लंबाई जो किसी तरह से इन कानूनों पर आरोपित हैं। मैं, दुर्भाग्य से, ज्ञात छंटाई के लिए सूत्र नहीं जानता हूं जो स्ट्रिंग्स के साथ काम करते समय समय की निर्भरता के सटीक कानून देगा;
• यह दिलचस्प है कि वास्तविक संख्याओं के साथ काम करने की गति पूर्णांक संख्याओं के समान है - यह इस तथ्य का परिणाम है कि आधुनिक x86 वास्तुकला में स्टैक के साथ काम करने के लिए बहुत प्रभावी अनुकूलन किए गए हैं;
• hash_sort ने काफी औसत दर्जे के परिणाम दिखाए, यह इस तथ्य के कारण संभव है कि अतिरिक्त मेमोरी के उपयोग के कारण प्रोसेसर कैश का प्रदर्शन तेजी से घटता है। छोटे यादृच्छिक डेटा (एक सौ हजार से कम तत्वों) पर हैश छँटाई सबसे अच्छे प्रकार से आगे निकल जाती है। आप यह भी देख सकते हैं कि यह फिर से संभव है क्योंकि कैश के कारण, इस छंटाई के कुछ परिणाम बहुत ही अजीब हैं, उदाहरण के लिए, आंशिक रूप से आदेशित भरने का उपयोग करते समय 10 ⁵ , 10 ⁶ और 10 ⁷ 32-बिट पूर्णांक लगभग समान के लिए क्रमबद्ध हैं। समय! लगभग किसी प्रकार का क्वांटम प्रभाव। :) मुझे यकीन है कि यदि आप खोज करते हैं, तो आप परिणामों को समझाने के लिए अन्य मुश्किल पा सकते हैं।

मैं कुछ विशेष मामलों पर कुछ और निष्कर्ष जोड़ूंगा:

• कुछ प्रकार के डेटा पैडिंग क्विकॉर्ट्स में कमजोरियों को प्रकट करते हैं। हालांकि, एक जटिल तरीके से एक समर्थन तत्व की पसंद व्यावहारिक रूप से शून्य को छांटने के लिए एक खराब अनुक्रम में गिरने की संभावना बनाता है। आप प्रत्येक पास पर अलग-अलग तरीके से या बेतरतीब ढंग से एक समर्थन तत्व का चयन कर सकते हैं। शायद वे क्यूसॉर्ट (क्लिब) में ऐसा करते हैं। विचाराधीन होरे विधि केवल विशेष रूप से डिज़ाइन किए गए अनुक्रमों पर बहुत धीरे-धीरे काम करती है, जो व्यावहारिक कार्य के दौरान संयोग से सामने आती हैं - यह 2 ^{एन -3} / एन ^एन की संभावना के साथ एक मामला है, जो कि लगभग पूरी तरह से असंभव घटना है। यद्यपि यदि हम उन दृश्यों पर विचार करते हैं जिन पर होर विधि धीरे-धीरे संभव नहीं होती है, लेकिन केवल एक महत्वपूर्ण मंदी के साथ, तो ऐसे और भी बहुत से मामले हैं, जो, हालांकि, अस्वीकार्य रूप से धीमी गति से डाटा प्रोसेसिंग मामले की संभावना को व्यावहारिक रूप से छोड़ देता है, यद्यपि इसके अंतर से बहुत कष्टप्रद है। शून्य। द्विघात नियंत्रण के अनुसार, गलती से डेटा प्राप्त करना लगभग असंभव है, जिस पर दो नियंत्रण बिंदुओं के साथ तेजी से छंटनी धीरे-धीरे काम करेगी। लोम्यूटो के बिना और बिना समर्थन तत्व के त्वरित प्रकार के विकल्प लगभग सभी विशेष भरण मामलों पर बहुत खराब परिणाम दिखाते हैं;
• कुछ विशेष मामलों में, सबसे धीमी "बुलबुला" छँटाई उत्कृष्ट परिणाम देती है, और कुछ सबसे तेज़, त्वरित-छँटाई, इसके विपरीत, बहुत खराब है;
• हैश सॉर्टिंग ने टाइप 8 और 9 के फिलिंग पर बहुत बुरा परिणाम दिखाया, इसका कारण यह है कि नीरस अनुक्रम लगातार मूल्यों से लिया जाता है, छोटे से शुरू होता है, और यादृच्छिक संख्या का 1% निचले से अधिकतम मूल्य तक की सीमा से लिया जाता है, जो सभी 99% डेटा को लगातार भरता है। एक हैश तत्व में। यह मामला बहुत अच्छी तरह से उन समस्याओं को प्रदर्शित करता है जो इस सॉर्टिंग का उपयोग करते समय उत्पन्न हो सकती हैं या अज्ञात डेटा के साथ एक सरणी के साथ छंटनी कर सकती हैं;
• चयन सॉर्टिंग सभी प्रकार के भरने पर बहुत सख्ती से व्यवहार करता है, ढेर-और पेड़ों की छंटाई भी स्पष्ट चोटियों और डिप्स के बिना काफी स्थिर होती है। यह सही है, ज़ाहिर है, शेल प्रकारों के लिए, साथ ही साथ मानक पुस्तकालयों से अधिकांश अन्य त्वरित तरीके।

अब छंटाई एल्गोरिदम के साथ उपयोग किए जाने वाले डेटा प्रकारों के बारे में बात करने का समय है:

1. पूर्णांक 32-बिट पर हस्ताक्षर किए (int32_t), लेकिन केवल गैर-नकारात्मक का उपयोग किया गया था। अन्य संख्यात्मक आंकड़ों को भी केवल गैर-नकारात्मक लिया गया - इससे परिणामों की व्यापकता कम नहीं होती है, लेकिन कुछ एल्गोरिदम के लिए उन्हें प्राप्त करना बहुत आसान हो जाता है;
2. पूर्णांक, 64-बिट हस्ताक्षरित (int64_t);
3. पूर्णांक, 128-बिट हस्ताक्षरित (__int128 - कम से कम GCC द्वारा समर्थित);
4. पांच पूर्णांक (int32_t) की संरचनाएं, जिनमें से एक कुंजी (INT1P4) के रूप में उपयोग की जाती है। इस तरह के डेटा को सॉर्ट करते समय, क्रमपरिवर्तन की संख्या कम्प्यूटेशनल समय को अधिक प्रभावित करने लगती है; इसलिए, कम क्रमपरिवर्तन वाले तरीकों से कुछ लाभ होता है;
5. वास्तविक संख्याएं जैसे कि दोहरी परिशुद्धता, डबल (फ्लोट संख्या);
6. शॉर्ट स्ट्रिंग्स C ++ और C. स्ट्रिंग्स को 1 से 16 तक लिया गया (स्ट्रिंग्स शॉर्ट और सी-स्ट्रिंग्स शॉर्ट);
7. मध्यम लंबाई के तार सी और सी ++, जिनमें से लंबाई 1 से 256 (तार और सी-तार) है;
8. लंबी लाइनें C और C ++, जिसकी लंबाई 1 से 2 ²⁰ (यह एक मिलियन से थोड़ी अधिक है), और लाइनें चुनी जाती हैं ताकि उनकी औसत लंबाई 512 से अधिक न हो, इसलिए लाइनों को केवल यादृच्छिक भरने के लिए चुना गया था, अन्य मामलों के लिए, लाइनें बस ली गई थीं लंबाई 1 से 512 (लंबे और सी-तार लंबे)।

और सॉर्टिंग के लिए स्रोत सरणी कैसे भरें, इसके बारे में भी:

1. संयोग से;
2. सख्ती से आरोही (आदेशित);
3. सख्ती से उतरते (रिवर्स ऑर्डर, उलट);
4. यादृच्छिक मान 0 से 99 तक (छोटे भिन्नता, कम भिन्नता 100);
5. 0 और 1 के यादृच्छिक अनुक्रम (छोटे भिन्नता, कम भिन्नता 2);
6. निरंतर 0 (छोटे प्रसार, कम भिन्नता 1);
7. अनुक्रम सबसे धीमी निष्पादन के लिए qsort (Hoare) संस्करण का नेतृत्व करता है। यह उत्सुक है कि लंबाई एन के सभी अनुक्रमों के बीच बिल्कुल 2 ^{एन -3} ऐसे अनुक्रम हैं;
8. सख्ती से आरोही, 1% यादृच्छिक संख्या (आंशिक रूप से आदेशित) के सम्मिलन के साथ;
9. सख्ती से उतरते हुए, 1% यादृच्छिक चर (आंशिक रूप से उलट) के सम्मिलन के साथ।

इस बात पर जोर दिया जाना चाहिए कि यादृच्छिक डेटा किसी सरणी को भरने का सबसे विशिष्ट मामला है, अन्य सभी विधियां अत्यंत दुर्लभ हैं और यहां तक ​​कि किसी विशेष के सामान्य संचालन के दौरान लगभग असंभव हैं।

आइए परीक्षा परिणामों को देखें, जहां छंटनी सभी संभव डेटा अनुक्रमों के साथ काम करती है। ऐसे अनुक्रमों की संख्या उनकी लंबाई के भाज्य के बराबर है, इसलिए, लंबाई 12 के अनुक्रमों के लिए 479'001'600 संस्करण हैं - एक अच्छा आधुनिक पीसी एक मिनट से भी कम समय में उनकी संख्या की गणना करेगा। यदि हम 14 की लंबाई के अनुक्रम लेते हैं, तो हमें कई घंटों के कंप्यूटर संचालन के लिए पहले से ही 87'178'291'200 वेरिएंट मिलते हैं। इसलिए, निम्न तालिका एक क्रमबद्धता के आरडीसीटी अनुदेश के माध्यम से प्राप्त औसत समय (प्रोसेसर चक्रों में) को दिखाती है जब सभी क्रमपरिवर्तन केवल 12. तक छँटाई करते हैं। डेटा में, पिछले संख्यात्मक प्रकार और छोटे तार लिए जाते हैं। बेशक, कोई यह नोटिस कर सकता है कि दोहराए जाने वाले तत्वों के साथ दृश्यों पर विचार नहीं किया जाता है। हालांकि, मैंने यह सुझाव देने का साहस किया कि उनकी उपस्थिति गुणात्मक रूप से परिणामों को नहीं बदलेगी, लेकिन उनकी प्राप्ति को धीमा कर सकती है।

इस तरह के छोटे डेटा के लिए परिणाम बहुत प्रतिनिधि नहीं हैं, और विशेष रूप से जटिल छंटाई के तरीकों के लिए, लेकिन वे अभी भी छंटनी व्यवहार के विचार के पूरक हैं। कुछ प्रकार, जहां तक ​​मुझे पता है, छोटे सरणियों के साथ काम करते समय अपने मुख्य एल्गोरिथ्म को दूसरे के साथ बदलें - ये फैले हुए प्रकार हैं, दो एंकर बिंदुओं और रेडिक्स_एमएस (अंतिम दो उपयोग आवेषण) के साथ तेजी से। और कुछ सॉर्टिंग (फ्लैट_स्टेबल और मूलांक) छोटे तालिकाओं का उपयोग करते हैं, लेकिन छोटे डेटा आकारों के साथ, ये तालिकाएं डेटा की तुलना में बहुत बड़ी हो जाती हैं, जो दूसरों की तुलना में इन विधियों को धीमा कर देती हैं और अजीब परिणाम पैदा करती हैं। अजीब परिणाम अन्य बिटवाइज़ सॉर्टिंग और हैश और सरणी सॉर्टिंग के साथ भी प्राप्त होते हैं। इस तरह के असामान्य परिणामों को इस तथ्य से आसानी से समझाया जाता है कि छोटे डेटा के लिए इन तरीकों की छँटाई करने से पहले डेटा के लिए तैयारी का समय छँटाई के समय से अधिक लंबा होता है। बेशक, ऐसे छोटे समय अंतराल (नैनोसेकंड) को मापते समय, प्रदर्शित कानून पर विभिन्न त्रुटियों का प्रभाव पिछली तालिका की तुलना में बहुत अधिक है। इसलिए, कानून बहुत अधिक अनुमानित थे, अक्सर "अत्यधिक बहाव के साथ" अतिरंजित मूल्यों के लिए। उत्तरार्द्ध को आंशिक रूप से इस तथ्य से समझाया जाता है कि छोटे डेटा के साथ काम करते समय छंटाई का समय खुद ही समय को मापने के लिए सॉर्टिंग फ़ंक्शन और कई आवश्यक सहायक संचालन को कॉल करने के समय के बराबर हो जाता है। कार्यक्रम आउटपुट से नामित ओवरहेड को घटाने की कोशिश करता है, लेकिन यह लगभग नहीं बल्कि बाहर किया जाता है। इस सब के साथ, मैं यह मानने की हिम्मत करता हूं कि विभिन्न प्रकार के डेटा के परिणामों की तुलना करके और किए गए टिप्पणियों को ध्यान में रखते हुए, आप कभी-कभी ऐसी धारणाएं बना सकते हैं जो सटीक से बहुत दूर नहीं हैं।

अंत में, एक अन्य तालिका जो दिखाती है कि अतिरिक्त मेमोरी को छांटने के लिए विभिन्न परीक्षण विधियों की कितनी आवश्यकता है। जाहिर है, यह मान सिस्टम पर निर्भर करता है। मेरे परीक्षणों में, जैसा कि मैंने पहले ही लिखा था, यह x86-64, GCC है। इसमें अक्षर T का अर्थ है बाइट्स में प्रकार का आकार (स्ट्रिंग की लंबाई इस आकार में शामिल नहीं है: C- लाइनों के लिए यह सूचक का आकार है, C ++ लाइनों के लिए यह विवरणक का आकार है, x86-64 GCC के लिए 32 बाइट्स), पत्र L मध्य है बाइट्स में प्रकार की लंबाई (संख्याओं के लिए यह टी है, और तार के लिए यह स्ट्रिंग की औसत लंबाई है), अक्षर ए में मान 1 या 0 हो सकता है - यह 64-बिट सीमा के लिए संरेखण है, और पत्र एम मानक मेमोरी आवंटन से संरेखण है (यह मान लिया गया है) 32-बाइट सीमा से संरेखित करता है)। ^* प्रतीक का अर्थ है कि इस प्रकार की छंटाई के लिए डेटा केवल VmRSS फ़ील्ड को / proc / PID / स्थिति से पढ़ने के विश्लेषण के आधार पर प्राप्त किया गया था (उल्लिखित फ़ील्ड प्रक्रिया कार्यक्रम का आकार है)।


निस्संदेह, अन्य छंटाई विधियां, आदिम और तेज दोनों हैं। बूस्ट लाइब्रेरी में समानांतर एल्गोरिदम हैं जो आपको सिस्टम में अतिरिक्त प्रोसेसर कोर की उपस्थिति का लाभ उठाने की अनुमति देते हैं। आप स्वयं-ऑर्डर करने वाले कंटेनर बूस्ट का उपयोग भी कर सकते हैं :: कंटेनर :: std के बजाय flat_multiset :: मल्टीसेट, लेकिन यह बहुत धीरे-धीरे काम करता है।

मैं सामान्य रूप से बूस्ट लाइब्रेरी के बारे में कुछ टिप्पणी कहने का अवसर लेता हूं। मेरा सुझाव है कि इससे न गुजरें। यहां तक ​​कि एक नियम के रूप में, मानक पुस्तकालय में जो विशेषताएं हैं, वे बेहतर तरीके से लागू की जाती हैं, और कभी-कभी (उदाहरण के लिए, नियमित अभिव्यक्ति की तरह) बहुत बेहतर होती हैं। यदि हम कंटेनरों के बारे में बात करते हैं, तो बढ़ावा देने में वे काफी हद तक बड़े होते हैं, और जो मानक के साथ मेल खाते हैं वे कभी-कभी कुछ तेज होते हैं और अक्सर छोटे, लेकिन अच्छे सुधार होते हैं। बूस्ट चेक अधिक अच्छी तरह से टाइप करते हैं, जो कभी-कभी लगभग मायावी त्रुटियों का पता लगाने में मदद कर सकते हैं जो आमतौर पर खुद को प्रकट नहीं करते हैं, लेकिन कुछ परिस्थितियों में अप्रत्याशित रूप से सक्रिय हो सकते हैं। इस पुस्तकालय से कई निर्माणों पर संकलन त्रुटियों के बारे में बढ़ावा देने के नुकसानों में बिना शर्त पूरी तरह से अपठनीय और विशाल संदेश शामिल हैं - यह, हालांकि कुछ हद तक, मानक पुस्तकालय पर लागू होता है। C ++ डेवलपर्स के लिए इस बारे में कुछ करने का समय आ गया है।

परीक्षण और कुछ अन्य संबंधित सामग्री वाली सभी फाइलें मेरे भंडार से ली जा सकती हैं। यदि कोई व्यक्ति कच्चे स्रोत डेटा में रुचि रखता है, तो आप इसे यहां प्राप्त कर सकते हैं (1.4 एमबी)। मुझे किसी भी टिप्पणी, आलोचना और परिवर्धन की खुशी होगी।