टिमसॉर्ट

From Vigyanwiki
Revision as of 08:11, 18 July 2023 by alpha>Adityak

टिमसॉर्ट
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] में गैर-आदिम प्रकार के सरणियों को क्रम करने के लिए भी किया जाता है।

यह पीटर मैकिलरॉय के 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 में, ईयू एफपी7 परिकल्पना प्रोजेक्ट में डच और जर्मन शोधकर्ताओं ने टिमसॉर्ट के मानक कार्यान्वयन में एक बग पाया।[14] इसे 2015 में पायथन, जावा और एंड्रॉइड में ठीक किया गया था। विशेष रूप से, स्टैक्ड रन साइज़ पर अपरिवर्तनीय आवश्यक स्टैक के अधिकतम आकार पर एक तंग ऊपरी सीमा सुनिश्चित करते हैं। कार्यान्वयन ने इनपुट के 264 बाइट्स को क्रम करने के लिए पर्याप्त स्टैक पूर्व-आवंटित किया, और आगे अतिप्रवाह जांच से बचा।

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

परिणामस्वरूप, कुछ इनपुट के लिए आवंटित आकार सभी अनमर्ज किए गए रनों को रखने के लिए पर्याप्त नहीं है। जावा में, यह उन इनपुट के लिए एक ऐरे-आउट-ऑफ-बाउंड अपवाद उत्पन्न करता है। जावा और एंड्रॉइड v7 में इस अपवाद को ट्रिगर करने वाला सबसे छोटा इनपुट आकार 67108864 (226) है। (पुराने एंड्रॉइड संस्करणों ने आकार 65536 (216) के कुछ इनपुट के लिए पहले से ही इस अपवाद को ट्रिगर कर दिया है)

अद्यतन निकृष्ट स्थिति के विश्लेषण के आधार पर पूर्व-आवंटित स्टैक के आकार को बढ़ाकर जावा कार्यान्वयन को ठीक किया गया था। लेख में औपचारिक तरीकों से यह भी दिखाया गया है कि स्टैक में चार शीर्षतम रन ऊपर दिए गए दो नियमों को पूरा करते हैं या नहीं, इसकी जांच करके इच्छित अपरिवर्तनीय को कैसे स्थापित किया जाए। यह दृष्टिकोण पायथन[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=226156’