Leistung von Javascript Set vs. Array

Vielleicht, weil Sets für Javascript relativ neu sind, aber ich konnte weder in StackO noch anderswo einen Artikel finden, der über den Leistungsunterschied zwischen den beiden in Javascript spricht. Was ist also der Unterschied in Bezug auf die Leistung zwischen den beiden? Insbesondere beim Entfernen, Hinzufügen und Iterieren.

Ok, ich habe das Hinzufügen, Iterieren und Entfernen von Elementen aus einem Array und einer Menge getestet. Ich habe einen "kleinen" Test mit 10 000 Elementen und einen "großen" Test mit 100 000 Elementen durchgeführt. Hier sind die Ergebnisse.

Hinzufügen von Elementen zu einer Sammlung

Es scheint, dass die .pushArray-Methode ungefähr viermal schneller ist als die .addSet-Methode, unabhängig von der Anzahl der hinzugefügten Elemente.

Elemente in einer Sammlung durchlaufen und ändern

Für diesen Teil des Tests habe ich eine forSchleife verwendet, um über das Array for ofzu iterieren, und eine Schleife, um über die Menge zu iterieren. Wiederum war das Iterieren über das Array schneller. Diesmal scheint es exponentiell zu sein, da es bei den "kleinen" Tests doppelt so lange und bei den "großen" Tests fast viermal länger dauerte.

Elemente aus einer Sammlung entfernen

Hier wird es interessant. Ich habe eine Kombination aus einer forSchleife verwendet und .spliceeinige Elemente aus dem Array entfernt, und ich habe for ofund verwendet.delete zu entfernen, einige Elemente aus dem Set entfernt. Bei den "kleinen" Tests war es ungefähr dreimal schneller, Elemente aus dem Satz zu entfernen (2,6 ms gegenüber 7,1 ms), aber beim "großen" Test, bei dem 1955,1 ms benötigt wurden, um Elemente aus dem Array zu entfernen, änderten sich die Dinge drastisch Es dauerte 83,6 ms, um sie aus dem Set zu entfernen, 23-mal schneller.

Schlussfolgerungen

Bei 10.000 Elementen liefen beide Tests vergleichbare Zeiten (Array: 16,6 ms, Satz: 20,7 ms), aber bei 100.000 Elementen war der Satz der klare Gewinner (Array: 1974,8 ms, Satz: 83,6 ms), jedoch nur aufgrund des Entfernens Betrieb. Ansonsten war das Array schneller. Ich konnte nicht genau sagen, warum das so ist.

Ich habe mit einigen Hybridszenarien herumgespielt, in denen ein Array erstellt und gefüllt und dann in eine Gruppe konvertiert wurde, in der einige Elemente entfernt wurden. Die Gruppe wurde dann wieder in ein Array konvertiert. Obwohl dies eine viel bessere Leistung bietet als das Entfernen von Elementen im Array, überwiegt die zusätzliche Verarbeitungszeit, die für die Übertragung zu und von einem Satz erforderlich ist, die Vorteile des Auffüllens eines Arrays anstelle eines Satzes. Am Ende ist es schneller, nur mit einem Satz umzugehen. Dennoch ist es eine interessante Idee, dass, wenn man ein Array als Datenerfassung für einige Big Data ohne Duplikate verwendet, dies in Bezug auf die Leistung vorteilhaft sein kann, wenn jemals viele Elemente in einem entfernt werden müssen Operation, um das Array in eine Gruppe zu konvertieren, führen Sie die Entfernungsoperation aus und konvertieren Sie die Gruppe zurück in ein Array.

Array-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++)
    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.")

Code einstellen:

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.")

BEMERKUNGEN :

• Set-Operationen können als Snapshots innerhalb des Ausführungsstroms verstanden werden.
• Wir stehen nicht vor einem endgültigen Ersatz.
• Die Elemente einer Set-Klasse haben keine zugänglichen Indizes.
• Die Set-Klasse ist eine Array-Klassenergänzung , die in solchen Szenarien nützlich ist, in denen eine Sammlung gespeichert werden muss, auf die grundlegende Additions-, Lösch-, Überprüfungs- und Iterationsoperationen angewendet werden sollen.

Ich teile einige Leistungstests. Versuchen Sie, Ihre Konsole zu öffnen und den folgenden Code kopieren.

Erstellen eines Arrays (125000)

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

1. Suchen eines Index

Wir haben die has-Methode von Set mit Array indexOf verglichen:

Array / indexOf (0,281 ms) | Set / has (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. Hinzufügen eines neuen Elements

Wir vergleichen die Add- und Push-Methoden der Set- und Array-Objekte:

Array / Push (1,612 ms) | Einstellen / Hinzufügen (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. Ein Element löschen

Beim Löschen von Elementen müssen wir berücksichtigen, dass Array und Set nicht unter gleichen Bedingungen starten. Das Array verfügt nicht über eine native Methode, daher ist eine externe Funktion erforderlich.

Array / deleteFromArr (0,356 ms) | Einstellen / Entfernen (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' );

Lesen Sie den ganzen Artikel hier

Meine Beobachtung ist, dass ein Set immer besser ist, wenn man zwei Fallstricke für große Arrays berücksichtigt:

a) Die Erstellung von Sets aus Arrays muss in einer forSchleife mit einer vorgespeicherten Länge erfolgen.

langsam (zB 18ms) new Set(largeArray)

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

b) Das Iterieren könnte auf die gleiche Weise erfolgen, da es auch schneller als eine for ofSchleife ist ...

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

für einen echten Leben Vergleich zu difference(), intersection(), union()und uniq()(+ ihre iteratee Begleiter etc.) mit 40.000 Elementen

Für den Iterationsteil Ihrer Frage habe ich kürzlich diesen Test durchgeführt und festgestellt, dass Set ein Array von 10.000 Elementen deutlich übertroffen hat (etwa das 10-fache der Vorgänge könnte im selben Zeitraum erfolgen). Und je nach Browser entweder geschlagen oder an Object.hasOwnProperty in einem Like-for-Like-Test verloren.

Sowohl Set als auch Object haben ihre "has" -Methode, die in einer amortisierten Form von O (1) ausgeführt wird. Abhängig von der Implementierung des Browsers kann ein einzelner Vorgang jedoch länger oder schneller dauern. Es scheint, dass die meisten Browser Schlüssel in Object schneller implementieren als Set.has (). Selbst Object.hasOwnProperty, das eine zusätzliche Überprüfung des Schlüssels enthält, ist zumindest für mich in Chrome v86 etwa 5% schneller als Set.has ().

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

Update: 11.11.2020: https://jsbench.me/irkhdxnoqa/2

Für den Fall, dass Sie Ihre eigenen Tests mit verschiedenen Browsern / Umgebungen ausführen möchten.

In ähnlicher Weise füge ich einen Benchmark zum Hinzufügen von Elementen zu einem Array hinzu, anstatt zu setzen und zu entfernen.

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

Diese drei Operationen an 10.000 Gegenständen gaben mir:

set: 7.787ms
array: 2.388ms