टिमसॉर्ट

From Vigyanwiki

टिमसॉर्ट
ClassSorting algorithm
Data structureArray
Worst-case performance[1][2]
Best-case performance[3]
Average performance
Worst-case space complexity

टिमसॉर्ट एक हाइब्रिड, स्थिर सॉर्टिंग एल्गोरिदम है, जो मर्ज सॉर्ट और इंसर्शन सॉर्ट से प्राप्त होता है, जिसे कई प्रकार के वास्तविक दुनिया के डेटा पर अच्छा प्रदर्शन करने के लिए डिज़ाइन किया गया है। इसे टिम पीटर्स द्वारा 2002 में पायथन प्रोग्रामिंग भाषा में उपयोग के लिए लागू किया गया था। एल्गोरिथम पहले से ऑर्डर किए गए डेटा के अनुक्रमों को ढूंढता है (चलता है) और शेष को अधिक कुशलता से क्रमबद्ध करने के लिए उनका उपयोग करता है। यह कुछ मानदंडों को पूरा होने तक रनों को मर्ज (संयोजित) करके किया जाता है। संस्करण 2.3 से टिम्सोर्ट पायथन का मानक सॉर्टिंग एल्गोरिदम रहा है।[4] इसका उपयोग एंड्रॉइड [5] प्लेटफॉर्म पर जावा एसई 7, जीएनयू ऑक्टेव में[6], वी8[7] पर, स्विफ्ट,[8] और रस्ट[9] में गैर-आदिम प्रकार के सरणियों को सॉर्ट करने के लिए भी किया जाता है। 9]

यह पीटर मैकिलरॉय के 1993 के पेपर "ऑप्टिमिस्टिक सॉर्टिंग एंड इंफॉर्मेशन थियोरेटिक कॉम्प्लेक्सिटी" की तकनीकों का उपयोग करता है।[10]

संक्रिया

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

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

मर्ज मानदंड

रन को स्टैक (डेटा संरचना) में डाला जाता है। अगर |Z| ≤ |Y| + |X|, फिर X और Y को मर्ज कर दिया जाता है और स्टैक पर प्रतिस्थापित कर दिया जाता है। इस प्रकार, विलय तब तक जारी रहता है जब तक कि सभी रन संतुष्ट न हो जाएं i. |Z| > |Y| + |X| और ii. |Y| > |X|.

टिमसॉर्ट एक स्थिर सॉर्टिंग एल्गोरिदम है (समान कुंजी वाले तत्वों का क्रम रखा जाता है) और संतुलित मर्ज करने का प्रयास करता है (इस प्रकार एक मर्ज समान आकार के रन को मर्ज करता है)।

सॉर्टिंग स्थिरता प्राप्त करने के लिए, केवल लगातार रन मर्ज किए जाते हैं। दो गैर-क्रमिक रन के बीच, रन के अंदर एक ही कुंजी वाला एक तत्व हो सकता है। उन दो रन को मिलाने से समान कुंजियों का क्रम बदल जाएगा। इस स्थिति का उदाहरण ([] रन क्रमबद्ध हैं): [1 2 2] 1 4 2 [0 1 2]

एक संतुलित मर्ज की खोज में, टाइमसॉर्ट स्टैक के शीर्ष पर तीन रन, X, Y, Z पर विचार करता है, और अपरिवर्तनीय को संरक्षित करता है:

  1. |Z| > |Y| + |X|
  2. |Y| > |X|[11]

यदि इनमें से किसी भी अपरिवर्तनीय का उल्लंघन किया जाता है, तो Y को X या Z में से छोटे के साथ विलय कर दिया जाता है और अपरिवर्तनीयों की दोबारा जाँच की जाती है। एक बार जब अपरिवर्तनीय पकड़ में आ जाते हैं, तो डेटा में एक नए रन की खोज शुरू हो सकती है।[12] संतुलन के लिए विलय में देरी, कैश मेमोरी में रनों की ताज़ा घटना का फायदा उठाने और मर्ज निर्णयों को अपेक्षाकृत सरल बनाने के बीच समझौता बनाए रखते हुए ये अपरिवर्तनीय मर्ज को लगभग संतुलित बनाए रखते हैं।

