टाइम कॉम्प्लेक्सिटी/बाहरी मर्ज की लागत क्रमबद्ध करें

Question

मुझे यह link से मिला जो बाहरी विलय प्रकार के बारे में बात करता है।

स्लाइड 6 उदाहरण से

: 5 बफर पृष्ठों के साथ, 108 पृष्ठ फ़ाइल को सॉर्ट करने

• Pass0: [108/5] = 22 5 पृष्ठों प्रत्येक (केवल 3 पृष्ठों के साथ पिछले रन)

  की क्रमबद्ध रन

• Pass1 [22/4] 20 पृष्ठों प्रत्येक (केवल 8 पृष्ठों के साथ पिछले रन) के = 6 अनुसार क्रमबद्ध रन

• Pass2: [6/3] = 2 छाँटे गए रन, 80 पृष्ठों और 28 पृष्ठों

• पास 3: [2/2] = 1 108 पृष्ठों

  के आधार पर छाँटे गए फ़ाइल

प्रश्न: मेरी समझ, बाहरी मर्ज प्रकार में है पास 0 में आप हिस्सा बना सकते हैं और उसके बाद प्रत्येक हिस्सा छांटते हैं। शेष पास में आप उन्हें विलय करते रहते हैं। तो, उपरोक्त उदाहरण के लिए आवेदन करना, चूंकि हमारे पास केवल 5 बफर पेज हैं, पास 0 में यह स्पष्ट है कि हमें प्रत्येक के 5 पृष्ठों के 22 क्रमबद्ध रन की आवश्यकता है।

1. अब, हम इसके बजाय शेष पास के लिए क्रमबद्ध रन क्यों कर रहे हैं या विलय कर रहे हैं?

2. हमारे पास केवल 5 बफर पेज होने पर 20 पृष्ठों के पास 1, 6 क्रमबद्ध रनों के लिए कैसे कहा जाता है?

3. जहां वास्तव में यहां विलय हो रहा है? और प्रत्येक पास में 108 से 22 से 6 से 2 तक एन कैसे कम हो रहा है?

Answer 1

बाहरी मर्ज क्रमबद्ध आवश्यक है जब आप स्मृति में सभी डाटा स्टोर नहीं कर सकते। सबसे अच्छा आप डेटा को सॉर्ट किए गए रनों में तोड़ सकते हैं और बाद के पास में रन मर्ज कर सकते हैं। रन की लंबाई आपके उपलब्ध बफर आकार से जुड़ी हुई है।

Pass0: यदि आप स्थान में संचालन कर रहे हैं। तो आप डेटा के 5 पृष्ठों को बफर में लोड करते हैं और फिर इसे जगह में सॉर्टिंग एल्गोरिदम का उपयोग करके क्रमबद्ध करते हैं। ये 5 पृष्ठ एक साथ चलाने के रूप में एकत्रित किए जाएंगे।

निम्नलिखित पास: आप कई पृष्ठों के रन विलय कर रहे हैं, इसलिए आप अब संचालन नहीं कर सकते हैं। 4 पेज बफर में लोड होते हैं और 5 वां लिखने वाला बफर होता है। विलय विलय सॉर्ट एल्गोरिदम के समान है, लेकिन आप 2 के बजाय बी -1 के कारक द्वारा विभाजित और जीतेंगे। जब लिखने वाला बफर भर जाता है, तो यह डिस्क पर लिखा जाता है और अगला पृष्ठ शुरू होता है।

जटिलता: जब बाहरी मर्ज प्रकार की जटिलता का विश्लेषण करने, आई/ओएस की संख्या क्या माना जा रहा है। प्रत्येक पास में, आपको एक पृष्ठ पढ़ना होगा और पृष्ठ लिखना होगा। एन को पृष्ठों की संख्या होने दें। प्रत्येक रन 2 एन खर्च होंगे। पृष्ठ पढ़ें, पेज लिखें।
बी बी उन पृष्ठों की संख्या बनें जिन्हें आप बफर स्पेस रखते हैं और एन पृष्ठों की संख्या हो।
छत होगी (log_B-1 (छत (एन/बी))) गुजरती है। प्रत्येक पास में 2 एन आई/ओएस होगा। तो ओ (nlogn)।

प्रत्येक पास में, रन की पृष्ठ लंबाई बी -1 के कारक से बढ़ रही है, और क्रमबद्ध रनों की संख्या बी -1 के कारक द्वारा घट रही है।
Pass0: प्लस्तर लगाना (108/5) = 22, रन प्रति 5 पृष्ठों
Pass1: प्लस्तर लगाना (22/4) = 6, रन प्रति 20 पृष्ठों
Pass2: प्लस्तर लगाना (6/4) = 2, प्रति 80 पृष्ठों रन
पास 3: छत (2/4) = 1 - किया गया, 108 पृष्ठों का 1 रन

Answer 2

ए चूंकि यह विलय का उल्लेख नहीं करता है, इसलिए मुझे लगता है कि उम्मीद है कि बाद में "सॉर्टिंग" पास विलय कर रहे हैं।

बी। फिर, यह मानते हुए कि यह विलय हो रहा है, आपको मर्ज किए गए रिकॉर्ड को सहेजने के लिए एक बफर की आवश्यकता है, और प्रत्येक फ़ाइल को विलय करने के लिए शेष बफर का उपयोग करें: इस प्रकार, 4 इनपुट फ़ाइलें, प्रत्येक w/5 पृष्ठ: 20 पृष्ठ ।

सी सोचो मैं उत्तर दिया है जहां मर्ज अब दो बार है :)