【轉】JavaScript 高性能數組去重

来源:https://www.cnblogs.com/PeunZhang/archive/2019/08/30/11436166.html
-Advertisement-
Play Games

原文地址:https://www.cnblogs.com/wisewrong/p/9642264.html 一、測試模版 數組去重是一個老生常談的問題,網上流傳著有各種各樣的解法 為了測試這些解法的性能,我寫了一個測試模版,用來計算數組去重的耗時 這裡分別創建了兩個長度為 10W 和 5W 的數組 ...


原文地址:https://www.cnblogs.com/wisewrong/p/9642264.html

 

一、測試模版

數組去重是一個老生常談的問題,網上流傳著有各種各樣的解法

為了測試這些解法的性能,我寫了一個測試模版,用來計算數組去重的耗時

複製代碼
// distinct.js

let arr1 = Array.from(new Array(100000), (x, index)=>{
    return index
})

let arr2 = Array.from(new Array(50000), (x, index)=>{
    return index+index
})

let start = new Date().getTime()
console.log('開始數組去重')

function distinct(a, b) {
    // 數組去重
}

console.log('去重後的長度', distinct(arr1, arr2).length)

let end = new Date().getTime()
console.log('耗時', end - start)
複製代碼

這裡分別創建了兩個長度為 10W 和 5W 的數組

然後通過 distinct() 方法合併兩個數組,並去掉其中的重覆項

數據量不大也不小,但已經能說明一些問題了

 

二、Array.filter() + indexOf

這個方法的思路是,將兩個數組拼接為一個數組,然後使用 ES6 中的 Array.filter() 遍曆數組,並結合 indexOf 來排除重覆項

function distinct(a, b) {
    let arr = a.concat(b);
    return arr.filter((item, index)=> {
        return arr.indexOf(item) === index
    })
}

這就是我被吐槽的那個數組去重方法,看起來非常簡潔,但實際性能。。。

是的,現實就是這麼殘酷,處理一個長度為 15W 的數組都需要 8427ms

 

三、雙重 for 迴圈

最容易理解的方法,外層迴圈遍歷元素,內層迴圈檢查是否重覆

當有重覆值的時候,可以使用 push(),也可以使用 splice()

複製代碼
function distinct(a, b) {
    let arr = a.concat(b);
    for (let i=0, len=arr.length; i<len; i++) {
        for (let j=i+1; j<len; j++) {
            if (arr[i] == arr[j]) {
                arr.splice(j, 1);
                // splice 會改變數組長度,所以要將數組長度 len 和下標 j 減一
                len--;
                j--;
            }
        }
    }
    return arr
}
複製代碼

但這種方法占用的記憶體較高,效率也是最低的

 

 

四、for...of + includes()

雙重for迴圈的升級版,外層用 for...of 語句替換 for 迴圈,把內層迴圈改為 includes()

先創建一個空數組,當 includes() 返回 false 的時候,就將該元素 push 到空數組中 

類似的,還可以用 indexOf() 來替代 includes()

複製代碼
function distinct(a, b) {
    let arr = a.concat(b)
    let result = []
    for (let i of arr) {
        !result.includes(i) && result.push(i)
    }
    return result
}
複製代碼

這種方法和 filter + indexOf 挺類似

只是把 filter() 的內部邏輯用 for 迴圈實現出來,再把 indexOf 換為 includes

所以時長上也比較接近

 

  

五、Array.sort()

首先使用 sort() 將數組進行排序

然後比較相鄰元素是否相等,從而排除重覆項

複製代碼
function distinct(a, b) {
    let arr = a.concat(b)
    arr = arr.sort()
    let result = [arr[0]]

    for (let i=1, len=arr.length; i<len; i++) {
        arr[i] !== arr[i-1] && result.push(arr[i])
    }
    return result
}
複製代碼

這種方法只做了一次排序和一次迴圈,所以效率會比上面的方法都要高

 

  

六、new Set()

ES6 新增了 Set 這一數據結構,類似於數組,但 Set 的成員具有唯一性

基於這一特性,就非常適合用來做數組去重了

function distinct(a, b) {
    return Array.from(new Set([...a, ...b]))
}

那使用 Set 又需要多久時間來處理 15W 的數據呢?

喵喵喵??? 57ms ??我沒眼花吧??

然後我在兩個數組長度後面分別加了一個0,在 150W 的數據量之下...

居然有如此高性能且簡潔的數組去重辦法?!

 

七、for...of + Object

這個方法我只在一些文章里見過,實際工作中倒沒怎麼用

首先創建一個空對象,然後用 for 迴圈遍歷

利用對象的屬性不會重覆這一特性,校驗數組元素是否重覆

複製代碼
function distinct(a, b) {
    let arr = a.concat(b)
    let result = []
    let obj = {}

    for (let i of arr) {
        if (!obj[i]) {
            result.push(i)
            obj[i] = 1
        }
    }

    return result
}
複製代碼

當我看到這個方法的處理時長,我又傻眼了

15W 的數據居然只要 16ms ??? 比 Set() 還快???

然後我又試了試 150W 的數據量...

emmmmmmm.... 惹不起惹不起...


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

-Advertisement-
Play Games
更多相關文章
  • 我們略過概念,直接看函數式響應式編程解決了什麼問題。 故事從下麵這個例子展開: 兩個密碼輸入框,一個提交按鈕。 密碼、確認密碼都填寫並一致,允許提交;不一致提示錯誤。 HTML 如下: 常規做法 初始版 加強版 問題: 輸入密碼時,確認密碼還是空的,出現密碼不一致錯誤提示,干擾用戶輸入。 期望: 確 ...
  • HTML 描寫 HTML是網頁語言(超文本標記語言),採用標簽格式進行編寫 HTML標簽:採用尖括弧包圍的關鍵字,通常成對出現(閉合標簽),但是也有個別非成對的(非閉合標簽) HTML文檔:一個完整的HTML編寫的文檔,可以形成一個瀏覽器可以訪問的資源網頁 如上就是最簡單的HTML文檔內容, 標簽之 ...
  • 遞歸: 所謂遞歸,就是既有傳遞,又有回歸,與其說是傳遞與回歸,初學不如理解是一種 “循序遞進”與“規律約束”。 為什麼這樣說,因為遞歸演算法相比較於迴圈在代碼結構方面個人認為更加簡潔清晰,清晰易懂,遞歸註重的是一種有序的規律,所以在每個程式開始之前,我們只要能找到一個使程式循序遞進的規律;並且在整個過 ...
  • 0830自我總結 HTML標簽嵌套規則 1.塊級元素: div、h1~h6、address、blockquote、center、dir、dl、dt、dd、fieldset、form、hr、isindex、menu、noframes、noscript、ol、p、pre、table、ul 特點:總是在新 ...
  • 博客園美化小火箭 一.代碼 二.原理 三.效果展示 ...
  • 問題在於對數據的操作,或數據類型,或數據名稱 ...
  • <!DOCTYPE html><html lang="en"><head> <meta charset="UTF-8"> <title>Title</title></head><body><div id="app"> <!-- 在組件標簽上綁定的事件都vue的自定義事件。 --> <v-xiaosh ...
  • 完成最基礎的Vue環境及新建一個vue項目。 一般來說,我們拿到一個項目需求或者得到一個需求的時候,第一件應該做的事情不是立馬坐在電腦前面去寫代碼,如果你這麼做的,好吧。。。我只能暫時認定你為一個剛上路的。 首先,用戶給你一個需求,我們先要做的是需求的分析,明白用戶需要什麼?我們當前的條件能為他創造 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...