जावा - PriorityQueue

Question

से कुछ तेज़ी से खोज रहा है, मैं जावा की बड़ी मात्रा में डेटा का उपयोग कर रहा हूं।

असल में मैं एक छोटा सा वर्ग (तत्व) है एक पूर्णांक कुंजी और एक डबल वजन (getters & setters के साथ) से युक्त [मैं जितना संभव हो उतना समस्या को आसान बनाने की कोशिश करते हैं]।

मैंने इन ऑब्जेक्ट्स को एक फ़ाइल से पढ़ा है और मुझे सबसे अच्छा (सबसे वज़न) एम ऑब्जेक्ट प्राप्त करना है।

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

क्या आप जानते हैं (मुझे पता है) ऐसा करने का कोई तेज़ तरीका है?

आप

Answer 1

एक ढेर-आधारित प्राथमिकता कतार इस समस्या के लिए एक अच्छी डेटा संरचना है। एक सैनिटी चेक के रूप में, सत्यापित करें कि आप कतार का सही उपयोग कर रहे हैं।

यदि आप उच्चतम वजन वाले आइटम चाहते हैं, तो मिनट -queue — का उपयोग करें जहां ढेर का शीर्ष सबसे छोटा आइटम है। प्रत्येक आइटम को अधिकतम-कतार में जोड़ना और शीर्ष पर होने पर शीर्ष M आइटमों की जांच करना कुशल नहीं है।

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

कुछ ढेर में ढेर के शीर्ष को बदलने के लिए शॉर्टकट एपीआई हैं, लेकिन जावा का Queue नहीं है। फिर भी, बड़ी-जटिलता समान है।

Answer 2

धन्यवाद तो एम उपयुक्त रूप से छोटा है, तो सभी तत्वों छँटाई कंप्यूटिंग बहुत समय बर्बाद हो सकता है। आप केवल पहली एम ऑब्जेक्ट्स को प्राथमिकता कतार में डाल सकते हैं (उदाहरण के लिए एक ढेर, शीर्ष पर न्यूनतम तत्व), और उसके बाद शेष तत्वों पर पुनरावृत्ति करें: हर बार एक तत्व ढेर के शीर्ष से बड़ा होता है, ऊपर हटा देता है और नया धक्का देता है ढेर में तत्व।

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

Answer 3

@Tnay: आपके पास तुलना करने के बारे में कोई बात नहीं है। दुर्भाग्य से, आपका उदाहरण कोड अभी भी एक करता है। इस समस्या का हल:

public int compare(ListElement i, ListElement j) { 
    return i.getValue() - j.getValue(); 
} 

इसके अलावा, न तो तुम्हारा, और न ही बिग्स तुलना विधि को सख्ती से सही है, क्योंकि वे 0. वापस कभी नहीं इस के बाद से, कुछ छँटाई एल्गोरिदम के साथ एक समस्या है, जो एक बहुत ही मुश्किल बग है हो सकता है यह केवल तब दिखाई देगा यदि आप किसी अन्य कार्यान्वयन पर स्विच करते हैं।

the Java docs से

:

implementor कि sgn (तुलना (एक्स, वाई)) == -sgn (तुलना (y, x)) सब x और y के लिए यह सुनिश्चित करना चाहिए।

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

Answer 4

सुझाए गए "हेप के शीर्ष पर चोटी" एल्गोरिदम के अलावा, जो आपको एन वस्तुओं के शीर्ष-मीटर प्राप्त करने के लिए ओ (एन लॉग एम) जटिलता देता है, यहां दो और समाधान हैं।

समाधान 1: एक फाइबोनैकी ढेर का उपयोग करें।

जेडीके की प्राथमिकता क्यूई कार्यान्वयन एक संतुलित बाइनरी ढेर है। आपको Fibonacci heap कार्यान्वयन से अधिक प्रदर्शन निचोड़ने में सक्षम होना चाहिए। यह एक बार बाइनरी ढेर में डालने के दौरान निरंतर समय सम्मिलित किया जाएगा, ढेर के आकार में जटिलता Ω (लॉग एन) है। यदि आप हर तत्व के लिए ऐसा कर रहे हैं, तो आप Ω (एन लॉग एन) पर हैं। एक फाइब ढेर का उपयोग कर एन वस्तुओं के शीर्ष-एम को ढूंढना जटिलता ओ (एन + एम लॉग एन) है। इस सुझाव को केवल ढेर में एम तत्वों को सम्मिलित करने के सुझाव के साथ संयोजित करें, और आपके पास ओ (एन + एम लॉग एम) है, जो आपको प्राप्त होने वाले रैखिक समय के करीब है।

समाधान 2: सूची एम बार को पार करें।

आपको ओ (एन) समय में एक सेट में केथ-सबसे बड़ा तत्व प्राप्त करने में सक्षम होना चाहिए। बस सूची में सबकुछ पढ़ें और निम्न कार्य करें:

kthLargest(k, xs) 
    Pick a random pivot element p from the list 
    (the first one will do if your list is already random). 
    Go over the set once and group it into two lists. 
    Left: smaller than p. 
    Right: Larger or equal to p. 
    If the Right list is shorter than k, return kthLargest(k - right.size, Left) 
    If the Right list is longer than k, return kthLargest(k, right) 
    Otherwise, return p. 

जो आपको ओ (एन) समय देता है। उस समय को चलाना, आप समय (ओएम) में अपने सेट में शीर्ष-एम ऑब्जेक्ट्स प्राप्त करने में सक्षम होना चाहिए, जो पर्याप्त रूप से बड़े n और पर्याप्त छोटे मीटर के लिए n लॉग n से सख्ती से कम होगा। उदाहरण के लिए, दस लाख से अधिक वस्तुओं में शीर्ष -10 प्राप्त करने से बाइनरी ढेर प्राथमिकता कतार का उपयोग करने में आधा समय लगेगा, अन्य सभी चीजें बराबर होंगी।