Czy jest szybsza metoda List<T>.Remove(T) lub List<T>.RemoveAt(int) w kolekcjach .NET? Czy prędkość różni się dla typów wartości lub typów odniesienia?Czy jest to szybsze niż metoda <T> .Usuń (T) lub Lista <T> .RemoveAt (int)?
List.Remove (T) używa IndexOf i RemoveAt (int) w swojej implementacji. Tak List.RemoveAt (int) jest szybszy.
public bool Remove(T item)
{
int index = this.IndexOf(item);
if (index >= 0)
{
this.RemoveAt(index);
return true;
}
return false;
}
Remove (T) sprawia, że wewnętrznie wezwanie do RemoveAt (int) Więc robi bezpośrednio RemoveAt jest szybsze.
Ale co chcesz osiągnąć?
Prosta odpowiedź:
Ogólnie RemoveAt jest szybsza, choć nie zawsze ogromnie.
Długa odpowiedź:
Miejmy tylko rozważyć znalezienie pierwszy element jest właściwa. Metoda Remove musi przeszukiwać listę dla elementu, który pasuje do danego obiektu, a zatem ogólnie czas jest O(n). RemoveAt na liście może po prostu zindeksować dany element, a zatem jest O(1).
Teraz usunięcie elementu z końca listy to oczywiście O(1), ale generalnie usunięcie przedmiotu zajmuje czas O(n), ponieważ należy przeprowadzić przetasowanie (przenoszenie przedmiotów po usuniętym do przodu). Dlatego w ogólnym przypadku całkowita złożoność czasu dla usunięcia wynosi odpowiednio O(n) + O(n) lub O(n) + O(1) dla Remove and RemoveAt, a zatem po prostu O(n) w obu przypadkach. Jednakże, gwarantowane jest, że RemoveAt jest co najmniej tak szybki, chociaż skalowanie jest takie samo, chyba że wiesz, że usuwasz je w/blisko końca.
Dzięki, teraz rozumiem, dlaczego MSDN mówi, że RemoveAt to O (n), gdzie n to Count-index – Yellowfog
Zastosowanie System.Diagnostics.Stopwatch()
bym właśnie stworzyliśmy małą aplikację konsoli, aby sprawdzić, które jest szybsze.
Biorąc pod uwagę, że .Net infekuje wektor (lub tablicę), a nie listę połączoną, metoda RemoveAt() jest szybsza.
Ale jeśli sprawi, że twój kod będzie najgorszy lub nieczytelny, równie dobrze może nadal używać Remote (T). –
'this.IndexOf (item)' kod ma ogromną cenę pod względem wydajności, ponieważ skanuje całą tablicę backingową, dopóki nie zostanie usunięty element. Zwłaszcza gdy element do usunięcia znajduje się na końcu listy, skanuje całą listę za każdym razem, gdy żądane jest usunięcie. Stało się to ze mną, gdy próbowałem zaimplementować strukturę danych stosu za pomocą klasy 'List'. Ponieważ rozmiar listy znacznie rośnie, np. poza elementami 10K, usunięcie z końca za pomocą Remove (T) może zniszczyć twój program. –
RBT