您的位置:首頁(yè) > 軟件教程 > 教程 > 深入解讀V8源碼中的Array.sort()方法

深入解讀V8源碼中的Array.sort()方法

來(lái)源:好特整理 | 時(shí)間:2024-06-28 08:46:45 | 閱讀:86 |  標簽: T v S AR   | 分享到:

源碼地址 V8源碼Array 710行開(kāi)始為sort()相關(guān) Array.sort()方法是那種排序呢? 去看源碼主要是源于這個(gè)問(wèn)題 // In-place QuickSort algorithm. // For short (length <= 22) arrays, insertion s

在V8引擎的源碼中,Array.sort()方法是一個(gè)非常重要的排序方法。如果我們想深入了解這個(gè)方法的具體實(shí)現,就需要去查看V8引擎的源碼。下面將對V8源碼中的Array.sort()方法進(jìn)行詳細的解讀。

源碼地址

V8源碼Array
710行開(kāi)始為sort()相關(guān)

Array.sort()方法是那種排序呢?

去看源碼主要是源于這個(gè)問(wèn)題

// In-place QuickSort algorithm.
// For short (length <= 22) arrays, insertion sort is used for efficiency.

源碼中的第一句話(huà)就回答了我的問(wèn)題

// 通常使用快速排序算法
// 如果數組長(cháng)度小于23,則插入排序效率更好

既然都打開(kāi)了,索性就看看源碼叭,看看sort到底做了些啥
我把一整坨源碼碼分成一塊一塊來(lái)看,讓自己比較清晰的知道sort到底干了些啥,下面是閱讀代碼時(shí),自己的思路梳理

第一塊代碼

if (!IS_CALLABLE(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;
  };
}

第一塊內容判斷,如果傳進(jìn)來(lái)的參數不可回調,則給一個(gè)默認的回調函數
這個(gè)回調函數,判斷倆值是不是 Smi

// Smi:小整數(Small integers)V8引擎中的元素類(lèi)型之一
`https://medium.com/@justjavac/v8-internals-how-small-is-a-small-integer-ba5e17a3ae5f`
// PS: markdown語(yǔ)法有問(wèn)題,這里直接貼出 url

如果是則進(jìn)行小整數字典序比較
什么是字典序

否則將兩個(gè)值轉換成字符串進(jìn)行字符串比較大小
字符串如何比較大小

第二塊代碼

var InsertionSort = function InsertionSort(a, from, to) {
  ...
};
var QuickSort = function QuickSort(a, from, to) {
  if (to - from <= 10) {
    InsertionSort(a, from, to);
    return;
  }
  ...
};

第二塊就是正常的快速排序和插入排序
這里采取的是數量小于10的數組使用 InsertionSort(插入),比10大的數組則使用 QuickSort(快速)。

第三塊代碼

if (!is_array) {
  // For compatibility with JSC, we also sort elements inherited from
  // the prototype chain on non-Array objects.
  // We do this by copying them to this object and sorting only
  // own elements. This is not very efficient, but sorting with
  // inherited elements happens very, very rarely, if at all.
  // The specification allows "implementation dependent" behavior
  // if an element on the prototype chain has an element that
  // might interact with sorting.
  max_prototype_element = CopyFromPrototype(array, length);
}

這塊代碼里面的注釋?zhuān)v的還是比較詳細的,百度翻譯也非常nice

// 為了與JSC兼容,我們還在非數組對象上對從原型鏈繼承的元素進(jìn)行排序。
// 我們通過(guò)將它們復制到這個(gè)對象并只對自己的元素排序來(lái)實(shí)現這一點(diǎn)。
// 這不是很有效,但是使用繼承的元素進(jìn)行排序的情況很少發(fā)生,如果有的話(huà)。
// 如果原型鏈上的元素具有可能與排序交互的元素,則規范允許“依賴(lài)于實(shí)現”的行為。

第四塊代碼

// Copy elements in the range 0..length from obj's prototype chain
// to obj itself, if obj has holes. Return one more than the maximal index
// of a prototype property.
var CopyFromPrototype = function CopyFromPrototype(obj, length) {
  var max = 0;
  for (var proto = %object_get_prototype_of(obj); 
        proto;
        proto = %object_get_prototype_of(proto)) {
        var indices = IS_PROXY(proto) ? length : %GetArrayKeys(proto, length);
        if (IS_NUMBER(indices)) {
            // It's an interval.
            var proto_length = indices;
            for (var i = 0; i < proto_length; i++) {
                if (!HAS_OWN_PROPERTY(obj, i) && HAS_OWN_PROPERTY(proto, i)) {
                obj[i] = proto[i];
                if (i >= max) { max = i + 1; }
            }
        }
        } 
        else {
            for (var i = 0; i < indices.length; i++) {
                var index = indices[i];
                if (!HAS_OWN_PROPERTY(obj, index) && HAS_OWN_PROPERTY(proto, index)) {
                    obj[index] = proto[index];
                    if (index >= max) { max = index + 1; }
                }
            }
        }
    }
    return max;
};

這塊代碼是對于非數組的一個(gè)處理
注釋里面說(shuō)到

// 如果obj有holes(能猜出大概意思,不咋好翻譯這個(gè)hole)
// 就把obj原型鏈上0-length所有元素賦值給obj本身
// 返回一個(gè)max,max是比原型屬性索引最大值+1

返回的max會(huì )在下面用到

第五塊代碼

if (!is_array && (num_non_undefined + 1 < max_prototype_element)) {
  // For compatibility with JSC, we shadow any elements in the prototype
  // chain that has become exposed by sort moving a hole to its position.
  ShadowPrototypeElements(array, num_non_undefined, max_prototype_element);
}

注釋翻譯:

// 為了與JSC兼容
// 我們對原型鏈中通過(guò)sort將一個(gè)hole移動(dòng)到其位置而暴露的所有元素
// 進(jìn)行shadow處理。

可能因為英語(yǔ)語(yǔ)法水平不夠,單看注釋還有點(diǎn)不明白
大致意思是,把“掀開(kāi)的東西,再蓋上”
直接看下面一塊代碼,看看這個(gè)shadow操作到底干了啥叭

第六塊代碼

// Set a value of "undefined" on all indices in the range from..to
// where a prototype of obj has an element. I.e., shadow all prototype
// elements in that range.
var ShadowPrototypeElements = function(obj, from, to) {
  for (var proto = %object_get_prototype_of(obj); proto;
        proto = %object_get_prototype_of(proto)) {
        var indices = IS_PROXY(proto) ? to : %GetArrayKeys(proto, to);
        if (IS_NUMBER(indices)) {
          // It's an interval.
          var proto_length = indices;
          for (var i = from; i < proto_length; i++) {
            if (HAS_OWN_PROPERTY(proto, i)) {
              obj[i] = UNDEFINED;
            }
          }
        } 
        else {
            for (var i = 0; i < indices.length; i++) {
                var index = indices[i];
                if (from <= index && HAS_OWN_PROPERTY(proto, index)) {
                    obj[index] = UNDEFINED;
                }
            }
        }
    }
};

這塊代碼就是shadow操作,注釋翻譯如下:

// 在范圍從..到obj原型包含元素的所有索引上設置一個(gè)“undefined”值。
// 換句話(huà)說(shuō)
// 在該范圍內對所有原型元素進(jìn)行shadow處理。

其中:
I.e.是拉丁文id est 的縮寫(xiě),它的意思就是“那就是說(shuō),換句話(huà)說(shuō)”
英文不夠你用了是不你還要寫(xiě)拉丁文?!

果然大致的意思猜的沒(méi)錯
在剛剛把對象的原型屬性的復制,現在要設置undefined來(lái)shadow他了

第七塊代碼

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);
}

意思是 數組中有索引訪(fǎng)問(wèn)器。使用JS函數將數組hole和未定義項移到末尾,該函數在訪(fǎng)問(wèn)器存在時(shí)是安全的。
下面是安全移出數組hole方法

var SafeRemoveArrayHoles = function SafeRemoveArrayHoles(obj) {
  // Copy defined elements from the end to fill in all holes and undefineds
  // in the beginning of the array.  Write undefineds and holes at the end
  // after loop is finished.
    var first_undefined = 0;
    var last_defined = length - 1;
    var num_holes = 0;
    while (first_undefined < last_defined) {
        // Find first undefined element.
        while (first_undefined < last_defined &&
            !IS_UNDEFINED(obj[first_undefined])) {
            first_undefined++;
        }
        // Maintain the invariant num_holes = the number of holes in the original
        // array with indices <= first_undefined or > last_defined.
        if (!HAS_OWN_PROPERTY(obj, first_undefined)) {
          num_holes++;
        }
        // Find last defined element.
        while (first_undefined < last_defined &&
            IS_UNDEFINED(obj[last_defined])) {
            if (!HAS_OWN_PROPERTY(obj, last_defined)) {
                num_holes++;
            }
            last_defined--;
        }
        if (first_undefined < last_defined) {
            // Fill in hole or undefined.
            obj[first_undefined] = obj[last_defined];
            obj[last_defined] = UNDEFINED;
        }
    }
    // If there were any undefineds in the entire array, first_undefined
    // points to one past the last defined element.  Make this true if
    // there were no undefineds, as well, so that first_undefined == number
    // of defined elements.
    if (!IS_UNDEFINED(obj[first_undefined])) first_undefined++;
    // Fill in the undefineds and the holes.  There may be a hole where
    // an undefined should be and vice versa.
    var i;
    for (i = first_undefined; i < length - num_holes; i++) {
        obj[i] = UNDEFINED;
    }
    for (i = length - num_holes; i < length; i++) {
        // For compatability with Webkit, do not expose elements in the prototype.
        if (i in %object_get_prototype_of(obj)) {
            obj[i] = UNDEFINED;
        } else {
            delete obj[i];
        }
    }
    // Return the number of defined elements.
    return first_undefined;
};

還會(huì )判斷數組長(cháng)度

if (length < 2) return array;
小編推薦閱讀

好特網(wǎng)發(fā)布此文僅為傳遞信息,不代表好特網(wǎng)認同期限觀(guān)點(diǎn)或證實(shí)其描述。

相關(guān)視頻攻略

更多

掃二維碼進(jìn)入好特網(wǎng)手機版本!

掃二維碼進(jìn)入好特網(wǎng)微信公眾號!

本站所有軟件,都由網(wǎng)友上傳,如有侵犯你的版權,請發(fā)郵件admin@haote.com

湘ICP備2022002427號-10 湘公網(wǎng)安備:43070202000427號© 2013~2024 haote.com 好特網(wǎng)