合適的集合類排序的數據需要快速檢索

Question

我在一個場景，我需要存儲的KeyValuePair收集工作，有DateTimeOffset關鍵。 我正在接收這個數據的列表（通過Http請求），我只需要讀取並從中生成集合。要求集合保持排序，並且它必須是可枚舉的。另外，我可能需要通過密鑰對這些數據進行大量的查找。

另請注意，我收到的數據本身已經排序。我可以定期重複接收數據並再次生成收集的操作。但是，現有集合未被修改，而是每次刷新數據時都會創建一個新集合。

現在，我心裏有以下方法：

1. 使用SortedDictionary<,>（我現在的方法）。
2. 使用Dictionary<,>，在填充接收到的數據中的所有項目後手動對其進行排序。 （雖然這使得它非常快速查找（O（1）），我現在需要對數據進行排序，因爲在一個有序的方式加入，當Dictionary<,>不維護的項目。）
3. 使用一個簡單的數組（或List），它直接從數據填充。元素的順序是隱含的。然後，使用鍵上的二進制搜索來完成搜索項目（即查找）。

哪一種方法是適合這種情況？我可以使用上述方法還有其他選擇或變體，這會給我更好的整體性能嗎？

編輯

對不起，我忘了提，我對WinRT的（特別是Windows phone）系統平臺的開發。因此，我不能使用SortedList<,>（也不是OrderedDictionary），這是@lc指出的最佳選擇。

此外，我的收藏將只有幾百個項目。也許在這個規模上可能沒有任何顯着差異，但我想知道一個答案都是一樣的。

Answer 1

在三個選項中，我肯定會排除1（SortedDictionary），因爲3（數組或List）根據您的要求（快速查找，排序，項目按順序提供，未修改）優於它。

做一個排序後的數組上二進制搜索運行在O（LG n）的時間。根據documentation，SortedDictionary中的查找也在O（lg n）時間內運行，因此在使用它時沒有優勢。

因爲你得到的數據已經排序，則數組在O（n）的填充。插入SortedDictionary在O（lg n）中運行，因此填充它在O（n * lg n）中運行，這更糟糕。

枚舉運行在兩個O（n）時間。

要回答你的問題，我覺得2和3都是可行的選擇。哪一個最好取決於你將得到的插入/查找/枚舉的比例。例如，如果您每次枚舉執行十億次查找，那麼使用Dictionary可能會收回成本。如果枚舉更頻繁發生，最後排序的數組可能會更好，因爲Dictionary中的數據首先必須進行排序，像QuickSort這樣的算法可以在O（n * log n）時間內執行此操作。

我建議你在一個典型的使用場景中爲你的應用程序嘗試，看看哪一個是最好的。

或者，如果內存不是問題，爲什麼不使用Dictionary和排序的數組？如果這樣做是正確的，你可以得到兩全其美的好處。