如何從列表<T>高效地刪除（C＃）？

如果我理解正確（如果我錯了，請糾正我），列表是由.NET中的數組實現的，這意味着每次刪除列表中的項目都將導致重新分配所有列表（在轉動意味着O(n)）。我正在開發一款遊戲，在遊戲中，我有很多子彈在任何給出的時刻都會在空中飛翔，比方說100個子彈，每一幀我都將它們移動幾個像素，並檢查與遊戲中物體的碰撞，我需要從列表中刪除每一顆相撞的子彈。如何從列表<T>高效地刪除（C＃）？

所以我收集另一個臨時列表中的子彈相撞，然後執行以下操作：

foreach (Bullet bullet in bulletsForDeletion) 
    mBullets.Remove(bullet);

由於環路是O(n)和刪除是O(n)，我花O(n^2）時間來消除。

有沒有更好的方法來刪除它，或更適合收藏使用？

來源

2012-12-29 OopsUser

不要說對不起。我們都在這裏學習。 –

你確定你有一個實際的問題，或者你是否過早優化？ – Oded

我沒有實際的問題，它運行在60 fps，我只是「感覺」像我寫的東西是錯誤的，因爲這樣的操作不應該是O（n^2）。 – OopsUser

創建一個新的列表：

var newList = `oldList.Except(deleteItems).ToList()`.

嘗試儘可能使用功能的成語。不要修改現有的數據結構，創建新的數據結構。

這個算法是O（N）歸功於哈希。

來源

2012-12-29 13:21:49 usr

爲什麼它是O（n）？當他將變量複製到另一個列表時，他需要檢查每個項目是否存在於「deleteItems」列表中，它看起來像O（n^2） – OopsUser

@OopsUser'Except'在內部建立一個哈希表，因此在oldList中每個項目的存在檢查是O（1），這就使得O（oldList.Count + deleteItems.Count）〜O （N）' – usr

+1。 @OopsUser，['Except'擴展方法]（http://msdn.microsoft.com/en-us/library/system.linq.enumerable.except.aspx）從源枚舉中讀取每個項目並輸出那些是不在'deleteItems'中。它在內部構建了一個'deleteItems'哈希，並根據該哈希測試每個輸入的存在。只有在哈希中未找到的項纔會被傳遞到輸出。這是O（N），但它會導致分配新的哈希和新數組（由'ToList'創建）。可能你不需要擔心這種內存開銷，但你應該知道它在那裏。 –

難道你不能只從List（相當於Java的ArrayList來突出顯示）切換到LinkedList？ LinkedList需要O（1）刪除特定的元素，但O（n）要通過索引刪除

來源

2012-12-29 13:18:41

列表如何在內部實現並不是您應該考慮的。您應該與該抽象級別的列表進行交互。

如果您確實遇到性能問題，並且將它們指向列表，那麼現在該查看它是如何實現的。

至於從列表中刪除項目 - 您可以使用mBullets.RemoveAll(predicate)，其中predicate是標識已衝突項目的表達式。

來源

2012-12-29 13:19:06 Oded

集合和鏈接列表都有恆定的時間刪除。你可以使用這些數據結構嗎？

無法避免從List<T>移除O（N）成本。如果這對您來說是個問題，您將需要使用不同的數據結構。它可能會使計算bulletsToRemove的代碼感覺更好。

ISet<T>有很好的方法來計算對象集之間的差異和交集。

你失去了使用集的順序，但考慮到你正在服用子彈，我猜這不是問題。您仍然可以在一段時間內枚舉它。

在你的情況，你可能會這樣寫：

mBullets.ExceptWith(bulletsForDeletion);

來源

2012-12-29 13:19:11

如何在.net中調用「set」？我沒有看到任何通用的集合。鏈接列表（和集）的問題是數據不在內存中的相同位置，所以當我從列表中讀取時，我有緩存的好處，但是當我使用集合/鏈接列表時放棄這個好處。儘管我必須從列表中刪除約一秒的項目，但我需要從列表中讀取100次以上（碰撞檢查等）。 – OopsUser

@OopsUser，您正在尋找'ISet '，您可以[請閱讀此處]（http://msdn.microsoft.com/en-us/library/dd412081.aspx）。 –

@OopsUser，同樣，看看你如何計算'bulletsForDeletion'會很有用。也許有一種方法可以使得這個更加優化。 –

RemoveAt(int index)比Remove(T item)快，因爲後面使用第一個裏面，做反射，這是每個函數裏面的代碼。

此外，Remove(T)有功能IndexOf，其中有一個第二個循環評估每個項目的索引。

public bool Remove(T item) 
{ 
    int index = this.IndexOf(item); 
    if (index < 0) 
    return false; 
    this.RemoveAt(index); 
    return true; 
} 


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

我會做這樣一個循環：

for (int i=MyList.Count-1; i>=0; i--) 
{ 
    // add some code here 
    if (needtodelete == true) 
    MyList.RemoveAt(i); 
}

來源

2012-12-29 13:25:58 sharp12345

你最後的代碼塊是'MyList.Clear（）'的低效版本。你的意思是寫點別的嗎？ –

@DrewNoakes，是的，我假設詢問用戶將添加一些條件來刪除一些項目，他不會實際刪除所有項目，編輯我的帖子。 – sharp12345

在功能成語是「USR」建議的精神，你可能會考慮不從你的列表中刪除的。相反，你的更新例程需要一個列表並返回一個列表。返回的列表只包含「仍然存在」的對象。然後，您可以在遊戲循環結束時交換列表（或者立即，如果適用）。我自己做過。

來源

2012-12-29 14:20:17 Griffin

如何從列表<T>高效地刪除（C＃）？

回答

相關問題