Mar*_*tin 22 .net sorting performance sortedlist sorteddictionary
这是像这样的问题的延续.
是否有任何调整性能的指导原则？我并不是指大O的收益,只是节省一些线性时间.
例如,要花多少钱预分类保存在任SortedList或SortedDictionary？
假设我有一个有3个属性的人类排序,其中一个是年龄.我应该先按年龄换取物品吗？
我应该首先对一个属性进行排序,然后使用结果列表/字典对两个属性进行排序,依此类推？
想到的任何其他优化？
Han*_*ant 57
好吧,它在SortedList上轻松获胜.插入项目需要二进制搜索(O(log(n))来查找插入点,然后使用List.Insert(O(n))来插入项目.Insert()占主导地位,填充列表需要O(n ^ 2).如果输入项已经排序,那么Insert会折叠到O(1)但不会影响搜索.填充现在是O(nlog(n)).你不用担心哦有多大,首先排序总是更有效率.假设您可以承受双倍的存储需求.
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的目的是在插入后对集合进行排序.如果您只担心填充但不变异,那么您不应该使用这些集合.