मर्ज स्पेस ओवरहेड

मर्ज करने के लिए, टिमसॉर्ट छोटे ऐरे (इस चित्रण में X) के तत्वों को अस्थायी मेमोरी में कॉपी करता है, फिर तत्वों को अंतिम क्रम में X और Y के संयुक्त स्थान में सॉर्ट और भरता है।

मूल मर्ज सॉर्ट कार्यान्वयन यथास्थान नहीं है और इसमें N (डेटा आकार) का एक अतिरिक्त स्थान है। इन-प्लेस मर्ज सॉर्ट कार्यान्वयन मौजूद हैं, लेकिन इसमें काफी समय लगता है। एक मध्य अवधि प्राप्त करने के लिए, टिमसॉर्ट एन की तुलना में छोटे समय ओवरहेड और छोटे स्थान ओवरहेड के साथ मर्ज सॉर्ट करता है।

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

उदाहरण: दो रन [1, 2, 3, 6, 10] और [4, 5, 7, 9, 12, 14, 17] को मिलाना होगा। ध्यान दें कि दोनों रन पहले से ही व्यक्तिगत रूप से क्रमबद्ध हैं। दूसरे रन का सबसे छोटा तत्व 4 है और इसके क्रम को संरक्षित करने के लिए इसे पहले रन के चौथे स्थान पर जोड़ना होगा (यह मानते हुए कि रन की पहली स्थिति 1 है)। पहले रन का सबसे बड़ा तत्व 10 है और इसका क्रम बनाए रखने के लिए इसे दूसरे रन के पांचवें स्थान पर जोड़ना होगा। इसलिए, [1, 2, 3] और [12, 14, 17] पहले से ही अपनी अंतिम स्थिति में हैं और वे रन जिनमें तत्वों की गति की आवश्यकता होती है वे हैं [6, 10] और [4, 5, 7, 9]। इस ज्ञान के साथ, हमें केवल 4 के बजाय आकार 2 का अस्थायी बफर आवंटित करने की आवश्यकता है।

मर्ज दिशा

मर्ज दोनों दिशाओं में किया जा सकता है: बाएं से दाएं, पारंपरिक मर्जसॉर्ट की तरह, या दाएं से बाएं।

मर्ज पर्यन्त गैलोपिंग मोड

तत्वों (नीले तीर द्वारा इंगित) की तुलना की जाती है और छोटे तत्व को उसकी अंतिम स्थिति (लाल तीर द्वारा इंगित) पर ले जाया जाता है।

रन R1 और R2 का एक अलग मर्ज एक रन से चुने गए लगातार तत्वों की गिनती रखता है। जब यह संख्या न्यूनतम गैलोपिंग की सीमा (मिन-गैलोप) तक पहुंच जाती है, तो टिमसॉर्ट का मानना ​​है कि यह संभावना है कि उस रन से कई लगातार तत्व अभी भी चुने जा सकते हैं और गैलोपिंग मोड में स्विच हो जाते हैं। चलिए मान लेते हैं कि R1 इसे ट्रिगर करने के लिए जिम्मेदार है। इस मोड में, एल्गोरिथ्म रन R1 में रन R2 के अगले तत्व x के लिए एक घातांकीय खोज करता है, जिसे सरपट खोज के रूप में भी जाना जाता है। यह दो चरणों में किया जाता है: पहला चरण (2k − 1, 2k+1 - 1) का दायरा ढूँढता है जहाँ x है। दूसरा चरण पहले चरण में पाई गई श्रेणी में तत्व x के लिए एक द्विआधारी खोज करता है। गैलोपिंग रन में तत्वों के बीच अंतराल के पैटर्न के लिए मर्ज एल्गोरिदम को अनुकूलित करने का एक प्रयास है।

