SortedList與SortedDictionary與Sort（）

這是類似this one這樣的問題的延續。SortedList與SortedDictionary與Sort（）

是否有任何指導方針來調整性能？我不是說大O的收益，只是節省了一些線性時間。

例如，預分類保存在SortedList或SortedDictionary上的保存數量是多少？

假設我有一個具有3個屬性的人類排序，其中一個是年齡。我應該首先年齡對象的對象？

我應該先對一個屬性進行排序，然後使用生成的列表/字典對兩個屬性進行排序，依此類推？

任何其他優化想到？

來源

2010-01-10 Martin

您是否嘗試過分析代碼以確保初始化已排序的數據結構實際上是代碼中的瓶頸？ – 2010-01-10 11:56:03

到目前爲止，這是一個假設性的問題，但是，是的，到目前爲止，這將是瓶頸。 – Martin 2010-01-10 15:32:08

我不記得了，但我想我假設所有方法在性能上漸近地相等，但是根據用例的不同，平均值（O（1））的性能可能不同。 – Martin 2014-02-03 14:14:41

嗯，這是一個簡單的勝利SortedList。插入一個項目需要一個二進制搜索（O（log（n））來查找插入點，然後用List.Insert（O（n））來插入該項目。Insert（）占主導地位，填充列表需要O（n^2）。如果輸入項目已經被排序，那麼插入會崩潰到O（1），但不會影響搜索。現在填充是O（nlog（n））。你不用擔心哦，首先進行排序總是更高效，假設你可以負擔兩倍的存儲需求

SortedDictionary是不同的，它使用紅黑樹，查找插入點需要O（log（n））。（nlog（n））。使用排序後的輸入不會改變尋找插入點或重新平衡的努力，它仍然是O（nlog（n））。 n））現在哦，雖然，插入排序的輸入需要樹到consta nt重新平衡本身。如果輸入是隨機的，你不需要排序輸入，它會更好。

因此，使用排序後的輸入填充SortedList並使用未排序的輸入填充SortedDictionary同時都是O（nlog（n））。忽略提供排序輸入的成本，SortedList的Oh小於SortedDictionary的Oh。由於List分配內存的方式，這是一個實現細節。它只需要做O（log（n））次，紅黑樹必須分配O（n）次。很小哦，順便說一句。

值得注意的是，沒有一個人比單純填充List，然後調用Sort（）更有利。這也是O（nlog（n））。事實上，如果輸入已經意外排序，您可以繞過Sort（）調用，這會崩潰到O（n）。成本分析現在需要轉移到將輸入分類的努力。很難繞過Sort（），O（nlog（n））的基本複雜性。它可能不容易看到，你可能會得到按SQL查詢排序的輸入。這將需要更長的時間才能完成。

使用SortedList或SortedDictonary的要點是保持集合在插入後排序。如果你只擔心填充而不是突變，那麼你不應該使用這些集合。

來源

2010-01-10 15:10:26

旁註：如果數據可以使用非比較方法（如基數排序）進行排序，則排序可以是僞線性的（取決於與輸入相比「基數」的長度）摺疊爲O（n）時間即使對未排序的輸入進行排序，在這種情況下，創建列表並使用Sort（）可能會更快。 – apokryfos 2012-03-23 11:04:35

真的很有幫助的答案，謝謝！ – namford 2015-05-09 15:40:07

SortedList與SortedDictionary與Sort（）

回答

相關問題