RemoveRange（）方法如何在List <>中工作？

如標題所示。我知道它可能會在刪除項目之前和之後合併2個子列表，但在刪除LAST元素時該方法的行爲如何？換句話說：它是否以某種方式複製了刪除索引之前的所有元素？我只是好奇在一個巨大的列表（假設有5000個元素）上使用RemoveRange來消除f.e.只有最後2個。RemoveRange（）方法如何在List <>中工作？

如果它做了一個副本，那麼有沒有辦法改變一些設置List大小的內部變量（並將剩餘的分配元素視爲垃圾）？

我只設法找到一個信息，它是一個O（n）複雜度算法，但我不確定這個情況下的「n」是列表大小還是要刪除的項目數。

對任何提示都會很高興。

來源

2013-04-17 Tarec

http://msdn.microsoft.com/en-gb/library/y33yd2b5.aspx「此方法是O（n）操作，其中n是Count。」「這些項目被刪除，列表中的所有元素的索引都減少了。」 http://geekswithblogs.net/BlackRabbitCoder/archive/2012/02/23/c.net-little-wondersndashthe-listlttgt-range-methods.aspx「請注意，這會導致列表的其餘部分需要向下移動到填補空白，這可以是不平凡的。但是，它不需要重新分配列表，因爲它的大小可能會縮小，而不會增加。「 –

來吧，你認爲計數是要刪除的數字。從十列表中刪除2將花費相同的時間從百萬中刪除2如果你點擊文檔中的計數鏈接列表計數 – Paparazzi

@Blam這是不正確的，除非你從列表的末尾移除如果你從列表的開始處移除那麼這兩個項目之間的差異就是將內存中的8個項目向上移動兩個項目，而將內存中的1,999,998個項目向上移動兩個項目，這兩個項目不會相同 – Servy

它將做的是將項目範圍結束後的每個項目移除並在列表中將其移出項目數量。就性能影響而言，移動項目範圍結束後，每個項目都會有一個副本。這意味着當從最後移除（它將是O（1））時它將表現最好，並且在從開始移除（O（n））時表現最差。

作爲一個例子，考慮以下列表：

index - value 

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

如果我們調用RemoveRange(2, 2)然後我們將移除兩個項目開始於索引2，所以我們取消了C和D.

這意味着需要將E複製到索引2，然後將F複製到索引3，並將G複製到索引4中。在刪除最後一個項目後，每個項目都有一個複製操作。

請注意，由於您可以將整個內存塊「向上」移動兩位，因此實際上可以更有效地複製每個項目。對於計算機內存而言，將整塊內存向上移動一定數量的字節比將大量內存移動到不同的任意位置要容易得多。儘管如此，它將具有相同的漸近複雜性。

來源

2013-04-17 16:11:28 Servy

這正是我想知道的，謝謝。 – Tarec

List<T>只是一個數組的封裝，在下面的代碼中被稱爲_items。該陣列中可能有更多的插槽，而不是列表中的項目，因此_size用於跟蹤實際有效的數量。當您從過去的範圍內做一個RemoveRange(index, count) ...

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

...它複製項目到現在空的空間，並清除舊項目。

如果您正在移除一個接近大型列表開頭的範圍，那麼成本與列表大小成正比，因爲必須移除很多東西。

如果你正在移除一個接近大型列表末尾的較大範圍，那麼複製很便宜，但清理費用很高，所以成本將與所移除範圍的大小成比例。

來源

2013-04-17 16:13:10

請問您能否深入瞭解爲什麼結算在第二種情況下價格昂貴？據我瞭解，我們必須清除數組中受影響的元素，其大小不會大於'_size'或'_items.Length'大列表的情況。例如，如果您在開始或接近結束時刪除大列表中的小範圍。 –

這是否意味着我應該使用'LinkedList '如果我知道列表會很大，我想稍後移除項目？ – Jodrell

@Jodrell可能不是。使用鏈表時，即使對於迭代鏈表等簡單任務，內存丟失也會導致性能很差。雖然它的很多操作的大O值很低，但在大多數實際情況下，鏈接列表很少成爲淨贏。 – Servy

RemoveRange（）方法如何在List <>中工作？

回答

相關問題