Wie funktioniert die RemoveRange() - Methode in einer Liste <>?

Question

Wie im Titel. Ich weiß, dass es wahrscheinlich zwei Unterlisten vor und nach gelöschten Elementen zusammenführt, aber wie verhält sich diese Methode beim Entfernen von LAST-Elementen? Mit anderen Worten: Macht es irgendwie eine Kopie aller Elemente, die sich vor dem Entfernen des Index befinden? Ich bin nur neugierig auf die Leistung der Verwendung von RemoveRange auf einer riesigen Liste (sagen wir 5000 Elemente), nur um z. B. zu entfernen. nur die letzten 2 von ihnen.

Wenn es dann eine Kopie macht, gibt es eine Möglichkeit, eine interne Variable zu ändern, die die Größe der Liste einstellt (und Rest der zugeordneten Elemente als Müll behandeln)?

Ich habe nur eine Information gefunden, dass es ein O (n) Komplexitätsalgorithmus ist, aber ich bin mir nicht sicher, ob das "n" in diesem Fall eine Listengröße oder eine Anzahl zu löschender Elemente ist.

Wir freuen uns über jeden Hinweis.

Answer 1

Es wird jedes Element nach dem Ende des Bereichs von Elementen, die entfernt werden sollen, genommen und in der Liste nach der Anzahl der Elemente verschoben, die entfernt wurden. Im Hinblick auf die Auswirkungen auf die Leistung wird es nach dem Ende des Bereichs der verschobenen Artikel eine Kopie für jeden Artikel geben. Dies bedeutet, dass es am besten funktioniert, wenn es vom Ende entfernt wird (es wird O (1) sein), und führt am schlechtesten aus, wenn es von Anfang an entfernt wird (O (n)).

Als Beispiel betrachten wir die folgende Liste:

index - value 

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

Wenn wir RemoveRange(2, 2) rufen dann sind wir zwei Punkte entfernt an der Position index 2, so dass wir entfernen C und D.

Diese bedeutet, dass E in den Index 2 kopiert werden muss, dann muss F in den Index 3 kopiert werden, und G muss in den Index 4 kopiert werden. Nach dem letzten entfernten Objekt gibt es einen Kopiervorgang für jedes Element.

Beachten Sie, dass aufgrund der Tatsache, dass Sie den gesamten Speicherblock um "zwei" nach oben verschieben können, dies in der Praxis effizienter ist, dass jedes Element einzeln kopiert wird. Es ist viel einfacher für einen Computerspeicher, einen ganzen Speicherblock um eine bestimmte Anzahl von Bytes zu verschieben, als viele kleine Speicherbereiche an verschiedene willkürliche Speicherorte zu verschieben. Es wird jedoch die gleiche asymptotische Komplexität haben.

Answer 2

List<T> ist nur ein Wrapper um ein Array, im folgenden Code _items genannt. Das Array enthält möglicherweise mehr Slots als Elemente in der Liste. Daher wird _size verwendet, um zu verfolgen, wie viele tatsächlich gültig sind. Wenn Sie das tun ein RemoveRange(index, count) ...

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

... es kopiert die Elemente aus früherem Bereich in den leeren Raum, und löschen die alten Elemente.

Wenn Sie einen Bereich nahe am Anfang einer großen Liste entfernen, dann sind die Kosten proportional zur Größe der Liste, weil so viele Dinge nach unten verschoben werden müssen.

Wenn Sie einen großen Bereich nahe am Ende einer großen Liste entfernen, ist das Kopieren zwar billig, aber das Löschen ist teuer, so dass die Kosten proportional zur Größe des entfernten Bereichs sind.