国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

從 V8 源碼看 JS 數(shù)組排序的詭異問題

MkkHou / 2027人閱讀

摘要：前幾天一個(gè)朋友在微信里面問我一個(gè)關(guān)于數(shù)組排序的問題。對(duì)數(shù)組的進(jìn)行排序，然后把排完序的數(shù)組進(jìn)行處理。翻譯成編程術(shù)語(yǔ)就是排序算法是不穩(wěn)定排序。因此第二個(gè)排序算法會(huì)把移動(dòng)到最后，然后對(duì)剩余的數(shù)據(jù)進(jìn)行排序。

前幾天一個(gè)朋友在微信里面問我一個(gè)關(guān)于 JS 數(shù)組排序的問題。

原始數(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]

顯然這沒有達(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]

遇到這種情況第一感覺肯定是要去看看 ECMA 規(guī)范，萬(wàn)一是 JS 引擎的 bug 呢。

在 ES6 規(guī)范 22.1.3.24 節(jié)寫道：

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)說，這段代碼是有 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í)我們最疑惑的問題上，上面兩行代碼為什么會(huì)輸出不同的結(jié)果。我們只能通過查看 V8 源碼去找答案了。

V8 對(duì)數(shù)組排序是這樣進(jìn)行的：

如果沒有定義 comparefn 參數(shù)，則生成一個(gè)（高能預(yù)警，有坑啊）：

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ù)都定義完成后，開始正式的排序操作：

// %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。排序之前會(huì)把數(shù)組里面的 undefined 移動(dòng)到最后。因此第二個(gè)排序算法會(huì)把 undefined 移動(dòng)到最后，然后對(duì)剩余的數(shù)據(jù) [4,2,1,7,4] 進(jìn)行排序。

而在第一種寫法時(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)注過，再貼一次：

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()

掃碼二維碼關(guān)注我的公眾號(hào)

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/87238.html

相關(guān)文章

  • 2017-08-13 前端日?qǐng)?bào)

    摘要：前端日?qǐng)?bào)精選從源碼看數(shù)組排序的詭異問題顯示網(wǎng)格和隱式網(wǎng)格的區(qū)別打包工具完全入門指南使用之前要在里學(xué)的件事工作機(jī)制第部分中文深入理解中的代碼片段，你能猜對(duì)幾個(gè)掘金深入理解筆記中的類深入理解筆記迭代器和生成器最新版構(gòu)建分享小王子 2017-08-13 前端日?qǐng)?bào) 精選 從 V8 源碼看 JS 數(shù)組排序的詭異問題顯示網(wǎng)格和隱式網(wǎng)格的區(qū)別JS打包工具rollup——完全入門指南使用 Redux ...

    Eastboat 評(píng)論0 收藏0

  • JavaScript專題之解讀 v8 排序源碼

    摘要：插入排序是穩(wěn)定的算法。所以準(zhǔn)確的說，當(dāng)數(shù)組長(zhǎng)度大于的時(shí)候，采用了快速排序和插入排序的混合排序方法。在對(duì)數(shù)組進(jìn)行了一次快速排序后，然后對(duì)兩個(gè)子集分別進(jìn)行了插入排序，最終修改數(shù)組為正確排序后的數(shù)組。 JavaScript 專題系列第二十篇，也是最后一篇，解讀 v8 排序源碼 前言 v8 是 Chrome 的 JavaScript 引擎，其中關(guān)于數(shù)組的排序完全采用了 JavaScript 實(shí)...

    princekin 評(píng)論0 收藏0

  • JavaScript專題之亂序

    摘要：源碼地址為了簡(jiǎn)化篇幅，我們對(duì)這個(gè)數(shù)組進(jìn)行分析，數(shù)組長(zhǎng)度為，此時(shí)采用的是插入排序。插入排序的源碼是其原理在于將第一個(gè)元素視為有序序列，遍歷數(shù)組，將之后的元素依次插入這個(gè)構(gòu)建的有序序列中。 JavaScript 專題系列第十九篇，講解數(shù)組亂序，重點(diǎn)探究 Math.random() 為什么不能真正的亂序？ 亂序 亂序的意思就是將數(shù)組打亂。 嗯，沒有了，直接看代碼吧。 Math.random ...

    I_Am 評(píng)論0 收藏0

  • JavaScript專題系列20篇正式完結(jié)！

    摘要：寫在前面專題系列是我寫的第二個(gè)系列，第一個(gè)系列是深入系列。專題系列自月日發(fā)布第一篇文章，到月日發(fā)布最后一篇，感謝各位朋友的收藏點(diǎn)贊，鼓勵(lì)指正。 寫在前面 JavaScript 專題系列是我寫的第二個(gè)系列，第一個(gè)系列是 JavaScript 深入系列。 JavaScript 專題系列共計(jì) 20 篇，主要研究日常開發(fā)中一些功能點(diǎn)的實(shí)現(xiàn)，比如防抖、節(jié)流、去重、類型判斷、拷貝、最值、扁平、柯里...

    sixleaves 評(píng)論0 收藏0

  • 控制臺(tái)詭異錄之展開與縮略不同

    摘要：?jiǎn)栴}復(fù)現(xiàn)最近朋友發(fā)給我這樣的一個(gè)串代碼朋友說，這個(gè)輸出不正確。我表示不信，就試了下從結(jié)果看，沒毛病啊。朋友說，你展開看看，一看果然有問題縮略狀態(tài)的顯示與展開的顯示不同問題思考這個(gè)問題的表現(xiàn)是縮略狀態(tài)下顯示原數(shù)組，展開狀態(tài)下顯示排序后的數(shù)組。 問題復(fù)現(xiàn) 最近朋友發(fā)給我這樣的一個(gè)串代碼： var arr = [1, 4, 2, 3 ]; console.log(arr); arr.sort...

    opengps 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<