संख्याओं के बड़े सेट के लिए सबसे कुशल सॉर्टिंग एल्गोरिदम

Question

मैं एक बड़ी परियोजना पर काम कर रहा हूं, मैं इसे सारांशित करने के लिए परेशान नहीं हूं, लेकिन परियोजना का यह अनुभाग टेक्स्ट का एक बहुत बड़ा दस्तावेज़ लेना है (न्यूनतम लगभग 50,000 शब्द (अद्वितीय नहीं)), और कम से कम उपयोग किए जाने वाले क्रमशः प्रत्येक अद्वितीय शब्द को आउटपुट करते हैं (शायद शीर्ष तीन "ए" "ए" और "द" होंगे)।

मेरा प्रश्न निश्चित रूप से उपयोग करने के लिए सबसे अच्छा सॉर्टिंग एल्गोरिदम क्या होगा? मैं गिनती की तरह पढ़ रहा था, और मुझे यह पसंद है, लेकिन मेरी चिंता यह है कि अद्वितीय शब्दों की संख्या की तुलना में मूल्यों की सीमा बहुत बड़ी होगी।

कोई सुझाव?

Answer 1

सबसे पहले, आपको शब्द -> गिनती के मानचित्र की आवश्यकता होगी। 50,000 शब्द ज्यादा नहीं हैं - यह आसानी से स्मृति में फिट होगा, इसलिए चिंता करने की कोई बात नहीं है। सी ++ में आप मानक एसटीएल std :: मानचित्र का उपयोग कर सकते हैं।

फिर, एक बार आपके पास नक्शा हो जाने पर, आप सभी नक्शा कुंजी को वेक्टर में कॉपी कर सकते हैं।

फिर, कस्टम तुलना ऑपरेटर का उपयोग करके इस वेक्टर को सॉर्ट करें: शब्दों की तुलना करने के बजाय, मानचित्र से गणना की तुलना करें। (विशिष्ट सॉर्टिंग एल्गोरिदम के बारे में चिंता न करें - आपकी सरणी इतनी बड़ी नहीं है, इसलिए कोई भी मानक लाइब्रेरी सॉर्ट आपके लिए काम करेगा।)

Answer 2

मैं quicksort से शुरू करूंगा और वहां से जाऊंगा।

अंतर जानने के लिए wiki page on sorting algorithms देखें, हालांकि।

Answer 3

लिंक पर एक नज़र डालें। अलग-अलग एल्गोरिदम कैसे काम करता है पर एक सचित्र प्रतिनिधित्व। यह आपको एक संकेत देगा!

Sorting Algorithms

Answer 4

आप एक MSD radix तरह की कोशिश करनी चाहिए। यह आपकी प्रविष्टियों को lexicographical order में सॉर्ट करेगा। यहां एक google code project है जिसमें आपको रुचि हो सकती है।

Answer 5

यह थोड़ा मुश्किल है क्योंकि आप शब्दों का मानचित्र चाहते हैं -> आवृत्ति, और आप कुंजी के बजाय मूल्य से सॉर्ट करना चाहते हैं (जो आम है)। एक जावा उदाहरण here है जो दिखाता है कि एक कस्टम तुलनित्र का उपयोग करके इसे कैसे किया जाए।

आपके द्वारा उपयोग किए जाने वाले विशेष एल्गोरिदम का प्रभाव बहुत अधिक नहीं होगा, इसलिए मैं बस आपके मानक लाइब्रेरी कार्यान्वयन के साथ रहूंगा।

Answer 6

आप इस विशेष समस्या के साथ क्विकॉर्ट से बेहतर प्रदर्शन प्राप्त कर सकते हैं यह मानते हुए कि यदि दो शब्द समान संख्या में होते हैं, तो इससे कोई फर्क नहीं पड़ता कि आप उन्हें किस क्रम में आउटपुट करते हैं।

