.net - SortedList vs. SortedDictionary vs. Sort()

Question

这是类似问题的延续。

是否有任何调整性能的指导方针？我不是说大 O 的收益，只是节省一些线性时间。

例如，预分类在SortedList或上节省了多少SortedDictionary？

假设我有一个人类，有 3 个属性要排序，其中一个是年龄。我应该先按年龄存储对象吗？

我是否应该首先对一个属性进行排序，然后使用生成的列表/字典对两个属性进行排序等等？

想到其他优化吗？

Answer 1

好吧，这在 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 的目的是在插入后保持集合排序。如果您只担心填充而不是变异，那么您不应该使用这些集合。