Jak skutecznie usunąć z listy <T> (C#)?

Question

Jeśli dobrze zrozumiałem (i proszę mnie poprawić, jeśli się mylę), lista jest zaimplementowana przez tablicę w .NET, co oznacza, że ​​każde usunięcie pozycji na liście spowoduje ponowne przydzielenie całej listy (która w obrót oznacza O(n)).

Rozwijam grę, w grze mam wiele pocisków lecących w powietrzu w dowolnym momencie, powiedzmy 100 pocisków, każda klatka poruszam je o kilka pikseli i sprawdzam kolizję z obiektami w grze, Muszę usunąć z listy każdy trafiony punkt.

Więc zebrać zderzył kulę w innej listy tymczasowego, a następnie wykonaj następujące czynności:

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

Ponieważ pętla jest O(n) i usuń to O(n), spędzam O(n^2) czas usunięcia.

Czy istnieje lepszy sposób na usunięcie go lub bardziej odpowiedni do użycia?

Answer 1

Utwórz nową listę:

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

próbować używać idiomów funkcjonalne, jeśli możliwe. Nie modyfikuj istniejących struktur danych, twórz nowe.

Algorytm ten to O (N) dzięki hashu.

Answer 2

Nie możesz po prostu zmienić z List (odpowiednik Javy ArrayList, aby to zaznaczyć) na LinkedList? LinkedList pobiera O (1), aby usunąć konkretny element, ale O (n) do usunięcia według indeksu

Answer 3

Sposób, w jaki lista jest wdrażana wewnętrznie, nie jest czymś, o czym powinieneś się zastanowić. Powinieneś wchodzić w interakcję z listą na tym poziomie abstrakcji.

Jeśli masz problemy z wydajnością i wskazałeś je na liście, czas sprawdzić, jak jest zaimplementowany.

Jeśli chodzi o usuwanie pozycji z listy - można użyć mBullets.RemoveAll(predicate), gdzie predicate jest wyrażeniem identyfikującym przedmioty, które uległy kolizji.

Answer 4

Zestawy i połączone listy mają stały czas usuwania. Czy możesz użyć którejś z tych struktur danych?

Nie można uniknąć kosztu usunięcia (O) z List<T>. Będziesz musiał użyć innej struktury danych, jeśli jest to dla ciebie problem. Może sprawić, że kod, który wylicza pociski, również sprawi, że poczujesz się lepiej.

ISet<T> ma ładne metody obliczania różnic i przecięć między zestawami obiektów.

Tracisz porządek, używając zestawów, ale biorąc pod uwagę, że bierzesz kule, domyślam się, że to nie jest problem. Nadal można go wyliczyć w stałym czasie.

---

W twoim przypadku, można napisać:

mBullets.ExceptWith(bulletsForDeletion); 

Answer 5

jest szybszy niż Remove(T item), ponieważ później korzysta z pierwszego wewnątrz, wykonując odbicie, jest to kod wewnątrz każdej funkcji.

Ponadto, Remove(T) ma funkcję IndexOf, która ma w sobie drugą pętlę do oceny indeksu każdego elementu.

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; 
} 

chciałbym zrobić pętlę tak:

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

Answer 6

w duchu idiomu funkcjonalnej sugerowanej przez „usr”, można rozważyć nie usuwając z listy w ogóle. Zamiast tego rutyna aktualizacji powinna mieć listę i zwrócić listę. Zwrócona lista zawiera tylko obiekty "wciąż żywe". Następnie możesz zamienić listy na końcu pętli gry (lub natychmiast, jeśli to konieczne). Zrobiłem to sam.