rimozione Java CodaConPriorita di elementi arbitrari Performance

Question

dire che ho un CodaConPriorita java (che java implementa come un mucchio) che iterare per rimuovere gli elementi sulla base di alcuni criteri:

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

Quanto dura ogni remove() operazione prendere? Non sono sicuro che sia O (log (n)) o O (1).

Answer 1

Se si sta utilizzando l'implementazione Sun, è O(log(n)). Dal Javadocs: nota

implementazione: questa implementazione fornisce O (log (n)) per l'Enqueing e metodi dequeing (offer, poll, remove() e add); tempo lineare per i metodi remove(Object) e contains(Object) ; e tempo costante per i metodi di recupero (peek, element e size).

Altre implementazioni potrebbero avere diversa complessità.

---

Edit: Le Javadocs non coprire l'esecuzione di rimozione di un elemento con un iteratore, così ho dovuto cercare il codice sorgente. Tutto ciò è pertinente all'implementazione di Sun e potrebbe differire nella versione di Apple, GNU Classpath, ecc. La sorgente Sun è disponibile here; è anche incluso nel JDK, quindi potresti già averlo installato.

In iteratore s' il PriorityQueue, il caso di default per remove() è chiamare PriorityQueue.removeAt(lastRet), dove lastRet è l'indice per l'ultima volta restituito da next(). removeAt() sembra essere O(log(n)) nel peggiore dei casi (potrebbe dover setacciare la coda, ma non deve iterare).

Tuttavia, a volte accadono cose brutte. Dai commenti di 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. 
*/ 

Quando un elemento non nullo viene restituito dalla removeAt(), l'iteratore lo aggiunge a una coda speciale per un uso successivo: quando l'iteratore si esaurisce di elementi in coda, ha poi itera attraverso questa coda speciale. Quando viene chiamato remove() durante questa seconda fase di iterazione, l'iteratore chiama PriorityQueue.removeEq(lastRetElt), dove lastRetElt è l'ultimo elemento restituito dalla coda speciale. removeEq è costretto a utilizzare una ricerca lineare per trovare l'elemento corretto da rimuovere, che lo rende O(n). MA può controllare gli elementi usando == anziché .equals(), quindi il suo fattore costante è inferiore a PriorityQueue.remove(Object).

Quindi, in altre parole, la rimozione con un iteratore è tecnicamente O(n), ma in pratica dovrebbe essere un po 'più veloce di remove(Object).