这篇文章主要介绍了如何通过V8源码看一个关于JS数组排序的诡异问题,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。
原始数组如下:
var data = [ {value: 4}, {value: 2}, {value: undefined}, {value: undefined}, {value: 1}, {value: undefined}, {value: undefined}, {value: 7}, {value: undefined}, {value: 4} ];
data 是个数组,数组的每一项都是一个拥有 value 作为 key 的对象,值为数字或者 undefined。
data .sort((x, y) => x.value - y.value) .map(x => x.value);
对数组的 value 进行排序,然后把排完序的数组进行 flat 处理。得到的结果如下:
[2, 4, undefined, undefined, 1, undefined, undefined, 7, undefined, 4]
显然这没有达到我们的目的。
现在我们修改一下排序,挑战一下函数的调用顺序:先对数组进行扁平化(flat)处理,然后再排序。
data .map(x => x.value) .sort((x, y) => x - y)
这时我们得到的结果和之前截然不同:
[1, 2, 4, 4, 7, undefined, undefined, undefined, undefined, undefined]
遇到这种情况第一感觉肯定是要去看看 ECMA 规范,万一是 JS 引擎的 bug 呢。
在 ES6 规范 22.1.3.24 节写道:
Calling comparefn(a,b) always returns the same value v when given a specific pair of values a and b as its two arguments. Furthermore, Type(v) is Number, and v is not NaN. Note that this implies that exactly one of a < b, a = b, and a > b will be true for a given pair of a and b.
简单翻译一下就是:第二个参数 comparefn 返回一个数字,并且不是 NaN。一个注意事项是,对于参与比较的两个数 a 小于 b、a 等于 b、a 大于 b 这三种情况必须有一个为 true。
所以严格意义上来说,这段代码是有 bug 的,因为比较的结果出现了 NaN。
在 MDN 文档上还有一个细节:
如果 comparefn(a, b) 等于 0, a 和 b 的相对位置不变。备注:ECMAScript 标准并不保证这一行为,而且也不是所有浏览器都会遵守。
翻译成编程术语就是:sort 排序算法是不稳定排序。
其实我们最疑惑的问题上,上面两行代码为什么会输出不同的结果。我们只能通过查看 V8 源码去找答案了。
V8 对数组排序是这样进行的:
如果没有定义 comparefn 参数,则生成一个(高能预警,有坑啊):
comparefn = function (x, y) { if (x === y) return 0; if (%_IsSmi(x) && %_IsSmi(y)) { return %SmiLexicographicCompare(x, y); } x = TO_STRING(x); // <----- 坑 y = TO_STRING(y); // <----- 坑 if (x == y) return 0; else return x < y ? -1 : 1; };
然后定义了一个插入排序算法:
function InsertionSort(a, from, to) { for (var i = from + 1; i < to; i++) { var element = a[i]; for (var j = i - 1; j >= from; j--) { var tmp = a[j]; var order = comparefn(tmp, element); if (order > 0) { // <---- 注意这里 a[j + 1] = tmp; } else { break; } } a[j + 1] = element; }
为什么是插入排序?V8 为了性能考虑,当数组元素个数少于 10 个时,使用插入排序;大于 10 个时使用快速排序。
后面还定义了快速排序函数和其它几个函数,我就不一一列出了。
函数都定义完成后,开始正式的排序操作:
// %RemoveArrayHoles returns -1 if fast removal is not supported. var num_non_undefined = %RemoveArrayHoles(array, length); if (num_non_undefined == -1) { // There were indexed accessors in the array. // Move array holes and undefineds to the end using a Javascript function // that is safe in the presence of accessors. num_non_undefined = SafeRemoveArrayHoles(array); }
中间的注释:Move array holes and undefineds to the end using a Javascript function。排序之前会把数组里面的 undefined 移动到最后。因此第二个排序算法会把 undefined 移动到最后,然后对剩余的数据 [4,2,1,7,4] 进行排序。
而在第一种写法时,数组的每一项都是一个 Object,然后最 Object 调用 x.value - y.value 进行计算,当 undefined 参与运算时比较的结果是 NaN。
当返回 NaN 时 V8 怎么处理的呢?我前面标注过,再贴一次:
var order = comparefn(tmp, element); if (order > 0) { // <---- 这里 a[j + 1] = tmp; } else { break; }
NaN > 0 为 false,执行了 else 分支代码。
思考题,以下代码的结果:
[1, 23, 2, 3].sort()
感谢你能够认真阅读完这篇文章,希望小编分享的“如何通过V8源码看一个关于JS数组排序的诡异问题”这篇文章对大家有帮助,同时也希望大家多多支持创新互联成都网站制作公司,关注创新互联成都网站制作公司行业资讯频道,更多相关知识等着你来学习!
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、网站制作公司香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
当前文章:如何通过V8源码看一个关于JS数组排序的诡异问题-创新互联
文章来源:https://www.cdcxhl.com/article28/dhpdcp.html
成都网站建设公司_创新互联,为您提供网页设计公司、网站维护、标签优化、建站公司、企业建站、虚拟主机
声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联