通过V8源码看一个关于JS数组排序的诡异问题
前言
前几天一个朋友在微信里面问我一个关于 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()
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作能带来一定的帮助，如果有疑问大家可以留言交流，谢谢大家对我们的支持。
相关推荐
-
Javascript数组的排序 sort()方法和reverse()方法
其中: 1.JavaScript的sort()中如果没有指定比较函数,则默认会按照字符的编码顺序进行升序排序.也就是说如果我们想要对数值进行排序得到的不一定是我们想要的结果. 2.Javascript的reverse()将数组中的元素逆序. 先看看上面的第一点,如果有一个数组arr=[1,6,3,7,9],使用arr.sort()后,数组的顺序为1,3,6,7,9,得到了我们想要的结果. 再看看下面的一个数组排序:arr=[3,1,16,34,30],如果执行arr.sort()后是不是还是会得
-
js对象数组按属性快速排序
按所推荐的程序在IE下跑了下,的确,排序耗时很小. 复制代码 代码如下: <script> /* * 洗牌 */ function getRandomPlayCard(m){ var array1=new Array(m); for(var i=0;i<m;i++){ var rnd=Math.floor(Math.random()*(i+0.99999)) array1[i]=array1[rnd]; array1[rnd]=i; } return array1; }; /* * 快速
-
js中数组(Array)的排序(sort)注意事项说明
直接看代码吧,测试结果也贴在里面了 复制代码 代码如下: var arrDemo = new Array(); arrDemo[0] = 10; arrDemo[1] = 50; arrDemo[2] = 51; arrDemo[3] = 100; arrDemo.sort(); //调用sort方法后,数组本身会被改变,即影响原数组 alert(arrDemo);//10,100,50,51 默认情况下sort方法是按ascii字母顺序排序的,而非我们认为是按数字大小排序 arrDemo.so
-
js算法中的排序、数组去重详细概述
其实在js中实现数组排序,采用数组中sort方法实现还是比较简单的: 一.排序 简单实现数组排序 复制代码 代码如下: var arr = []; for(var i=0;i<20;i++){ arr.push(Math.floor(Math.random()*100)) } arr.sort(function(a,b){ return a>b?1:-1; }) alert(arr) 不能简单使用sort方法,默认情况下 sort方法是按ascii字母顺序排序的,
-
Js数组排序函数sort()介绍
JavaScript实现多维数组.对象数组排序,其实用的就是原生的sort()方法,用于对数组的元素进行排序. sort() 方法用于对数组的元素进行排序.语法如下: arrayObject.sort(sortby) 返回值为对数组的引用.请注意,数组在原数组上进行排序,不生成副本. 如果调用该方法时没有使用参数,将按字母顺序对数组中的元素进行排序,说得更精确点,是按照字符编码的顺序进行排序.要实现这一点,首先应把数组的元素都转换成字符串(如有必要),以便进行比较. 如果想按照其他标准进行排序,
-
js对数组中的数字从小到大排序实现代码
例子 1 In this example we will create an array and sort it alphabetically: var arr = new Array(6) arr[0] = "Jani" arr[1] = "Hege" arr[2] = "Stale" arr[3] = "Kai Jim" arr[4] = "Borge" arr[5] = "Tove"
-
js中数组排序sort方法的原理分析
本文实例分析了js中数组排序sort方法的原理.分享给大家供大家参考.具体分析如下: 最近在百度的项目中要用到对数组进行排序,当然一开始自然想到了数组的sort方法,这方法应用非常简单,大致如下: 复制代码 代码如下: window.onload=function(){ var arr=[2,55,55,1,75,3,9,35,70,166,432,678,32,98]; var arr2=["George","John","
-
js sort 二维数组排序的用法小结
最近在搞js 排序的问题,因为数据库排序太耗资源,如果能转移到客户端去排序,能大大D减少服务器内存消耗.客户端的话,除了js,就是as了,可惜我as学得太烂,所以只能选择js来研究研究了...经过我的测试,js内置方法sort的效率非常高 我们知道在js中默认提供了sort函数,但是这个函数默认是按照数组内容的ascii码升序进行排列的,如果我们要对二维数组排序要如何做呢?在php中是有multi_sort函数可供调用的,但是在js中似乎没有这种函数,但是没关系 ,因为js的sort函数其实也提
-
通过V8源码看一个关于JS数组排序的诡异问题
前言 前几天一个朋友在微信里面问我一个关于 JS 数组排序的问题.通过该问题发现了一些之前没发现的内容,下面话不多少了,来一起看看详细的介绍吧. 原始数组如下: var data = [ {value: 4}, {value: 2}, {value: undefined}, {value: undefined}, {value: 1}, {value: undefined}, {value: undefined}, {value: 7}, {value: undefined}, {value:
-
解析从小程序开发者工具源码看原理实现
如何查看小程序开发者工具源码 下面我们通过微信小程序开发者工具的源码来说说小程序的底层实现原理.以开发者工具版本号State v1.02.1904090的源码来窥探小程序的实现思路.如何查看微信源码,对于mac用户而言,查看微信小程序开发者工具的包内容,然后进入Contents/Resources/app.nw/js/core/index.js,注释掉如下代码就可以查看开发者工具渲染后的代码. // 打开 inspect 窗口 if (nw.App.argv.indexOf('inspect')
-
从Linux源码看Socket(TCP)Client端的Connect的示例详解
前言 笔者一直觉得如果能知道从应用到框架再到操作系统的每一处代码,是一件Exciting的事情. 今天笔者就来从Linux源码的角度看下Client端的Socket在进行Connect的时候到底做了哪些事情.由于篇幅原因,关于Server端的Accept源码讲解留给下一篇博客. (基于Linux 3.10内核) 一个最简单的Connect例子 int clientSocket; if((clientSocket = socket(AF_INET, SOCK_STREAM, 0)) < 0) {
-
分析从Linux源码看TIME_WAIT的持续时间
目录 一.前言 二.首先介绍下Linux环境 三.TIME_WAIT状态转移图 四.持续时间真如TCP_TIMEWAIT_LEN所定义么? 五.TIME_WAIT定时器源码 5.1.inet_twsk_schedule 5.2.具体的清理函数 5.3.先作出一个假设 5.4.如果一个slot中的TIME_WAIT<=100 5.5.如果一个slot中的TIME_WAIT>100 5.6.PAWS(Protection Against Wrapped Sequences)使得TIME_WAIT延
-
详解从Linux源码看Socket(TCP)的bind
目录 一.一个最简单的Server端例子 二.bind系统调用 2.1.inet_bind 2.2.inet_csk_get_port 三.判断端口号是否冲突 四.SO_REUSEADDR和SO_REUSEPORT 五.SO_REUSEADDR 六.SO_REUSEPORT 七.总结 一.一个最简单的Server端例子 众所周知,一个Server端Socket的建立,需要socket.bind.listen.accept四个步骤. 代码如下: void start_server(){ // se
-
Java从源码看异步任务计算FutureTask
目录 了解一下什么是FutureTask? FutureTask 是如何实现的呢? FutureTask 运行流程 FutureTask 的使用 前言: 大家是否熟悉FutureTask呢?或者说你有没有异步计算的需求呢?FutureTask就能够很好的帮助你实现异步计算,并且可以实现同步获取异步任务的计算结果.下面我们就一起从源码分析一下FutureTask. 了解一下什么是FutureTask? FutureTask 是一个可取消的异步计算. FutureTask提供了对Future的基本实
-
详解从Vue.js源码看异步更新DOM策略及nextTick
写在前面 因为对Vue.js很感兴趣,而且平时工作的技术栈也是Vue.js,这几个月花了些时间研究学习了一下Vue.js源码,并做了总结与输出. 文章的原地址:https://github.com/answershuto/learnVue. 在学习过程中,为Vue加上了中文的注释https://github.com/answershuto/learnVue/tree/master/vue-src,希望可以对其他想学习Vue源码的小伙伴有所帮助. 可能会有理解存在偏差的地方,欢迎提issue指出,
-
从源码看angular/material2 中 dialog模块的实现方法
本文将探讨material2中popup弹窗即其Dialog模块的实现. 使用方法 引入弹窗模块 自己准备作为模板的弹窗内容组件 在需要使用的组件内注入 MatDialog 服务 调用 open 方法创建弹窗,并支持传入配置.数据,以及对关闭事件的订阅 深入源码 进入material2的源码,先从 MatDialog 的代码入手,找到这个 open 方法: open<T>( componentOrTemplateRef: ComponentType<T> | TemplateRef
-
浅析从vue源码看观察者模式
观察者模式 首先话题下来,我们得反问一下自己,什么是观察者模式? 概念 观察者模式(Observer):通常又被称作为发布-订阅者模式.它定义了一种一对多的依赖关系,即当一个对象的状态发生改变的时候,所有依赖于它的对象都会得到通知并自动更新,解决了主体对象与观察者之间功能的耦合. 讲个故事 上面对于观察者模式的概念可能会比较官方化,所以我们讲个故事来理解它. A:是共产党派往国民党密探,代号 001(发布者) B:是共产党的通信人员,负责与 A 进行秘密交接(订阅者) A 日常工作就是在明面采集
-
从vue源码看props的用法
前言 平时写vue的时候知道 props 有很多种用法,今天我们来看看vue内部是怎么处理 props 中那么多的用法的. vue提供的props的用法 1. 数组形式 props: ['name', 'value'] 2. 对象形式 对象形式内部也提供了三种写法: props: { // 基础的类型检查 name: String, // 多个可能的类型 value: [String, Number], // 对象形式 id: { type: Number, required: true } }