पहला चरण: संबंधित मूल्यों के रूप में शब्दों के साथ एक हैश मानचित्र बनाएं। जब आप फ़ाइल को पार्स करते हैं तो आप इस हैश मानचित्र को भर देंगे। जबकि आप यह कर रहे हैं, उच्चतम आवृत्ति का सामना करना सुनिश्चित करें। यह कदम ओ (एन) जटिलता है।

दूसरा चरण: पहले चरण से उच्चतम आवृत्ति के बराबर प्रविष्टियों की संख्या के साथ एक सूची बनाएं। इस सूची में प्रत्येक स्लॉट की अनुक्रमणिका इंडेक्स के बराबर आवृत्ति गणना वाले शब्दों की एक सूची रखेगी। तो दस्तावेज़ में 3 बार होने वाले शब्द सूची में [3] सूची में जाएंगे। हैश मानचित्र के माध्यम से Iterate और शब्दों में उचित स्थानों में शब्दों को डालें। यह कदम ओ (एन) जटिलता है।

तीसरा कदम: रिवर्स और आउटपुट सभी शब्दों में सूची के माध्यम से दोहराएं। यह कदम ओ (एन) जटिलता है।

कुल मिलाकर यह एल्गोरिदम आपके कार्य को ओ (एन) समय में त्वरित रूप से ओ (nlogn) की आवश्यकता के बजाय पूरा करेगा।

Answer 7

मुझे लगता है कि आप कुछ करना चाहता हूँ के रूप में नीचे पोस्ट में विस्तार से बताया:

http://karephul.blogspot.com/2008/12/groovy-closures.html

बोली जो समर्थन बंद समाधान बहुत आसान बनाने के लिए, LINQ की तरह के रूप में एरिक उल्लेख किया है।

Answer 8

लगभग हर मामले में मैंने कभी परीक्षण किया है, क्विक्सोर्ट ने मेरे लिए सबसे अच्छा काम किया है। हालांकि, मेरे पास दो मामले थे जहां कॉम्बोर्ट सबसे अच्छा था। हो सकता है कि उन मामलों में कॉम्बोर्ट बेहतर था क्योंकि कोड इतना छोटा था, या कुछ कर्कश के कारण डेटा का आदेश दिया गया था।

किसी भी समय सॉर्टिंग मेरी प्रोफ़ाइल में दिखाई देती है, मैं प्रमुख प्रकारों को आजमाता हूं। मेरे पास कभी भी कुछ भी नहीं था जो क्विक्सोर्ट और कॉम्बोर्ट दोनों में सबसे ऊपर था।

Answer 9

बड़े सेट का उपयोग कर सकते क्या "प्रकार आधारित अनुक्रमण" सूचना पुनर्प्राप्ति के रूप में जाना जाता है के लिए

, लेकिन 50,000 शब्द आप निम्नलिखित का उपयोग कर सकते हैं के लिए:

• एक बफर में पूरी फ़ाइल पढ़ें।
• बफर को पार्स करें और स्ट्रक्चर टोकन {char * term, int termlen के साथ टोकन वेक्टर बनाएं; } शब्द बफर में शब्द के लिए एक सूचक है।
• शब्द (शब्दावली क्रम) द्वारा तालिका को सॉर्ट करें।
• एंट्रीनम = 0 सेट करें, शब्द वेक्टर, के माध्यम से फिर से चालू करें, जब यह नया हो, इसे एक वेक्टर में स्टोर करें: संरचना {char * term; int आवृत्ति; } इंडेक्स एंट्रीम पर, आवृत्ति सेट 1 और प्रवेश संख्या में वृद्धि, अन्यथा वृद्धि आवृत्ति।
• अवरोही क्रम में आवृत्ति द्वारा वेक्टर को सॉर्ट करें।

Answer 10

आप डिजिटल पेड़ों को भी लागू करने का प्रयास कर सकते हैं जिन्हें ट्री भी कहा जाता है। यहां link