पॉलीफ़ेज़ मर्ज सॉर्ट

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

साधारण मर्ज सॉर्ट

मर्ज सॉर्ट एक डेटासेट के रिकॉर्ड को रिकॉर्ड के क्रमबद्ध रन में विभाजित करता है और फिर बार-बार सॉर्ट किए गए रन को बड़े क्रमबद्ध रन में मर्ज करता है जब तक कि केवल एक रन, सॉर्ट किया गया डेटासेट नहीं रह जाता है।

चार कार्यशील फ़ाइलों का उपयोग करके एक सामान्य मर्ज सॉर्ट उन्हें इनपुट फ़ाइलों की एक जोड़ी और आउटपुट फ़ाइलों की एक जोड़ी के रूप में व्यवस्थित करता है। डेटासेट को दो कार्यशील फ़ाइलों के बीच समान रूप से वितरित किया जाता है, या तो क्रमबद्ध रन के रूप में या सरलतम मामले में, एकल रिकॉर्ड, जिसे आकार 1 के क्रमबद्ध रन माना जा सकता है। एक बार जब सभी डेटासेट दो कार्यशील फ़ाइलों में स्थानांतरित हो जाते हैं, तो वे दो कार्यशील फ़ाइलें पहले मर्ज पुनरावृत्ति के लिए इनपुट फ़ाइलें बन जाती हैं। प्रत्येक मर्ज पुनरावृत्ति मर्ज दो इनपुट कार्यशील फ़ाइलों से चलती है, दो आउटपुट फ़ाइलों के बीच मर्ज किए गए आउटपुट को वैकल्पिक करती है, फिर से मर्ज किए गए रन को दो आउटपुट फ़ाइलों के बीच समान रूप से वितरित करती है (अंतिम मर्ज पुनरावृत्ति तक)। एक बार जब दो इनपुट फ़ाइलों से सभी रन विलय और आउटपुट हो जाते हैं, तो आउटपुट फ़ाइलें इनपुट फ़ाइलें बन जाती हैं और अगले मर्ज पुनरावृत्ति के लिए जो इसके विपरीत भी संभव है। प्रत्येक पुनरावृत्ति पर रन की संख्या 2 के कारक से घट जाती है, जैसे कि 64, 32, 16, 8, 4, 2, 1। अंतिम मर्ज पुनरावृत्ति के लिए, दो इनपुट फ़ाइलों में केवल एक क्रमबद्ध रन (1/2) होता है डेटासेट) प्रत्येक, और मर्ज किया गया परिणाम आउटपुट फ़ाइलों में से एक पर एकल सॉर्ट किया गया रन (सॉर्ट किया गया डेटासेट) है। इसका वर्णन मर्ज सॉर्ट § टेप ड्राइव के साथ उपयोग में भी किया गया है।

यदि केवल तीन कार्यशील फ़ाइलें हैं, तो एक साधारण मर्ज सॉर्ट दो कार्यशील फ़ाइलों से सॉर्ट किए गए रन को एक कार्यशील फ़ाइल में मर्ज कर देता है, फिर रन को दो आउटपुट फ़ाइलों के बीच समान रूप से वितरित करता है। मर्ज पुनरावृत्ति रन संख्या को 2 के कारक से कम कर देता है, पुनर्वितरित पुनरावृत्ति रन गणना को कम नहीं करता है (कारक 1 है)। प्रत्येक पुनरावृत्ति को √2 ≈ 1.41 के औसत कारक द्वारा रन गिनती को कम करने पर विचार किया जा सकता है। यदि 5 कार्यशील फ़ाइलें हैं, तो पैटर्न √6 ≈ 2.45 के औसत कारक के लिए, 3-तरफा मर्ज और 2-तरफा मर्ज के बीच वैकल्पिक होता है।

सामान्य तौर पर, कार्यशील फ़ाइलों की सम संख्या N के लिए, सामान्य मर्ज सॉर्ट का प्रत्येक पुनरावृत्ति रन संख्या को N/2 के कारक से कम कर देता है, जबकि कार्यशील फ़ाइलों की विषम संख्या N के लिए, प्रत्येक पुनरावृत्ति रन संख्या को √(N²−1)/4 = √N²−1/2 के औसत कारक से कम कर देता है।

