Come rimuovere dalla Lista <T> in modo efficiente (C#)?

Question

Se ho capito correttamente (e per favore correggimi se ho torto), la lista è implementata da array in .NET, il che significa che ogni cancellazione di un elemento nell'elenco causerà la riassegnazione di tutta la lista (che in turn significa O(n)).

sto sviluppando un gioco, nel gioco ho molti proiettili volano in aria su qualsiasi dando momento, diciamo 100 proiettili, ogni fotogramma li sposta da pochi pixel e verificare la presenza di collisioni con gli oggetti nel gioco, Devo rimuovere dall'elenco ogni proiettile che si è scontrato.

Così ho raccogliere il proiettile entrato in collisione in un altro elenco temporanea e quindi effettuare le seguenti:

foreach (Bullet bullet in bulletsForDeletion) 
    mBullets.Remove(bullet); 

Poiché il ciclo è O(n) e la rimozione è O(n), passo O(n^2) tempo per rimuovere.

C'è un modo migliore per rimuoverlo o una raccolta più adatta da usare?

Answer 1

creare un nuovo elenco:

var newList = `oldList.Except(deleteItems).ToList()`. 

tenta di utilizzare linguaggi funzionali, ove possibile. Non modificare strutture dati esistenti, crearne di nuove.

Questo algoritmo è O (N) grazie all'hashing.

Answer 2

Non è possibile passare da List (equivalente di Java ArrayList per evidenziarlo) a LinkedList? LinkedList accetta O (1) per eliminare un elemento specifico, ma O (n) per eliminare dall'indice

Answer 3

Il modo in cui una lista viene implementata internamente non è qualcosa a cui dovresti pensare. Dovresti interagire con la lista in quel livello di astrazione.

Se si verificano problemi di prestazioni e li si individua nell'elenco, è ora di esaminare il modo in cui è implementato.

Come per rimuovere elementi da un elenco, è possibile utilizzare mBullets.RemoveAll(predicate), dove predicate è un'espressione che identifica gli elementi che sono entrati in collisione.

Answer 4

Gli insiemi e le liste concatenate hanno entrambi una rimozione di tempo costante. Puoi utilizzare una di queste strutture dati?

Non c'è modo di evitare il costo di rimozione O (N) da List<T>. Avrai bisogno di utilizzare una diversa struttura dati se questo è un problema per te. Potrebbe anche rendere più gradevole il codice che calcola i proiettili.

ISet<T> ha buoni metodi per calcolare le differenze e le intersezioni tra insiemi di oggetti.

Si perde l'ordine utilizzando i set, ma dato che si stanno prendendo proiettili, suppongo che non sia un problema. Puoi ancora enumerarlo in tempo costante.

---

Nel tuo caso, si potrebbe scrivere:

mBullets.ExceptWith(bulletsForDeletion); 

Answer 5

RemoveAt(int index) è più veloce di Remove(T item) perché in seguito utilizzare il primo al suo interno, facendo riflesso, questo è il codice all'interno di ciascuna funzione.

Inoltre, Remove(T) ha la funzione IndexOf, che ha al suo interno un secondo ciclo per la valutazione dell'indice di ciascun articolo.

public bool Remove(T item) 
{ 
    int index = this.IndexOf(item); 
    if (index < 0) 
    return false; 
    this.RemoveAt(index); 
    return true; 
} 


public void RemoveAt(int index) 
{ 
    if ((uint) index >= (uint) this._size) 
    ThrowHelper.ThrowArgumentOutOfRangeException(); 
    --this._size; 
    if (index < this._size) 
    Array.Copy((Array) this._items, index + 1, (Array) this._items, index, this._size - index); 
    this._items[this._size] = default (T); 
    ++this._version; 
} 

vorrei fare un ciclo come questo:

for (int i=MyList.Count-1; i>=0; i--) 
{ 
    // add some code here 
    if (needtodelete == true) 
    MyList.RemoveAt(i); 
} 

Answer 6

Nello spirito di linguaggio funzionale suggerito da "usr", si potrebbe prendere in considerazione non la rimozione dall'elenco a tutti. Invece, fare in modo che la routine di aggiornamento esegua un elenco e restituisca un elenco. L'elenco restituito contiene solo gli oggetti "ancora vivi". È quindi possibile scambiare le liste alla fine del ciclo di gioco (o immediatamente, se appropriato). L'ho fatto anch'io.