फ्लैशसॉर्ट

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

संकल्पना

फ्लैशसॉर्ट हिस्टोग्राम सॉर्ट का एक कुशल इन-प्लेस कार्यान्वयन है, जो स्वयं एक प्रकार का बकेट सॉर्ट है। यह प्रत्येक n इनपुट अवयव को m बकेट में से एक को निर्दिष्ट करता है, बकेट को सही क्रम में रखने के लिए इनपुट को कुशलतापूर्वक पुनर्व्यवस्थित करता है, फिर प्रत्येक बकेट को सॉर्ट करता है। मूल एल्गोरिदम एक इनपुट सरणी A को निम्नानुसार सॉर्ट करता है:

• इनपुट पर पहले पास या प्राथमिक ज्ञान का उपयोग करके न्यूनतम और अधिकतम सॉर्ट कुंजी खोजे।
• रेंज [A_min, A_max] को रैखिक रूप से m बकेट में विभाजित करें।
• प्रत्येक बकेट में गिरने वाले A_i अवयव की संख्या गिनते हुए, इनपुट पर एक पास बनाते है। (न्यूबर्ट बकेट को "वर्ग" और उनकी बकेट में अवयव के असाइनमेंट को "वर्गीकरण" कहते हैं।)
• प्रत्येक बकेट में अवयव की संख्या को उपसर्ग योग में बदलें, जहां L_b बकेट b या उससे कम में अवयव A_i की संख्या है। (L0 = 0 और Lm = n.)
• प्रत्येक बकेट b के सभी अवयव के इनपुट को पुनर्व्यवस्थित करें, स्थिति A_i में संग्रहीत किया जाता है जहां L_b−1 < i ≤ L_b।
• सम्मिलन सॉर्ट का उपयोग करके प्रत्येक बकेट को सॉर्ट करें।

चरण 1-3 और 6 किसी भी बकेट सॉर्ट के लिए सामान्य हैं, और बकेट सॉर्ट के लिए सामान्य तकनीकों का उपयोग करके इसमें सुधार किया जा सकता है। विशेष रूप से, लक्ष्य यह है कि बकेट लगभग समान आकार (प्रत्येकn/m अवयव ) की हों जिसका आदर्श रूप m मात्राओं में विभाजन है। जबकि मूल एल्गोरिथ्म एक रैखिक प्रक्षेप प्रकार है, यदि इनपुट वितरण को गैर-समान माना जाता है, तो एक गैर-रेखीय विभाजन इस आदर्श को अधिक निकटता से अनुमानित करेगा। इसी तरह अंतिम सॉर्ट पुनरावर्ती फ़्लैश सॉर्ट सहित कई तकनीकों में से किसी एक का उपयोग कर सकता है।

फ़्लैश सॉर्ट को जो अलग करता है वह चरण 5 है: अतिरिक्त मेमोरी के केवल एम शब्दों का उपयोग करके प्रत्येक बकेट के अवयव को सही सापेक्ष क्रम में एकत्र करने के लिए एक कुशल O(n) इन-प्लेस एल्गोरिदम है ।

मेमोरी कुशल कार्यान्वयन

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

प्रति बकेट दो (शब्द-आकार) चर का उपयोग करके विवरण को समझना आसान है। चतुर भाग उन चरों में से एक को समाप्त करना है, जिससे दोगुनी बकेट का उपयोग किया जा सकता है और इसलिए अंतिम O(n²) सॉर्टिंग पर आधा समय खर्च किया जाता है।

प्रति बकेट दो चर के साथ इसे समझने के लिए, मान लें कि दो सारणियाँ हैं मान ले की m अतिरिक्त शब्द: K_b बकेट की (निश्चित) ऊपरी सीमा है b (और K₀ = 0), जबकि L_b बकेट b में एक (चलने योग्य) सूचकांक है इसलिए K_b−1 ≤ L_b ≤ K_b

हम लूप को अपरिवर्तनीय बनाए रखते हैं कि प्रत्येक बकेट को L_b द्वारा एक अवर्गीकृत उपसर्ग में विभाजित किया जाता है (K_b−1 < i ≤ L_b के लिए A_i को अभी तक उनके लक्ष्य बकेट में स्थानांतरित नहीं किया गया है) और एक वर्गीकृत प्रत्यय (L_b < i ≤ K_b के लिए A_i सभी हैं) सही बकेट में और दोबारा नहीं ले जाया जाएगा)। प्रारंभ में L_b = K_b और सभी अवयव अवर्गीकृत हैं। जैसे-जैसे छँटाई आगे बढ़ती है,L_b को सभी b के लिए L_b = K_b−1 तक घटाया जाता है और सभी अवयव को सही बकेट में वर्गीकृत किया जाता है।

