संख्याओं की एक बड़ी सूची में अक्सर बार-बार संख्या

Question

मेरे पास एक फ़ाइल है जिसमें एक सफेद स्थान से अलग कई यादृच्छिक पूर्णांक (लगभग दस लाख) हैं। मुझे उस फ़ाइल में शीर्ष 10 सबसे अधिक बार होने वाली संख्याओं को खोजने की आवश्यकता है। जावा में ऐसा करने का सबसे प्रभावी तरीका क्या है? मैं के बारे में सोच सकता हूं 1. हैश नक्शा बनाएं, कुंजी फ़ाइल से पूर्णांक है और मान गिनती है। फ़ाइल में प्रत्येक नंबर के लिए, जांचें कि हैश मैप में यह कुंजी पहले से मौजूद है या नहीं, यदि हां, मान ++, तो हैश में एक नई प्रविष्टि करें 2. एक बीएसटी बनाएं, प्रत्येक नोड फ़ाइल से पूर्णांक है। फ़ाइल से प्रत्येक पूर्णांक के लिए देखें कि यदि बीएसटी में कोई नोड है तो हाँ, मान ++ करें, मान नोड का हिस्सा है।

मुझे लगता है कि हैश मैप बेहतर विकल्प है अगर मैं अच्छे हैशिंग फ़ंक्शन के साथ आ सकता हूं, क्या कोई मुझे बता सकता है कि ऐसा करने का सबसे अच्छा क्या है? क्या कोई और कुशल अहंकार है जिसका मैं उपयोग कर सकता हूं?

Answer 1

जावा हैंडल हैशिंग। आपको हैश फ़ंक्शन लिखने की आवश्यकता नहीं है। बस हैश मानचित्र में सामान को धक्का देना शुरू करें।

इसके अलावा, अगर ऐसा कुछ है जो केवल एक बार (या केवल कभी-कभी) चलाने की आवश्यकता है, तो दोनों अनुकूलन न करें। यह काफी तेज़ होगा। केवल परेशान करें यदि यह ऐसा कुछ है जो किसी एप्लिकेशन के भीतर चल रहा है।

Answer 2

# 2 संपादित करें:

ठीक है, मैं अपने ही पहला नियम बँधा हुआ - समय से पहले अनुकूलन कभी नहीं। इसके लिए सबसे खराब मामला शायद एक विस्तृत श्रृंखला के साथ स्टॉक हैश मैप का उपयोग कर रहा है - इसलिए मैंने अभी ऐसा किया है। यह अभी भी एक सेकंड की तरह चलता है, इसलिए यहां सबकुछ भूल जाओ और बस ऐसा करें।

और मैं मुश्किल कार्यान्वयन के बारे में चिंता करने से पहले परीक्षण की गति के लिए खुद को एक और नोट कर दूंगा।

एक HashSet काम करेगा (नीचे पुराने अप्रचलित पोस्ट है कि अभी भी अगर किसी को एक लाख से कई अधिक अंक था मान्य हो सकता है), लेकिन अपने पूर्णांकों (जैसे कि, 1-1000) एक उचित सीमा है, यह 1000 पूर्णांक की सरणी बनाने के लिए और आपके प्रत्येक मिलियन पूर्णांक के लिए अधिक कुशल होगा, सरणी के उस तत्व को बढ़ाएगा। (हैश मैप के रूप में बहुत ही वही विचार है, लेकिन कुछ अज्ञातों को ऑप्टिमाइज़ करना है जिन्हें हैश को भत्ते बनाना है, इसे इसे कुछ गुना तेज बनाना चाहिए)।

आप एक पेड़ भी बना सकते हैं। पेड़ में प्रत्येक नोड में (मान, गिनती) होगी और पेड़ मूल्य द्वारा व्यवस्थित किया जाएगा (बाईं ओर निचले मान, दाईं ओर ऊंचे)। अपने नोड पर जाएं, यदि यह अस्तित्व में नहीं है - इसे डालें - अगर ऐसा होता है, तो केवल गिनती बढ़ाएं।

