通过V8源码看一个关于JS数组排序的诡异问题
前言
前几天一个朋友在微信里面问我一个关于JS数组排序的问题。通过该问题发现了一些之前没发现的内容,下面话不多少了,来一起看看详细的介绍吧。
原始数组如下:
vardata=[ {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节写道:
Callingcomparefn(a,b)alwaysreturnsthesamevaluevwhengivenaspecificpairofvaluesaandbasitstwoarguments.Furthermore,Type(v)isNumber,andvisnotNaN.Notethatthisimpliesthatexactlyoneofabwillbetrueforagivenpairofaandb.
简单翻译一下就是:第二个参数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)return0; if(%_IsSmi(x)&&%_IsSmi(y)){ return%SmiLexicographicCompare(x,y); } x=TO_STRING(x);//<-----坑 y=TO_STRING(y);//<-----坑 if(x==y)return0; elsereturnx然后定义了一个插入排序算法:
functionInsertionSort(a,from,to){ for(vari=from+1;i=from;j--){ vartmp=a[j]; varorder=comparefn(tmp,element); if(order>0){//<----注意这里 a[j+1]=tmp; }else{ break; } } a[j+1]=element; } 为什么是插入排序?V8为了性能考虑,当数组元素个数少于10个时,使用插入排序;大于10个时使用快速排序。
后面还定义了快速排序函数和其它几个函数,我就不一一列出了。
函数都定义完成后,开始正式的排序操作:
//%RemoveArrayHolesreturns-1iffastremovalisnotsupported. varnum_non_undefined=%RemoveArrayHoles(array,length); if(num_non_undefined==-1){ //Therewereindexedaccessorsinthearray. //MovearrayholesandundefinedstotheendusingaJavascriptfunction //thatissafeinthepresenceofaccessors. num_non_undefined=SafeRemoveArrayHoles(array); }中间的注释:MovearrayholesandundefinedstotheendusingaJavascriptfunction。排序之前会把数组里面的undefined移动到最后。因此第二个排序算法会把undefined移动到最后,然后对剩余的数据[4,2,1,7,4]进行排序。
而在第一种写法时,数组的每一项都是一个Object,然后最Object调用x.value-y.value进行计算,当undefined参与运算时比较的结果是NaN。
当返回NaN时V8怎么处理的呢?我前面标注过,再贴一次:
varorder=comparefn(tmp,element); if(order>0){//<----这里 a[j+1]=tmp; }else{ break; }NaN>0为false,执行了else分支代码。
思考题,以下代码的结果:
[1,23,2,3].sort()总结
以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作能带来一定的帮助,如果有疑问大家可以留言交流,谢谢大家对毛票票的支持。