गैलोपिंग हमेशा कुशल नहीं होता है। कुछ मामलों में गैलोपिंग मोड में साधारण रैखिक खोज की तुलना में अधिक तुलना की आवश्यकता होती है। डेवलपर द्वारा किए गए बेंचमार्क के अनुसार, गैलोपिंग केवल तभी फायदेमंद होता है जब एक रन का प्रारंभिक तत्व दूसरे रन के पहले सात तत्वों में से एक नहीं होता है। इसका तात्पर्य 7 की प्रारंभिक सीमा से है। गैलोपिंग मोड की कमियों से बचने के लिए, दो क्रियाएं की जाती हैं: (1) जब गैलोपिंग को बाइनरी खोज से कम कुशल पाया जाता है, तो गैलोपिंग मोड से बाहर निकल जाता है। (2) गैलोपिंग की सफलता या विफलता का उपयोग न्यूनतम_गैलप को समायोजित करने के लिए किया जाता है। यदि चयनित तत्व उसी सरणी से है जिसने पहले एक तत्व लौटाया था, तो मिन-गैलोप को एक से कम कर दिया जाता है, इस प्रकार गैलोपिंग मोड में वापसी को प्रोत्साहित किया जाता है। अन्यथा, मूल्य एक से बढ़ जाता है, इस प्रकार गैलोपिंग मोड पर वापसी को हतोत्साहित करता है। यादृच्छिक डेटा के मामले में, मिन-गैलोप का मान इतना बड़ा हो जाता है कि गैलोपिंग मोड की पुनरावृत्ति कभी नहीं होती है।[13]

सभी लाल तत्व नीले से छोटे हैं (यहाँ, 21)। इस प्रकार उन्हें एक टुकड़े में अंतिम सरणी में ले जाया जा सकता है।

अवरोही रन

अवरोही क्रम में क्रमबद्ध किए गए डेटा का लाभ उठाने के लिए, टिमसॉर्ट उन्हें मिलने पर कड़ाई से अवरोही रनों को परिवर्तित कर दिया जाता है और उन्हें रनों के संचय में जोड़ दिया जाता है। चूँकि अवरोही रन बाद में अंधवत् परिवर्तिति कर दिए जाते हैं, समान तत्वों वाले रन को छोड़कर एल्गोरिदम की स्थिरता बनी रहती है; अर्थात, समान तत्व परिवर्तित नहीं होंगे।

न्यूनतम रन आकार

टिम्सोर्ट एल्गोरिदम अपने प्रकार को निष्पादित करने के लिए न्यूनतम आकार के आदेशित अनुक्रमों, मिनरन की खोज करता है।

क्योंकि मर्ज सबसे अधिक कुशल होता है जब रनों की संख्या दो की घात के बराबर या उससे थोड़ी कम होती है, और विशेष रूप से कम कुशल होती है जब रनों की संख्या दो की घात से थोड़ी अधिक होती है, टिमसॉर्ट ने पूर्व स्थिति सुनिश्चित करने के प्रयास के लिए मिनरन को चुना।[11]

मिनरन को श्रेणी 32 से 64 तक चुना जाता है, जैसे कि डेटा का आकार, मिनरन द्वारा विभाजित, दो की शक्ति के बराबर या उससे थोड़ा कम होता है। अंतिम एल्गोरिदम सरणी के आकार के छह सबसे महत्वपूर्ण बिट्स लेता है, यदि शेष बिट्स में से कोई भी सेट किया जाता है तो एक जोड़ता है, और उस परिणाम को मिनरून के रूप में उपयोग करता है। यह एल्गोरिथम सभी सरणियों के लिए काम करता है, जिसमें 64 से छोटी सरणियाँ भी शामिल हैं; 63 या उससे कम आकार की सरणियों के लिए, यह minrun को सरणी आकार के बराबर सेट करता है और टिमसॉर्ट एक सम्मिलन सॉर्ट में कम हो जाता है।[11]

