Jeu Javascript vs performances du tableau

C'est peut-être parce que les sets sont relativement nouveaux en Javascript mais je n'ai pas pu trouver d'article, sur StackO ou ailleurs, qui parle de la différence de performance entre les deux en Javascript. Alors, quelle est la différence, en termes de performances, entre les deux? Plus précisément, lorsqu'il s'agit de supprimer, d'ajouter et d'itérer.

Ok, j'ai testé l'ajout, l'itération et la suppression d'éléments à la fois d'un tableau et d'un ensemble. J'ai fait un "petit" test, utilisant 10 000 éléments et un "grand" test, utilisant 100 000 éléments. Voici les résultats.

Ajouter des éléments à une collection

Il semblerait que la .pushméthode tableau soit environ 4 fois plus rapide que la .addméthode set, quel que soit le nombre d'éléments ajoutés.

Itérer et modifier des éléments dans une collection

Pour cette partie du test, j'ai utilisé une forboucle pour parcourir le tableau et une for ofboucle pour parcourir l'ensemble. Encore une fois, l'itération sur le tableau était plus rapide. Cette fois, il semblerait que ce soit de façon exponentielle car cela a pris deux fois plus de temps lors des "petits" tests et presque quatre fois plus lors des "grands" tests.

Supprimer des éléments d'une collection

Maintenant, c'est là que ça devient intéressant. J'ai utilisé une combinaison d'une forboucle et .splicepour supprimer certains éléments du tableau et j'ai utilisé for ofet .deletepour supprimer certains éléments de l'ensemble. Pour les "petits" tests, il était environ trois fois plus rapide de supprimer des éléments de l'ensemble (2,6 ms contre 7,1 ms) mais les choses ont radicalement changé pour le "grand" test où il a fallu 1955,1 ms pour supprimer des éléments du tableau alors qu'il ne s'agissait que de il a fallu 83,6 ms pour les supprimer du plateau, 23 fois plus vite.

Conclusions

À 10k éléments, les deux tests se sont déroulés à des temps comparables (tableau: 16,6 ms, ensemble: 20,7 ms) mais lorsqu'il s'agissait de 100k éléments, l'ensemble était clairement gagnant (tableau: 1974,8 ms, ensemble: 83,6 ms) mais uniquement à cause de la suppression opération. Sinon, le tableau était plus rapide. Je ne pourrais pas dire exactement pourquoi.

J'ai joué avec certains scénarios hybrides où un tableau était créé et peuplé, puis converti en un ensemble où certains éléments seraient supprimés, l'ensemble serait ensuite reconverti en un tableau. Bien que cela donne de bien meilleures performances que la suppression d'éléments dans le tableau, le temps de traitement supplémentaire nécessaire pour transférer vers et depuis un ensemble l'emporte sur les gains de peuplement d'un tableau au lieu d'un ensemble. Au final, il est plus rapide de ne traiter qu'un ensemble. Pourtant, c'est une idée intéressante, que si l'on choisit d'utiliser un tableau comme collection de données pour certaines données volumineuses qui n'ont pas de doublons, cela pourrait être avantageux en termes de performances, s'il est jamais nécessaire de supprimer de nombreux éléments en un seul. , pour convertir le tableau en ensemble, effectuer l'opération de suppression et reconvertir l'ensemble en tableau.

Code de tableau:

var timer = function(name) {
  var start = new Date();
  return {
    stop: function() {
      var end = new Date();
      var time = end.getTime() - start.getTime();
      console.log('Timer:', name, 'finished in', time, 'ms');
    }
  }
};

var getRandom = function(min, max) {
  return Math.random() * (max - min) + min;
};

var lastNames = ['SMITH', 'JOHNSON', 'WILLIAMS', 'JONES', 'BROWN', 'DAVIS', 'MILLER', 'WILSON', 'MOORE', 'TAYLOR', 'ANDERSON', 'THOMAS'];

var genLastName = function() {
  var index = Math.round(getRandom(0, lastNames.length - 1));
  return lastNames[index];
};

var sex = ["Male", "Female"];

var genSex = function() {
  var index = Math.round(getRandom(0, sex.length - 1));
  return sex[index];
};

var Person = function() {
  this.name = genLastName();
  this.age = Math.round(getRandom(0, 100))
  this.sex = "Male"
};

var genPersons = function() {
  for (var i = 0; i < 100000; i++)
    personArray.push(new Person());
};

var changeSex = function() {
  for (var i = 0; i < personArray.length; i++) {
    personArray[i].sex = genSex();
  }
};

var deleteMale = function() {
  for (var i = 0; i < personArray.length; i++) {
    if (personArray[i].sex === "Male") {
      personArray.splice(i, 1)
      i--
    }
  }
};

var t = timer("Array");

var personArray = [];

genPersons();

changeSex();

deleteMale();

t.stop();

console.log("Done! There are " + personArray.length + " persons.")

Définir le code:

var timer = function(name) {
    var start = new Date();
    return {
        stop: function() {
            var end  = new Date();
            var time = end.getTime() - start.getTime();
            console.log('Timer:', name, 'finished in', time, 'ms');
        }
    }
};

var getRandom = function (min, max) {
  return Math.random() * (max - min) + min;
};

var lastNames = ['SMITH','JOHNSON','WILLIAMS','JONES','BROWN','DAVIS','MILLER','WILSON','MOORE','TAYLOR','ANDERSON','THOMAS'];

var genLastName = function() {
    var index = Math.round(getRandom(0, lastNames.length - 1));
    return lastNames[index];
};

var sex = ["Male", "Female"];

var genSex = function() {
    var index = Math.round(getRandom(0, sex.length - 1));
    return sex[index];
};

