gpt4 book ai didi

.net - SortedList 与 SortedDictionary 与 Sort()

转载 作者:行者123 更新时间:2023-12-03 11:32:33 26 4
gpt4 key购买 nike

这是 this one 等问题的延续.

是否有任何调整性能的指南?我不是说大 O 的 yield ,只是节省一些线性时间。

例如,预排序为 SortedList 节省了多少或 SortedDictionary ?

假设我有一个有 3 个属性要排序的人员类,其中一个是年龄。我应该先按年龄分桶吗?

我应该首先对一个属性进行排序,然后使用结果列表/字典对两个属性进行排序等等吗?

想到的任何其他优化?

最佳答案

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

关于.net - SortedList 与 SortedDictionary 与 Sort(),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2036890/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com