SortedList与SortedDictionary与Sort（）

这是类似this one这样的问题的延续。SortedList与SortedDictionary与Sort（）

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

例如，预分类保存在SortedList或SortedDictionary上的保存数量是多少？

假设我有一个具有3个属性的人类排序，其中一个是年龄。我应该首先年龄对象的对象？

我应该先对一个属性进行排序，然后使用生成的列表/字典对两个属性进行排序，依此类推？

任何其他优化想到？

来源

2010-01-10 Martin

您是否尝试过分析代码以确保初始化已排序的数据结构实际上是代码中的瓶颈？ – 2010-01-10 11:56:03

到目前为止，这是一个假设性的问题，但是，是的，到目前为止，这将是瓶颈。 – Martin 2010-01-10 15:32:08

我不记得了，但我想我假设所有方法在性能上渐近地相等，但是根据用例的不同，平均值（O（1））的性能可能不同。 – Martin 2014-02-03 14:14:41

嗯，这是一个简单的胜利SortedList。插入一个项目需要一个二进制搜索（O（log（n））来查找插入点，然后用List.Insert（O（n））来插入该项目。Insert（）占主导地位，填充列表需要O（n^2）。如果输入项目已经被排序，那么插入会崩溃到O（1），但不会影响搜索。现在填充是O（nlog（n））。你不用担心哦，首先进行排序总是更高效，假设你可以负担两倍的存储需求

SortedDictionary是不同的，它使用红黑树，查找插入点需要O（log（n））。（nlog（n））。使用排序后的输入不会改变寻找插入点或重新平衡的努力，它仍然是O（nlog（n））。 n））现在哦，虽然，插入排序的输入需要树到consta nt重新平衡本身。如果输入是随机的，你不需要排序输入，它会更好。

因此，使用排序后的输入填充SortedList并使用未排序的输入填充SortedDictionary同时都是O（nlog（n））。忽略提供排序输入的成本，SortedList的Oh小于SortedDictionary的Oh。由于List分配内存的方式，这是一个实现细节。它只需要做O（log（n））次，红黑树必须分配O（n）次。很小哦，顺便说一句。

值得注意的是，没有一个人比单纯填充List，然后调用Sort（）更有利。这也是O（nlog（n））。事实上，如果输入已经意外排序，您可以绕过Sort（）调用，这会崩溃到O（n）。成本分析现在需要转移到将输入分类的努力。很难绕过Sort（），O（nlog（n））的基本复杂性。它可能不容易看到，你可能会得到按SQL查询排序的输入。这将需要更长的时间才能完成。

使用SortedList或SortedDictonary的要点是保持集合在插入后排序。如果你只担心填充而不是突变，那么你不应该使用这些集合。

来源

2010-01-10 15:10:26

旁注：如果数据可以使用非比较方法（如基数排序）进行排序，则排序可以是伪线性的（取决于与输入相比“基数”的长度）折叠为O（n）时间即使对未排序的输入进行排序，在这种情况下，创建列表并使用Sort（）可能会更快。 – apokryfos 2012-03-23 11:04:35

真的很有帮助的答案，谢谢！ – namford 2015-05-09 15:40:07

SortedList与SortedDictionary与Sort（）

回答

相关问题