Com'è possibile che "RemoveAll" in LINQ sia molto più veloce dell'iterazione?

Question

Il seguente codice:

List<Interval> intervals = new List<Interval>(); 
List<int> points = new List<int>(); 

//Initialization of the two lists 
// [...] 

foreach (var point in points) 
{ 
    intervals.RemoveAll (x => x.Intersects (point)); 
} 

è almeno 100 volte più veloce di questo, quando le liste sono di dimensioni ~ 10000:

List<Interval> intervals = new List<Interval>(); 
List<int> points = new List<int>(); 

//Initialization of the two lists 
// [...] 

foreach (var point in points) 
{ 
    for (int i = 0; i < intervals.Count;) 
    { 
     if (intervals[i].Intersects(point)) 
     { 
      intervals.Remove(intervals[i]); 
     } 
     else 
     { 
      i++; 
     } 
    } 
} 

Come è possibile? Cosa viene eseguito sotto il cofano con "RemoveAll"? Secondo MSDN, "RemoveAll" esegue una ricerca lineare ed è quindi in O (n). Quindi mi aspetterei prestazioni simili per entrambi.

Quando si sostituisce "Rimuovi" con "RimuoviAt", l'iterazione è molto più veloce, paragonabile a "Rimuovi tutto". Ma sia "Rimuovi" e "RimuoviAt" hanno complessità O (n), quindi perché la differenza di prestazioni tra loro è così grande? Potrebbe essere solo dovuto al fatto che "Rimuovi (elemento)" confronta gli elementi dell'elenco con "elemento" e "RimuoviAt" non esegue alcun confronto?

Answer 1

Se si rimuove un elemento da una List<T>, tutti gli articoli dopo che verrà spostato indietro di un posto. Quindi, se rimuovi n elementi, molti articoli verranno spostati n volte.
RemoveAll sarà solo fare il movimento, una volta, che potete vedere nel sorgente per List<T>: source

Un'altra cosa è che Remove(T item) cercherà l'intero elenco per la voce, in modo che un altro le operazioni n.

qualcosa che non ha nulla a che fare con la tua domanda, ma vorrei sottolineare in ogni caso:
Se si utilizza un ciclo for per eliminare gli elementi da un elenco, è molto più facile per iniziare alla fine:

for (int i = intervals.Count - 1; i >= 0; i--) 
{ 
    if (intervals[i].Intersects(point)) 
    { 
     intervals.RemoveAt(i); 
    } 
} 

In questo modo, non è necessario che la brutta else-clausola

Answer 2

RemoveAll può essere fatto in O(n) controllando la condizione per n elementi e spostando al massimo n elementi.

Il ciclo è O(n^2), poiché ogni Remove deve controllare fino a n elementi. E anche se lo si modifica in RemoveAt, deve comunque passare a n elementi.

Questa potrebbe essere la soluzione più veloce: intervals.RemoveAll(x => points.Any(x.Intersects));

Answer 3

List è un array, e la rimozione di un elemento di un array richiede lo spostamento di tutti gli elementi dopo quello che si sta rimuovendo al precedente indice, quindi a[i] viene spostato su a[i-1].

Questa operazione richiede ripetutamente più spostamenti, anche se più elementi soddisfano i criteri di rimozione. RemoveAll può ottimizzare questo spostando gli elementi di più di 1 indice alla volta mentre attraversa l'elenco e trova più elementi che corrispondono ai criteri di rimozione.

Answer 4

La differenza è che Remove stesso è un O (n), quindi ottieni O (n^2).

Sostituire for con una nuova raccolta e un compito.

items = items.Where(i => ...).ToList(); 

Questo metodo ha la stessa complessità algoritmica tempo come RemoveAll, ma utilizza (n) memoria aggiuntiva O.