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

Question

输入的顺序是否可能影响 Array.sort() 的性能？如果是，怎么办？

Answer 1

这取决于几件事:

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

我正在处理的一个应用程序在一个模块中遇到了严重的性能下降，该模块正在对 35K+ 字符串的列表进行排序，在它访问的 API 端点开始按排序顺序向其提供数据后。前端排序花费的时间从大约 30 毫秒减少到 6 秒 (200x)。

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

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

[the worst case] may occur if the pivot happens to be the smallest or largest element in the list, or in some implementations (e.g., the Lomuto partition scheme as described above) when all the elements are equal.

我变得很好奇，并对进行排序的多种变体进行了基准测试。我在命令行中使用了在节点上运行的 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，但问题没有重现。我认为这是因为使用了不同的排序算法。