प्रत्येक समय पहली अपूर्ण रूप से वर्गीकृत बकेट c (जिसमें K_c−1 < L_c है) को खोजने और उस बकेट A_i में पहला अवर्गीकृत अवयव लेने से प्रारंभ होता है जहां i = K_c−1 + 1 है। (न्यूबर्ट इसे "साइकिल लीडर" कहते हैं।) A_i को अस्थायी चर t में प्रतिलिपि करें और दोहराएं:

• उस बकेट b की गणना करें जिससे t संबंधित है।
• मान लीजिए j = L_b वह स्थान है जहाँ t संग्रहीत किया जाएगा।
• t को A_j के साथ बदलें, अथार्त पिछले मान A_j को प्राप्त करते समय t को A_j में संग्रहीत करें जिससे A_j विस्थापित हो जाए।
• इस तथ्य को प्रतिबिंबित करने के लिए L_b घटाएं कि A_j को अब सही रूप से वर्गीकृत किया गया है।
• यदि j ≠ i, तो इस लूप को नए t के साथ पुनरारंभ करें।
• यदि j = i, तो यह दौर समाप्त हो गया है और एक नया पहला अवर्गीकृत अवयव A_i खोजे जाते है।
• जब कोई अवर्गीकृत अवयव नहीं रह जाते हैं, तो बकेट में वितरण पूरा हो जाता है।

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

यद्यपि पिछला विवरण चक्र नेताओं को खोजने के लिए K का उपयोग करता है, वास्तव में इसके बिना ऐसा करना संभव है, जिससे संपूर्ण m-शब्द सरणी को समाप्त किया जा सकता है। (वितरण पूरा होने के बाद, बकेट सीमाएँ L में पाई जा सकती हैं।)

मान लीजिए कि हमने i−1 तक के सभी अवयव को वर्गीकृत कर दिया है, और A_i को एक संभावित नए चक्र नेता के रूप में मान रहे हैं। इसके लक्ष्य बकेट b की गणना करना आसान है। लूप इनवेरिएंट द्वारा, इसे वर्गीकृत किया जाता है यदि L_b < i ≤ K_b, और यदि i उस सीमा से बाहर है तो अवर्गीकृत किया जाता है। पहली असमानता का परीक्षण करना आसान है, किंतु दूसरे के लिए मान K_b की आवश्यकता होती है।

यह पता चलता है कि प्रेरण परिकल्पना कि i−1 तक के सभी अवयव को वर्गीकृत किया गया है, इसका तात्पर्य है कि i ≤ K_b, इसलिए दूसरी असमानता का परीक्षण करना आवश्यक नहीं है।

बकेट c पर विचार करें जो i स्थिति में आती है। अर्थात्, K_c−1 < i ≤ K_c. प्रेरण परिकल्पना के अनुसार, नीचे दिए गए सभी अवयव i, जिसमें K_c−1 < iतक की सभी बकेट सम्मिलित हैं, पूरी तरह से वर्गीकृत हैं। अर्थात। उन बकेट में सम्मिलित कोई भी अवयव शेष सरणी में नहीं रहता है। इसलिए, यह संभव नहीं है कि b < c.

एकमात्र शेष स्थिति b ≥ c है, जिसका अर्थ है K_b ≥ K_c ≥ i, Q.E.D.

इसे सम्मिलित करते हुए, फ्लैशसॉर्ट वितरण एल्गोरिदम ऊपर बताए अनुसार L से प्रारंभ होता है और i = 1. फिर आगे बढ़ें:

• यदिi > n तो वितरण पूरा हो गया है।
• A_i को देखते हुए, उस बकेट b की गणना करें जिससे वह संबंधित है।
• यदि i ≤ L_b, तो A_i अवर्गीकृत है। इसे एक अस्थायी चर t प्रतिलिपि करें और:
  • मान लीजिए j = L_b वह स्थान है जहाँ t संग्रहीत किया जाएगा।
  • t को A_j के साथ बदलें, अर्थात पिछले मान A_jको प्राप्त करते समय t को A_jमें संग्रहीत करें जिससे A_jविस्थापित हो जाए।
  • इस तथ्य को प्रतिबिंबित करने के लिए L_b घटाएं कि A_jको अब सही रूप से वर्गीकृत किया गया है।
  • यदि j ≠ i, तो उस बकेट b की गणना करें जिससे t संबंधित है और इस (आंतरिक) लूप को नए t के साथ पुनरारंभ करें।
• A_i अब सही रूप से वर्गीकृत किया गया है। वेतन वृद्धि i और (बाहरी) लूप को पुनरारंभ करें।

