Une discussion approfondie sur la façon dont les objets Set en JavaScript accélèrent le code

Je suis sûr qu'il y a beaucoup de développeurs coincés avec les objets globaux de base : nombres, chaînes, objets, tableaux et booléens. Pour de nombreux cas d’utilisation, ceux-ci sont nécessaires. Mais si vous souhaitez que votre code soit aussi rapide et évolutif que possible, ces types de base ne suffisent pas toujours.

Dans cet article, nous verrons comment Set les objets en JS peuvent rendre votre code plus rapide, notamment évolutif. Il y a beaucoup de croisements dans la façon dont Array et Set fonctionnent. Mais utiliser Set aura un avantage sur Array en termes de vitesse d'exécution du code.

Quelle est la différence entre Set

La différence la plus fondamentale est que le tableau est une collection indexée, ce qui signifie que les valeurs de données du tableau sont triées par index.

const arr = [A, B, C, D];
console.log(arr.indexOf(A)); // Result: 0
console.log(arr.indexOf(C)); // Result: 2

En revanche, set est une collection de clés. setN'utilisez pas d'index, utilisez plutôt des clés pour trier les données. Les éléments de set sont itérables dans l'ordre d'insertion et ne peuvent contenir aucune donnée en double. En d’autres termes, chaque élément de set doit être unique.

Quels sont les principaux avantages

set Il existe plusieurs avantages par rapport aux tableaux, notamment en termes d'exécution :

• Afficher les éléments : Utiliser indexOf() ou includes() pour vérifier si un élément d'un tableau existe est plus lent.
• Supprimer l'élément  : Dans Set, vous pouvez supprimer l'élément en fonction de son value. Dans les tableaux, l'approche équivalente consiste à utiliser l'indexation basée sur les éléments splice(). Comme le point précédent, s’appuyer sur des index est lent.
• Sauvegarder NaN : Vous ne pouvez pas utiliser indexOf() ou includes() pour trouver la valeur NaN, alors que Set peut contenir cette valeur.
• Supprimer les doublons : SetLes objets ne stockent que des valeurs uniques. Si vous ne souhaitez pas que les doublons existent, c'est un avantage significatif par rapport aux tableaux, car les tableaux nécessitent du code supplémentaire pour gérer les doublons. .

Complexité temporelle ? La complexité temporelle de la méthode tableau

utilisée pour rechercher des éléments est 0(N). En d’autres termes, le temps d’exécution augmente au même rythme que la taille des données.

En revanche, les méthodes Set de recherche, de suppression et d'insertion d'éléments ont toutes une complexité temporelle de seulement O(1), ce qui signifie que la taille des données est effectivement indépendante du temps d'exécution de ces méthodes.

À quelle vitesse est réglé ?

Bien que les temps d'exécution puissent varier considérablement en fonction du système utilisé, de la taille des données fournies et d'autres variables, j'espère que les résultats de mes tests vous donneront une idée réaliste de la vitesse de Set. Je vais partager trois tests simples et les résultats que j'ai obtenus.

Préparation des tests

Avant d'exécuter des tests, créez un tableau et un Set, chacun avec 1 million d'éléments. Pour faire simple, j'ai commencé avec 0 et j'ai compté jusqu'à 999999.

let arr = [], set = new Set(), n = 1000000;
for (let i = 0; i < n; i++) {
  arr.push(i);
  set.add(i);
}

Test 1 : Trouver l'élément

On recherche le nombre 123123

let result;
console.time('Array'); 
result = arr.indexOf(123123) !== -1; 
console.timeEnd('Array');
console.time('Set'); 
result = set.has(123123); 
console.timeEnd('Set');

• Array : 0.173ms
• Set : 0.023ms

Set La vitesse est 7.54 fois plus rapide

Test 2 : Ajouter un élément

console.time('Array'); 
arr.push(n);
console.timeEnd('Array');
console.time('Set'); 
set.add(n);
console.timeEnd('Set');

• Array : 0,018 ms
• Définir : 0,003 ms

Set Plus rapide 6.73 fois

Test 3 : Suppression d'éléments

Enfin, supprimez un élément puisque le tableau a. pas de méthode intégrée, créez d'abord une fonction d'assistance :

const deleteFromArr = (arr, item) => {
  let index = arr.indexOf(item);
  return index !== -1 && arr.splice(index, 1);
};

Voici le code de test :

console.time('Array'); 
deleteFromArr(arr, n);
console.timeEnd('Array');
console.time('Set'); 
set.delete(n);
console.timeEnd('Set');

• Array : 1,122 ms
• Set : 0,015 ms

Set est 74.13 fois plus rapide

Dans l'ensemble, nous pouvons voir que l'utilisation de Set améliore considérablement le temps d'exécution. Jetons un coup d’œil à quelques Set exemples pratiques utiles.

Cas 1 : Supprimer les valeurs en double d'un tableau

Si vous souhaitez supprimer rapidement les valeurs en double d'un tableau, vous pouvez le convertir en un Set. C'est de loin le moyen le plus propre de filtrer des valeurs uniques :

const duplicateCollection = ['A', 'B', 'B', 'C', 'D', 'B', 'C'];
// 将数组转换为 Set
let uniqueCollection = new Set(duplicateCollection);
console.log(uniqueCollection) // Result: Set(4) {"A", "B", "C", "D"}
// 值保存在数组中
let uniqueCollection = [...new Set(duplicateCollection)];
console.log(uniqueCollection) // Result: ["A", "B", "C", "D"]

Cas 2 : Questions d'entretien Google

Question :

Étant donné un tableau non ordonné d'entiers et une variable sum, s'il existe une valeur telle que la somme de deux éléments du tableau est égale à sum, renvoyez true. Sinon, retournez false. Par exemple, pour les tableaux [3,5,1,4] et sum = 9, la fonction doit renvoyer true à cause de 4 + 5 = 9.

Réponse

Un bon moyen de résoudre ce problème est de parcourir le tableau et de créer Set pour conserver les différences relatives.

当我们遇到3时，我们可以把6加到Set中, 因为我们知道我们需要找到9的和。然后，每当我们接触到数组中的新值时，我们可以检查它是否在 Set 中。当遇到5时，在 Set 加上4。最后，当我们最终遇到4时，可以在Set中找到它，就返回true。

const findSum = (arr, val) => {
  let searchValues = new Set();
  searchValues.add(val - arr[0]);
  for (let i = 1, length = arr.length; i < length; i++) {
    let searchVal = val - arr[i];
    if (searchValues.has(arr[i])) {
      return true;
    } else {
      searchValues.add(searchVal);
    }
  };
  return false;
};

简洁的版本：

const findSum = (arr, sum) =>
  arr.some((set => n => set.has(n) || !set.add(sum - n))(new Set));

因为Set.prototype.has()的时间复杂度仅为O(1)，所以使用 Set 来代替数组，最终使整个解决方案的线性运行时为O(N)。

如果使用 Array.prototype.indexOf()或Array.prototype.includes()，它们的时间复杂度都为 O(N)，则总运行时间将为O(N²)，慢得多！

原文地址：https://medium.com/@bretcameron/how-to-make-your-code-faster-using-javascript-sets-b432457a4a77

为了保证的可读性，本文采用意译而非直译。

更多编程相关知识，请访问：编程学习网站！！

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!