"5 सेंट" सॉर्ट्स के बारे में बात करने के लिए

विषय की निरंतरता में मैं अपना कोड साझा करना चाहता हूं, जो GNU C ++ लाइब्रेरी के वर्तमान संस्करणों से std::sort() को ओवरटेक std::sort() और (लगभग, कोई सटीक डेटा नहीं है) CppCon 2019 के साथ "Sort Alexandrescu" के परिणाम को दोहराता है।

टास्क की शर्तें

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

परिणाम

उपलब्ध जानकारी के अनुसार, एल्गोरिदम और कार्यान्वयन सुविधाओं का यह संयोजन व्यावहारिक अर्थों में कई अन्य विकल्पों की तुलना में तेज़ है:

• तुलना और चाल की संख्या (गणना और असाइनमेंट की गणना के लिए C++ वर्ग को प्रतिस्थापित करके मापा जाता है)।
• मशीन कोड की मात्रा से (कैश में बहुत कम जगह लेता है)।
• स्रोत कोड की मात्रा और इसकी पारदर्शिता से।
• SORT_THRESHOLD के आधार पर, लंबे यादृच्छिक क्रम में, लाभ 3-5% तक हो जाता है।
• आदेश या मुख्य रूप से आदेशित डेटा के साथ 1.5-2-3 गुना तेज़ी तक।
• रिवर्स ऑर्डर में केवल बहुत कम दृश्यों पर मामूली नुकसान।

यह बहुत संभावना है कि यह विकल्प विशाल बहुमत की तुलना में थोड़ा तेज और / या थोड़ा धीमा है, लेकिन यह पता लगाना शाब्दिक रूप से एक टाइटैनिक काम है जिसे मैं बर्दाश्त नहीं कर सकता।

यह दिलचस्प है अगर कोई इस विकल्प की तुलना टारनटूल, पोस्टग्रेक्यूएल, SQLite और MySQL में वर्तमान विकल्पों के साथ करता है। मुझे उम्मीद है कि कामोस अपने SysBench के साथ पास नहीं कर पाएगी ।

अलेक्जेंड्रेस्कु कैसे है?

RPG18 से पहली टिप्पणी में , आंद्रेई अलेक्जेंड्रेस्कु द्वारा हाल के प्रदर्शन का एक लिंक था "स्पीड इज़ इन माइंड्स ऑफ पीपल" , जहां वह काफी हद तक एक समान विचार की ओर जाता है, लेकिन अंतिम के करीब heap_sort जाता है।

प्रदर्शन मुझे थोड़ा लंबा लग रहा था (यदि ऑलीगबिन ने कम से कम एक बार 90 मिनट दिए हों ...), लेकिन संख्या पर्याप्त नहीं है। विशेष रूप से, मैं बढ़ते N साथ छंटनी का व्यवहार देखना चाहता हूं, क्योंकि क्विकॉर्ट पूरा होने की सीमा में वृद्धि बड़े आकार में त्वरण और छोटे लोगों के लिए मंदी आदि की ओर जाता है।

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

वैचारिक पक्ष

"एल्गोरिथ्म" का सैद्धांतिक और वैचारिक पक्ष काफी सरल है:

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

यह ध्यान देने योग्य है कि प्रोसेसर वास्तुकला और आवेदन की स्थिति के आधार पर, आप SORT_THRESHOLD भीतर SORT_THRESHOLD चुनकर 10-15% तक लंबे अनुक्रमों पर लाभ बढ़ा सकते हैं। हालांकि, यह रिवर्स ऑर्डर के साथ अनुक्रमों के प्रसंस्करण को धीमा कर देता है और इसके करीब है।
फिर भी, यह एक अच्छा बोनस है यदि आप समझते हैं कि रिवर्स ऑर्डर आपके डेटा में संभावना नहीं है, या यदि आप सस्ते में ऐसे मामलों का पता लगा सकते हैं और एक छोटे SORT_THRESHOLD साथ एक शाखा निष्पादित कर सकते हैं।

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