前端 Array.sort() 源碼學習

来源:https://www.cnblogs.com/xw-01/p/18266079
-Advertisement-
Play Games

源碼地址 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;

您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • ‍ 寫在開頭 點贊 + 收藏 學會 場景是用戶通過微信掃app內的收款碼,跳到一個h5頁面。然後完成支付。 代碼實現的整體流程: 使用微信掃碼,碼是app內生成的,碼的內容是一個h5頁面鏈接,掃碼完成後跳轉到自定義的h5支付界面。 掃碼進入後,將頁面展示所需要的參數進行緩存起來, ...
  • 摘要:本文詳細介紹了Nuxt3中的六個核心生命周期鉤子及其用法,包括build:done、build:manifest、builder:generateApp、builder:watch、pages:extend和server:devHandler:handler。內容涵蓋各鉤子的調用時機、參數、環... ...
  • 一.定時器 1. JS存在兩種定時器 setTimeout() 延遲定時器 setInterval() 迴圈定時器(“間隔器”) 定時器中的函數掛載在window對象,內部的this ——> window setTimerout(function(){ console.log('wuwei') }, ...
  • ‍ 寫在開頭 點贊 + 收藏 學會 近期產品期望在後臺發佈帖子或視頻時,需要添加 @用戶 的功能,以便用戶收到通知,例如“xxx在xxx提及了您!”。然而,現有的開源庫未能滿足我們的需求,例如 ant-design 的 Mentions 組件: 但是不難發現跟微信飛書對比下,有兩 ...
  • 前言 petite-vue 是為漸進增強而優化的另一種 Vue 發行版。它提供與標準 Vue 相同的模板語法和反應性心智模型。 不過,它專門針對在由伺服器框架呈現的現有 HTML 頁面上“散佈”少量交互進行了優化。 petite-vue,它在提供 vue 基本功能的同時,還能一個輕量級,簡單應用的微 ...
  • 概述了Nuxt3的六個關鍵生命周期鉤子用途:modules:before至build:before,指導如何在應用初始化、模塊管理、配置解析、模板處理及構建前執行自定義操作,附帶實例代碼,強化Nuxt應用的靈活性和可控性。 ...
  • 我們是袋鼠雲數棧 UED 團隊,致力於打造優秀的一站式數據中台產品。我們始終保持工匠精神,探索前端道路,為社區積累並傳播經驗價值。 本文作者:霽明 背景 我們產品中會有一些流程圖應用,例如審批中心的審批流程圖: 我們數棧產品內的流程圖,基本都是使用的 mxGraph 實現的,mxGraph 使用了S ...
  • Vue3發佈後,各家第三方庫開始陸續重構並支持 Vue3 ,國內兩大知名框架 Element Plus 和 Ant Design Vue 也相續發佈新版支持 Vue3。Element Plus 和 Ant Design Vue 都是基於 Vue.js 的 UI 組件庫,它們具備一系列可復用的組件和豐... ...
一周排行
    -Advertisement-
    Play Games
  • 通過WPF的按鈕、文本輸入框實現了一個簡單的SpinBox數字輸入用戶組件並可以通過數據綁定數值和步長。本文中介紹了通過Xaml代碼實現自定義組件的佈局,依賴屬性的定義和使用等知識點。 ...
  • 以前,我看到一個朋友在對一個系統做初始化的時候,通過一組魔幻般的按鍵,調出來一個隱藏的系統設置界面,這個界面在常規的菜單或者工具欄是看不到的,因為它是一個後臺設置的關鍵界面,不公開,同時避免常規用戶的誤操作,它是作為一個超級管理員的入口功能,這個是很不錯的思路。其實Winform做這樣的處理也是很容... ...
  • 一:背景 1. 講故事 前些天有位朋友找到我,說他的程式每次關閉時就會自動崩潰,一直找不到原因讓我幫忙看一下怎麼回事,這位朋友應該是第二次找我了,分析了下 dump 還是挺經典的,拿出來給大家分享一下吧。 二:WinDbg 分析 1. 為什麼會崩潰 找崩潰原因比較簡單,用 !analyze -v 命 ...
  • 在一些報表模塊中,需要我們根據用戶操作的名稱,來動態根據人員姓名,更新報表的簽名圖片,也就是電子手寫簽名效果,本篇隨筆介紹一下使用FastReport報表動態更新人員簽名圖片。 ...
  • 最新內容優先發佈於個人博客:小虎技術分享站,隨後逐步搬運到博客園。 創作不易,如果覺得有用請在Github上為博主點亮一顆小星星吧! 博主開始學習編程於11年前,年少時還只會使用cin 和cout ,給單片機點點燈。那時候,類似async/await 和future/promise 模型的認知還不是 ...
  • 之前在阿裡雲ECS 99元/年的活動實例上搭建了一個測試用的MINIO服務,以前都是直接當基礎設施來使用的,這次準備自己學一下S3相容API相關的對象存儲開發,因此有了這個小工具。目前僅包含上傳功能,後續計劃開發一個類似圖床的對象存儲應用。 ...
  • 目錄簡介快速入門安裝 NuGet 包實體類User資料庫類DbFactory增刪改查InsertSelectUpdateDelete總結 簡介 NPoco 是 PetaPoco 的一個分支,具有一些額外的功能,截至現在 github 星數 839。NPoco 中文資料沒多少,我是被博客園群友推薦的, ...
  • 前言 前面使用 Admin.Core 的代碼生成器生成了通用代碼生成器的基礎模塊 分組,模板,項目,項目模型,項目欄位的基礎功能,本篇繼續完善,實現最核心的模板生成功能,並提供生成預覽及代碼文件壓縮下載 準備 首先清楚幾個模塊的關係,如何使用,簡單畫一個流程圖 前面完成了基礎的模板組,模板管理,項目 ...
  • 假設需要實現一個圖標和文本結合的按鈕 ,普通做法是 直接重寫該按鈕的模板; 如果想作為通用的呢? 兩種做法: 附加屬性 自定義控制項 推薦使用附加屬性的形式 第一種:附加屬性 創建Button的附加屬性 ButtonExtensions 1 public static class ButtonExte ...
  • 在C#中,委托是一種引用類型的數據類型,允許我們封裝方法的引用。通過使用委托,我們可以將方法作為參數傳遞給其他方法,或者將多個方法組合在一起,從而實現更靈活的編程模式。委托類似於函數指針,但提供了類型安全和垃圾回收等現代語言特性。 基本概念 定義委托 定義委托需要指定它所代表的方法的原型,包括返回類 ...