Array.sort性能如何受输入初始排序的影响？

Question

输入的排序是否有可能影响性能Array.sort()？如果是这样,怎么样？

Answer 1

这取决于一些事情:

• 运行时(不同的浏览器/运行时使用不同的排序算法)
• 您的输入相对于所需顺序的排列方式
• 如果您使用的是自定义比较器(也与前一点有关)

我正在处理的一个应用程序在一个模块中经历了严重的性能下降,该模块在它开始的API端点之后对35K +字符串列表进行排序,并按排序顺序提供数据.前端排序所花费的时间从大约30毫秒增加到6 秒(200倍).

使用自定义比较器完成排序,该比较器优先使用以某个后缀结尾的字符串.如果没有或两个字符串以后缀结尾,则使用自然排序.我使用浏览器开发人员工具对模块进行了分析,发现大部分时间花在了这个比较上.该配置文件还显示,这QuickSort是Array.sort()(至少在Chrome中)使用的基础算法.

这很奇怪,因为QuickSort不应受输入顺序的影响.根据维基百科:

如果枢轴恰好是列表中的最小或最大元素,或者在所有元素相等的一些实现中(例如,如上所述的Lomuto分区方案),则可能发生[最坏情况].

我变得很好奇,并对这种排序的多种变体进行了基准测试.我在命令行中使用了在节点上运行的benchmark.js. 基准测试和浏览器都在v8之上运行,因此他们应该使用相同的排序算法.结果令人惊讶:

6 tests completed.

  Ordered array, sorted with a default comparator           x 34.27 ops/sec ±1.07% (59 runs sampled)
  Ordered array, sorted with a custom comparator            x  0.18 ops/sec ±2.81% (5 runs sampled)
  Ordered array, shuffled, sorted with a custom comparator  x 38.37 ops/sec ±3.67% (51 runs sampled)
  Ordered array, shuffled, sorted with a default comparator x 29.20 ops/sec ±1.28% (51 runs sampled)
  Unordered array, sorted with a default comparator         x 28.38 ops/sec ±1.28% (50 runs sampled)
  Unordered array, sorted with a custom comparator          x 42.10 ops/sec ±1.32% (55 runs sampled)

这些结果表明性能下降是由于数据与比较器的分布.以下是输入的一些特征:

• 比较器优先级(/Prod)的后缀匹配大约20%的字符串
• 当字符串按字母顺序排序时,结尾的字符串/Prod很可能在整个过程中相对均匀地传播
• 样序列ABC/Alpha,ABC/Beta,ABC/Prod是常见的.

这可能使算法更可能选择在其子序列中处于极端的枢轴,从而导致要执行的元素之间的大量比较.

这只发生在Chrome 61中.我测试了Firefox 52.3和Safari 10.1,但问题没有复制.我认为这是因为使用了不同的排序算法.