120 जीबी के साथ हार्डड्राइव को देखते हुए, जिनमें से 100 लंबाई 256 और 2 जीबी राम के तारों से भरे हुए हैं, मैं जावा में उन तारों को सबसे कुशलता से कैसे क्रमबद्ध करूं? इसमें कितना समय लगेगा?100 जीबी के तारों को क्रमबद्ध करने के लिए कैसे करें
मैं मूल रूप से Krystian's answer दोहरा रहा हूँ, लेकिन व्याख्या:
हाँ आप इस अधिक या कम जगह में, आप थोड़ा रैम उपलब्ध है के बाद से करने की जरूरत है। लेकिन आसपास के तारों की चलती लागत के कारण यहां बेवकूफ जगहों पर आपदा एक आपदा होगी।
वास्तव में चारों ओर तारों को स्थानांतरित करने की बजाय, केवल ट्रैक करें कि कौन से तारों को स्वैप करना चाहिए और वास्तव में उन्हें अंत में, अंतिम स्थान पर, अंत में स्थानांतरित करना चाहिए। यही है, अगर आपके पास 1000 तार थे, तो 1000 इंट्स की सरणी बनाएं। सरणी [i] वह स्थान है जहां स्ट्रिंग को समाप्त करना चाहिए। यदि सरणी [17] == 133 अंत में है, तो इसका मतलब है कि स्ट्रिंग 17 को स्ट्रिंग 133 के लिए स्पॉट में समाप्त होना चाहिए। सरणी [i] == मैं सभी को शुरू करने के लिए। तारों को स्वैप करना, फिर, दो चींटियों को स्वैप करने का मामला है।
फिर, क्विक्सॉर्ट जैसे किसी भी स्थान पर एल्गोरिदम बहुत अच्छी तरह से काम करता है।
चलने का समय निश्चित रूप से तारों के अंतिम चरण से प्रभावित होता है। प्रत्येक एक चाल को मानते हुए, आप उचित रूप से आकार के लिखने में लगभग 100GB डेटा ले जा रहे हैं। मुझे लगता है कि ड्राइव/नियंत्रक/ओएस आपके लिए लगभग 100 एमबी/सेकंड स्थानांतरित कर सकता है। तो, 1000 सेकंड या तो? 20 मिनट?
लेकिन क्या यह स्मृति में फिट है? आपके पास 100GB स्ट्रिंग हैं, जिनमें से प्रत्येक 256 बाइट्स है। कितने तार? 100 * 2^30/2^8, या लगभग 41 9 एम तार।आपको 41 9 एम इन्स की जरूरत है, प्रत्येक 4 बाइट्स या लगभग 1.7 जीबी है। वोला, आपके 2 जीबी में फिट बैठता है।
अच्छा बिंदु, लेकिन मैं समय तलाशने के बारे में चिंतित थोड़ा चिंतित होगा। यह विधि बहुत सारी इच्छाओं की आवश्यकता के समान लगता है, इसलिए 100 एमबी/सेकेंड का निरंतर थ्रूपुट सबसे अच्छा उपाय नहीं हो सकता है। हमें लगभग 100 * 2^30/2^8 ~ 100 * 2^22 स्ट्रिंग्स ले जाना है। अगर हम सावधान नहीं हैं, तो हमें प्रति 100 लिखने की आवश्यकता हो सकती है। यदि प्रत्येक खोज 4ms ~ 2^-8 सेकेंड है, तो यह 2^14 सेकंड ~ 4.5 एच की तरह कुछ ले जाएगा। – Krystian
मैं स्पष्ट रूप से थोड़ा धीमा हूं - आप इंडेक्स सरणी को कैसे पॉप्युलेट करते हैं? मैं देख सकता हूं कि एक बार जब आप इंडेक्स सरणी बनाते हैं तो स्मृति में सॉर्ट करना आसान और त्वरित होता है, लेकिन मुझे समझ में नहीं आता कि आप इसे पहले स्थान पर कैसे सेट करते हैं। –
@ क्रिस्टियन - मुझे लगता है कि लिखित 100 प्रति 100 रिकॉर्ड्स का अनुमान अत्यधिक आशावादी है ... –
ए 1। आप शायद मर्ज-सॉर्ट के कुछ रूपों को लागू करना चाहते हैं।
ए 2: यदि आपकी मशीन पर 256GB रैम था तो उससे लंबा होगा।
संपादित करें: आलोचना से डंक मार, मैं मर्ज प्रकार पर विकिपीडिया के लेख से बोली:
मर्ज तरह तो स्वाभाविक अनुक्रमिक कि यह इनपुट और आउटपुट डिवाइस के रूप में धीमी गति से टेप ड्राइव का उपयोग कर इसे चलाने के लिए व्यावहारिक है। इसे बहुत छोटी मेमोरी की आवश्यकता है, और आवश्यक स्मृति डेटा तत्वों की संख्या पर निर्भर नहीं है।
इसी कारण से यह डिस्क पर डेटा को सॉर्ट करने के लिए भी उपयोगी है जो पूरी तरह से प्राथमिक स्मृति में फिट होने के लिए बहुत बड़ा है। टेप ड्राइव पर दोनों पीछे और आगे चला सकते हैं, विलय समय दिशाओं में विलय समय से बचने के लिए चलाया जा सकता है।
मर्ज सॉर्ट जरूरी नहीं है कि जगह में सॉर्ट करें, जिसका अर्थ यह होगा कि ऐसा करना असंभव है। –
बिलकुल असंभव नहीं है! –
विस्तृत करने के लिए देखभाल, @ हाई? आपने मर्ज-सॉर्ट की स्पेस आवश्यकताएं संबोधित नहीं की हैं। –
External sorting विधि के लिए कॉल करने वाले कार्य की तरह लगता है। "कंप्यूटर प्रोग्रामिंग की कला" के खंड 3 में बाहरी सॉर्टिंग विधियों की व्यापक चर्चा के साथ एक अनुभाग शामिल है।
@ क्रिस्टियन, क्या आप बाहरी प्रकार के बारे में जानते हैं जिसके लिए 2 एन स्पेस की आवश्यकता नहीं है? –
आपको trie (उर्फ: एक उपसर्ग पेड़) का उपयोग करना चाहिए: एक वृक्ष जैसी संरचना बनाने के लिए जो आपको अपने उपसर्गों की तुलना करके क्रमशः अपने तारों से आसानी से चलने की अनुमति देता है। वास्तव में, आपको इसे स्मृति में संग्रहीत करने की आवश्यकता नहीं है। आप अपने फाइल सिस्टम पर निर्देशिकाओं के वृक्ष के रूप में त्रिभुज का निर्माण कर सकते हैं (जाहिर है, वह डेटा नहीं जो डेटा से आ रहा है)।
AFAIK, मर्ज-सॉर्ट के रूप में आपके पास डेटा के रूप में बहुत खाली स्थान की आवश्यकता होती है। यह किसी बाहरी प्रकार के लिए एक आवश्यकता हो सकती है जो यादृच्छिक अभिगम से बचाती है, हालांकि मुझे इसके बारे में निश्चित नहीं है।
नीचे अपनी टिप्पणी पर मेरी टिप्पणी देखें। –
यहाँ कैसे मैं यह कर होता है:
चरण 1, 2GB की 50 विभाजनों में 100Gb विभाजित स्मृति में 50 विभाजन से प्रत्येक पढ़ते हैं, तरह quicksort उपयोग कर, और लिखने के लिए है। आप डिस्क के शीर्ष छोर पर क्रमबद्ध विभाजन चाहते हैं।
चरण 2 फिर 50 क्रमबद्ध विभाजनों को मर्ज करना है। यह मुश्किल बिट है क्योंकि आपके पास विभाजन और अंतिम क्रमबद्ध आउटपुट को स्टोर करने के लिए डिस्क पर पर्याप्त स्थान नहीं है। तो ...
50 रास्ता मर्ज डिस्क के नीचे अंत में पहली 20Gb को भरने के लिए करते हैं।
शेष 20 जीबी के अंत के साथ एक और 20 जीबी मुक्त स्थान संगत करने के लिए शेष 50 पृष्ठों में शेष डेटा को स्लाइड करें।
चरणों को दोहराएं 1. और 2. पूरा होने तक।
यह डिस्क आईओ का एक बहुत है, लेकिन आप को कॉपी करने में बफरिंग और डिस्क चाहता है की संख्या कम करके डेटा थ्रूपुट पाने के लिए कदम मर्ज करने के लिए स्मृति के अपने 2GB की उपयोग कर सकते हैं, और बड़े डाटा हस्तांतरण करना ।
EDIT - @meriton ने प्रतिलिपि को कम करने के लिए एक चालाक तरीका प्रस्तावित किया है। स्लाइडिंग के बजाए, वह सुझाव देता है कि विभाजन को रिवर्स ऑर्डर में क्रमबद्ध किया जाए और विलय चरण में पीछे की ओर पढ़ा जाए। इससे एल्गोरिदम विभाजन विभाजन फ़ाइलों को छोटा करके विभाजन (चरण 2, चरण 2) द्वारा उपयोग की जाने वाली डिस्क स्थान को रिलीज़ करने की अनुमति देगा।
इसकी संभावित डाउनसाइड्स डिस्क विखंडन में वृद्धि हुई है, और पीछे की ओर विभाजन को पढ़ने के कारण प्रदर्शन की हानि हुई है। (बाद के बिंदु पर, लिनक्स/यूनिक्स पर पीछे की ओर एक फ़ाइल पढ़ने के लिए अधिक सिस्कोल की आवश्यकता होती है, और एफएस कार्यान्वयन विपरीत दिशा में "पढ़ने-आगे" करने में सक्षम नहीं हो सकता है।)
अंत में, मैं चाहूंगा इंगित करें कि इस एल्गोरिदम (और अन्य) द्वारा लिया गया समय की सैद्धांतिक रूप से भविष्यवाणियां काफी हद तक अनुमानित हैं। असली जेवीएम + असली ओएस + असली डिस्क पर इन एल्गोरिदम का व्यवहार विश्वसनीय जवाब देने के लिए "लिफाफा के लिए वापस" गणना के लिए बहुत जटिल है। एक उचित उपचार के लिए वास्तविक कार्यान्वयन, ट्यूनिंग और बेंचमार्किंग की आवश्यकता होगी।
डेटा अनुमान कितना डेटा लिखा गया है (यह मानते हुए कि गणना समानांतर में की जा सकती है और इसलिए मुफ़्त है): 100 जीबी (पहला चरण) + 100 जीबी (अंतिम आउटपुट) + 80 जीबी (स्लाइड 1) + 60 जीबी (स्लाइड 2) + 40 जीबी (स्लाइड 3) + 20 जीबी (स्लाइड 4) = 400 जीबी लिखित। लगभग चार घंटे, रूढ़िवादी 30 एमबी/एस निरंतर लेखन मानते हैं। सभ्य हार्डवेयर पर तेज़ी से, लेकिन सभ्य हार्डवेयर में केवल 2 जीबी रैम है? ;-) –
... लेकिन इस तथ्य के लिए कुछ समय जोड़ें कि चरण 1 में पढ़ने/क्रमबद्ध/लिखना समानांतर नहीं हो सकता है। "2 जीबी रैम" के मुकाबले एक संभावित क्विबल भी है। आपने रैम द्वारा समर्थित 2 जीबी संगत पता स्थान की उपलब्धता को संभाला है, जो मुझे लगता है कि यह काफी उचित है कि यह एक काल्पनिक प्रश्न है। लेकिन अगर * मशीन * में 2 जीबी रैम और 32-बिट एड्रेसिंग है, तो पहले चरण में आपके हिस्से को छोटा होना होगा, जिसके परिणामस्वरूप बाद में 50 से अधिक प्रकार का सॉर्ट होगा। आखिरकार, एक बहुत-तरफा विलय धीमा हो जाएगा। –
मुझे लगता है कि रिकॉर्ड प्रति रिकॉर्ड लॉगएन तुलना के साथ एक एन-मार्ग विलय किया जा सकता है। –
मुझे लगता है कि आपको BogoSort का उपयोग करना चाहिए। इनस्थल सॉर्टिंग की अनुमति देने के लिए आपको एल्गोरिदम को थोड़ा सा संशोधित करना पड़ सकता है, लेकिन यह बहुत कठिन नहीं होना चाहिए। :)
+1 - शुद्ध ऑडैसिटी के लिए :-) –
आपको लगभग निश्चित रूप से * इन-प्लेस * सॉर्टिंग एल्गोरिदम की आवश्यकता होगी। – stakx
तारों को कैसे सीमित किया जाता है? जैसा कि: क्या यह उनके बीच शून्य वर्णों वाला एक अनुक्रम है या वे कुछ सेट लंबाई के साथ बफर का समूह हैं और पात्रों से भरे हुए हैं। मेरा मूल प्रश्न यह है कि तारों को ढूंढना और स्थानांतरित करना कितना आसान है? –
यह एक Google साक्षात्कार प्रश्न था। मुझे पता है, क्योंकि जब मैंने वहां साक्षात्कार किया तो मुझे सवाल मिला। –