http://web.eecs.utk.edu/~huangj/CS302S04/notes/external-sorting2.html
मर्ज जिसके परिणामस्वरूप क्रमिक बड़ा रन में एक साथ चलता है, जब तक फ़ाइल क्रमबद्ध किया जाता है।
जैसा कि मैंने उद्धृत किया है, हम परिणामी रनों को एक साथ कैसे विलय कर सकते हैं ??? हम उस स्मृति को हल नहीं करते हैं।
कल्पना कीजिए कि आप संख्या 1 ऐसा - 9
9 7 2 6 3 4 8 5 1
और मान लें कि चलो एक बार में स्मृति में केवल 3 फिट।
तो आप उन्हें 3 के टुकड़ों में तोड़ने के लिए और प्रत्येक को सॉर्ट करना चाहते हैं, एक अलग फ़ाइल में प्रत्येक परिणाम भंडारण:
279
346
158
अब आप धाराओं के रूप में तीन फाइलों में से प्रत्येक खोलने के लिए और पहले मान पढ़ा था प्रत्येक से:
2 3 1
आउटपुट न्यूनतम मूल्य 1, और, कि धारा से अगले मूल्य प्राप्त अब आप:
2 3 5
आउटपुट अगले सबसे कम मूल्य 2 आउटपुट, और तब तक जारी रखें जब तक आप पूरी क्रमबद्ध सूची आउटपुट नहीं कर लेते।
आप कुछ बड़े रन C में दो रन A और B प्रोसेस हो जाती हैं तो आप इस पंक्ति-दर-पंक्ति उत्तरोत्तर बड़ा रन पैदा कर सकते हैं, लेकिन अभी भी एक बार में केवल सबसे 2 लाइनों पर पढ़ने। क्योंकि प्रक्रिया पुनरावृत्त है और क्योंकि आप डेटा के पूर्ण कटौती के बजाय डेटा की धाराओं पर काम कर रहे हैं, आपको स्मृति उपयोग के बारे में चिंता करने की आवश्यकता नहीं है। दूसरी ओर, डिस्क का उपयोग पूरी प्रक्रिया को धीमा कर सकता है - लेकिन यह सुनिश्चित करता है कि पहले स्थान पर काम करने में सक्षम न हो।
ब्रो, यह थोड़ा शर्मनाक होगा, आज मैंने कुछ साक्षात्कारकर्ता से पूछा एक प्रश्न पोस्ट किया, कुछ मदद पाने की उम्मीद है, लेकिन किसी ने 30+ बार देखा जाने के साथ इसका उत्तर नहीं दिया। मुझे उम्मीद है कि आप इसके बारे में मेरी मदद करने में थोड़ी देर दे सकते हैं, यहां लिंक है: http://stackoverflow.com/q/7425400/888051 बहुत बहुत धन्यवाद। – Alcott
धन्यवाद। लेकिन, कृपया उस वेबसाइट का उदाहरण दें, यह कहता है "6 आई/ओ इकाइयों का उपयोग किया जाता है।" ... कैसे ??? यदि आपके रास्ते का पालन करें, तो यह बहुत सारे IOs –
अच्छी तरह से है, यह वही सिद्धांत है, लेकिन आप इसे एक साथ नहीं कर सकते हैं, आपको विभाजन करना होगा, भाग को सॉर्ट करना होगा और इसे सभी मर्ज करना होगा, फिर बाकी विभाजन को सॉर्ट करें , और शुरुआत में विलय-क्रमबद्ध सूची के साथ विलय करें। जैसे कि आप 6 से अधिक I/o इकाइयों का उपयोग नहीं करेंगे। पृष्ठ पर एल्गोरिदम आपके आई/ओ यूनिट बाधाओं को देखते हुए आपके डेटा को विभाजित करने का सबसे अच्छा तरीका बताते हैं। –
वह उस उदाहरण के लिए काम करता है, लेकिन इसके बजाय आपके पास इस सूची के बारे में कैसा है? 9 7 8 6 3 4 2 5 1, तो आप निम्न समूहों के साथ समाप्त हो जाएंगे: 78 9, 346, 125. यदि आप प्रत्येक समूह से पहले क्रमबद्ध करते हैं, तो सेकंड और फिर तीसरे, आप कुछ ऐसा खत्म कर देंगे यह: 127248569, जो गलत है। तो संक्षेप में, मुझे अभी भी यह नहीं पता कि यह कैसे काम करता है ... – Gaara