हमें एन-वे विलय का उपयोग क्यों करना चाहिए? 2-तरफा विलय पर इसके फायदे क्या हैं?

Question

मैंने एन-वे विलय पर कुछ लेख पढ़ने की कोशिश की, लेकिन अवधारणा को समझ में नहीं आया। मैं उलझन में हूं कि आप 2-तरफा विलय पर एन-वे विलय का उपयोग क्यों करेंगे? तुम क्यों 3 भागों में विभाजित सरणी हैं, उन्हें सॉर्ट की तरह तो 2 तरह 2 भागों के विलय और उसके बाद इस के साथ 3 भाग की 2 तरह मर्ज 2 भागों :)

धन्यवाद

Answer 1

विलय कर दिया है एक "सामान्य में "मर्ज सॉर्ट करें, आप log2n की गहराई तक पहुंचने तक सरणी को 2 तक विभाजित करते हैं और फिर विलय शुरू करते हैं। आकार m के दो सरणी के प्रत्येक विलय में 2m संचालन भी होंगे।

यह निम्न सूत्र के लिए आप हो जाता है (समय विश्लेषण में):

n/2 * 2 + n/4 * 4 + ... 1 * n = n * log2n

अब अगर आप एक तीन तरह से मर्ज करते हैं, आप 3. द्वारा सरणी बांट देगा पिछले विधि के साथ अंतर दोहरा है :

• विभाजन की गहराई अब log3n है।
• मर्ज के दौरान, 2 तत्वों की तुलना करने के बजाय, आपको कम से कम 3 तत्वों को खोजने की आवश्यकता है।

इसका मतलब है कि, सबसे बुनियादी कार्यान्वयन में, आप इस तरह के एक सूत्र मिल जाएगा:

n/3 * 2*3 + n/9 * 2*9 + ... 1 * 2*n = 2 * n * log3n

ध्यान दें कि 2 गुणा किया जाता है, क्योंकि तीन तत्वों की न्यूनतम खोजने 2 आपरेशन के होते हैं।

असम्बद्ध रूप से, ये दोनों Θ(nlogn) दोनों हैं। हालांकि, शायद (मैंने कोशिश नहीं की है) अभ्यास में तीन-तरफा विलय प्रकार log3n की वजह से बेहतर प्रदर्शन करेगा। फिर भी, चूंकि log2n एन = 1000000 के लिए केवल 20 है, और log3n समान संख्या के लिए 12.5 है, मुझे संदेह है कि यह अनुकूलन वास्तव में प्रभावी होगा जब तक कि n काफी बड़ा न हो।

---

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

---

Jerry's answer भी देखना सुनिश्चित करें। मैं उनके साथ सहमत हूं कि मल्टीवे विलय की वास्तविक शक्ति कई डिस्क और समांतर प्रसंस्करण से निपटने से आती है।

Answer 2

जब आप बाहरी प्रकार कर रहे हों तो आप आम तौर पर विलय करने के लिए कई धाराओं के साथ समाप्त हो जाते हैं। उदाहरण के लिए, मान लें कि आपको डेटा के टेराबाइट को सॉर्ट करने की आवश्यकता है, और केवल 64 (गीगाबाइट्स रैम) कहें।

आप आमतौर पर इसे 64 गीगाबाइट्स में पढ़कर, इसे सॉर्ट करके, फिर इसे लिखकर ऐसा करेंगे। डेटा के पूर्ण टेराबाइट के लिए दोहराएं, प्रत्येक "खंड" के लिए एक इंटरमीडिएट फ़ाइल का उत्पादन करें, आप एक बार में स्मृति में रख सकते हैं। इसे सुधारने के तरीके हैं, लेकिन सबसे अच्छा आप आमतौर पर उम्मीद कर सकते हैं कि आप लगभग 128 गीगाबाइट्स की क्रमबद्ध इंटरमीडिएट फाइलें उत्पन्न करते हैं।

है कि आप मध्यवर्ती फाइल की संख्या के साथ छोड़ देता है एक साथ विलय करने के लिए - और संख्या लगभग निश्चित रूप से एक से अधिक 2.

हो जाएगा आप एक नियमित आधार पर यह करने के लिए कर रहे हैं, तो आप शायद कुछ है इसके साथ करने के लिए सुंदर उच्च अंत हार्डवेयर। यदि आपने प्रत्येक इंटरमीडिएट फ़ाइल को एक अलग डिस्क ड्राइव पर रखा है, (और आपके आउटपुट के लिए कम से कम एक और है) तो आप लगभग एक ही समय में केवल एक ही समय में सभी डेटा एक साथ विलय करके गति में सुधार कर सकते हैं। प्रक्रिया आम तौर पर I/O बाध्य होगी, इसलिए एक समय में (कहें) 8 डिस्क से पढ़ना आम तौर पर एक समय में केवल 2 डिस्क से पढ़ने के रूप में लगभग 4 गुना होगा (हालांकि यह आपकी आउटपुट डिस्क पर निर्भर करता है जिसमें बैंडविड्थ है , जो सच नहीं हो सकता है)। अधिक इंटरमीडिएट फ़ाइलों को बनाने से बचने के लिए (जिसके लिए आगे विलय की आवश्यकता होगी) आपकी समग्र गति शायद एक बड़े कारक द्वारा भी सुधार जाएगी।