मनमाना तत्वों के जावा PriorityQueue हटाने प्रदर्शन

Question

मैं एक जावा PriorityQueue (जो जावा एक ढेर के रूप में लागू करता है) कहते हैं कि मैं अधिक पुनरावृति कुछ मानदंडों के आधार पर तत्वों को दूर करने के:

PriorityQueue q = new PriorityQueue(); 
... 
Iterator it = q.iterator(); 
while(it.hasNext()){ 
    if(someCriterion(it.next())) 
     it.remove(); 
} 

कब तक प्रत्येक निकालता है() ऑपरेशन लेते हैं? मुझे यकीन नहीं है कि यह ओ है (लॉग (एन)) या ओ (1)।

Answer 1

यदि आप सूर्य कार्यान्वयन का उपयोग कर रहे हैं, तो यह O(log(n)) है। Javadocs से:

कार्यान्वयन ध्यान दें: इस कार्यान्वयन प्रदान करता है enqueing के लिए हे (लॉग (एन)) समय और dequeing तरीकों (offer, poll, remove() और add); remove(Object) और contains(Object) विधियों के लिए रैखिक समय; और पुनर्प्राप्ति विधियों के लिए निरंतर समय (peek, element, और size)।

अन्य कार्यान्वयन में अलग-अलग जटिलता हो सकती है।

---

संपादित करें: Javadocs पुनरावर्तक के साथ एक तत्व को दूर करने के प्रदर्शन को कवर नहीं है, इसलिए मैं स्रोत कोड को देखने के लिए किया था। यह सूर्य कार्यान्वयन के लिए सभी प्रासंगिक है, और ऐप्पल के संस्करण, जीएनयू कक्षापथ आदि में भिन्न हो सकता है। सूर्य का स्रोत here उपलब्ध है; यह जेडीके में भी शामिल है, इसलिए आप इसे पहले से ही स्थापित कर सकते हैं।

PriorityQueue के इटरेटर में, remove() के लिए डिफ़ॉल्ट मामले PriorityQueue.removeAt(lastRet), कॉल करने के लिए जहां lastRet सूचकांक है कि पिछले next() द्वारा दिया था है। removeAt()O(log(n)) सबसे खराब मामला प्रतीत होता है (इसे कतार को छोड़ना पड़ सकता है, लेकिन इसे फिर से शुरू नहीं करना पड़ता है)।

हालांकि, कभी-कभी बुरी चीजें होती हैं। removeAt() की टिप्पणी से:

/** 
* Removes the ith element from queue. 
* 
* Normally this method leaves the elements at up to i-1, 
* inclusive, untouched. Under these circumstances, it returns 
* null. Occasionally, in order to maintain the heap invariant, 
* it must swap a later element of the list with one earlier than 
* i. Under these circumstances, this method returns the element 
* that was previously at the end of the list and is now at some 
* position before i. This fact is used by iterator.remove so as to 
* avoid missing traversing elements. 
*/ 

जब एक गैर-शून्य तत्व removeAt() द्वारा दिया जाता है, इटरेटर बाद में उपयोग के लिए एक विशेष कतार में शामिल करता है: जब इटरेटर कतार में तत्वों से बाहर चलाता है, यह तो दोहराता इस विशेष कतार के माध्यम से। जब remove() को पुनरावृत्ति के इस दूसरे चरण के दौरान बुलाया जाता है, तो इटेटरेटर PriorityQueue.removeEq(lastRetElt) पर कॉल करता है, जहां lastRetElt विशेष कतार से अंतिम तत्व लौटाया जाता है। removeEq को हटाने के लिए सही तत्व खोजने के लिए एक रैखिक खोज का उपयोग करने के लिए मजबूर होना पड़ता है, जो इसे O(n) बनाता है। लेकिन यह .equals() के बजाय == का उपयोग कर तत्वों की जांच कर सकता है, इसलिए इसका निरंतर कारक PriorityQueue.remove(Object) से कम है।

तो, दूसरे शब्दों में, एक पुनरावर्तक के साथ हटाने तकनीकी रूप से O(n) है, लेकिन व्यवहार में यह remove(Object) से काफी तेज होना चाहिए।