Jak działa metoda RemoveRange() na liście <>?

Question

Podobnie jak w tytule. Wiem, że prawdopodobnie łączy 2 podlisty przed i po usuniętych elementach, ale jak zachowuje się ta metoda podczas usuwania elementów OSTATNIEGO? Innymi słowy: czy w jakiś sposób tworzy kopię wszystkich elementów znajdujących się przed indeksem usuwania? Jestem po prostu ciekawa, jak wykorzystać funkcję RemoveRange na gigantycznej liście (powiedzmy 5000 elementów), aby usunąć f.e. tylko ostatnie 2 z nich.

Jeśli tworzy kopię, czy istnieje sposób na zmianę wewnętrznej zmiennej, która ustawia rozmiar listy (i traktuje resztę przydzielonych elementów jako śmieci)?

Udało mi się tylko znaleźć informację, że jest to algorytm złożoności O (n), ale nie jestem pewien, czy "n" w tym przypadku jest wielkością Listy, czy też liczbą elementów do usunięcia.

Będzie zadowolony z wszelkich wskazówek.

Answer 1

To, co zrobi, to usunięcie każdego z przedmiotów po końcu zakresu pozycji i przesunięcie go na liście o liczbę usuniętych elementów. Pod względem implikacji wydajnościowych będzie jedna kopia dla każdej pozycji po końcu zakresu przeniesionych pozycji. Oznacza to, że będzie on działał najlepiej podczas usuwania z końca (będzie to O (1)) i będzie najgorszy podczas usuwania od początku (O (n)).

Jako przykład rozważmy następującą listę:

index - value 

0 - A 
1 - B 
2 - C 
3 - D 
4 - E 
5 - F 
6 - G

Jeśli nazywamy RemoveRange(2, 2) Następnie usuwamy dwa elementy zaczynając od indeksu 2, więc mamy do usuwania C i D.

ten oznacza, że ​​E musi zostać skopiowane do indeksu 2, następnie F musi zostać skopiowane do indeksu 3, a G musi zostać skopiowane do indeksu 4. Dla każdego elementu po usunięciu ostatniego elementu jest wykonywana jedna operacja kopiowania.

Należy pamiętać, że ze względu na to, że można przenieść cały blok pamięci "w górę" o dwa, w praktyce oznacza to, że kopiowanie każdego elementu odbywa się indywidualnie. O wiele łatwiej jest pamięci komputera przenieść cały blok pamięci o określoną stałą liczbę bajtów, niż przenieść wiele małych sekcji pamięci do różnych dowolnych lokalizacji. Będzie mieć jednakową złożoność asymptotyczną.

Answer 2

List<T> to tylko opakowanie wokół tablicy o nazwie _items w poniższym kodzie. Tablica może mieć więcej slotów niż pozycji na liście, więc _size służy do śledzenia, ile z nich jest rzeczywiście poprawnych. Po wykonaniu RemoveRange(index, count) ...

_size -= count; 
if (index < _size) 
    Array.Copy(_items, index + count, _items, index, _size - index); 
Array.Clear(_items, _size, count); 

... kopiuje elementy z przeszłości zakresie do teraz pustej przestrzeni, a wyczyszczenie starych przedmiotów.

Jeśli usuwasz zakres bliski początku dużej listy, koszt jest proporcjonalny do rozmiaru listy, ponieważ tak wiele rzeczy musi zostać przesuniętych w dół.

Jeśli usuwasz duży zakres blisko końca dużej listy, kopiowanie jest tanie, ale rozliczenie jest kosztowne, więc koszt będzie proporcjonalny do rozmiaru usuniętego zakresu.