विश्लेषण

सबसे अच्छे, सबसे खराब और औसत मामले में, टिमसॉर्ट लेता है किसी सरणी को क्रमबद्ध करने के लिए तुलनाएँ nतत्व. सबसे अच्छे मामले में, जो तब होता है जब इनपुट पहले से ही सॉर्ट किया गया हो, यह रैखिक समय में चलता है, जिसका अर्थ है कि यह एक अनुकूली सॉर्टिंग एल्गोरिदम है।[3]

ऑब्जेक्ट संदर्भों या पॉइंटर्स को सॉर्ट करने के लिए यह जल्दी से सुलझाएं से बेहतर है क्योंकि इन्हें डेटा तक पहुंचने और तुलना करने के लिए महंगी मेमोरी इनडायरेक्शन की आवश्यकता होती है और क्विकॉर्ट के कैश सुसंगतता लाभ बहुत कम हो जाते हैं।

औपचारिक सत्यापन

2015 में, EU FP7 ENVISAGE प्रोजेक्ट में डच और जर्मन शोधकर्ताओं ने टिमसॉर्ट के मानक कार्यान्वयन में एक बग पाया।[14] इसे 2015 में Python, Java और Android में ठीक किया गया था।

विशेष रूप से, स्टैक्ड रन आकारों पर अपरिवर्तनीय आवश्यक स्टैक के अधिकतम आकार पर एक तंग ऊपरी सीमा सुनिश्चित करते हैं। कार्यान्वयन ने सॉर्ट 2 के लिए पर्याप्त स्टैक पूर्व-आवंटित कियाइनपुट के 64 बाइट्स, और आगे अतिप्रवाह जांच से बचा गया।

हालाँकि, गारंटी के लिए इनवेरिएंट्स को लगातार तीन रनों के प्रत्येक समूह पर लागू करने की आवश्यकता होती है, लेकिन कार्यान्वयन ने इसे केवल शीर्ष तीन के लिए जांचा।[14] जावा सॉफ़्टवेयर चाबी औपचारिक सत्यापन के लिए KeY टूल का उपयोग करते हुए, शोधकर्ताओं ने पाया कि यह जाँच पर्याप्त नहीं है, और वे रन लंबाई (और इनपुट जो उन रन लंबाई उत्पन्न करते हैं) को खोजने में सक्षम थे, जिसके परिणामस्वरूप स्टैक में गहराई से इनवेरिएंट का उल्लंघन हो सकता था। स्टैक के शीर्ष को मर्ज करने के बाद।[15] परिणामस्वरूप, कुछ इनपुट के लिए आवंटित आकार सभी असंबद्ध रन को रखने के लिए पर्याप्त नहीं है। जावा में, यह उन इनपुटों के लिए एक ऐरे-आउट-ऑफ-बाउंड अपवाद उत्पन्न करता है। जावा और एंड्रॉइड v7 में इस अपवाद को ट्रिगर करने वाला सबसे छोटा इनपुट आकार का है 67108864 (226). (पुराने एंड्रॉइड संस्करणों ने पहले ही आकार के कुछ इनपुट के लिए इस अपवाद को ट्रिगर कर दिया है 65536 (216))

अद्यतन सबसे खराब स्थिति विश्लेषण के आधार पर पूर्व-आवंटित स्टैक के आकार को बढ़ाकर जावा कार्यान्वयन को ठीक किया गया था। लेख में औपचारिक तरीकों से यह भी दिखाया गया है कि स्टैक में चार सबसे ऊपरी रन ऊपर दिए गए दो नियमों को पूरा करते हैं या नहीं, इसकी जांच करके इच्छित अपरिवर्तनीय को कैसे स्थापित किया जाए। यह दृष्टिकोण Python द्वारा अपनाया गया था[16] और एंड्रॉइड।

