📱 〰️ 😑 बिटवाइज़ एलएसडी सॉर्ट (रेडिक्स सॉर्ट) 🙎🏾 👶🏻 🏛️

हाल ही में विभिन्न सॉर्टिंग एल्गोरिदम और उनकी तुलना पर कई लेख प्रकाशित किए, मैंने अपने खुद के पांच सेंट बनाने का फैसला किया।

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

इसलिए, प्रस्तावित छंटाई टिकाऊ है। हम पूर्णांक 32 बिट संख्याओं को क्रमबद्ध करेंगे। काम करने के लिए, आपको ~ (n + 4KB) अतिरिक्त मेमोरी की आवश्यकता है, जो कुछ हद तक बेकार है, लेकिन आपको प्रदर्शन में कुछ वृद्धि हासिल करने की अनुमति देता है।

इस तरह के एलएसडी में तुलना और आदान-प्रदान का उपयोग नहीं किया जाता है, एल्गोरिथ्म पूरी तरह से रैखिक है। कम्प्यूटेशनल जटिलता ओ (एन)।

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

मेमोरी को बचाने के लिए स्थानीय स्तर पर छंटनी होती है।

//================================================== // RADIX  (  by rebuilder) //   ,  . //   (n),   ~(n+4k) //================================================== procedure RSort(var m: array of Longword); //-------------------------------------------------- procedure Sort_step(var source, dest, offset: array of Longword; const num: Byte); var i,temp : Longword; k : Byte; begin for i := High(source) downto 0 do begin temp := source[i]; k := temp SHR num; dec(offset[k]); dest[offset[k]] := temp; end; end; //-------------------------------------------------- //    ,     var s : array[0..3] of array[0..255] of Longword; i,k : longword; //     k offset : array[0..3] of byte absolute k; m_temp : array of Longword; begin SetLength(m_temp, Length(m)); //    FillChar(s[0], 256 * 4 * SizeOf(Longword), 0); //   for i := 0 to High(m) do begin k := m[i]; Inc(s[0,offset[0]]); Inc(s[1,offset[1]]); Inc(s[2,offset[2]]); Inc(s[3,offset[3]]); end; //     for i := 1 to 255 do begin Inc(s[0,i], s[0,i-1]); Inc(s[1,i], s[1,i-1]); Inc(s[2,i], s[2,i-1]); Inc(s[3,i], s[3,i-1]); end; //         Sort_step(m, m_temp, s[0], 0); Sort_step(m_temp, m, s[1], 8); Sort_step(m, m_temp, s[2], 16); Sort_step(m_temp, m, s[3], 24); SetLength(m_temp, 0); end; //================================================== ... SetLength(m, n); for i := 0 to n - 1 do m[i] := Random(65536 * 65536); ... RSort(m); ...

कोड पास्कल में लिखा गया है, लेकिन इसे आपके लिए सुविधाजनक किसी भी भाषा में पोर्ट करना मुश्किल नहीं होगा।

निष्पादन अनुक्रम में दो चरण होते हैं:

प्रत्येक ब्लॉक के लिए (आठ बाइनरी अंक - 1 बाइट (इष्टतम मूल्य)), गिनती के द्वारा, एक नए सरणी में इसकी स्थिति की गणना की जाती है।
प्रत्येक ब्लॉक के लिए क्रमिक रूप से (कम से कम महत्वपूर्ण से उच्चतम), यह पहले की गणना की स्थिति में जाता है।

सुधार:

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

इसकी सादगी के कारण, कोड लगभग 32 और 64 बिट संकलक दोनों की गति में समान है। यदि आवश्यक हो, तो 16 और 64 बिट संख्या के लिए एल्गोरिथ्म के एक संस्करण की कल्पना करना आसान है।

64-बिट प्लेटफ़ॉर्म (औसतन दस पास प्रत्येक) पर त्वरित छँटाई के साथ यादृच्छिक नमूना एल्गोरिथ्म की तुलना।

अनुकूलन के संबंध में सुझाव और टिप्पणियां स्वागत योग्य हैं।

आपका धन्यवाद

बिटवाइज़ एलएसडी सॉर्ट (रेडिक्स सॉर्ट)

More articles: