前端 Array.sort() 源碼學習_ZenDei技術網路在線

源碼地址 V8源碼Array 710行開始為sort()相關 Array.sort()方法是那種排序呢？去看源碼主要是源於這個問題 // In-place QuickSort algorithm. // For short (length <= 22) arrays, insertion sort ...

源碼地址

V8源碼Array
710行開始為sort()相關

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

去看源碼主要是源於這個問題

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

源碼中的第一句話就回答了我的問題

// 通常使用快速排序演算法
// 如果數組長度小於23，則插入排序效率更好

既然都打開了，索性就看看源碼叭，看看sort到底做了些啥
我把一整坨源碼碼分成一塊一塊來看，讓自己比較清晰的知道sort到底幹了些啥，下麵是閱讀代碼時，自己的思路梳理

第一塊代碼

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

第一塊內容判斷，如果傳進來的參數不可回調，則給一個預設的回調函數
這個回調函數，判斷倆值是不是Smi

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

如果是則進行小整數字典序比較
什麼是字典序

否則將兩個值轉換成字元串進行字元串比較大小
字元串如何比較大小

第二塊代碼

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

這塊代碼裡面的註釋，講的還是比較詳細的，百度翻譯也非常nice

// 為了與JSC相容，我們還在非數組對象上對從原型鏈繼承的元素進行排序。
// 我們通過將它們複製到這個對象並只對自己的元素排序來實現這一點。
// 這不是很有效，但是使用繼承的元素進行排序的情況很少發生，如果有的話。
// 如果原型鏈上的元素具有可能與排序交互的元素，則規範允許“依賴於實現”的行為。

第四塊代碼

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

這塊代碼是對於非數組的一個處理
註釋裡面說到

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

返回的max會在下麵用到

第五塊代碼

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相容
// 我們對原型鏈中通過sort將一個hole移動到其位置而暴露的所有元素
// 進行shadow處理。

可能因為英語語法水平不夠，單看註釋還有點不明白
大致意思是，把“掀開的東西，再蓋上”
直接看下麵一塊代碼，看看這個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原型包含元素的所有索引上設置一個“undefined”值。
// 換句話說
// 在該範圍內對所有原型元素進行shadow處理。

其中：
I.e.是拉丁文id est 的縮寫，它的意思就是“那就是說，換句話說”
英文不夠你用了是不你還要寫拉丁文？！

果然大致的意思猜的沒錯
在剛剛把對象的原型屬性的複製，現在要設置undefined來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);
}

意思是數組中有索引訪問器。使用JS函數將數組hole和未定義項移到末尾，該函數在訪問器存在時是安全的。
下麵是安全移出數組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;
};

還會判斷數組長度

if (length < 2) return array;