Comparaison des tests de performances des méthodes de déduplication de tableau js

Le contenu de cet article concerne la comparaison des tests de performances des méthodes de déduplication de tableaux js. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.

1. Modèle de test

La déduplication de tableau est un problème courant. Internet. Diverses solutions

Afin de tester les performances de ces solutions, j'ai écrit un modèle de test pour calculer le temps de déduplication des tableaux

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

Ici, deux tableaux d'une longueur de 10W et 5W sont créés respectivement

puis fusionnés via distinct() méthode Deux tableaux et supprimer les doublons

La quantité de données n'est ni grande ni petite, mais elle peut déjà expliquer certains problèmes

2. Array.filter() + indexOf

L'idée de cette méthode est de fusionner deux tableaux en un seul, puis d'utiliser Array.filter( dans ES6 ) Parcourez le tableau et combinez-le avec indexOf pour éliminer les doublons

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

C'est la méthode de déduplication de tableau pour laquelle on m'a critiqué, Cela semble très simple, mais fonctionne réellement bien. . .

Oui, la réalité est si cruelle, il faut 8427 ms pour traiter un tableau d'une longueur de 15W

3. Double boucle for

La façon la plus simple de comprendre, la boucle externe traverse les éléments et la boucle interne vérifie qu'il soit répété

Lorsqu'il y a des valeurs en double, vous pouvez utiliser push() ou 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
}

Mais cette méthode prend beaucoup de mémoire et est la moins efficace

4. for...of + include()

Une version améliorée de la double boucle for La couche externe utilise l'instruction for...of pour. remplacez la boucle for et la boucle interne Remplacez par include()

Créez d'abord un tableau vide Lorsque include() renvoie false, poussez l'élément dans le tableau vide <.>

De même, vous pouvez également utiliser indexOf() pour remplacer include()

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

Ceci La méthode est la même que filter + indexOf est assez similaire à

Elle implémente simplement la logique interne de filter() en utilisant une boucle for, puis remplace indexOf par include<.>

donc la longueur est plus longue Elle est aussi relativement proche de

5 . Array.sort()

Utilisez d'abord sort() pour trier le tableau

Comparez ensuite si les éléments adjacents sont égaux à. éliminer les doublons

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
}

Cette méthode ne fait qu'un seul tri et une seule boucle, donc l'efficacité sera supérieure à la méthode ci-dessus

6. nouvel ensemble()

ES6 ajoute la structure de données Set, qui est similaire à Array, mais

Les membres de Set sont uniques

Basé sur cette fonctionnalité, il est très approprié pour la déduplication de baies

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

Combien de temps faut-il pour traiter 15 W de données à l'aide de Set ?

Miaou miaou ? ? ? 57 ms ? ? Ne suis-je pas ébloui ? ?

然后我在两个数组长度后面分别加了一个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 的数据量...

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!