आपके मूल्यों की सीमा और वितरण यह निर्धारित करेगा कि इनमें से कौन सा (या नियमित हैश) बेहतर प्रदर्शन करेगा। मुझे लगता है कि एक नियमित हैश में कई "जीतने" मामले नहीं होंगे, हालांकि (यह एक विस्तृत श्रृंखला और "समूहीकृत" डेटा होना चाहिए, और फिर भी पेड़ जीत सकता है।

चूंकि यह बहुत छोटा है - I आप वास्तविक डेटा सेट के खिलाफ एक से अधिक समाधान और परीक्षण गति लागू की सिफारिश

संपादित करें:। टिप्पणी आरई

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

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

Answer 3

हैशटेबल का उपयोग क्यों करें? बस एक सरणी का उपयोग करें जो आपकी संख्या की सीमा के समान आकार है। फिर आप हैशिंग फ़ंक्शन निष्पादित करने में समय बर्बाद नहीं करते हैं। फिर आपके द्वारा किए जाने के बाद मानों को क्रमबद्ध करें। हे (एन लॉग ऑन एन)

Answer 4

यह java.lang.Integer.hashCode() के लिए स्रोत, हैशिंग समारोह है कि अगर आप एक HashMap<Integer, Integer> के रूप में अपनी प्रविष्टियां की दुकान इस्तेमाल किया जाएगा जो है:

public int hashCode() { 
return value; 
} 

दूसरे शब्दों में

तो, (डिफ़ॉल्ट) java.lang.Integer का हैश मान पूर्णांक है।

उससे अधिक कुशल क्या है?

Answer 5

1. इनपुट आइटम्स की संख्या के रूप में एक ही आकार की एक सरणी/वेक्टर का आवंटन आप
2. संख्या के साथ अपनी फ़ाइल, तत्व
3. सूची रखो प्रति एक नंबर से सरणी भरें क्रम में है
4. सूची के माध्यम से Iterate और आपके सामने आने वाले नंबरों के शीर्ष 10 रनों का ट्रैक रखें।
5. अंत में शीर्ष दस रन आउटपुट।

चरण 4 पर परिष्करण के रूप में, आपको केवल अपने 10 वें सबसे लंबे समय तक चलने वाले चरणों में सरणी के माध्यम से आगे बढ़ने की आवश्यकता है। इससे भी अधिक रन आपके नमूने के साथ ओवरलैप होगा। यदि दसवीं सबसे लंबी दौड़ 100 तत्व लंबी होती है, तो आपको केवल 100, 200, 300 तत्व नमूना करने की आवश्यकता होती है और प्रत्येक बिंदु पर आप जो पूर्णांक प्राप्त करते हैं (दोनों आगे और पीछे) के रन को गिनती है। आपके 10 वें सबसे लंबे समय तक चलने वाला कोई भी रन आपके नमूने के साथ ओवरलैप करना सुनिश्चित करता है।

आपको अपनी 10 वीं रन लंबाई के बाद सरणी में अन्य रनों की तुलना में यह अनुकूलन लागू करना चाहिए।

इस प्रश्न के लिए एक नक्शा अधिक है जब तक कि आपके पास बड़ी संख्या में दोहराने के साथ बहुत कम अद्वितीय संख्याएं न हों।

एनबी: gshauger के जवाब देने के लिए इसी तरह की है, लेकिन

Answer 6

बाहर fleshed आप इसे के रूप में संभव के रूप में कुशल बनाने के लिए, स्थिति मूल्य और सामग्री गिनती का प्रतिनिधित्व करने का प्रतिनिधित्व करने के साथ ints की एक सरणी का उपयोग करें, है। इस तरह आप एक मानक जावा संग्रह की सबसे संभावित हत्यारा autoboxing और unboxing से बचें।

यदि संख्याओं की संख्या बहुत बड़ी है तो पीजेसी और उसके IntKeyIntMap कार्यान्वयन पर एक नज़र डालें। यह ऑटोबॉक्सिंग से भी बच जाएगा। मुझे नहीं पता कि यह आपके लिए पर्याप्त तेज़ होगा, हालांकि।

Answer 7

ऐसा करने का सही तरीका एक लिंक्ड सूची के साथ है। जब आप कोई तत्व डालते हैं, तो आप लिंक की गई सूची में जाते हैं, यदि वहां आप नोड्स गिनती बढ़ाते हैं, अन्यथा 1 की गिनती के साथ एक नया नोड बनाएं। प्रत्येक तत्व डालने के बाद, आपके पास O (n) में तत्वों की एक क्रमबद्ध सूची होगी * लॉग (एन))।