पॉलीफ़ेज़ मर्ज

N <8 कार्यशील फ़ाइलों के लिए, एक पॉलीफ़ेज़ मर्ज सॉर्ट N−1 कार्यशील फ़ाइलों के बीच क्रमबद्ध रन को असमान रूप से वितरित करके एक उच्च प्रभावी रन गिनती कमी कारक प्राप्त करता है (अगले भाग में समझाया गया है)। प्रत्येक पुनरावृत्ति विलय N−1 कार्यशील फ़ाइलों से एकल आउटपुट कार्यशील फ़ाइल पर चलता है। जब N−1 कार्यशील फ़ाइलों में से एक का अंत पहुँच जाता है, तो यह नई आउटपुट फ़ाइल बन जाती है और जो आउटपुट फ़ाइल थी वह N−1 कार्यशील इनपुट फ़ाइलों में से एक बन जाती है, जिससे पॉलीफ़ेज़ मर्ज सॉर्ट का एक नया पुनरावृत्ति शुरू हो जाता है। प्रत्येक पुनरावृत्ति डेटासेट के केवल एक अंश (लगभग 1/2 से 3/4) को मर्ज करती है, अंतिम पुनरावृत्ति को छोड़कर जो सभी डेटासेट को एक ही क्रमबद्ध रन में मर्ज कर देता है। प्रारंभिक वितरण स्थापित किया गया है ताकि एक समय में केवल एक इनपुट वर्किंग फ़ाइल खाली हो, अंतिम मर्ज पुनरावृत्ति को छोड़कर जो N−1 इनपुट वर्किंग फ़ाइलों से N−1 सिंगल रन (अलग-अलग आकार के, इसे आगे समझाया गया है) को मर्ज करता है। एकल आउटपुट फ़ाइल में, जिसके परिणामस्वरूप एकल क्रमबद्ध रन, क्रमबद्ध डेटासेट होता है।

प्रत्येक पॉलीफ़ेज़ पुनरावृत्ति के लिए, रनों की कुल संख्या उच्च क्रम अनुक्रम के उलट फाइबोनैचि संख्याओं के समान एक पैटर्न का अनुसरण करती है। 4 फ़ाइलों और 57 रन वाले डेटासेट के साथ, प्रत्येक पुनरावृत्ति पर कुल रन संख्या 57, 31, 17, 9, 5, 3, 1 होगी। ध्यान दें कि अंतिम पुनरावृत्ति को छोड़कर, रन गिनती में कमी कारक 2, 57/31, 31/17, 17/9, 9/5, 5/3, 3/1 से थोड़ा कम है, 4 फ़ाइल के लिए लगभग 1.84 मामला, लेकिन अंतिम को छोड़कर प्रत्येक पुनरावृत्ति ने लगभग 65% डेटासेट को संसाधित करते समय रन गिनती को कम कर दिया, इसलिए मध्यवर्ती पुनरावृत्तियों के दौरान संसाधित प्रति डेटासेट रन गिनती में कमी कारक लगभग 1.84 / 0.65 = 2.83 है। प्रत्येक 1 रिकॉर्ड के 57 रन वाले डेटासेट के लिए, प्रारंभिक वितरण के बाद, पॉलीफ़ेज़ मर्ज सॉर्ट 2.70 के समग्र कमी कारक के लिए डेटासेट को सॉर्ट करने के लिए लगने वाले 6 पुनरावृत्तियों के दौरान 232 रिकॉर्ड ले जाता है (इसे बाद में अधिक विस्तार से समझाया गया है)

