के-वे मर्ज एल्गोरिदम
कंप्यूटर विज्ञान में, के-वे मर्ज एल्गोरिदम या मल्टीवे मर्ज एक विशिष्ट प्रकार k अनुक्रम मर्ज एल्गोरिदम हैं जो k क्रमबद्ध सूचियों को लेने और उन्हें एक एकल क्रमबद्ध सूची में विलय करने में विशेषज्ञ हैं। यह मर्ज एल्गोरिदम सामान्यतः मर्ज एल्गोरिदम को संदर्भित करते हैं जो दो से अधिक क्रमबद्ध सूचियों को लेते हैं। इस प्रकार दो-तरफा मर्ज को बाइनरी मर्ज भी कहा जाता है। के-वे मर्ज बाहरी सॉर्टिंग एल्गोरिदम भी है।
दोतरफा विलय
मर्ज़ सॉर्ट में इसकी महत्वपूर्ण भूमिका के कारण 2-तरफ़ा मर्ज, या बाइनरी मर्ज का बड़े पैमाने पर अध्ययन किया गया है। इस प्रकार इसका एक उदाहरण क्लासिक मर्ज है जो मर्ज सॉर्ट उदाहरणों में अधिकांशतः दिखाई देता है। क्लासिक मर्ज प्रत्येक चरण में सबसे कम कुंजी के साथ डेटा आइटम को आउटपुट करता है; कुछ क्रमबद्ध सूचियों को देखते हुए, यह एक क्रमबद्ध सूची तैयार करता है जिसमें किसी भी इनपुट सूची में सभी तत्व सम्मिलित होते हैं, और यह इनपुट सूचियों की लंबाई के योग के अनुपात में समय पर ऐसा करता है।
बढ़ते क्रम में क्रमबद्ध दो सरणियों को A[1..p] और B[1..q] द्वारा निरूपित करें।
इसके अतिरिक्त, आउटपुट ऐरे को C[1..n] से निरूपित करें।
कैनोनिकल 2-वे मर्ज एल्गोरिदम[1] सूचकांक i, j, और k को क्रमशः A, B, और C में संग्रहीत करता है।
प्रारंभ में, यह सूचकांक पहले तत्व को संदर्भित करते हैं, अर्थात 1 हैं।
यदि A[i] < B[j], तब एल्गोरिथ्म A[i] को C[k] में कॉपी करता है और i और k को बढ़ाता है।
अन्यथा, एल्गोरिदम B[j] को C[k] में कॉपी करता है और j और k को बढ़ाता है।
एक विशेष मामला उत्पन्न होता है यदि i या j में से कोई भी A या B के अंत तक पहुँच गया है।
इस स्थितियों में एल्गोरिदम B या A के शेष तत्वों को C में कॉपी करता है और समाप्त करता है।
के-वे मर्ज
के-वे मर्ज समस्या में समान तत्वों के साथ एकल क्रमबद्ध सरणी बनाने के लिए k क्रमबद्ध सरणियों को मर्ज करना सम्मिलित है।
तत्वों की कुल संख्या को n से निरूपित करें।
इस प्रकार n आउटपुट ऐरे k आकार और k इनपुट ऐरे k आकार के योग के सामान्तर है।
सरलता के लिए, हम मानते हैं कि कोई भी इनपुट ऐरे खाली नहीं है।
एक परिणाम के रूप में , जो सूची किए गए चलने के समय को सरल बनाता है।
उसमें समस्या का समाधान किया जा सकता है के साथ समय चल रहा है अंतरिक्ष।
इस रनिंग टाइम को प्राप्त करने वाले अनेक एल्गोरिदम उपस्तिथ हैं।
पुनरावृत्तीय 2-तरफा विलय
समस्या को 2-तरफा मर्ज का उपयोग करके दो k सरणियों को पुनरावृत्त रूप से मर्ज करके हल किया जा सकता है जब तक कि केवल एक ही ऐरे न रह जाए। इस प्रकार यदि सरणियों को मनमाने क्रम में मर्ज किया जाता है, तब परिणामी रनिंग समय केवल O(kn) होता है। यह उप-इष्टतम है.
पहले को दूसरे के साथ, तीसरे को चौथे के साथ, इत्यादि को पुनरावृत्त रूप से विलय करके चलने के समय में सुधार किया जा सकता है। चूँकि प्रत्येक पुनरावृत्ति में सरणियों की संख्या आधी हो जाती है, केवल Θ(लॉग k) पुनरावृत्तियाँ होती हैं। इस प्रकार प्रत्येक पुनरावृत्ति में प्रत्येक तत्व को ठीक एक बार स्थानांतरित किया जाता है। इसलिए प्रति पुनरावृत्ति चलने का समय Θ(n) में है क्योंकि n तत्वों की संख्या है। इसलिए कुल चलने का समय Θ(n log k) में है।
हम दो सबसे छोटी सरणियों को पुनरावृत्त रूप से मर्ज करके, इस एल्गोरिदम में और सुधार कर सकते हैं। इस प्रकार यह स्पष्ट है कि यह चलने के समय को कम करता है और इसलिए पिछले पैराग्राफ में वर्णित रणनीति से बदतर नहीं हो सकता है। इसलिए चलने का समय O(n log k) में है। सौभाग्य से, सीमावर्ती स्थितियों में चलने का समय उत्तम हो सकता है। उदाहरण के लिए पतित स्थितियों पर विचार करें, जहां एक सरणी को छोड़कर सभी में केवल एक तत्व होता है। इस प्रकार पिछले पैराग्राफ में बताई गई रणनीति के लिए Θ(n log k) रनिंग टाइम की आवश्यकता होती है, जबकि उत्तम रणनीति के लिए केवल Θ(n + k log k) रनिंग टाइम की आवश्यकता होती है।
डायरेक्ट के-वे मर्ज
इस स्थितियों में, हम एक साथ k-रन को एक साथ मर्ज कर देंगे।
एक सीधा कार्यान्वयन न्यूनतम निर्धारित करने के लिए सभी k सरणियों को स्कैन करेगा।
इस सीधे कार्यान्वयन के परिणामस्वरूप Θ(kn) का रनिंग टाइम प्राप्त होता है।
ध्यान दें कि इसका उल्लेख केवल चर्चा के लिए एक संभावना के रूप में किया गया है। चूँकि यह काम करेगा, किन्तु यह कुशल नहीं है।
हम सबसे छोटे तत्व की तेजी से गणना करके इसमें सुधार कर सकते हैं।
हीप (डेटा संरचना), टूर्नामेंट ट्री, या बिखरा हुआ ट्री का उपयोग करके, सबसे छोटा तत्व O(लॉग k) समय में निर्धारित किया जा सकता है।
इसलिए परिणामी चलने का समय O(n log k) में है।
ढेर का उपयोग सामान्यतः अधिक किया जाता है, चूंकि टूर्नामेंट ट्री व्यवहार में तेज़ होता है। एक ढेर प्रत्येक चरण में लगभग 2*लॉग(k) तुलनाओं का उपयोग करता है क्योंकि यह ट्री को जड़ से नीचे तक संभालता है और प्रत्येक नोड के दोनों बच्चों की तुलना करने की आवश्यकता होती है। इस प्रकार इस मध्य, एक टूर्नामेंट ट्री को केवल लॉग (के) तुलना की आवश्यकता होती है क्योंकि यह ट्री के नीचे से प्रारंभ होता है और जड़ तक काम करता है, प्रत्येक परत में केवल एक ही तुलना करता है। इसलिए टूर्नामेंट ट्री को पसंदीदा कार्यान्वयन होना चाहिए।
ढेर
विचार यह है कि k सूचियों का न्यूनतम-ढेर बनाए रखा जाए, प्रत्येक को उनके सबसे छोटे वर्तमान तत्व द्वारा कुंजीबद्ध किया जाए। इस प्रकार एक सरल एल्गोरिदम ढेर से नोड्स के साथ एक आउटपुट बफर बनाता है। इस प्रकार नोड्स का एक न्यूनतम-ढेर बनाकर प्रारंभ करें, जहां प्रत्येक नोड में सूची का एक प्रमुख तत्व और सूची का शेष (या पूंछ) होता है। चूँकि सूचियाँ प्रारंभ में क्रमबद्ध होती हैं, शीर्ष प्रत्येक सूची का सबसे छोटा तत्व होता है; हीप प्रॉपर्टी गारंटी देती है कि रूट में सभी सूचियों में न्यूनतम तत्व सम्मिलित हैं। हीप से रूट नोड निकालें, हेड एलिमेंट को आउटपुट बफर में जोड़ें, टेल से एक नया नोड बनाएं और इसे हीप में डालें। इस प्रकार तब तक दोहराएं जब तक कि ढेर में केवल एक नोड न रह जाए, उस बिंदु पर बस उस शेष सूची (हेड और टेल) को आउटपुट बफर में जोड़ दें।
पॉइंटर्स का उपयोग करना, एक इन-प्लेस हीप एल्गोरिदम[2] इनपुट सरणियों में पॉइंटर्स का एक न्यूनतम-ढेर आवंटित करता है।
प्रारंभ में यह पॉइंटर्स इनपुट ऐरे के सबसे छोटे तत्वों की ओर संकेत करते हैं।
सूचकों को उस मान के आधार पर क्रमबद्ध किया जाता है जिस पर वे इंगित करते हैं।
O(k) प्रीप्रोसेसिंग चरण में मानक हीपिफ़ाई प्रक्रिया का उपयोग करके ढेर बनाया जाता है।
पश्चात् में, एल्गोरिदम पुनरावृत्त रूप से उस तत्व को स्थानांतरित करता है जिसे रूट पॉइंटर इंगित करता है, इस पॉइंटर को बढ़ाता है और रूट तत्व पर मानक कमी कुंजी प्रक्रिया निष्पादित करता है।
वृद्धि कुंजी प्रक्रिया का चलने का समय O(लॉग k) से घिरा है।
चूँकि n तत्व हैं, कुल चलने का समय O(n log k) है।
ध्यान दें कि कुंजी को बदलने और पुनरावृत्त रूप से कमी-कुंजी या सिफ्ट-डाउन करने का संचालन अनेक प्राथमिकता कतार पुस्तकालयों जैसे सी ++ एसटीएल और जावा द्वारा समर्थित नहीं है। एक्स्ट्रेक्ट-मिन और इंसर्ट फलन करना कम कुशल है।
टूर्नामेंट ट्री
टूर्नामेंट ट्री [3] खेल प्रतियोगिताओं की तरह, एक एलिमिनेशन टूर्नामेंट पर आधारित है। प्रत्येक गेम में, दो इनपुट तत्व प्रतिस्पर्धा करते हैं। विजेता को अगले दौर में पदोन्नत किया जाता है। इसलिए, हमें खेलों का एक द्विआधारी ट्री मिलता है। सूची को आरोही क्रम में क्रमबद्ध किया गया है, इसलिए गेम का विजेता दोनों तत्वों में से छोटा होता है।
के-वे विलय के लिए, केवल प्रत्येक गेम के हारने वाले को स्टोर करना अधिक कुशल है (छवि देखें)। इसलिए डेटा संरचना को लूज़र ट्री कहा जाता है। इस प्रकार ट्री बनाते समय या किसी तत्व को उसकी सूची में से अगले तत्व से प्रतिस्थापित करते समय, हम अभी भी गेम के विजेता को शीर्ष पर बढ़ावा देते हैं। इस प्रकार ट्री एक खेल मैच की तरह भरा हुआ है किन्तु नोड्स केवल हारने वाले को ही संग्रहीत करते हैं। सामान्यतः, रूट के ऊपर एक अतिरिक्त नोड जोड़ा जाता है जो समग्र विजेता का प्रतिनिधित्व करता है। प्रत्येक पत्ता किसी एक इनपुट ऐरे में एक पॉइंटर संग्रहीत करता है। प्रत्येक आंतरिक नोड एक मान और एक सूचकांक संग्रहीत करता है। इस प्रकार आंतरिक नोड का सूचकांक इंगित करता है कि मान किस इनपुट सरणी से आता है। मान में संबंधित इनपुट सरणी के पहले तत्व की एक प्रति सम्मिलित है।
एल्गोरिथ्म पुनरावृत्त रूप से न्यूनतम तत्व को परिणाम में जोड़ता है और फिर तत्व को संबंधित इनपुट सूची से हटा देता है। यह अद्यतन पत्ती से रूट (प्रतिस्थापन चयन) तक पथ पर नोड्स को अद्यतन करता है। इस प्रकार हटाया गया तत्व समग्र विजेता है। इसलिए, इसने इनपुट ऐरे से रूट तक के पथ पर प्रत्येक गेम जीता है। इनपुट ऐरे से एक नया तत्व चुनते समय, तत्व को रूट के पथ पर पिछले हारे हुए तत्वों के विरुद्ध प्रतिस्पर्धा करने की आवश्यकता होती है। इस प्रकार हारे हुए ट्री का उपयोग करते समय, गेम को दोबारा खेलने के लिए भागीदार पहले से ही नोड्स में संग्रहीत होता है। दोबारा खेले गए प्रत्येक गेम के हारने वाले को नोड में लिखा जाता है और विजेता को पुनरावृत्त रूप से शीर्ष पर पदोन्नत किया जाता है। जब रूट पर पहुंच जाता है, तब नया समग्र विजेता मिल जाता है और विलय के अगले दौर में इसका उपयोग किया जा सकता है।
इस अनुभाग में टूर्नामेंट ट्री और हारने वाले ट्री की छवियां समान डेटा का उपयोग करती हैं और हारने वाले ट्री के काम करने के तरीके को समझने के लिए उनकी तुलना की जा सकती है।
एल्गोरिथम
एक टूर्नामेंट ट्री को इनपुट सूचियों में सेंटिनल्स जोड़कर (अर्थात अनंत के मूल्य के साथ प्रत्येक सूची के अंत में एक सदस्य जोड़कर) और संख्या तक शून्य सूचियां (केवल एक सेंटिनल सम्मिलित करके) जोड़कर एक संतुलित बाइनरी ट्री के रूप में दर्शाया जा सकता है। सूचियाँ दो की शक्ति है। संतुलित ट्री को एक ही सारणी में संग्रहित किया जा सकता है। वर्तमान सूचकांक को दो से विभाजित करके मूल तत्व तक पहुंचा जा सकता है।
जब पत्तों में से एक को अद्यतन किया जाता है, तब पत्ते से जड़ तक सभी खेल दोबारा खेले जाते हैं। इस प्रकार निम्नलिखित स्यूडोकोड में, एक सरणी के अतिरिक्त एक ऑब्जेक्ट ओरिएंटेड ट्री का उपयोग किया जाता है क्योंकि इसे समझना आसान है। इसके अतिरिक्त, विलय की जाने वाली सूचियों की संख्या दो की घात मानी जाती है।
function merge(L1, ..., Ln) buildTree(heads of L1, ..., Ln) while tree has elements winner := tree.winner output winner.value new := winner.index.next replayGames(winner, new) // Replacement selection
function replayGames(node, new) loser, winner := playGame(node, new) node.value := loser.value node.index := loser.index if node != root replayGames(node.parent, winner)
function buildTree(elements) nextLayer := new Array() while elements not empty el1 := elements.take() el2 := elements.take() loser, winner := playGame(el1, el2) parent := new Node(el1, el2, loser) nextLayer.add(parent) if nextLayer.size == 1 return nextLayer // only root else return buildTree(nextLayer)
कार्यकारी समय
शुरुआत में, ट्री पहली बार Θ(k) समय में बनाया गया है। विलय के प्रत्येक चरण में, केवल नए तत्व से रूट तक के पथ पर गेम को फिर से चलाने की आवश्यकता होती है। इस प्रकार प्रत्येक परत में, केवल एक तुलना की आवश्यकता है। चूँकि ट्री संतुलित है, इनपुट सरणियों में से एक से रूट तक के पथ में केवल Θ(लॉग k) तत्व होते हैं। कुल मिलाकर, ऐसे n तत्व हैं जिन्हें स्थानांतरित करने की आवश्यकता है। परिणामस्वरूप कुल चलने का समय Θ(n log k) में है।[3]
उदाहरण
निम्नलिखित अनुभाग में प्रतिस्थापन चयन चरण के लिए एक विस्तृत उदाहरण और एकाधिक प्रतिस्थापन चयन वाले पूर्ण मर्ज के लिए एक उदाहरण सम्मिलित है।
प्रतिस्थापन चयन
खेल नीचे से ऊपर तक दोबारा खेले जाते हैं। ट्री की प्रत्येक परत में, नोड का वर्तमान में संग्रहीत तत्व और नीचे की परत से प्रदान किया गया तत्व प्रतिस्पर्धा करते हैं। इस प्रकार विजेता को तब तक शीर्ष पर पदोन्नत किया जाता है जब तक हमें नया समग्र विजेता नहीं मिल जाता हैं। हारने वाला ट्री के नोड में संग्रहीत होता है।
| चरण | कार्य |
|---|---|
| 1 | लीफ 1 (समग्र विजेता) को इनपुट सूची से अगले तत्व 9 से बदल दिया गया है। |
| 2 | खेल 9 बनाम 7 (पिछला हारा हुआ) दोबारा खेलना। 7 जीतता है क्योंकि यह छोटा है। इसलिए, 7 को शीर्ष पर पदोन्नत किया गया है जबकि 9 को नोड में सहेजा गया है। |
| 3 | गेम 7 बनाम 3 (पिछला हारा हुआ) दोबारा खेलना। 3 जीतता है क्योंकि यह छोटा है। इसलिए, 3 को शीर्ष पर पदोन्नत किया गया है जबकि 7 को नोड में सहेजा गया है। |
| 4 | गेम 3 बनाम 2 (पिछला हारा हुआ) दोबारा खेलना। 2 जीतता है क्योंकि यह छोटा है। इसलिए, 2 को शीर्ष पर पदोन्नत किया गया है जबकि 3 को नोड में सहेजा गया है। |
| 5 | नया समग्र विजेता 2 रूट के ऊपर सहेजा गया है। |
मर्ज
मर्ज को निष्पादित करने के लिए, समग्र सबसे छोटे तत्व को बार-बार अगले इनपुट तत्व के साथ प्रतिस्थापित किया जाता है। इस प्रकार उसके पश्चात्, शीर्ष तक के खेल दोबारा खेले जाते हैं।
यह उदाहरण इनपुट के रूप में चार क्रमबद्ध सरणियों का उपयोग करता है।
{2, 7, 16}
{5, 10, 20}
{3, 6, 21}
{4, 8, 9}
एल्गोरिदम की शुरुआत प्रत्येक इनपुट सूची के प्रमुखों से की जाती है। इन तत्वों का उपयोग करके, हारे हुए लोगों का एक द्विआधारी ट्री बनाया जाता है। इस प्रकार विलय के लिए, निम्नतम सूची तत्व 2 को ट्री के शीर्ष पर समग्र न्यूनतम तत्व को देखकर निर्धारित किया जाता है। फिर उस मान को हटा दिया जाता है, और उसके पत्ते को 7 से भर दिया जाता है, जो इनपुट सूची में अगला मान है। प्रतिस्थापन चयन के बारे में पिछले अनुभाग की तरह शीर्ष पर जाने वाले खेल दोबारा खेले जाते हैं। इस प्रकार हटाया जाने वाला अगला तत्व 3 है। सूची में अगले मान 6 से प्रारंभ करके, गेम को रूट तक दोबारा खेला जाता है। इसे तब तक दोहराया जा रहा है जब तक कि ट्री का न्यूनतम मान अनंत के सामान्तर न हो जाए।
चलने के समय की निचली सीमा
कोई यह दिखा सकता है कि O(n f(k)) में चलने वाले समय के साथ कोई तुलना-आधारित k-वे मर्ज एल्गोरिदम उपस्तिथ नहीं है, इस प्रकार जहां f एक लघुगणक की तुलना में असम्बद्ध रूप से धीमी गति से बढ़ता है, और n तत्वों की कुल संख्या है।
(असंयुक्त श्रेणियों जैसे वांछनीय वितरण वाले डेटा को छोड़कर।)
इसका प्रमाण तुलना-आधारित छँटाई से एक सीधी कमी है।
मान लीजिए कि ऐसा कोई एल्गोरिदम उपस्तिथ है, तब हम निम्न प्रकार से रनिंग टाइम O(n f(n)) के साथ तुलना-आधारित सॉर्टिंग एल्गोरिदम का निर्माण इस प्रकार कर सकते हैं:
इनपुट ऐरे को आकार 1 के n ऐरे में काटें।
इन n सरणियों को k-वे मर्ज एल्गोरिथम के साथ मर्ज करें।
परिणामी सरणी को क्रमबद्ध किया गया है और एल्गोरिथ्म में O(n f(n)) में चलने का समय है।
यह सुविख्यात परिणाम का विरोधाभास है कि O(n log n) के नीचे सबसे खराब स्थिति में चलने वाले समय के साथ कोई तुलना-आधारित सॉर्टिंग एल्गोरिदम उपस्तिथ नहीं है।
बाहरी छँटाई
के-वे मर्ज का उपयोग बाहरी सॉर्टिंग प्रक्रियाओं में किया जाता है।[4] बाहरी सॉर्टिंग सॉर्टिंग एल्गोरिदम का एक वर्ग है जो भारी मात्रा में डेटा को संभाल सकता है। इस प्रकार बाहरी सॉर्टिंग की आवश्यकता तब होती है जब सॉर्ट किया जा रहा डेटा कंप्यूटिंग डिवाइस (सामान्यतः रैम) की मुख्य मेमोरी में फिट नहीं होता है और इसके अतिरिक्त उन्हें धीमी बाहरी मेमोरी (सामान्यतः हार्ड ड्राइव) में रहना चाहिए। इस प्रकार के-वे मर्ज एल्गोरिदम सामान्यतः बाहरी सॉर्टिंग एल्गोरिदम के दूसरे चरण में होते हैं, ठीक वैसे ही जैसे वे मर्ज सॉर्ट के लिए करते हैं।
मल्टीवे मर्ज मेमोरी के बाहर की फ़ाइलों को बाइनरी मर्ज की तुलना में कम पास में मर्ज करने की अनुमति देता है। यदि 6 रन हैं जिन्हें मर्ज करने की आवश्यकता है तब एक बाइनरी मर्ज को 3 मर्ज पास लेने की आवश्यकता होगी, 6-वे मर्ज के एकल मर्ज पास के विपरीत। मर्ज पास की यह कमी विशेष रूप से बड़ी मात्रा में जानकारी को ध्यान में रखते हुए महत्वपूर्ण है जिसे सामान्यतः पहले स्थान पर क्रमबद्ध किया जाता है, जिससे अधिक गति-अप की अनुमति मिलती है जबकि धीमी भंडारण तक पहुंच की मात्रा भी कम हो जाती है।
संदर्भ
- ↑ Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (2001). एल्गोरिदम का परिचय. MIT Press. pp. 28–29. ISBN 978-0-262-03293-3.
- ↑ Bentley, Jon Louis (2000). Programming Pearls (2nd ed.). Addison Wesley. pp. 147–162. ISBN 0201657880.
- ↑ 3.0 3.1 Knuth, Donald (1998). "Chapter 5.4.1. Multiway Merging and Replacement Selection". Sorting and Searching. The Art of Computer Programming. Vol. 3 (2nd ed.). Addison-Wesley. pp. 252–255. ISBN 0-201-89685-0.
- ↑ Shaffer, Clifford A. (2012-07-26). C++ में डेटा संरचनाएं और एल्गोरिथम विश्लेषण, तीसरा संस्करण. Courier Corporation. ISBN 9780486172620.
