Qual è la complessità di tempo e spazio del metodo retainAll quando utilizzato su HashSet in Java?

Question

Ad esempio, nel codice qui sotto:

public int commonTwo(String[] a, String[] b) 
{ 
    Set common = new HashSet<String>(Arrays.asList(a)); 
    common.retainAll(new HashSet<String>(Arrays.asList(b))); 
    return common.size(); 
} 

Answer 1

Diamo peruse a the code. Il metodo retainAll viene ereditato da AbstractCollection e (almeno in OpenJDK) si presenta così:

public boolean retainAll(Collection<?> c) { 
    boolean modified = false; 
    Iterator<E> it = iterator(); 
    while (it.hasNext()) { 
     if (!c.contains(it.next())) { 
      it.remove(); 
      modified = true; 
     } 
    } 
    return modified; 
} 

c'è un grosso questo da notare qui, abbiamo un ciclo su this.iterator() e chiamare c.contains. Quindi la complessità temporale è n chiamate a c.contains dove n = this.size() e al massimo n chiamate a it.remove().

Questa cosa importante è che il metodo contains viene chiamato sul dall'altroCollection e così la complessità dipende dalla complessità dell'altro Collectioncontains.

Così, mentre:

Set<String> common = new HashSet<>(Arrays.asList(a)); 
common.retainAll(new HashSet<>(Arrays.asList(b))); 

sarebbe O(a.length), come HashSet.contains e HashSet.remove sono entrambi O(1) (ammortizzato).

Se si dovesse chiamare

common.retainAll(Arrays.asList(b)); 

Poi a causa della O(n)contains su Arrays.ArrayList questo sarebbe diventato O(a.length * b.length) - cioè spendendo O(n) copiando l'array a un HashSet effettivamente fare la chiamata a retainAll molto più veloce.

Per quanto riguarda la complessità spaziale va, nessun spazio aggiuntivo (al di là del Iterator) è richiesto da retainAll, ma la vostra invocazione è in realtà piuttosto costoso spazio-saggio come si assegnano due nuovi HashSet implementazioni che sono in realtà a tutti gli effetti HashMap.

Due ulteriori cose si possono notare:

1. Non v'è alcun motivo per assegnare un HashSet dagli elementi in a - una collezione più economica che ha anche O(1) rimuovere dal mezzo come un LinkedList può essere utilizzato. (più economico nella memoria e tempo di compilazione - una tabella hash non viene creata)
2. Le modifiche si vanno perdere quando si creano nuove istanze di raccolta e si restituisce solo b.size().

Answer 2

L'implementazione è disponibile nella classe java.util.AbstractCollection. Il modo in cui viene implementato assomiglia a questo:

public boolean retainAll(Collection<?> c) { 
     Objects.requireNonNull(c); 
     boolean modified = false; 
     Iterator<E> it = iterator(); 
     while (it.hasNext()) { 
      if (!c.contains(it.next())) { 
       it.remove(); 
       modified = true; 
      } 
     } 
     return modified; 
    } 

ti iterare tutto nella vostra common insieme e verificare se la raccolta che è stato passato come parametro contiene questo elemento.

Nel tuo caso entrambi sono HashSet s, quindi sarà O (n), come dovrebbe essere O (1) ammortizzato e iterando sul tuo set common è O (n).

Un miglioramento che è possibile effettuare, è semplicemente non copiare a in un nuovo HashSet, perché verrà iterato in ogni caso è possibile mantenere una lista.