पहले पॉलीफ़ेज़ पुनरावृत्ति के बाद, आउटपुट फ़ाइल में अब N−1 मूल रन के विलय के परिणाम शामिल हैं, लेकिन शेष N−2 इनपुट कार्यशील फ़ाइलों में अभी भी शेष मूल रन शामिल हैं, इसलिए दूसरा मर्ज पुनरावृत्ति आकार के रन उत्पन्न करता है (N−1) + (N−2) = (2N − 3) मूल रन। तीसरा पुनरावृत्ति आकार (4N − 7) के मूल रन उत्पन्न करता है। 4 फ़ाइलों के साथ, पहला पुनरावृत्ति आकार 3 मूल रन बनाता है, दूसरा पुनरावृत्ति 5 मूल रन बनाता है, तीसरा पुनरावृत्ति 9 मूल रन बनाता है और इसी तरह, फाइबोनैचि जैसे पैटर्न का अनुसरण करते हुए, 1, 3, 5, 9, 17, 31, 57, ..., इसलिए रन आकार में वृद्धि उसी पैटर्न का अनुसरण करती है, जिसके विपरीत रन संख्या में कमी होती है। 4 फ़ाइलों और 1 रिकॉर्ड के 57 रन के उदाहरण मामले में, अंतिम पुनरावृत्ति 31, 17, 9 आकार के 3 रन को मर्ज करती है, जिसके परिणामस्वरूप आकार 31+17+9 = 57 रिकॉर्ड का एकल क्रमबद्ध रन होता है, क्रमबद्ध डेटासेट। 4 फ़ाइलों, 31 रिकॉर्ड के लिए रन गणना और रन आकार का एक उदाहरण तालिका 4.3 में पाया जा सकता है।

परफेक्ट 3 फ़ाइल पॉलीफ़ेज़ मर्ज सॉर्ट

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

फ़ाइल 1 अभी-अभी खाली हुई और नई आउटपुट फ़ाइल बन गई। प्रत्येक इनपुट टेप पर एक रन छोड़ा गया है, और उन रन को एक साथ मर्ज करने से सॉर्ट की गई फ़ाइल बन जाएगी।

<पूर्व> फ़ाइल 1 (बाहर): <1 रन> * (क्रमबद्ध फ़ाइल) फ़ाइल 2 (में): ... | <1 रन> * --> ... <1 रन> | * (ग्रहण किया हुआ) फ़ाइल 3 (इंच): | <1 रन> * <1 रन> | * (ग्रहण किया हुआ)

... संभावित रन जो पहले ही पढ़े जा चुके हैं | फ़ाइल के रीड पॉइंटर को चिह्नित करता है

• फ़ाइल के अंत को चिह्नित करता है

</पूर्व>

पिछले पुनरावृत्ति पर वापस लौटते हुए, हम 1 और 2 से पढ़ रहे थे। फ़ाइल 1 खाली होने से पहले 1 और 2 से एक रन मर्ज किया जाता है। ध्यान दें कि फ़ाइल 2 पूरी तरह से ख़त्म नहीं हुई है—अंतिम मर्ज (ऊपर) से मेल खाने के लिए इसमें एक रन बचा है।

<पूर्व> फ़ाइल 1 (में): ... | <1 रन> * ... <1 रन> | * फ़ाइल 2 (इंच): | <2 रन> * --> <1 रन> | <1 रन> * फ़ाइल 3 (बाहर): <1 रन> * </पूर्व>

एक और पुनरावृत्ति को पीछे छोड़ते हुए, फ़ाइल 3 के खाली होने से पहले 1 और 3 से 2 रन मर्ज किए जाते हैं।

<पूर्व> फ़ाइल 1 (इंच): | <3 रन> ... <2 रन> | <1 रन> * फ़ाइल 2 (बाहर): --> <2 रन> * फ़ाइल 3 (में): ... | <2 रन> * <2 रन> | * </पूर्व>

एक और पुनरावृत्ति को पीछे छोड़ते हुए, फ़ाइल 2 के खाली होने से पहले 2 और 3 से 3 रन मर्ज कर दिए जाते हैं।

<पूर्व> फ़ाइल 1 (बाहर): <3 रन> * फ़ाइल 2 (में): ... | <3 रन> * --> ... <3 रन> | * फ़ाइल 3 (इंच): | <5 रन> * <3 रन> | <2 रन> * </पूर्व>

एक और पुनरावृत्ति को पीछे छोड़ते हुए, फ़ाइल 1 के खाली होने से पहले 1 और 2 से 5 रन मर्ज कर दिए जाते हैं।

<पूर्व> फ़ाइल 1 (में): ... | <5 रन> * ... <5 रन> | * फ़ाइल 2 (इंच): | <8 रन> * --> <5 रन> | <3 रन> * फ़ाइल 3 (बाहर): <5 रन> * </पूर्व>

पॉलीफ़ेज़ मर्ज सॉर्ट के लिए वितरण

