c# - 适用于需要快速检索的排序数据的集合类

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 都是可行的选择。哪一个最好取决于您将获得的插入/查找/枚举的比例。

例如，如果您对每个枚举进行 10 亿次查找，那么使用 Dictionary 可能会有返回。相反，如果枚举发生得更频繁，最终排序数组可能会更好，因为首先必须对 Dictionary 中的数据进行排序，而像 QuickSort 这样的算法可以在 O(n * log n ) 时间。

我建议您在您的应用程序的典型使用场景中尝试这两种方法，看看哪一种最好。

或者，如果内存不是问题，为什么不使用 Dictionary 和排序数组？如果处理得当，您可以两全其美。