您好,登录后才能下订单哦!
算法对于前端工程师来说总有一层神秘色彩,这篇文章通过解读V8源码,带你探索Array.prototype.sort
函数下的算法实现。
<!-- more -->
来,先把你用过的和听说过的排序算法都列出来:
答题环节到了, sort 函数使用的以上哪一种算法?
如果你在网上搜索过关于 sort 源码的文章,可能会告诉你数组长度小于10用插入排序,否则用快速排序。
开始我也是这么认为的,可当我带着答案去 GitHub 验证的时候发现并非如此。
首先我并没有找到对应的 js 源码(文章说实现逻辑是用js写的),因为但新版本的V8源码已经修改,改用V8 Torque
。V8 Torque
是专门用来开发V8而创造的语言,语法类似TypeScript(再一次证明TypeScript的价值),它的编译器使用CodeStubAssembler
转换成高效的汇编代码。
简单理解起来就是创造了一个类似TypeScript的高效的高级语言,这个语言的文件后缀是tq
。
这里需要感谢 justjavac 大神指点~
其次当我开始阅读源码的时候,并没有找到使用快速排序的代码,也没有找到判断数组长度的常数值10。
所有的证据表明,之前的源码解读文章很可能已经过时。
那么最新版本的 V8 用的是什么排序算法呢?
V8引擎在xx版本之后就舍弃了快速排序,因为它不是稳定的排序算法,在最坏情况下,时间复杂度会降级到O(n^2)。
而是采用了一种混合排序的算法:TimSort。
这种功能算法最初用于Python语言中,严格地说它t不属于以上10种排序算法中的任何一种,属于一种混合排序算法:
在数据量小的子数组中使用插入排序,然后再使用归并排序将有序的子数组进行合并排序,时间复杂度为 O(nlogn) 。
结合V8源码,具体实现步骤如下:
/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可别怪作者~
参考:
一部由众多技术专家推荐,帮你成为具有全面能力和全局视野工程师的进阶利器——《了不起的JavaScript工程师》已经在京东、当当、淘宝各大平台上架了~
点击下方链接即刻踏上属于你的进阶之路吧!
https://u.jd.com/nETVMh
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。