最適合調度程序的.net計時器

Question

我們使用CCR timers在我們的代碼中確定了一個熱點。看起來，如果我們排隊成千上萬的定時器，代碼遭受終端放緩。

修復方法是選擇最快的計劃項目併爲此事件排入計時器。當它發生時，我們重複。這樣，我們一次只排隊一個定時器間隔。

我們現在發現的是，我們用來管理預定項目的SortedList實例正在使用列表中刪除的權重進行刻錄。

是否所有.net定時器都受到CPU使用率隨排隊項數量增加的問題的影響，還是存在更智能化寫入的問題。

另外，是否有更好的數據結構來保持我們排序的項目有序，即支持快速插入和從列表的前面快速移除？

Answer 1

嘗試使用LinkedList<T>，我相信你會看到性能的巨大提升。它非常適合快速添加和刪除。

Answer 2

要始終獲得最快的預定項目，您需要使用Heap而不是SortedList。

標準.Net庫沒有堆。您可以從here下載實施或自行推出。

Answer 3

有序列表使用下面的數組，因此從列表前移除是其中最慢的操作之一。按相反的順序排序會減少從列表中刪除項目所需的時間，因爲您將從最後刪除項目。

如果你關心的是下一個項目，Priority Queue可能是一個不錯的選擇。

Answer 4

聽起來像你需要使用優先級隊列。 Priority queues通常用堆實現，但我發現skip lists傾向於更好地工作。不幸的是，BCL沒有優先級隊列，因此您必須自己編寫或在其他地方找到。 SortedList將會破壞你的表現。即使您決定對優先隊列，您也可以通過移動到SortedDictionary來獲得快速提升。

編輯：我爲什麼會喜歡這裏優先級隊列，而不是到SortedDictionary的原因是因爲在SortedDictionary最低鍵清除是爲O（log（n））的，而不是O（1）爲優先隊列。

Answer 5

如果你絕對需要排序功能，你可以考慮使用SortedDictionary而不是SortedList。 SortedDictionary是O（日誌n）插入和remonal，因爲它在內部使用樹。

http://msdn.microsoft.com/en-us/library/5z658b67(VS.80).aspx

Answer 6

快速修復可能（也可能不）是不夠的，切換到一個排序的字典。

排序列表會導致問題，因爲它的基礎數據結構是一個數組。正如另一張海報指出的那樣，如果您從排序列表的「頂部」（[0]）中移除，則所有其他項目必須在陣列中向下移動一個，因此列表中的項目越多，則越多昂貴的是要刪除一個。 （所以表現是O（n）或更差）。

交換後，對已排序字典的插入和刪除操作是O（log n），因此當列表中有大量項目時，刪除性能的影響要小得多。