tablas - Javascript Set vs rendimiento de la matriz

obtener datos de una tabla html javascript

Question

Quizás 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.

Answer 1

OBSERVACIONES

• Las operaciones de conjuntos pueden entenderse como instantáneas dentro de la secuencia 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 en los que necesitamos almacenar una colección en la que aplicar operaciones básicas de adición, eliminación, verificación e iteración.

Comparto algunas pruebas de rendimiento. Intenta abrir tu consola y copia el siguiente código.

Crear una matriz (125000)

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

1. Localización de un índice

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

Array / indexOf (0.281 ms) | Conjunto / 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 / inserción (1.612 ms) | 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

Al eliminar elementos, debemos tener en cuenta que Array y Set no comienzan en igualdad de condiciones. La matriz no tiene un método nativo, por lo que es necesaria una función externa.

Array / deleteFromArr (0.356 ms) | Establecer / eliminar (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'' );

Lee el artículo completo here

Answer 2

Mi observación es que un conjunto siempre es mejor con dos trampas para las matrices grandes en mente:

a) La creación de conjuntos a partir de matrices se debe hacer en un bucle for con una longitud precached.

new Set(largeArray) lento (p. ej., 18 ms) new Set(largeArray)

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

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

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

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

Answer 3

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

Agregar elementos a una colección

Parecería que el método de matriz .push es aproximadamente 4 veces más rápido que el método .add set, 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 bucle for para iterar sobre la matriz y un bucle for of para iterar sobre el conjunto. Nuevamente, iterar sobre la matriz fue más rápido. Esta vez parecería 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. .splice una combinación de un bucle for y .splice para eliminar algunos elementos de la matriz y utilicé for of y .delete para 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 del conjunto mientras solo tardó 83,6 ms en eliminarlos del conjunto, 23 veces más rápido.

Conclusiones

Con 10k elementos, ambas pruebas corrieron tiempos comparables (matriz: 16.6 ms, conjunto: 20.7 ms) pero cuando se trata de elementos de 100k, 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é es eso.

Jugué con algunos escenarios híbridos donde 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 completar 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 recopilación de datos para algunos datos grandes que no tienen duplicados, podría ser ventajoso en términos de rendimiento, si alguna vez es necesario eliminar muchos elementos en uno operación, para convertir el conjunto en un conjunto, realizar la operación de eliminación y convertir el conjunto de nuevo en un conjunto.

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

Answer 4

Recientemente ejecuté esta prueba y descubrí que Set superó mucho a una matriz de 1000 elementos (alrededor de 10 veces las operaciones podrían ocurrir en el mismo período de tiempo). Y dependiendo del navegador, venció o perdió ante Object.hasOwnProperty en una prueba similar.

Tanto Set como Object tienen su método "has" funcionando en lo que parece ser amortizado a O (1), pero dependiendo de la implementación del navegador, una sola operación podría tomar más tiempo o más rápido.

https://jsperf.com/set-has-vs-object-hasownproperty-vs-array-includes/1 En caso de que desee ejecutar sus propias pruebas con diferentes navegadores / entornos.

Answer 5

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