SortedList、SortedDictionary和Sort()的比较

Question

这是类似于此问题的延续。

有没有调整性能的指南？我不是指在大O方面的收益，只是节省一些线性时间。

例如，在SortedList或SortedDictionary上预先排序可以节省多少时间？

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

我应该先按照一个属性进行排序，然后使用结果列表/字典对两个属性进行排序，依此类推吗？

还有其他优化方法吗？

- Martin

---

你尝试过对你的代码进行性能分析，以确保初始化你的排序数据结构实际上是你代码中的瓶颈吗？ - Mark Byers

到目前为止，这只是一个假设性的问题，但是是的，这将是迄今为止最大的瓶颈。 - Martin

我记不清了，但我想我当时假设所有方法在性能上渐近相等，但可能根据使用情况在平均（O(1)）性能上有所不同。 - Martin

你链接的问题中有文档部分，阐明了预排序的效果。 - nawfal

Answer 1

嗯，使用 SortedList 很容易获取胜利。插入项需要进行二分查找（O(log(n))）以找到插入点，然后进行 List.Insert (O(n)) 插入项。Insert() 是主要瓶颈，填充列表需要 O(n^2) 的时间复杂度。如果输入项已经排序，则 Insert 坍塌为 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) 次分配。顺便提一下，Oh 非常小。

值得注意的是，与仅填充 List，然后调用 Sort() 相比，两者都没有优势。这也是 O(nlog(n))。如果输入已经意外排序，则可以跳过 Sort() 调用，这将坍塌为 O(n)。现在成本分析需要转向获取输入排序所需的工作量。很难跳过 Sort() 的基本复杂度，即 O(nlog(n))。这可能不容易看到，你可能会通过 SQL 查询之类的方式来获取已排序的输入。但这会导致更长的完成时间。

使用SortedList或SortedDictionary的目的是在插入后保持集合排序。如果只关心填充而不是更改，则不应使用这些集合。

- Hans Passant

---

附注：如果数据可以使用非比较方法（如基数排序）进行排序，则排序可以是伪线性的，这取决于“基数”的长度与输入相比。即使对于未排序的输入，排序时间也会折叠到O(n)。在这种情况下，制作一个列表并使用Sort()可能会更快。 - apokryfos

“使用SortedDictionary的目的是在插入后保持集合排序。”这是正确的。然而，我遇到了另一种特殊情况，即SortedDictionary >> 'create List + .Sort()'：我不得不使用一个临时的排序数据结构来对大量数据进行验证。逐个节点构建的SortedDictionary在每次插入时执行验证。因此，它可以在分配更少的内存的同时快速失败。列表将在调用sort()之前分配整个数组，因此会稍微紧张一些内存（如果内存充足，则当然更好）。 - XDS