算法对于前端工程师来说总有一层神秘色彩, 这篇文章通过解读 V8 源码, 带你探索 Array.prototype.sort 函数下的算法实现.
来, 先把你用过的和听说过的排序算法都列出来:
快速排序
冒泡排序
插入排序
归并排序
堆排序
希尔排序
选择排序
计数排序
桶排序
基数排序
答题环节到了, sort 函数使用的以上哪一种算法?
如果你在网上搜索过关于 sort 源码的文章, 可能会告诉你数组长度小于 10 用插入排序, 否则用快速排序.
开始我也是这么认为的, 可当我带着答案去 GitHub 验证的时候发现并非如此.
首先我并没有找到对应的 JS 源码 (文章说实现逻辑是用 JS 写的), 因为但新版本的 V8 源码已经修改, 改用 V8 Torque . V8 Torque 是专门用来开发 V8 而创造的语言, 语法类似 TypeScript(再一次证明 TypeScript 的价值), 它的编译器使用 CodeStubAssembler 转换成高效的汇编代码.
简单理解起来就是创造了一个类似 TypeScript 的高效的高级语言, 这个语言的文件后缀是 tq .
这里需要感谢 https://justjavac.com/about.html 大神指点~
其次当我开始阅读源码的时候, 并没有找到使用快速排序的代码, 也没有找到判断数组长度的常数值 10.
所有的证据表明, 之前的源码解读文章很可能已经过时.
那么最新版本的 V8 用的是什么排序算法呢?
算法解读
V8 引擎在 xx 版本之后就舍弃了快速排序, 因为它不是稳定的排序算法, 在最坏情况下, 时间复杂度会降级到 O(n^2).
而是采用了一种混合排序的算法: TimSort.
这种功能算法最初用于 Python 语言中, 严格地说它 t 不属于以上 10 种排序算法中的任何一种, 属于一种混合排序算法:
在数据量小的子数组中使用 插入排序 , 然后再使用 归并排序 将有序的子数组进行合并排序, 时间复杂度为 O(nlogn) .
结合 V8 源码, 具体实现步骤如下:
判断数组长度, 小于 2 直接返回, 不排序.
开始循环.
找出一个有序子数组, 我们称之为 "run", 长度为 currentRunLength .
计算最小合并序列长度 minRunLength (这个值会根据数组长度动态变化, 在 32~64 之间).
比较 currentRunLength 和 minRunLength , 如果 currentRunLength>= minRunLength , 否则采用插入排序补足数组长度至 minRunLength , 将 run 压入栈 pendingRuns 中.
每次有新的 run 被压入 pendingRuns 时保证栈内任意 3 个连续的 run(run0, run1, run2) 从下至上满足 run0>run1+run2 && run1>run2 , 不满足的话进行调整直至满足.
如果剩余子数组为 0, 结束循环.
合并栈中所有 run, 排序结束.
源码解读
源码路径
/thrid_party/v8/builtins/array-sort.tq
调用栈
- 1386 ArrayPrototypeSort
- 1403 ArrayTimSort
- 1369 ArrayTimSortImpl
- 1260 ComputeMinRunLength // 计算 minRunLength
- // while 循环
- 1262 CountAndMakeRun // 计算当前 run 的长度
- 1267 BinaryInsertionSort // 用插入排序补足 run 长度
- 1274 MergeCollapse // 放入 pendingRuns 并根据需要进行调整
- // 循环结束
- 1281 MergeForceCollapse // 合并 pendingRuns 中所有 run
核心源码
tq 语言虽然有些不一样, 但如果有 TypeScript 基础的话阅读起来应该不成问题.
下面重点解读 3 个函数的源码:
- // 在 while 循环之前调用, 每次排序只调用一次, 用来计算 minRunLength
- macro ComputeMinRunLength(nArg: Smi): Smi {
- let n: Smi = nArg;
- let r: Smi = 0;
- assert(n>= 0);
- // 不断除以 2, 得到结果在 32~64 之间
- while (n>= 64) {
- r = r | (n & 1);
- n = n>> 1;
- }
- const minRunLength: Smi = n + r;
- assert(nArg <64 || (32 <= minRunLength && minRunLength <= 64));
- return minRunLength;
- }
- // 计算第一个 run 的长度
- macro CountAndMakeRun(implicit context: Context, sortState: SortState)(
- lowArg: Smi, high: Smi): Smi {
- assert(lowArg < high);
- // 这里保存的才是我们传入的数组数据
- const workArray = sortState.workArray;
- const low: Smi = lowArg + 1;
- if (low == high) return 1;
- let runLength: Smi = 2;
- const elementLow = UnsafeCast<JSAny>(workArray.objects[low]);
- const elementLowPred = UnsafeCast<JSAny>(workArray.objects[low - 1]);
- // 调用比对函数来比对数据
- let order = sortState.Compare(elementLow, elementLowPred);
- const isDescending: bool = order <0 ? true : false;
- let previousElement: JSAny = elementLow;
- // 遍历子数组并计算 run 的长度
- for (let idx: Smi = low + 1; idx < high; ++idx) {
- const currentElement = UnsafeCast<JSAny>(workArray.objects[idx]);
- order = sortState.Compare(currentElement, previousElement);
- if (isDescending) {
- if (order>= 0) break;
- } else {
- if (order <0) break;
- }
- previousElement = currentElement;
- ++runLength;
- }
- if (isDescending) {
- ReverseRange(workArray, lowArg, lowArg + runLength);
- }
- return runLength;
- }
- // 调整 pendingRuns , 使栈长度大于 3 时, 所有 run 都满足 run[n]>run[n+1]+run[n+2] 且 run[n+1]>run2[n+2]
- transitioning macro MergeCollapse(context: Context, sortState: SortState) {
- const pendingRuns: FixedArray = sortState.pendingRuns;
- while (GetPendingRunsSize(sortState)> 1) {
- let n: Smi = GetPendingRunsSize(sortState) - 2;
- if (!RunInvariantEstablished(pendingRuns, n + 1) ||
- !RunInvariantEstablished(pendingRuns, n)) {
- if (GetPendingRunLength(pendingRuns, n - 1) <
- GetPendingRunLength(pendingRuns, n + 1)) {
- --n;
- }
- MergeAt(n); // 将第 n 个 run 和第 n+1 个 run 进行合并
- } else if (
- GetPendingRunLength(pendingRuns, n) <=
- GetPendingRunLength(pendingRuns, n + 1)) {
- MergeAt(n); // 将第 n 个 run 和第 n+1 个 run 进行合并
- } else {
- break;
- }
- }
- }
总结
下次面试前端岗位的时候, 如果面试官问你算法题, 你可以莞尔一笑地问他 / 她:
知道 Array 的 sort 函数使用了什么算法吗? TimSort 要不要了解一下?
当然如果因此搞得面试官难堪而导致拿不到 offer 可别怪作者~
参考:
V8 源码 https://github.com/v8/v8
《V8 引擎中的排序》 https://juejin.im/post/5c472940e51d455249762bef
《男科一梦 (再续一集)-TimSort 的实现》
一部由众多技术专家推荐, 帮你成为具有全面能力和全局视野工程师的进阶利器 -- 《了不起的 JavaScript 工程师》 https://item.jd.com/12562349.html?dist=jd 出版了! 点击下方链接即刻踏上进阶之路!
淘宝: https://detail.tmall.com/item.htm?id=600756390664
京东: https://item.jd.com/12562349.html?dist=jd
当当: http://product.dangdang.com/27922044.html
来源: http://www.tuicool.com/articles/VzEZFrz