पॉलीफ़ेज़ मर्ज सॉर्ट
पॉलीफ़ेज़ मर्ज़ सॉर्ट एक नीचे से ऊपर मर्ज सॉर्ट का एक रूप है जो उप-सूचियों (रन) के प्रारंभिक असमान वितरण का उपयोग करके एक सूची को सॉर्ट करता है, मुख्य रूप से बाहरी सॉर्टिंग (सॉर्टिंग एल्गोरिदम का एक वर्ग है) के लिए उपयोग किया जाता है, और यह सामान्य मर्ज सॉर्ट की समानता से अधिक कुशल है जब आठ से कम बाहरी कार्यशील फ़ाइलें (जैसे टेप ड्राइव या हार्ड ड्राइव पर फ़ाइल) हों। पॉलीफ़ेज़ मर्ज सॉर्ट एक सॉर्टिंग एल्गोरिदम नहीं है।
साधारण मर्ज सॉर्ट
मर्ज सॉर्ट एक डेटासेट के रिकॉर्ड को रिकॉर्ड के क्रमबद्ध रन में विभाजित करता है और फिर बार-बार सॉर्ट किए गए रन को बड़े क्रमबद्ध रन में मर्ज करता है जब तक कि केवल एक रन, सॉर्ट किया गया डेटासेट नहीं रह जाता है।
चार कार्यशील फ़ाइलों का उपयोग करके एक सामान्य मर्ज सॉर्ट उन्हें इनपुट फ़ाइलों की एक जोड़ी और आउटपुट फ़ाइलों की एक जोड़ी के रूप में व्यवस्थित करता है। डेटासेट को दो कार्यशील फ़ाइलों के बीच समान रूप से वितरित किया जाता है, या तो क्रमबद्ध रन के रूप में या सरलतम स्थिति में, एकल रिकॉर्ड, जिसे आकार 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 के लिए, प्रत्येक पुनरावृत्ति रन संख्या को √(N2−1)/4 = √N2−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 होगी।[1][2] ध्यान दें कि अंतिम पुनरावृत्ति को छोड़कर, रन गिनती में कमी कारक 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 फ़ाइल पॉलीफ़ेज़ मर्ज सॉर्ट
पॉलीफ़ेज़ मर्ज को उसकी अंतिम स्थितियों से शुरू करके पीछे की ओर काम करते हुए देखना सबसे आसान है। प्रत्येक पुनरावृत्ति की प्रारंभ में, दो इनपुट फ़ाइलें और एक आउटपुट फ़ाइल होगी। पुनरावृत्ति के अंत में, एक इनपुट फ़ाइल पूरी तरह से समाप्त हो जाएगी और अगले पुनरावृत्ति के लिए आउटपुट फ़ाइल बन जाएगी। वर्तमान आउटपुट फ़ाइल अगले पुनरावृत्ति के लिए एक इनपुट फ़ाइल बन जाएगी। शेष फ़ाइलें (3 फ़ाइल केस में केवल एक) केवल आंशिक रूप से उपभोग की गई हैं और उनके शेष रन अगले पुनरावृत्ति के लिए इनपुट होंगे।
फ़ाइल 1 अभी-अभी खाली हुई और नई आउटपुट फ़ाइल बन गई। प्रत्येक इनपुट टेप पर एक रन छोड़ा गया है, और उन रन को एक साथ मर्ज करने से सॉर्ट की गई फ़ाइल बन जाएगी।
File 1 (out): <1 run> * (the sorted file)
File 2 (in ): ... | <1 run> * --> ... <1 run> | * (consumed)
File 3 (in ): | <1 run> * <1 run> | * (consumed)
... possible runs that have already been read
| marks the read pointer of the file
* marks end of fileपिछले पुनरावृत्ति पर वापस लौटते हुए, हम 1 और 2 से पढ़ रहे थे। फ़ाइल 1 खाली होने से पहले 1 और 2 से एक रन मर्ज किया जाता है। ध्यान दें कि फ़ाइल 2 पूरी तरह से ख़त्म नहीं हुई है—अंतिम मर्ज (ऊपर) से मेल खाने के लिए इसमें एक रन बचा है।
File 1 (in ): ... | <1 run> * ... <1 run> | *
File 2 (in ): | <2 run> * --> <1 run> | <1 run> *
File 3 (out): <1 run> *एक और पुनरावृत्ति को पीछे छोड़ते हुए, फ़ाइल 3 के खाली होने से पहले 1 और 3 से 2 रन मर्ज किए जाते हैं।
File 1 (in ): | <3 run> ... <2 run> | <1 run> *
File 2 (out): --> <2 run> *
File 3 (in ): ... | <2 run> * <2 run> | *एक और पुनरावृत्ति को पीछे छोड़ते हुए, फ़ाइल 2 के खाली होने से पहले 2 और 3 से 3 रन मर्ज कर दिए जाते हैं।
File 1 (out): <3 run> *
File 2 (in ): ... | <3 run> * --> ... <3 run> | *
File 3 (in ): | <5 run> * <3 run> | <2 run> *एक और पुनरावृत्ति को पीछे छोड़ते हुए, फ़ाइल 1 के खाली होने से पहले 1 और 2 से 5 रन मर्ज कर दिए जाते हैं।
File 1 (in ): ... | <5 run> * ... <5 run> | *
File 2 (in ): | <8 run> * --> <5 run> | <3 run> *
File 3 (out): <5 run> *पॉलीफ़ेज़ मर्ज सॉर्ट के लिए वितरण
सही 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 रन लिखेगी।
व्यवहार में, इनपुट फ़ाइल में पूर्ण वितरण के लिए आवश्यक रनों की सटीक संख्या नहीं होगी। इससे निपटने का एक तरीका एक आदर्श रन वितरण का अनुकरण करने के लिए काल्पनिक "डमी रन" के साथ वास्तविक वितरण को पैडिंग करना है।[1] एक डमी रन एक ऐसे रन की तरह व्यवहार करता है जिसमें कोई रिकॉर्ड नहीं होता है। एक या अधिक डमी रन को एक या अधिक वास्तविक रन के साथ मर्ज करने से केवल वास्तविक रन ही मर्ज होते हैं, और बिना किसी वास्तविक रन के एक या अधिक डमी रन को मर्ज करने से एकल डमी रन बनता है। एक अन्य दृष्टिकोण मर्ज ऑपरेशन के समय आवश्यकतानुसार डमी रन का अनुकरण करना है।[4]
"इष्टतम" वितरण एल्गोरिदम के लिए रनों की संख्या पहले से जानने की आवश्यकता होती है। अन्यथा, अधिक सामान्य मामले में जहां रनों की संख्या पहले से ज्ञात नहीं होती है, "इष्टतम के निकट" वितरण एल्गोरिदम का उपयोग किया जाता है। कुछ वितरण एल्गोरिदम में रन को पुनर्व्यवस्थित करना सम्मलित है।[5] यदि रनों की संख्या पहले से ज्ञात है, तो मर्ज चरणों को शुरू करने से पहले केवल आंशिक वितरण की आवश्यकता होती है। उदाहरण के लिए, 3 फ़ाइल केस पर विचार करें, जो फ़ाइल_1 में n रन से शुरू होता है। Fi = Fi−1 + Fi−2 को iवें फाइबोनैचि संख्या के रूप में परिभाषित करें। यदि n = Fi, तो Fi−2 रन को File_2 पर ले जाएं, Fi−1 रन को File_1 पर शेष छोड़ दें, जो एक आदर्श रन वितरण है। यदि Fi < n < Fi+1, तो n−Fi को File_2 पर चलाएं और Fi+1−n को File_3 पर चलाएं। पहला मर्ज पुनरावृत्ति फ़ाइल_1 और फ़ाइल_2 से n−Fi रन को मर्ज करता है, n−Fi मर्ज किए गए रन को Fi+1−n रन में जोड़ता है जो पहले से ही File_3 में ले जाया गया है। File_1 Fi-2 रन शेष के साथ समाप्त होता है, File_2 खाली हो जाता है, और File_3 Fi−1 रन के साथ समाप्त होता है, फिर से एक आदर्श रन वितरण। 4 या अधिक फ़ाइलों के लिए, गणित अधिक जटिल है, लेकिन अवधारणा समान है।
तुलना बनाम साधारण मर्ज सॉर्ट
प्रारंभिक वितरण के पश्चात, 4 फ़ाइलों का उपयोग करके एक सामान्य मर्ज सॉर्ट पूरे डेटासेट के 4 पुनरावृत्तियों में 16 एकल रिकॉर्ड रन को सॉर्ट करेगा, प्रारंभिक वितरण के पश्चात डेटासेट को सॉर्ट करने के लिए कुल 64 रिकॉर्ड को स्थानांतरित करेगा। 4 फ़ाइलों का उपयोग करके एक पॉलीफ़ेज़ मर्ज सॉर्ट 4 पुनरावृत्तियों में 17 एकल रिकॉर्ड को सॉर्ट करेगा, लेकिन चूंकि प्रत्येक पुनरावृत्ति लेकिन अंतिम पुनरावृत्ति केवल डेटासेट के एक अंश को स्थानांतरित करती है, यह प्रारंभिक के पश्चात डेटासेट को सॉर्ट करने के लिए कुल 48 रिकॉर्ड को ही स्थानांतरित वितरण करती है। इस मामले में, सामान्य मर्ज सॉर्ट फ़ैक्टर 2.0 है, जबकि पॉलीफ़ेज़ समग्र फ़ैक्टर ≈2.73 है।
यह समझाने के लिए कि कमी कारक सॉर्ट प्रदर्शन से कैसे संबंधित है, कमी कारक समीकरण हैं:
reduction_factor = exp(number_of_runs*log(number_of_runs)/run_move_count)
run_move_count = number_of_runs * log(number_of_runs)/log(reduction_factor)
run_move_count = number_of_runs * log_reduction_factor(number_of_runs)उपरोक्त उदाहरणों के लिए रन मूव काउंट समीकरण का उपयोग करना:
- साधारण मर्ज सॉर्ट → ,
- पॉलीफ़ेज़ मर्ज सॉर्ट → .
यहां कुछ मिलियन रिकॉर्ड्स के वास्तविक प्रकारों के आधार पर, फ़ाइलों की संख्या के आधार पर सूचीबद्ध पॉलीफ़ेज़ और सामान्य मर्ज सॉर्ट के लिए प्रभावी कमी कारकों की एक तालिका दी गई है। यह तालिका मोटे तौर पर पॉलीफ़ेज़ मर्ज सॉर्ट के चित्र 3 और चित्र 4 में दिखाए गए प्रति डेटासेट स्थानांतरित तालिकाओं में कमी कारक से मेल खाती है। पीडीएफ
# files
| average fraction of data per iteration
| | polyphase reduction factor on ideal sized data
| | | ordinary reduction factor on ideal sized data
| | | |
3 .73 1.94 1.41 (sqrt 2)
4 .63 2.68 2.00
5 .58 3.20 2.45 (sqrt 6)
6 .56 3.56 3.00
7 .55 3.80 3.46 (sqrt 12)
8 .54 3.95 4.00
9 .53 4.07 4.47 (sqrt 20)
10 .53 4.15 5.00
11 .53 4.22 5.48 (sqrt 30)
12 .53 4.28 6.00
32 .53 4.87 16.00सामान्यतः, जब 8 से कम फ़ाइलें होती हैं तो पॉलीफ़ेज़ मर्ज सॉर्ट सामान्य मर्ज सॉर्ट से बेहतर होता है, जबकि सामान्य मर्ज सॉर्ट प्राय 8 या अधिक फ़ाइलों पर बेहतर होने लगता है।[6][7]
संदर्भ
- ↑ 1.0 1.1 Donald Knuth, The Art of Computer Programming, Volume 3, Addison Wesley, 1973, Algorithm 5.4.2D.
- ↑ "एल्गोरिदम को सॉर्ट करना और खोजना". Archived from the original on 2012-11-22. Retrieved 2010-01-31.
- ↑ "बाहरी छँटाई". Archived from the original on 2016-01-28. Retrieved 2016-01-22.
- ↑ https://www.fq.math.ca/Scanned/8-1/lynch.pdf[bare URL PDF]
- ↑ http://i.stanford.edu/pub/cstr/reports/cs/tr/76/543/CS-TR-76-543.pdf[bare URL PDF]
- ↑ "Advanced Programming I Lecture Notes".
- ↑ http://www.mif.vu.lt/~algis/dsax/DsSort.pdf[bare URL PDF]
अग्रिम पठन
- ब्राडली, जेम्स (1982), फ़ाइल और डेटा बेस तकनीकें, होल्ट, राइनहार्ट और विंस्टन, ISBN 0-03-058673-9
{{citation}}: Invalid|url-access=पंजीकरण(help) - रेनॉल्ड्स, सैमुअल डब्ल्यू. (अगस्त 1961), "एक सामान्यीकृत पॉलीफ़ेज़ मर्ज एल्गोरिदम", एसीएम का संचार, न्यूयॉर्क, एनवाई: एसीएम, 4 (8): 347–349, doi:10.1145/366678.366689, S2CID 28416100
{{citation}}: Check date values in:|date=(help) - सेडगेविक, रॉबर्ट (1983), एल्गोरिदम, एडिसन-वेस्ले, pp. 163–165, ISBN 0-201-06672-6
{{citation}}: Invalid|url-access=पंजीकरण(help)
