Java: filtro ArrayList efficiente?

Question

Ho bisogno di filtrare un ArrayList e rimuovere gli elementi trovati. Essendo relativamente nuovo a Java, mi chiedo quale sia il metodo più efficace per raggiungere questo obiettivo (importa perché funziona su dispositivi mobili). Attualmente faccio questo:

// We display only top-level dealers (parentId=-10) 
ArrayList<DealerProductCount> subDealers = new ArrayList<DealerProductCount>(); 
for (DealerProductCount dealer : wsResponse.Dealers) { 
    if (dealer.ParentId != -10) subDealers.add(dealer); 
} 
wsResponse.Dealers.removeAll(subDealers); 

Può essere eseguito senza oggetti temporanei? Forse manipolando direttamente (rimuovendo) elementi della lista che viene iterata?

Answer 1

efficiente rimozione di un certo numero di elementi da un ArrayList richiede una riflessione. L'approccio ingenuo è qualcosa di simile:

Iterator<DealerProductCount> it = wsResponse.Dealers.iterator(); 
while (it.hasNext()) { 
    if (it.next().ParentId != -10) { 
     it.remove(); 
    } 
} 

Il problema è che ogni volta che si rimuove un elemento di copiare (in media) la metà degli elementi rimanenti. Questo perché rimuovere un elemento da un ArrayList comporta la copia di tutti gli elementi dopo che l'elemento è stato rimosso di una posizione a sinistra.

La soluzione originale che comprende l'elenco di elementi da rimuovere essenzialmente fa la stessa cosa. Sfortunatamente, le proprietà di un ArrayList non consentono a removeAll di fare meglio di quanto sopra.

Se si prevede di rimuovere una serie di elementi, il seguente è più efficiente:

ArrayList<DealerProductCount> retain = 
     new ArrayList<DealerProductCount>(wsResponse.Dealers.size()); 
for (DealerProductCount dealer : wsResponse.Dealers) { 
    if (dealer.ParentId == -10) { 
     retain.add(dealer); 
    } 
} 
// either assign 'retain' to 'wsResponse.Dealers' or ... 
wsResponse.Dealers.clear(); 
wsResponse.Dealers.addAll(retain); 

Siamo copia (quasi) l'intero elenco due volte, quindi questo dovrebbe andare in pari (in media) se si rimuove solo 4 elementi.

---

E 'interessante notare che i linguaggi di programmazione funzionali/librerie di supporto tipico di un metodo del filtro, e che può fare questo compito in un solo passaggio attraverso la lista; cioè molto più efficientemente. Penso che possiamo aspettarci miglioramenti significativi se/quando Java supporta lambdas e le API di raccolta sono migliorate per usarle.

Answer 2

Se si utilizza un iteratore, è possibile rimuovere gli elementi in modo sicuro durante l'iterazione.

Answer 3

Un modo sarebbe usare l'iteratore invece del per ogni:

Iterator<DealerProductCount> iter = wsResponse.Dealers.iterator() 
while(iter.hasNext()) { 
    if (iter.next().ParentId != -10) iter.remove(); 
}