通過(guò)V8源碼看一個(gè)關(guān)于JS數(shù)組排序的詭異問(wèn)題
前言
前幾天一個(gè)朋友在微信里面問(wèn)我一個(gè)關(guān)于 JS 數(shù)組排序的問(wèn)題。通過(guò)該問(wèn)題發(fā)現(xiàn)了一些之前沒(méi)發(fā)現(xiàn)的內(nèi)容,下面話不多少了,來(lái)一起看看詳細(xì)的介紹吧。
原始數(shù)組如下:
var data = [ {value: 4}, {value: 2}, {value: undefined}, {value: undefined}, {value: 1}, {value: undefined}, {value: undefined}, {value: 7}, {value: undefined}, {value: 4} ];
data 是個(gè)數(shù)組,數(shù)組的每一項(xiàng)都是一個(gè)擁有 value 作為 key 的對(duì)象,值為數(shù)字或者 undefined。
data .sort((x, y) => x.value - y.value) .map(x => x.value);
對(duì)數(shù)組的 value 進(jìn)行排序,然后把排完序的數(shù)組進(jìn)行 flat 處理。得到的結(jié)果如下:
[2, 4, undefined, undefined, 1, undefined, undefined, 7, undefined, 4]
顯然這沒(méi)有達(dá)到我們的目的。
現(xiàn)在我們修改一下排序,挑戰(zhàn)一下函數(shù)的調(diào)用順序:先對(duì)數(shù)組進(jìn)行扁平化(flat)處理,然后再排序。
data .map(x => x.value) .sort((x, y) => x - y)
這時(shí)我們得到的結(jié)果和之前截然不同:
[1, 2, 4, 4, 7, undefined, undefined, undefined, undefined, undefined]
遇到這種情況第一感覺(jué)肯定是要去看看 ECMA 規(guī)范,萬(wàn)一是 JS 引擎的 bug 呢。
在 ES6 規(guī)范 22.1.3.24 節(jié)寫(xiě)道:
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.
簡(jiǎn)單翻譯一下就是:第二個(gè)參數(shù) comparefn 返回一個(gè)數(shù)字,并且不是 NaN。一個(gè)注意事項(xiàng)是,對(duì)于參與比較的兩個(gè)數(shù) a 小于 b、a 等于 b、a 大于 b 這三種情況必須有一個(gè)為 true。
所以嚴(yán)格意義上來(lái)說(shuō),這段代碼是有 bug 的,因?yàn)楸容^的結(jié)果出現(xiàn)了 NaN。
在 MDN 文檔上還有一個(gè)細(xì)節(jié):
如果 comparefn(a, b) 等于 0, a 和 b 的相對(duì)位置不變。備注:ECMAScript 標(biāo)準(zhǔn)并不保證這一行為,而且也不是所有瀏覽器都會(huì)遵守。
翻譯成編程術(shù)語(yǔ)就是:sort 排序算法是不穩(wěn)定排序。
其實(shí)我們最疑惑的問(wèn)題上,上面兩行代碼為什么會(huì)輸出不同的結(jié)果。我們只能通過(guò)查看 V8 源碼去找答案了。
V8 對(duì)數(shù)組排序是這樣進(jìn)行的:
如果沒(méi)有定義 comparefn 參數(shù),則生成一個(gè)(高能預(yù)警,有坑?。?/p>
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; };
然后定義了一個(gè)插入排序算法:
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 為了性能考慮,當(dāng)數(shù)組元素個(gè)數(shù)少于 10 個(gè)時(shí),使用插入排序;大于 10 個(gè)時(shí)使用快速排序。
后面還定義了快速排序函數(shù)和其它幾個(gè)函數(shù),我就不一一列出了。
函數(shù)都定義完成后,開(kāi)始正式的排序操作:
// %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); }
中間的注釋?zhuān)篗ove array holes and undefineds to the end using a Javascript function。排序之前會(huì)把數(shù)組里面的 undefined 移動(dòng)到最后。因此第二個(gè)排序算法會(huì)把 undefined 移動(dòng)到最后,然后對(duì)剩余的數(shù)據(jù) [4,2,1,7,4] 進(jìn)行排序。
而在第一種寫(xiě)法時(shí),數(shù)組的每一項(xiàng)都是一個(gè) Object,然后最 Object 調(diào)用 x.value - y.value 進(jìn)行計(jì)算,當(dāng) undefined 參與運(yùn)算時(shí)比較的結(jié)果是 NaN。
當(dāng)返回 NaN 時(shí) V8 怎么處理的呢?我前面標(biāo)注過(guò),再貼一次:
var order = comparefn(tmp, element); if (order > 0) { // <---- 這里 a[j + 1] = tmp; } else { break; }
NaN > 0 為 false,執(zhí)行了 else 分支代碼。
思考題,以下代碼的結(jié)果:
[1, 23, 2, 3].sort()
總結(jié)
以上就是這篇文章的全部?jī)?nèi)容了,希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作能帶來(lái)一定的幫助,如果有疑問(wèn)大家可以留言交流,謝謝大家對(duì)腳本之家的支持。
相關(guān)文章
JS根據(jù)key值獲取URL中的參數(shù)值及把URL的參數(shù)轉(zhuǎn)換成json對(duì)象
本篇文章主要圍繞js url 參數(shù)值展開(kāi)話題,js根據(jù)key值獲取url中的參數(shù)值,接著把url的參數(shù)轉(zhuǎn)換成json,感興趣的朋友一起來(lái)學(xué)習(xí)吧,本文寫(xiě)的不好地方還望多多指出批評(píng)建議2015-08-08詳談構(gòu)造函數(shù)加括號(hào)與不加括號(hào)的區(qū)別
下面小編就為大家?guī)?lái)一篇詳談構(gòu)造函數(shù)加括號(hào)與不加括號(hào)的區(qū)別。小編覺(jué)得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-10-10JS跳出循環(huán)的5種方法總結(jié)(return、break、continue、throw等)
想必大家都遇到過(guò)循環(huán)遍歷時(shí)遇到滿足條件的時(shí)候就跳出循環(huán)這樣的需求,于是整理了一篇各種循環(huán)是如何結(jié)束的,這篇文章主要給大家介紹了關(guān)于JS跳出循環(huán)的5種方法,分別是return、break、continue、throw等的相關(guān)資料,需要的朋友可以參考下2024-05-05js form表單input框限制20個(gè)字符,10個(gè)漢字代碼實(shí)例
這篇文章主要介紹了js form表單input框限制20個(gè)字符,10個(gè)漢字,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-04-04javascript圖片延遲加載實(shí)現(xiàn)方法及思路
這篇文章主要介紹了javascript圖片延遲加載實(shí)現(xiàn)方法及思路,有時(shí)我們需要用懶加載,也就是延遲加載圖片的方式,來(lái)提高網(wǎng)站的親和力,需要的朋友可以參考下2015-12-12用webpack4開(kāi)發(fā)小程序的實(shí)現(xiàn)方法
這篇文章主要介紹了用webpack4開(kāi)發(fā)小程序的實(shí)現(xiàn)方法,分享通過(guò)webpack來(lái)構(gòu)建小程序的開(kāi)發(fā)架構(gòu),感興趣的小伙伴們可以參考一下2019-06-06利用Javascript仿Excel的數(shù)據(jù)透視分析功能
這篇文章給大家介紹了如何利用Javascript實(shí)現(xiàn)類(lèi)似Excel的數(shù)據(jù)透視分析功能,感興趣的朋友們可以參考借鑒,下面來(lái)一起看看吧。2016-09-09JavaScript實(shí)現(xiàn)多態(tài)和繼承的封裝操作示例
這篇文章主要介紹了JavaScript實(shí)現(xiàn)多態(tài)和繼承的封裝操作,結(jié)合實(shí)例形式分析了javascript中多態(tài)與繼承的實(shí)現(xiàn)及封裝相關(guān)操作技巧,需要的朋友可以參考下2018-08-08