सही 3 फ़ाइल केस को देखते हुए, मर्ज किए गए पीछे की ओर काम करने के लिए रनों की संख्या: 1, 1, 2, 3, 5, ... एक फाइबोनैचि अनुक्रम का पता चलता है। 3 से अधिक फ़ाइलों का क्रम थोड़ा अधिक जटिल है; 4 फ़ाइलों के लिए, अंतिम स्थिति से शुरू करके और पीछे की ओर काम करते हुए, रन गिनती पैटर्न {1,0,0,0}, {0,1,1,1}, {1,0,2,2}, {3 है ,2,0,4}, {7,6,4,0}, {0,13,11,7}, {13,0,24,20}, ...।

सब कुछ बेहतर ढंग से काम करने के लिए, अंतिम मर्ज चरण में प्रत्येक इनपुट फ़ाइल पर बिल्कुल एक रन होना चाहिए। यदि किसी इनपुट फ़ाइल में एक से अधिक रन हैं, तो दूसरे चरण की आवश्यकता होगी। नतीजतन, पॉलीफ़ेज़ मर्ज सॉर्ट को प्रारंभिक आउटपुट फ़ाइलों में इनपुट डेटा के रन के प्रारंभिक वितरण के बारे में चतुर होने की आवश्यकता है। उदाहरण के लिए, 13 रन वाली एक इनपुट फ़ाइल फ़ाइल 1 में 5 रन और फ़ाइल 2 में 8 रन लिखेगी।

व्यवहार में, इनपुट फ़ाइल में पूर्ण वितरण के लिए आवश्यक रनों की सटीक संख्या नहीं होगी। इससे निपटने का एक तरीका एक आदर्श रन वितरण का अनुकरण करने के लिए काल्पनिक डमी रन के साथ वास्तविक वितरण को पैडिंग करना है।एक डमी रन एक ऐसे रन की तरह व्यवहार करता है जिसमें कोई रिकॉर्ड नहीं होता है। एक या अधिक डमी रन को एक या अधिक वास्तविक रन के साथ मर्ज करने से केवल वास्तविक रन ही मर्ज होते हैं, और बिना किसी वास्तविक रन के एक या अधिक डमी रन को मर्ज करने से एकल डमी रन बनता है। एक अन्य दृष्टिकोण मर्ज ऑपरेशन के दौरान आवश्यकतानुसार डमी रन का अनुकरण करना है। इष्टतम वितरण एल्गोरिदम के लिए रनों की संख्या पहले से जानने की आवश्यकता होती है। अन्यथा, अधिक सामान्य मामले में जहां रनों की संख्या पहले से ज्ञात नहीं होती है, लगभग इष्टतम वितरण एल्गोरिदम का उपयोग किया जाता है। कुछ वितरण एल्गोरिदम में रन को पुनर्व्यवस्थित करना शामिल है। यदि रनों की संख्या पहले से ज्ञात है, तो मर्ज चरणों को शुरू करने से पहले केवल आंशिक वितरण की आवश्यकता होती है। उदाहरण के लिए, 3 फ़ाइल केस पर विचार करें, जो फ़ाइल_1 में n रन से शुरू होता है। एफ को परिभाषित करें_i= एफ_i−1 + एफ_i−2 ith फाइबोनैचि संख्या के रूप में। यदि n = F_i, फिर F को स्थानांतरित करें_i−2 F को छोड़कर File_2 पर चलता है_i−1 फ़ाइल_1 पर शेष चलता है, एक आदर्श रन वितरण। यदि एफ_i< एन < एफ_i+1, n−F ले जाएँ_iFile_2 और F तक चलता है_i+1−n File_3 तक चलता है। पहला मर्ज पुनरावृत्ति n−F का विलय करता है_in−F को जोड़ते हुए File_1 और File_2 से चलता है_iमर्ज किया गया रन F तक जाता है_i+1−n रन पहले ही File_3 में स्थानांतरित हो चुके हैं। फ़ाइल_1 F पर समाप्त होती है_i−2 शेष चलता है, File_2 खाली हो जाता है, और File_3 F पर समाप्त होता है_i−1 चलता है, फिर से एक आदर्श रन वितरण। 4 या अधिक फ़ाइलों के लिए, गणित अधिक जटिल है, लेकिन अवधारणा समान है।

तुलना बनाम साधारण मर्ज सॉर्ट

