हाय मैंने देखा कि एक साक्षात्कार प्रश्न के रूप में और सोचा कि यह एक दिलचस्प सवाल था कि मुझे जवाब के बारे में निश्चित नहीं है।रूबी का उपयोग स्क्रिप्टिंग भाषा के रूप में 4 जीबी रैम वाले कंप्यूटर के साथ 30 जीबी स्ट्रिंग को सॉर्ट करने का सबसे अच्छा तरीका क्या है?
सबसे अच्छा तरीका क्या होगा?
* nix मान लिया जाये:
system("sort <input_file >output_file")
"प्रकार" इनपुट के साथ काम करने के लिए अस्थायी फ़ाइलों का उपयोग कर सकते स्मृति से बड़े आकार वाली फ़ाइलें। यह आवश्यक होने पर, मुख्य मेमोरी की मात्रा और उपयोग की जाने वाली अस्थायी फ़ाइलों की संख्या को ट्यून करने के लिए स्विच कर चुका है।
यदि नहीं * nix, या साक्षात्कारकर्ता किनारे के जवाब के कारण फहरा हुआ है, तो मैं एक बाहरी merge sort कोड दूंगा। बाहरी सॉर्टिंग एल्गोरिदम के अच्छे सारांश के लिए @ psyho का उत्तर देखें।
धन्यवाद, यह वही है जो मुझे लगता है कि जवाब होना चाहिए ... मुझे नहीं पता * निक्स लेकिन मुझे लगता है कि यह किसी बिंदु पर प्रश्न में सूचीबद्ध है। –
आपका स्वागत है, और चेक मार्क के लिए धन्यवाद। –
उन्हें डेटाबेस में रखें और डेटाबेस को इसके बारे में चिंता करने दें।
डाटाबेस सिस्टम पहले से ही इस विशेष समस्या को संभालने में काम कर रहे हैं।
एक अच्छा जवाब मर्ज-सॉर्ट एल्गोरिदम का उपयोग करना है, इसे मर्ज चरणों के लिए आवश्यक डिस्क से डेटा तक स्पूल करने के लिए अनुकूलित करना है। यह स्मृति पर न्यूनतम मांगों के साथ किया जा सकता है।
अच्छा, यह एक दिलचस्प साक्षात्कार प्रश्न है ... लगभग सभी तरह के प्रश्न आपके कौशल का परीक्षण करने के लिए हैं और सौभाग्य से, वास्तविक जीवन उदाहरणों पर सीधे लागू नहीं होते हैं। यह एक जैसा दिखता है, तो चलिए पहेली
जब आपका साक्षात्कारकर्ता "सर्वश्रेष्ठ" मांगता है, तो मेरा मानना है कि वह केवल प्रदर्शन के बारे में बात करता है।
30GB स्ट्रिंग्स बहुत सारे डेटा हैं। सभी तुलना-स्वैप एल्गोरिदम Omega(n logn) हैं, इसलिए इसमें काफी समय लगेगा। जबकि O(n) एल्गोरिदम हैं, जैसे गिनती सॉर्ट, वे जगह पर नहीं हैं, इसलिए आप 30 जीबी गुणा कर रहे हैं और आपके पास केवल 4 जीबी रैम है (स्वैपिंग राशि पर विचार करें ...), इसलिए मैं क्विकॉर्ट
सॉर्ट करने के बारे में सोचना शुरू करें। आप पहले प्रत्येक अक्षर के लिए समूहों में स्ट्रिंग्स को विभाजित करना चाहते हैं (रेडिक्स सॉर्ट दृष्टिकोण का उपयोग करके)। आप फ़ाइल को स्कैन करना चाहते हैं और, प्रत्येक प्रारंभिक अक्षर के लिए, स्ट्रिंग स्ट्रिंग (इसलिए कॉपी और डिलीट करें, कोई स्पेस कचरा नहीं) अस्थायी फ़ाइल में ले जाएं। आप प्रत्येक स्ट्रिंग के पहले 2, 3 या 4 वर्णों के लिए प्रक्रिया को दोहराना चाह सकते हैं। फिर, कई फ़ाइलों को सॉर्ट करने की जटिलता को कम करने के लिए, आप अलग-अलग स्ट्रिंग को प्रत्येक के भीतर अलग कर सकते हैं (अब क्विकॉर्ट का उपयोग करके) और आखिर में सभी फाइलों को मर्ज करें।इस तरह से आप अभी भी एक O(n logn) लेकिन निष्पक्ष कम पर n
एक तरह से यह करने के लिए कर रहा है होगा उपयोग करने के लिए एक external sorting algorithm:
अलग-अलग फ़ाइलों में संग्रहीत परिणामों के साथ विभाजित और जीतने वाले एल्गोरिदम की तरह लगता है तो अंत में विलय हो जाता है। – Omar