ArrayList rimuovi vs removeAll

Question

Che cosa è meglio usare, se voglio rimuovere una raccolta da un arraylist? Penso che il metodo removeAll in ArrayList sia scritto per questa attività, ma in un test che ho scritto, solo iterando attraverso gli oggetti e rimuovendoli individualmente è stato qualche secondo più veloce.

A cosa serve?

edit:

il codice di removeAll ho trovato sul grepcode chiama batchRemove (c, false):

booleano Più ... batchRemove (Collection c, complemento booleano) {

700   final Object[] elementData = this.elementData; 
701   int r = 0, w = 0; 
702   boolean modified = false; 
703   try { 
704    for (; r < size; r++) 
705     if (c.contains(elementData[r]) == complement) 
706      elementData[w++] = elementData[r]; 
707   } finally { 
708    // Preserve behavioral compatibility with AbstractCollection, 
709    // even if c.contains() throws. 
710    if (r != size) { 
711     System.arraycopy(elementData, r, 
712         elementData, w, 
713         size - r); 
714     w += size - r; 
715    } 
716    if (w != size) { 
717     // clear to let GC do its work 
718     for (int i = w; i < size; i++) 
719      elementData[i] = null; 
720     modCount += size - w; 
721     size = w; 
722     modified = true; 
723    } 
724   } 
725   return modified; 
726  } 

io in realtà non capisco è ..

il mio codice di prova è stato questo:

public class RemoveVsRemovall { 

    public static void main(String[] args){ 
     ArrayList<String> source = new ArrayList<>(); 
     ArrayList<String> toRemove = new ArrayList<>(); 
     for(int i = 0; i < 30000; i++){ 
      String s = String.valueOf(System.nanoTime()); 
      source.add(s); 
      if(i % 2 == 0) toRemove.add(s); 
     } 
     long startTime = System.nanoTime(); 
     removeList1(source, toRemove); 
     long endTime = System.nanoTime(); 
     System.out.println("diff: " + (endTime - startTime) * 1e-9); 
    } 

    static void removeList1(ArrayList<String> source, ArrayList<String> toRemove){ 
     source.removeAll(toRemove); 
    } 

    static void removeList2(ArrayList<String> source, ArrayList<String> toRemove){ 
     for(String s : toRemove){ 
      source.remove(s); 
     } 
    } 
} 

chiamandolo un paio di volte con elenchi di dimensioni e commutazione diversi tra i due metodi.

Answer 1

Ci sono molte ragioni per cui è difficile dare una risposta generale a questa domanda.

In primo luogo, è necessario comprendere che queste caratteristiche di prestazione dipendono dall'implementazione. È abbastanza probabile che l'implementazione vari a seconda della piattaforma e della versione di JDK.

Detto questo, ci sono per lo più 2 strategie per l'attuazione removeAll:

1. Per ogni elemento della vostra ArrayList, controllare se è nell'altra Collection; se è così, rimuovilo.
2. Per ogni elemento dello Collection, verificare se è nello ArrayList; se è così, rimuovilo.

Se il Collection esegue contiene in tempo costante, la strategia 1 (asintoticamente) vince. D'altra parte, se si esegue contains eseguendo la scansione dell'intera connessione e Collection itera molto lentamente, la strategia 2 ha generalmente un vantaggio, perché itera su Collection una sola volta; ma anche in questo caso, se lo Collection è molto grande e la maggior parte degli elementi dello ArrayList sono tra i primi elementi dello Collection, la strategia 1 vince ancora ... non c'è fine.

Probabilmente starai meglio affidandoti all'implementazione di removeAll(); se fallisce, prova a cambiare le strutture dei dati; e se anche questo fallisce, implementa il tuo metodo da benchmark empirici.

Answer 2

Un'altra cosa da considerare:

Il codice di Java è stato battletested per secoli, ed è scritto in modo tale da adattarsi ad un sacco di casi diversi e speciali (vedi il commento Preserve behavioral compatibility with AbstractCollection).

Quindi, in realtà è probabile che tu possa scrivere la tua implementazione dei metodi, che funzioneranno più velocemente. Ma d'altra parte, sei sicuro di poter trattare tutti i casi speciali a cui gli sviluppatori Java si sono confrontati sin dalla nascita di Java?

Prendere in considerazione anche che alcune funzioni Java potrebbero utilizzare alcune implementazioni C per velocizzare le operazioni. Apparentemente non è questo il caso, ma potrebbe.