प्रारंभिक वितरण के बाद, 4 फ़ाइलों का उपयोग करके एक सामान्य मर्ज सॉर्ट पूरे डेटासेट के 4 पुनरावृत्तियों में 16 एकल रिकॉर्ड रन को सॉर्ट करेगा, प्रारंभिक वितरण के बाद डेटासेट को सॉर्ट करने के लिए कुल 64 रिकॉर्ड को स्थानांतरित करेगा। 4 फ़ाइलों का उपयोग करके एक पॉलीफ़ेज़ मर्ज सॉर्ट 4 पुनरावृत्तियों में 17 एकल रिकॉर्ड को सॉर्ट करेगा, लेकिन चूंकि प्रत्येक पुनरावृत्ति लेकिन अंतिम पुनरावृत्ति केवल डेटासेट के एक अंश को स्थानांतरित करती है, यह प्रारंभिक के बाद डेटासेट को सॉर्ट करने के लिए कुल 48 रिकॉर्ड को ही स्थानांतरित करती है। वितरण। इस मामले में, सामान्य मर्ज सॉर्ट फ़ैक्टर 2.0 है, जबकि पॉलीफ़ेज़ समग्र फ़ैक्टर ≈2.73 है।

यह समझाने के लिए कि कमी कारक सॉर्ट प्रदर्शन से कैसे संबंधित है, कमी कारक समीकरण हैं:

कमी_कारक = exp(number_of_runs*log(number_of_runs)/run_move_count)
run_move_count = number_of_runs * लॉग(number_of_runs)/लॉग(reduction_factor)
run_move_count = number_of_runs * log_reduction_factor(number_of_runs)

उपरोक्त उदाहरणों के लिए रन मूव काउंट समीकरण का उपयोग करना:

• साधारण मर्ज सॉर्ट → $16\times \log _{2}(16)=64$,
• पॉलीफ़ेज़ मर्ज सॉर्ट → $17\times \log _{2.73}(17)=48$.

यहां कुछ मिलियन रिकॉर्ड्स के वास्तविक प्रकारों के आधार पर, फ़ाइलों की संख्या के आधार पर सूचीबद्ध पॉलीफ़ेज़ और सामान्य मर्ज सॉर्ट के लिए प्रभावी कमी कारकों की एक तालिका दी गई है। यह तालिका मोटे तौर पर पॉलीफ़ेज़ मर्ज सॉर्ट के चित्र 3 और चित्र 4 में दिखाए गए प्रति डेटासेट स्थानांतरित तालिकाओं में कमी कारक से मेल खाती है। पीडीएफ

<पूर्व>

1. फ़ाइलें

| प्रति पुनरावृत्ति डेटा का औसत अंश | | आदर्श आकार के डेटा पर पॉलीफ़ेज़ कमी कारक | | | आदर्श आकार के डेटा पर सामान्य कमी कारक | | | | 3 .73 1.94 1.41 (वर्ग 2) 4 .63 2.68 2.00 5 .58 3.20 2.45 (वर्ग 6) 6 .56 3.56 3.00 7 .55 3.80 3.46 (वर्ग 12) 8 .54 3.95 4.00 9 .53 4.07 4.47 (वर्ग 20) 10 .53 4.15 5.00 11 .53 4.22 5.48 (वर्ग 30) 12 .53 4.28 6.00 32 .53 4.87 16.00 </पूर्व>

सामान्य तौर पर, जब 8 से कम फ़ाइलें होती हैं तो पॉलीफ़ेज़ मर्ज सॉर्ट सामान्य मर्ज सॉर्ट से बेहतर होता है, जबकि सामान्य मर्ज सॉर्ट लगभग 8 या अधिक फ़ाइलों पर बेहतर होने लगता है।

अग्रिम पठन

• Bradley, James (1982), File and Data Base Techniques, Holt, Rinehart and Winston, ISBN 0-03-058673-9
• Reynolds, Samuel W. (August 1961), "A generalized polyphase merge algorithm", Communications of the ACM, New York, NY: ACM, 4 (8): 347–349, doi:10.1145/366678.366689, S2CID 28416100
• Sedgewick, Robert (1983), Algorithms, Addison-Wesley, pp. 163–165, ISBN 0-201-06672-6