Scala Collection排序,sortWith和sortBy性能

发布时间：2020-12-16 09:20:24 所属栏目：安全来源：网络整理

导读：Scala在标准库中包含几个方法来排序列表,例如排序列表列表,可以使用： list.sortedlist.sortWith(__)list.sortBy(x=x) 虽然这些可能是排序列表的最简单方法,但我发现对于较大的列表,它们具有显着的性能缺陷. 例如,要排序一百万个整数,排序平均为500ms,而sort

Scala在标准库中包含几个方法来排序列表,例如排序列表列表,可以使用：

list.sorted
list.sortWith(_<_)
list.sortBy(x=>x)

虽然这些可能是排序列表的最简单方法,但我发现对于较大的列表,它们具有显着的性能缺陷.

例如,要排序一百万个整数,排序平均为500ms,而sortWith和sortBy大约需要700ms.这与scala.util.Sorting.quickSort进行比较,它大约需要120ms,而java.util.Arrays.sort大约需要100ms.对于较大的列表,当我们进一步扩大时,观察到这个多因素差异.模式如下图所示.

这种表现滞后的原因是什么？为什么标准方法中使用的算法/实现不是更有效？

解决方法

请注意线条的斜率是否相同,但彼此偏移？使用对数刻度,我们正在看一个恒定因子的差异.排序和朋友支付将列表转换为数组的成本,排序(实际上为java.util.Arrays.sort),并转换回列表. scala.util.Sorting.quickSort和java.util.Arrays.sort直接对数组进行操作.在快速排序的n log n性能中的log n因子在很大程度上是无关紧要的,所以在创建Array所需的线性时间和结果列表中,我们得到一个常数因子差.五倍的性能可能看起来很糟糕,但是记住List有一个每个元素的cons单元格,这使得在创建Array时大量的随机访问,然后创建新的List需要花费分配内存的时间,一个垃圾回收周期或两个.

对于原始列表,更糟糕的是.列表是通用的,所以任何原语都必须被包装,这增加了另一个间接层.不幸的是,创建的数组也包含boxed值.实际上,当您确实要排序Array [Int]时,最终排序Array [java.lang.Integer].

总结一下：排序算法是一样的,但是为什么可变阵列优于不可变的单链表有很好的理由.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!