var Person = function() {
	this.name = genLastName();
	this.age = Math.round(getRandom(0,100))
	this.sex = "Male"
};

var genPersons = function() {
for (var i = 0; i < 100000; i++)
	personSet.add(new Person());
};

var changeSex = function() {
	for (var key of personSet) {
		key.sex = genSex();
	}
};

var deleteMale = function() {
	for (var key of personSet) {
		if (key.sex === "Male") {
			personSet.delete(key)
		}
	}
};

var t = timer("Set");

var personSet = new Set();

genPersons();

changeSex();

deleteMale();

t.stop();

console.log("Done! There are " + personSet.size + " persons.")

OBSERVATIONS :

• Les opérations d'ensemble peuvent être considérées comme des instantanés dans le flux d'exécution.
• Nous ne sommes pas devant un substitut définitif.
• Les éléments d'une classe Set n'ont pas d'index accessibles.
• La classe Set est un complément de classe Array , utile dans les scénarios où nous devons stocker une collection sur laquelle appliquer des opérations de base d'ajout, de suppression, de vérification et d'itération.

Je partage quelques tests de performances. Essayez d'ouvrir votre console et copiez le code ci-dessous.

Création d'un tableau (125000)

var n = 125000;
var arr = Array.apply( null, Array( n ) ).map( ( x, i ) => i );
console.info( arr.length ); // 125000

1. Localisation d'un index

Nous avons comparé la méthode has de Set avec Array indexOf:

Array / indexOf (0,281 ms) | Définir / a (0,053 ms)

// Helpers
var checkArr = ( arr, item ) => arr.indexOf( item ) !== -1;
var checkSet = ( set, item ) => set.has( item );

// Vars
var set, result;

console.time( 'timeTest' );
result = checkArr( arr, 123123 );
console.timeEnd( 'timeTest' );

set = new Set( arr );

console.time( 'timeTest' );
checkSet( set, 123123 );
console.timeEnd( 'timeTest' );

2. Ajout d'un nouvel élément

Nous comparons respectivement les méthodes add et push des objets Set et Array:

Array / push (1,612 ms) | Définir / ajouter (0,006 ms)

console.time( 'timeTest' );
arr.push( n + 1 );
console.timeEnd( 'timeTest' );

set = new Set( arr );

console.time( 'timeTest' );
set.add( n + 1 );
console.timeEnd( 'timeTest' );

console.info( arr.length ); // 125001
console.info( set.size ); // 125001

3. Suppression d'un élément

Lors de la suppression d'éléments, nous devons garder à l'esprit que Array et Set ne démarrent pas dans des conditions égales. Array n'a pas de méthode native, donc une fonction externe est nécessaire.

Array / deleteFromArr (0,356 ms) | Définir / supprimer (0,019 ms)

var deleteFromArr = ( arr, item ) => {
    var i = arr.indexOf( item );
    i !== -1 && arr.splice( i, 1 );
};

console.time( 'timeTest' );
deleteFromArr( arr, 123123 );
console.timeEnd( 'timeTest' );

set = new Set( arr );

console.time( 'timeTest' );
set.delete( 123123 );
console.timeEnd( 'timeTest' );

Lisez l'article complet ici

Mon observation est qu'un ensemble est toujours meilleur avec deux pièges à l'esprit pour les grands tableaux:

a) La création d'ensembles à partir de tableaux doit se faire dans une forboucle avec une longueur précachée.

lent (par exemple 18ms) new Set(largeArray)

rapide (par exemple 6ms) const SET = new Set(); const L = largeArray.length; for(var i = 0; i<L; i++) { SET.add(largeArray[i]) }

b) L'itération pourrait se faire de la même manière car elle est également plus rapide qu'une for ofboucle ...

Voir https://jsfiddle.net/0j2gkae7/5/

pour une réelle comparaison de vie difference(), intersection(), union()et uniq()(+ leurs compagnons de iteratee etc.) avec des éléments 40000

Pour la partie itération de votre question, j'ai récemment exécuté ce test et j'ai trouvé que Set surpassait de beaucoup un tableau de 10000 éléments (environ 10 fois les opérations pourraient se produire dans le même laps de temps). Et selon le navigateur battu ou perdu contre Object.hasOwnProperty dans un test similaire.

Les deux Set et Object ont leur méthode «a» exécutant dans ce qui semble être amorti à O (1), mais en fonction de l'implémentation du navigateur, une seule opération peut prendre plus ou plus vite. Il semble que la plupart des navigateurs implémentent la clé dans Object plus rapidement que Set.has (). Même Object.hasOwnProperty qui inclut une vérification supplémentaire sur la clé est environ 5% plus rapide que Set.has () au moins pour moi sur Chrome v86.

https://jsperf.com/set-has-vs-object-hasownproperty-vs-array-includes/1

Mise à jour: 11/11/2020: https://jsbench.me/irkhdxnoqa/2

Au cas où vous voudriez exécuter vos propres tests avec différents navigateurs / environnements.

De même, je vais ajouter un point de repère pour ajouter des éléments à un tableau par rapport à un ensemble et les supprimer.

console.time("set")
var s = new Set()
for(var i = 0; i < 10000; i++)
  s.add(Math.random())
s.forEach(function(e){
  s.delete(e)
})
console.timeEnd("set")
console.time("array")
var s = new Array()
for(var i = 0; i < 10000; i++)
  s.push(Math.random())
s.forEach(function(e,i){
  s.splice(i)
})
console.timeEnd("array")

Ces trois opérations sur 10K objets m'ont donné:

set: 7.787ms
array: 2.388ms