SortedList vs. SortedDictionary vs. Sort()
這是類似問題的延續。
是否有任何調整性能的指導方針？我不是說大 O 的收益，只是節省一些線性時間。
例如，預分類在
SortedList或上節省了多少SortedDictionary？假設我有一個人類，有 3 個屬性要排序，其中一個是年齡。我應該先按年齡儲存對象嗎？
我是否應該首先對一個屬性進行排序，然後使用生成的列表/字典對兩個屬性進行排序等等？
想到其他優化嗎？
好吧，這在 SortedList 上很容易獲勝。插入一項需要二分查找 (O(log(n)) 來找到插入點，然後是 List.Insert (O(n)) 來插入該項。Insert() 占主導地位，填充列表需要 O(n ^2)。如果輸入項已經排序，則插入折疊到 O(1) 但不影響搜尋。填充現在是 O(nlog(n))。你不用擔心 Oh 有多大，首先排序總是更有效。假設你能承受雙倍的儲存需求。
SortedDictionary 不同，它使用紅黑樹。找到插入點需要 O(log(n))。之後可能需要重新平衡樹，這也需要 O(log(n))。因此，填充字典需要 O(nlog(n))。使用排序輸入不會改變尋找插入點或重新平衡的努力，它仍然是 O(nlog(n))。現在 Oh 很重要，插入排序的輸入需要樹不斷地重新平衡自身。如果輸入是隨機的，它會更好地工作，你不想要排序的輸入。
所以用排序的輸入填充 SortedList 和用未排序的輸入填充 SortedDictionary 都是 O(nlog(n))。忽略提供排序輸入的成本，SortedList 的 Oh 小於 SortedDictionary 的 Oh。由於 List 分配記憶體的方式，這是一個實現細節。它只需要這樣做 O(log(n)) 次，紅黑樹必須分配 O(n) 次。非常小哦順便說一句。
值得注意的是，沒有一個比簡單地填充一個列表，然後呼叫 Sort() 更好。這也是 O(nlog(n))。事實上，如果輸入已經被意外排序，您可以繞過 Sort() 呼叫，這將折疊為 O(n)。成本分析現在需要轉移到對輸入進行排序所需的工作上。很難繞過 Sort() 的基本複雜性，O(nlog(n))。它可能不容易看到，您可能會得到按 SQL 查詢排序的輸入。只是需要更長的時間才能完成。
使用 SortedList 或 SortedDictonary 的目的是在插入後保持集合排序。如果您只擔心填充而不是變異，那麼您不應該使用這些集合。