संदर्भ

  1. ↑ Peters, Tim (20 July 2002). "[Python-Dev] Sorting". Python Developers Mailinglist. Retrieved 24 February 2011. [Timsort] also has good aspects: It's stable (items that compare equal retain their relative order, so, e.g., if you sort first on zip code, and a second time on name, people with the same name still appear in order of increasing zip code; this is important in apps that, e.g., refine the results of queries based on user input). ... It has no bad cases (O(N log N) is worst case; N−1 compares is best).
  2. ↑ Auger, Nicolas; Jugé, Vincent; Nicaud, Cyril; Pivoteau, Carine (2018). [DROPS]. doi:10.4230/LIPIcs.ESA.2018.4. ISBN 9783959770811. S2CID 44091254. Retrieved 1 September 2018. TimSort is an intriguing sorting algorithm designed in 2002 for Python, whose worst-case complexity was announced, but not proved until our recent preprint.
  3. ↑ 3.0 3.1 Chandramouli, Badrish; Goldstein, Jonathan (2014). Patience is a Virtue: Revisiting Merge and Sort on Modern Processors. SIGMOD/PODS.
  4. ↑ "[#JDK-6804124] (coll) Replace "modified mergesort" in java.util.Arrays.sort with timsort". JDK Bug System. Retrieved 11 June 2014.
  5. ↑ "Class: java.util.TimSort<T>". Android Gingerbread Documentation. Archived from the original on 16 July 2015. Retrieved 24 February 2011.
  6. ↑ "liboctave/util/oct-sort.cc". Mercurial repository of Octave source code. Lines 23-25 of the initial comment block. Retrieved 18 February 2013. Code stolen in large part from Python's, listobject.c, which itself had no license header. However, thanks to Tim Peters for the parts of the code I ripped-off.
  7. ↑ "Getting things sorted in V8 · V8". v8.dev. Retrieved 21 December 2018.
  8. ↑ "Is sort() stable in Swift 5?". Swift Forums (in English). 4 July 2019. Retrieved 4 July 2019.
  9. ↑ "टुकड़ा - जंग". doc.rust-lang.org. Retrieved 8 December 2022. The current algorithm is an adaptive, iterative merge sort inspired by timsort. It is designed to be very fast in cases where the slice is nearly sorted, or consists of two or more sorted sequences concatenated one after another.
  10. ↑ McIlroy, Peter (January 1993). "Optimistic Sorting and Information Theoretic Complexity". असतत एल्गोरिदम पर चौथे वार्षिक ACM-SIAM संगोष्ठी की कार्यवाही. pp. 467–474. ISBN 0-89871-313-7.
  11. ↑ 11.0 11.1 11.2 "listsort.txt". Python source code. 18 May 2022. Archived from the original on 28 January 2016.
  12. ↑ MacIver, David R. (11 January 2010). "Understanding timsort, Part 1: Adaptive Mergesort". Retrieved 5 December 2015.
  13. ↑ Peters, Tim. "listsort.txt". CPython git repository. Retrieved 5 December 2019.
  14. ↑ 14.0 14.1 de Gouw, Stijn; Rot, Jurriaan; de Boer, Frank S.; Bubel, Richard; Hähnle, Reiner (July 2015). "OpenJDK's Java.utils.Collection.sort() Is Broken: The Good, the Bad and the Worst Case" (PDF). Computer Aided Verification. Lecture Notes in Computer Science. 9206: 273–289. doi:10.1007/978-3-319-21690-4_16. ISBN 978-3-319-21689-8.
  15. ↑ de Gouw, Stijn (24 February 2015). "साबित करना कि एंड्रॉइड, जावा और पायथन का सॉर्टिंग एल्गोरिदम टूटा हुआ है (और इसे ठीक करने का तरीका दिखाएं)". Retrieved 6 May 2017.
  16. ↑ Python Issue Tracker – Issue 23515: Bad logic in timsort's merge_collapse


अग्रिम पठन


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=टिमसॉर्ट&oldid=226153’