मेमोरी को सहेजते समय, फ्लैशसॉर्ट का हानि यह है कि यह पहले से ही वर्गीकृत कई अवयव के लिए बकेट की पुन: गणना करता है। यह पहले से ही प्रति अवयव दो बार किया जाता है (एक बार बकेट -गिनती चरण के समय और दूसरी बार प्रत्येक अवयव को स्थानांतरित करते समय), किंतु पहले अवर्गीकृत अवयव की खोज के लिए अधिकांश अवयव के लिए तीसरी गणना की आवश्यकता होती है। यह मूल्यवान हो सकता है यदि बकेट को सरल रैखिक प्रक्षेप की तुलना में अधिक सम्मिश्र सूत्र का उपयोग करके निर्दिष्ट किया जाता है। एक प्रकार चक्र लीडर के रूप में एक अधूरी बकेट में अंतिम अवर्गीकृत तत्व को लेकर गणनाओं की संख्या को लगभग 3n से घटाकर अधिकतम 2n + m − 1 कर देता है:

• पहले अपूर्ण-वर्गीकृत बकेट की पहचान करने वाला एक वेरिएबल c बनाए रखें। आरंभ करने के लिए मान लीजिए c = 1 है, और जब c > m वितरण पूरा हो जाता है।
• चलो i = L_c. यदि i = L_c−1 है, तो c बढ़ाएँ और इस लूप को पुनरारंभ करें। (L0 = 0.)
• उस बकेट b की गणना करें जिससे A_i संबंधित है।
• यदि b < c, तो L_c = K_c−1 और हमने बकेट c का काम पूरा कर लिया है। c बढ़ाएँ और इस लूप को पुनरारंभ करें।
• यदि b = c है, तो वर्गीकरण तुच्छ है। L_c घटाएं और इस लूप को पुनरारंभ करें।
• यदि b > c, तो A_i अवर्गीकृत है। पिछले स्थिति की तरह ही वर्गीकरण लूप निष्पादित करें और फिर इस लूप को पुनरारंभ करें।

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

प्रदर्शन

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

सभी बकेट प्रकारों की तरह, प्रदर्शन गंभीर रूप से बकेट के संतुलन पर निर्भर करता है। संतुलित डेटा सेट के आदर्श स्थिति में, प्रत्येक बकेट लगभग समान आकार की होगी। यदि इनपुट आकार n में बकेट की संख्या m रैखिक है, तो प्रत्येक बकेट का एक स्थिर आकार होता है, इसलिए एक एकल बकेट को O(n²) एल्गोरिदम जैसे प्रविष्टि सॉर्ट के साथ सॉर्ट करने में सम्मिश्रता O(1²) = O(1) होती है। इसलिए अंतिम प्रविष्टि प्रकार का चलने का समय m ⋅ O(1) = O(m) = O(n) है।

m के लिए एक मान चुनना, बकेट की संख्या, तत्वों को वर्गीकृत करने में लगने वाला समय (उच्च m) और अंतिम प्रविष्टि सॉर्ट चरण (कम m) में लगने वाला समय कम हो जाता है। उदाहरण के लिए, यदि m को √n के आनुपातिक रूप से चुना गया है, तो अंतिम प्रविष्टि प्रकार का चलने का समय m ⋅ O(√n²) = O(n^3/2) है।

सबसे व्यर्थ स्थिति में जहां लगभग सभी तत्व कुछ बकेट में होते हैं, एल्गोरिदम की सम्मिश्रता अंतिम बकेट-सॉर्टिंग विधि के प्रदर्शन से सीमित होती है, इसलिए यह O(n²) तक घट जाती है। एल्गोरिदम की विविधताएं एक निश्चित आकार सीमा से अधिक की बकेट पर उत्तम प्रदर्शन करने वाले प्रकारों जैसे क्विकसॉर्ट या रिकर्सिव फ्लैशसॉर्ट का उपयोग करके सबसे व्यर्थ स्थिति के प्रदर्शन में सुधार करती हैं।।

समान रूप से वितरित यादृच्छिक डेटा के साथ m = 0.1 n के लिए, फ्लैशसॉर्ट सभी n के लिए हीप्सॉर्ट से तेज है और n > 80 के लिए क्विकॉर्ट से तेज है। यह n = 10000 पर क्विकॉर्ट से लगभग दोगुना तेज हो जाता है। ध्यान दें कि ये माप 1990 के दशक के अंत में लिए गए थे, जब मेमोरी पदानुक्रम कैशिंग पर बहुत कम निर्भर थे।

फ्लैशसॉर्ट अपनी वर्गीकरण प्रक्रिया में जो यथास्थान क्रमपरिवर्तन करता है, उसके कारण फ्लैशसॉर्ट स्थिर नहीं है। यदि स्थिरता की आवश्यकता है, तो दूसरी सरणी का उपयोग करना संभव है जिससे तत्वों को क्रमिक रूप से वर्गीकृत किया जा सके। चूँकि, इस स्थिति में, एल्गोरिदम को O(n) अतिरिक्त मेमोरी की आवश्यकता होगी।

यह भी देखें

• प्रक्षेप खोज, सॉर्टिंग के अतिरिक्त खोज के लिए वस्तुओं के वितरण का उपयोग करना

बाहरी संबंध

• Implementations of Randomized Sorting on Large Parallel Machines (1992)
• Implementation of Parallel Algorithms (1992)
• Visualization of Flashsort