这是类似问题的延续this one https://stackoverflow.com/questions/935621/whats-the-difference-between-sortedlist-and-sorteddictionary/935631#935631.
是否有调整性能的指导方针?我并不是指大 O 的增益,只是节省一些线性时间。
例如,预分类可以节省多少费用?SortedList
or 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))。现在,哦很重要,插入排序的输入需要树不断地重新平衡自身。如果输入是随机的,那么效果会更好,您不需要排序的输入。
因此,用排序的输入填充 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 的目的是在插入后保持集合排序。如果您只担心填充而不担心变异,那么您不应该使用这些集合。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)