Il modo migliore per rimuovere un elemento arraylist da un altro arrayist

Question

Qual è il miglior metodo di esecuzione in Java (7,8) per eliminare gli elementi integer di uno Arraylist da un altro. Tutti gli elementi sono unici nel primo e nel secondo elenco.

Al momento so il metodo API removeall e usarlo in questo modo:

tempList.removeAll(tempList2); 

Il problema si presenta quando operare con ArrayLists avere più di 10000 elementi. Ad esempio quando rimuovo 65000 elementi, il ritardo sembra essere di circa 2 secondi. Ma ho bisogno di lavorare con liste ancora più grandi con oltre 1000000 elementi.

Qual è la strategia per questo problema?

Forse qualcosa con la nuova API Stream dovrebbe risolverlo?

Answer 1

tl; dr:

mantenerlo semplice. Utilizzare

list.removeAll(new HashSet<T>(listOfElementsToRemove)); 

invece.

---

Come Eran già menzionato nel his answer: Il basso rendimento deriva dal fatto che la pseudocodice di un generico removeAll implementazione è

public boolean removeAll(Collection<?> c) { 
    for (each element e of this) { 
     if (c.contains(e)) { 
      this.remove(e); 
     } 
    } 
} 

Quindi la chiamata contains che viene fatto nella lista dei gli elementi da rimuovere causano la prestazione O (n * k) (dove n è il numero di elementi da rimuovere e è il numero di elementi nell'elenco in cui viene chiamato il metodo).

Ingenuamente, si potrebbe immaginare che la chiamata this.remove(e) su un List potrebbe anche avere O (k), e questa implementazione avrebbe anche complessità quadratica. Ma questo non è il caso: hai detto che gli elenchi sono specificatamente ArrayList istanze. E il metodo ArrayList#removeAll è implementato per delegare a un metodo chiamato batchRemove che opera direttamente sull'array sottostante e fa non rimuovere gli elementi singolarmente.

Quindi tutto quello che dovete fare è assicurarsi che la ricerca nella collezione che contiene gli elementi da rimuovere sia veloce - preferibilmente O (1). Questo può essere ottenuto inserendo questi elementi in un Set. Alla fine, si può semplicemente essere scritto come

list.removeAll(new HashSet<T>(listOfElementsToRemove)); 

---

note collaterali:

La risposta di Eran ha IMHO due grossi inconvenienti: Prima di tutto, richiede ordinamento le liste, che è O (n * logn) - e semplicemente non è necessario. Ma ancora più importante (e ovviamente): L'ordinamento probabilmente cambierà l'ordine degli elementi! Cosa succede se questo non è semplicemente desiderato?

In remoto: ci sono altre sottigliezze coinvolte nelle implementazioni removeAll. Ad esempio, HashSet removeAll method is surprisingly slow in alcuni casi. Anche se questo si riduce anche alla O (n * n) quando gli elementi da rimuovere sono memorizzati in una lista, il comportamento esatto può davvero essere sorprendente in questo caso particolare.

Answer 2

Ebbene, dal momento che removeAll i controlli per ogni elemento di tempList se appare nella tempList2, il tempo di esecuzione è proporzionale alla dimensione della prima lista moltiplicato per la dimensione della seconda lista, il che significa O(N^2) a meno che una delle due liste è molto piccolo e può essere considerato come "dimensione costante".

Se, d'altra parte, si pre-ordinare le liste, e poi iterare su entrambe le liste con una singola iterazione (simile alla fase unione in merge sort), l'ordinamento prenderà O(NlogN) e l'iterazione O(N), dando hai una durata totale di O(NlogN). Qui N è la dimensione del più grande dei due elenchi.

Se è possibile sostituire gli elenchi con una struttura ordinata (forse uno TreeSet, poiché si è detto che gli elementi sono univoci), è possibile implementare removeAll in tempo lineare, poiché non sarà necessario eseguire alcun ordinamento.

non ho ancora testato, ma qualcosa di simile può lavorare (supponendo che sia tempList e tempList2 sono ordinati):

Iterator<Integer> iter1 = tempList.iterator(); 
Iterator<Integer> iter2 = tempList2.iterator(); 
Integer current = null; 
Integer current2 = null; 
boolean advance = true; 
while (iter1.hasNext() && iter2.hasNext()) { 
    if (advance) { 
     current = iter1.next(); 
     advance = false; 
    } 
    if (current2 == null || current > current2) { 
     current2 = iter2.next(); 
    } 
    if (current <= current2) { 
     advance = true; 
     if (current == current2) 
      iter1.remove(); 
    } 
} 

Answer 3

Ho il sospetto che la rimozione da un ArrayList, è un successo perfromance in quanto l'elenco può o essere diviso quando viene rimosso un elemento nel mezzo o se l'elenco deve essere compattato dopo la rimozione di un elemento. Può essere più veloce per fare questo:

1. Crea 'set' degli elementi da rimuovere
2. Creare un nuovo ArrayList risultato che è necessario, chiamare R. Si può dare abbastanza taglia alla costruzione.
3. Iterate attraverso l'elenco originale da cui sono necessari elementi rimossi, se l'elemento si trova nel Set, non aggiungerlo a R, altrimenti aggiungerlo.

Questo dovrebbe avere O(N); se la creazione del Set e una ricerca in esso sono assunte come costanti.