L'auteur du document, dont nous publions la traduction aujourd'hui, affirme qu'il est convaincu que de nombreux développeurs JavaScript utilisent principalement des types de données tels que
Number ,
String ,
Object ,
Array et
Boolean . Dans la plupart des cas, cela suffit. Mais si vous devez rendre le code aussi rapide et évolutif que possible, l'utilisation de ces types de données n'est pas toujours justifiée.
Dans cet article, nous expliquerons comment, en utilisant le type de données
Set , qui offre la possibilité de travailler avec des collections de valeurs uniques, rendre le code plus rapide. Cela est particulièrement vrai pour le code des projets à grande échelle. Les types
Array et
Set ont beaucoup en commun, mais l'utilisation du type de données
Set peut donner au programmeur des fonctionnalités qui se manifestent clairement lors de l'exécution de programmes, contrairement au type
Array .
Quelle est la différence entre les types de données Array et Set?
La principale caractéristique du type de données
Array (nous appellerons les objets de ce type «tableaux») est que les tableaux sont des collections de valeurs indexées. Cela signifie que les données dans les tableaux sont stockées à l'aide d'index.
const arr = [A, B, C, D]; console.log(arr.indexOf(A));
Contrairement aux tableaux, les objets de type
Set (nous les appellerons «collections») sont des collections contenant des données au format clé / valeur. Au lieu d'utiliser des index, les collections stockent les éléments à l'aide de clés. Les éléments stockés dans la collection peuvent être triés dans l'ordre dans lequel ils ont été ajoutés à la collection, tandis que la collection ne peut pas stocker les mêmes éléments. En d'autres termes, tous les éléments de la collection doivent être uniques.
Quelles sont les principales forces des collections?
Si vous comparez des collections et des tableaux, vous pouvez trouver certains avantages par rapport aux collections par rapport aux tableaux, en particulier dans les situations où les performances du programme sont importantes:
- Recherchez des éléments. Les méthodes de tableau
indexOf() et includes() , utilisées pour rechercher des éléments et vérifier si un élément a un élément dans le tableau, fonctionnent lentement. - Suppression d'éléments. Un élément peut être supprimé dans la collection en fonction de sa valeur. Dans un tableau, l'équivalent d'une telle action serait d'utiliser la méthode
splice() , basée sur l'index de l'élément. Comme pour la recherche d'éléments, la suppression d'éléments à l'aide d'index est une opération lente. - Insérez un élément. Il est beaucoup plus rapide d'ajouter un élément à la collection que d'utiliser des méthodes comme
push() et unshift() dans un tableau. - Travaillez avec la valeur
NaN . La méthode indexOf() ne peut pas être utilisée pour trouver la valeur NaN dans un tableau, tandis qu'en utilisant la méthode de collecte has() , vous pouvez savoir si elle contient NaN . - Suppression des éléments en double.
Set objets Set ne stockent que des valeurs uniques. Si vous devez éviter d'enregistrer des éléments en double dans certaines structures de données, c'est leur avantage significatif sur les tableaux. Lorsque vous travaillez avec des tableaux pour supprimer les éléments en double, vous devrez écrire du code supplémentaire.
Une liste complète des méthodes intégrées d'objets de type
Set peut être trouvée
ici .
Sur la complexité temporelle des algorithmes
Les méthodes utilisées par les tableaux pour rechercher des éléments ont une complexité temporelle linéaire - O (N). En d'autres termes, le temps de recherche d'élément est proportionnel à la taille du tableau.
Contrairement aux tableaux, les méthodes utilisées par les collections pour rechercher, supprimer et ajouter des éléments ont une complexité temporelle O (1). Cela signifie que la taille de la collection n'a pratiquement aucun effet sur le temps de travail de ces méthodes.
Ici, vous pouvez en savoir plus sur la complexité temporelle des algorithmes.
Les collections sont-elles beaucoup plus rapides que les tableaux?
Bien que les indicateurs de performance du code JavaScript soient fortement influencés par divers facteurs, en particulier, ils dépendent du système sur lequel le code est exécuté, de l'environnement utilisé pour exécuter le code, de la taille des données en cours de traitement, j'espère que les résultats de mes tests vous donneront l'opportunité de comparer des tableaux et des collections d'un point de vue pratique, et comprendre comment les collections sont plus rapides que les tableaux. Nous allons maintenant considérer trois tests simples et analyser leurs résultats.
▍Préparation du test
Avant de faire des tests, créons un tableau avec un million d'éléments et la même collection. Par souci de simplicité, nous utiliserons un cycle, dont la première valeur de compteur sera 0 et la dernière - 999999:
let arr = [], set = new Set(), n = 1000000; for (let i = 0; i < n; i++) { arr.push(i); set.add(i); }
▍Test n ° 1: vérification de la présence d'un élément dans un tableau et dans une collection
Dans un premier temps, nous vérifierons la présence de l'élément
123123 dans le tableau et dans la collection, sachant à l'avance qu'un tel élément existe dans ces structures de données.
let result; console.time('Array'); result = arr.indexOf(123123) !== -1; console.timeEnd('Array'); console.time('Set'); result = set.has(123123); console.timeEnd('Set');
Voici les résultats de ce test:
Array: 0.173ms Set: 0.023ms
La collection est 7,54 fois plus rapide que le tableau.
▍Test n ° 2: insertion d'un élément
Essayons maintenant d'ajouter des éléments aux tableaux et aux collections.
console.time('Array'); arr.push(n); console.timeEnd('Array'); console.time('Set'); set.add(n); console.timeEnd('Set');
Voici ce qui s'est passé:
Array: 0.018ms Set: 0.003ms
La collection est 6,73 fois plus rapide que le tableau.
▍Test 3: supprimer un élément
Supprimons maintenant l'élément de chaque structure de données (par exemple, celui qui a été ajouté lors du test précédent). Les tableaux n'ont pas de méthode intégrée pour supprimer des éléments, nous allons donc créer une fonction d'aide pour garder notre code en bon état:
const deleteFromArr = (arr, item) => { let index = arr.indexOf(item); return index !== -1 && arr.splice(index, 1); };
Et voici le code de test:
console.time('Array'); deleteFromArr(arr, n); console.timeEnd('Array'); console.time('Set'); set.delete(n); console.timeEnd('Set');
Le résultat est le suivant:
Array: 1.122ms Set: 0.015ms
Dans ce cas, la collection était 74,13 fois plus rapide que le tableau!
En général, on peut noter que les performances du code peuvent être considérablement augmentées en utilisant des collections au lieu de tableaux. Prenons quelques exemples pratiques.
Exemple # 1: suppression des valeurs en double d'un tableau
Si vous devez supprimer rapidement les valeurs en double d'un tableau, vous pouvez le convertir en une collection. C'est peut-être le moyen le plus simple de se débarrasser des valeurs en double:
const duplicateCollection = ['A', 'B', 'B', 'C', 'D', 'B', 'C'];
Exemple 2: tâche d'entrevue chez Google
Dans l'un de mes
documents, j'ai examiné quatre options pour répondre à la question posée par un intervieweur de Google. L'interview a été réalisée en C ++, mais si JavaScript était utilisé à la place de ce langage, la structure de données
Set serait nécessairement utilisée pour résoudre le problème.
Si vous voulez comprendre plus profondément la réponse à cette question - lisez l'article ci-dessus. Ici, je montre juste une solution toute faite.
▍ Tâche
Étant donné un tableau non trié d'entiers et une valeur de
sum . Écrivez une fonction qui renvoie
true si, à la suite de l'ajout de deux éléments de ce tableau, nous obtenons la valeur de
sum . S'il n'y a pas de tels éléments dans le tableau, la fonction doit retourner
false .
Il s'avère, par exemple, que si l'on nous donne un tableau
[3, 5, 1, 4] et que la valeur de la
sum est
9 , alors la fonction devrait retourner
true , puisque
4+5=9 .
▍Solution
Vous pouvez aborder ce problème en utilisant l'idée suivante: vous devez parcourir le tableau, en créant la structure de données
Set au fur et à mesure de son tri, dans laquelle seront ajoutées des valeurs qui complètent les valeurs trouvées pour la valeur de
sum .
Analysons cette idée en utilisant l'exemple du tableau ci-dessus. Lorsque nous rencontrons
3 , nous pouvons ajouter le nombre
6 à la collection, car nous savons que nous devons trouver deux nombres qui totalisent
9 . Ensuite, chaque fois que nous rencontrons une nouvelle valeur dans le tableau, nous pouvons vérifier la collection et voir si elle existe. Lorsque nous rencontrerons le chiffre
5 , nous ajouterons
4 à la collection. Et quand, finalement, nous arrivons au numéro
4 , nous le trouvons dans la collection et pouvons retourner
true .
Voici à quoi pourrait ressembler une solution à ce problème:
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; };
Et voici une solution plus concise:
const findSum = (arr, sum) => arr.some((set => n => set.has(n) || !set.add(sum - n))(new Set));
Étant donné que la complexité temporelle de la méthode
Set.prototype.has() est O (1), l'utilisation de la structure de données
Set pour stocker des nombres qui complètent les nombres trouvés dans le tableau à une valeur donnée vous permet de trouver une solution en temps linéaire (O (N)).
Si la solution dépendait de la méthode
Array.prototype.indexOf() ou de la méthode
Array.prototype.includes() , la complexité temporelle de chacun d'eux est O (N), alors la complexité temporelle totale de l'algorithme serait O (N
2 ). En conséquence, il deviendrait beaucoup plus lent.
Résumé
Si vous n'avez jamais rencontré le type de données
Set en JavaScript auparavant, nous espérons que maintenant, en ayant une idée, vous pourrez l'utiliser avec avantage dans vos projets.
Chers lecteurs! Comment appliqueriez-vous la structure de données
Set dans votre code?