C＃List從結尾刪除，真的是O（n）？

我讀過幾篇文章，指出List.RemoveAt（）在O（n）時間。C＃List從結尾刪除，真的是O（n）？

如果我做這樣的事情：

var myList = new List<int>(); 

/* Add many ints to the list here. */ 

// Remove item at end of list: 
myList.RemoveAt(myList.Count - 1); // Does this line run in O(n) time?

從列表的末尾刪除應該是O（1），因爲它只是需要遞減表計數值。

我是否需要編寫自己的類來實現此行爲，還是刪除C＃列表末尾的項目已經在O（1）時間執行？

來源

2011-03-22 Olhovsky

我知道我可以剖析這個，看看，或者使用.NET反射器。創建這個問題的關鍵是爲我認爲是一個重要問題創建一個可搜索的結果。在我自己的搜索中，我沒有找到答案。 – Olhovsky 2011-03-22 18:47:14

一般而言，List<T>::RemoveAt是O（N），因爲需要在索引向上移動陣列中的一個插槽後移動元素。但是，從列表的末尾刪除的具體情況沒有進行轉換需要的，它因此是O（1）

來源

2011-03-22 18:46:42 JaredPar

它會是O（N），但這裏的'N'是'list.Count - indexRemoved'嗎？ – Blorgbeard 2011-03-22 18:49:00

你從哪裏讀到這個？他們的文檔會有其他建議，看起來程序是O（n）不管怎麼說 - 也就是說，他們並沒有做出特殊情況。 – 2014-09-11 14:43:57

@KevinDepue。這不是一個真正的特例，它本身就是一個特例。類似於遍歷一個總是O（N）的列表，但是當列表只有1個元素時，它也是O（1），因爲在這種情況下N是1。沒有理由將其視爲特殊情況，但無論如何它仍然是一個特殊情況。 – Nolonar 2015-07-21 09:52:30

這應該給你一個想法

public void RemoveAt(int index) { 
     if ((uint)index >= (uint)_size) { 
      ThrowHelper.ThrowArgumentOutOfRangeException(); 
     } 
     _size--; 
     if (index < _size) { 
      Array.Copy(_items, index + 1, _items, index, _size - index); 
     } 
     _items[_size] = default(T); 
     _version++; 
    }

來源

2011-03-22 18:48:52

刪除最後一個項目實際上是O(1)操作因爲只有在這種情況下，List纔不會移動數組中的下一項。下面是從反射器代碼：

this._size--; 
if (index < this._size) // this statement is false if index equals last index in List 
{ 
    Array.Copy(this._items, index + 1, this._items, index, this._size - index); 
} 
this._items[this._size] = default(T);

來源

2011-03-22 18:54:03 Snowbear

'Array.Copy'只是複製數據，而不是分配數據。 – Gabe 2011-03-22 18:57:50

@加貝，謝謝，修正了這個問題。 – Snowbear 2011-03-22 18:59:42

-2

在我看來，如果這是你的應用程序實際上是相關的，你可能會測量它在較短的時間比把要問的問題。現在你至少有兩個相互矛盾的答案，所以你不得不測試它。

我試圖做的一點是，除非MSDN文檔說removeAt是O（1）列表末尾的項目，否則你不能指望它以這種方式工作，它可能會更改任何給定的.NET更新。就這一點而言，對於不同類型的行爲可能會有所不同，因爲你知道。

如果List是要使用的「自然」數據結構，則使用它。如果從列表中刪除項目最終成爲熱點分析，那麼也許是時候實施自己的課程了。

來源

2011-03-22 18:56:18

如果您已經仔細閱讀我添加到問題中的評論，您會發現我解決了分析或使用反射器的問題。至於你對List類的屬性在未來版本中的變化的第二點，我認爲這是一個有效的觀點，但我也認爲提出關於當前事態的問題仍然是合理的。特別是因爲它很可能很長一段時間看不到變化。畢竟，編程行業變化相對較快，大多數實現特定問題僅在有限的時間內有關。 – Olhovsky 2011-03-22 19:01:14

如果今天從O（1）中刪除，則有99。999999％的機會將保持這種方式。我不會建議他開始實施他自己的數據結構，但這種變化的可能性很小。關於「自己衡量一下」的部分，這不是事實，它會更快。像JaredPar這樣的受信任的人可以在幾分鐘甚至幾秒鐘內給出一個很好的答案;-) – 2011-03-22 19:02:28

C＃List從結尾刪除，真的是O（n）？

回答

相關問題