अपनी विधियों के लिए, आप एन आवेषण कर रहे हैं और फिर ओ (एन * लॉग (एन)) में सॉर्ट कर रहे हैं, इसलिए जटिलता पर आपका गुणांक अधिक है।

Answer 8

यदि संख्याओं की संख्या छोटी है (उदा। 0-1000), तो एक सरणी का उपयोग करें। अन्यथा, HashMap<Integer, int[]> का उपयोग करें, जहां मान सभी लंबाई 1 सरणी हैं। हर बार जब आप मूल्य बढ़ाने की इच्छा रखते हैं तो एक नया इंटीजर बनाने की तुलना में प्राइमेटिव्स की एक सरणी में मूल्य बढ़ाने के लिए यह बहुत तेज़ होना चाहिए। आप अभी भी चाबियों के लिए इंटीजर ऑब्जेक्ट्स बना रहे हैं, लेकिन इससे बचना मुश्किल है। आखिरकार 2^31-1 इंच की सरणी बनाने के लिए संभव नहीं है।

यदि सभी इनपुट सामान्यीकृत हैं तो आपके पास 1 के बजाय 01 जैसे मान नहीं हैं, मानचित्र में स्ट्रिंग्स के रूप में स्ट्रिंग का उपयोग करें ताकि आपको इंटीजर कुंजी बनाने की आवश्यकता न हो।

Answer 9

HashMap

एक लाख पूर्णांकों नहीं वास्तव में एक बहुत कुछ, यहां तक ​​कि व्याख्या की भाषाओं के लिए है, लेकिन विशेष रूप से जावा की तरह एक तेजी से भाषा के लिए। आप शायद निष्पादन समय को शायद ही कभी नोटिस करेंगे। मैं इसे पहले कोशिश करता हूं और यदि आप इसे बहुत धीमा मानते हैं तो कुछ और जटिल हो जाते हैं।

शायद स्ट्रिंग स्प्लिटिंग और पार्सिंग करने में अधिक समय लगेगा, जो कि हैश मैप का उपयोग करके आवृत्तियों को खोजने के लिए सबसे सरल एल्गोरिदम से भी पूर्णांक में परिवर्तित हो जाएगा।

Answer 10

फ़ाइल को पार करते समय मेमोरी में अपना डेटासेट (वैल्यू-गिनती जोड़े) बनाने के लिए हैश मैप का उपयोग करें। जब आप डेटासेट बनाते हैं तो हैश मैप आपको तत्वों तक ओ (1) पहुंच के करीब देना चाहिए (तकनीकी रूप से, सबसे खराब मामले हैश मैप ओ (एन) में है)। एक बार जब आप फ़ाइल खोज कर लेंगे, तो मूल्य-गिनती जोड़े की क्रमबद्ध सूची बनाने के लिए HashMap.values ​​() द्वारा दिए गए मान संग्रह पर Collections.sort() का उपयोग करें। Collections.sort() का उपयोग ओ (nLogn) की गारंटी है। उदाहरण के लिए:

public static class Count implements Comparable<Count> { 
    int value; 
    int count; 
    public Count(int value) { 
     this.value = value; 
     this.count = 1; 
    } 
    public void increment() { 
     count++; 
    } 
    public int compareTo(Count other) { 
     return other.count - count; 
    } 
} 

public static void main(String args[]) throws Exception { 
    Scanner input = new Scanner(new FileInputStream(new File("..."))); 
    HashMap<Integer, Count> dataset = new HashMap<Integer, Count>(); 
    while (input.hasNextInt()) { 
     int tempInt = input.nextInt(); 
     Count tempCount = dataset.get(tempInt); 
     if (tempCount != null) { 
      tempCount.increment(); 
     } else { 
      dataset.put(tempInt, new Count(tempInt)); 
     } 
    } 

    List<Count> counts = new ArrayList<Count>(dataset.values()); 
    Collections.sort(counts); 

Answer 11

वास्तव में, वहाँ वास्तव में कर रही है कि आप क्या करना चाहते हैं के लिए एक हे (एन) एल्गोरिथ्म। आपका उपयोग केस एक एलएफयू कैश के समान है जहां तत्व की पहुंच गिनती निर्धारित करती है कि यह कैश में कहता है या इससे निकाला जाता है।

http://dhruvbird.blogspot.com/2009/11/o1-approach-to-lfu-page-replacement.html