Rendimiento de conjunto de Javascript frente a matriz

Tal vez porque los conjuntos son relativamente nuevos en Javascript, pero no he podido encontrar un artículo, en StackO o en ningún otro lugar, que hable sobre la diferencia de rendimiento entre los dos en Javascript. Entonces, ¿cuál es la diferencia, en términos de rendimiento, entre los dos? Específicamente, cuando se trata de eliminar, agregar e iterar.

Ok, he probado agregar, iterar y eliminar elementos tanto de una matriz como de un conjunto. Ejecuté una prueba "pequeña", usando 10 000 elementos y una prueba "grande", usando 100 000 elementos. Aquí están los resultados.

Agregar elementos a una colección

Parecería que el .pushmétodo de matriz es aproximadamente 4 veces más rápido que el.add método de conjunto, sin importar la cantidad de elementos que se agreguen.

Iterando y modificando elementos en una colección

Para esta parte de la prueba, utilicé un forciclo para iterar sobre la matriz y un for ofciclo para iterar sobre el conjunto. Nuevamente, iterar sobre la matriz fue más rápido. Esta vez parece que es exponencial, ya que tomó el doble de tiempo durante las pruebas "pequeñas" y casi cuatro veces más durante las pruebas "grandes".

Eliminar elementos de una colección

Ahora aquí es donde se pone interesante. Usé una combinación de un forbucle y .splicepara eliminar algunos elementos de la matriz y usé for ofy .deletepara eliminar algunos elementos del conjunto. Para las pruebas "pequeñas", fue aproximadamente tres veces más rápido eliminar elementos del conjunto (2,6 ms frente a 7,1 ms), pero las cosas cambiaron drásticamente para la prueba "grande", en la que se necesitaron 1955,1 ms para eliminar elementos de la matriz mientras solo tardó 83,6 ms en eliminarlos del conjunto, 23 veces más rápido.

Conclusiones

En 10k elementos, ambas pruebas se ejecutaron tiempos comparables (matriz: 16.6 ms, conjunto: 20,7 ms) pero cuando se trataba de 100k elementos, el conjunto fue el claro ganador (matriz: 1974.8 ms, conjunto: 83.6 ms) pero solo debido a la eliminación operación. De lo contrario, la matriz fue más rápida. No podría decir exactamente por qué.

Jugué con algunos escenarios híbridos en los que se creó y completó una matriz y luego se convirtió en un conjunto donde se eliminarían algunos elementos, el conjunto se reconvertiría en una matriz. Aunque hacer esto proporcionará un rendimiento mucho mejor que eliminar elementos en la matriz, el tiempo de procesamiento adicional necesario para transferir hacia y desde un conjunto supera las ganancias de poblar una matriz en lugar de un conjunto. Al final, es más rápido tratar solo con un conjunto. Aún así, es una idea interesante, que si uno elige usar una matriz como una colección de datos para algunos datos grandes que no tienen duplicados, podría ser ventajoso en cuanto al rendimiento, si alguna vez es necesario eliminar muchos elementos en uno. , para convertir la matriz en un conjunto, realizar la operación de eliminación y convertir el conjunto de nuevo en una matriz.

Código de matriz:

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

Establecer código:

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

OBSERVACIONES :

• Las operaciones de conjunto pueden entenderse como instantáneas dentro del flujo de ejecución.
• No estamos ante un sustituto definitivo.
• Los elementos de una clase Set no tienen índices accesibles.
• La clase Set es un complemento de la clase Array , útil en aquellos escenarios donde necesitamos almacenar una colección sobre la cual aplicar operaciones básicas de adición, eliminación, verificación e iteración.

Comparto alguna prueba de desempeño. Intente abrir su consola y copiar y pegar el código a continuación.

Creando una matriz (125000)

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

1. Ubicación de un índice

Comparamos el método has de Set con Array indexOf:

Array / indexOf (0.281ms) | Establecer / tiene (0.053ms)

// 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. Agregar un nuevo elemento

Comparamos los métodos add y push de los objetos Set y Array respectivamente:

Matriz / empuje (1.612ms) | Establecer / agregar (0.006ms)

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. Eliminar un elemento

A la hora de eliminar elementos, debemos tener en cuenta que Array y Set no se inician en iguales condiciones. Array no tiene un método nativo, por lo que es necesaria una función externa.

Array / deleteFromArr (0.356ms) | Establecer / quitar (0.019ms)

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' );

Lea el artículo completo aquí

Mi observación es que un conjunto siempre es mejor si se tienen en cuenta dos trampas para matrices grandes:

a) La creación de Conjuntos a partir de Arrays debe realizarse en un forbucle con una longitud almacenada previamente.

lento (por ejemplo, 18 ms) new Set(largeArray)

rápido (por ejemplo, 6ms) const SET = new Set(); const L = largeArray.length; for(var i = 0; i<L; i++) { SET.add(largeArray[i]) }

b) La iteración se podría hacer de la misma manera porque también es más rápido que un for of bucle ...

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

para una comparación real de la vida difference(), intersection(), union()y uniq()(+ sus compañeros iteratee etc.), con 40.000 elementos

Para la parte de la iteración de su pregunta, recientemente ejecuté esta prueba y descubrí que Set superó con creces una matriz de 10,000 elementos (alrededor de 10 veces las operaciones podrían ocurrir en el mismo período de tiempo). Y, dependiendo del navegador, venció o perdió a Object.hasOwnProperty en una prueba de igual a igual.

Tanto Set como Object tienen su método "has" funcionando en lo que parece amortizarse a O (1), pero dependiendo de la implementación del navegador, una sola operación podría llevar más tiempo o más rápido. Parece que la mayoría de los navegadores implementan claves en Object más rápido que Set.has (). Incluso Object.hasOwnProperty, que incluye una verificación adicional en la clave, es aproximadamente un 5% más rápido que Set.has () al menos para mí en Chrome v86.

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

Actualización: 11/11/2020: https://jsbench.me/irkhdxnoqa/2

En caso de que desee ejecutar sus propias pruebas con diferentes navegadores / entornos.

De manera similar, agregaré un punto de referencia para agregar elementos a una matriz frente a establecer y eliminar.

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

Esas tres operaciones en artículos de 10K me dieron:

set: 7.787ms
array: 2.388ms