Conjunto de Javascript vs. desempenho de array

Talvez porque Sets são relativamente novos em Javascript, mas não consegui encontrar um artigo, no StackO ou em qualquer outro lugar, que fale sobre a diferença de desempenho entre os dois em Javascript. Então, qual é a diferença, em termos de desempenho, entre os dois? Especificamente, quando se trata de remover, adicionar e iterar.

Ok, eu testei adicionar, iterar e remover elementos de uma matriz e de um conjunto. Fiz um teste "pequeno", usando 10.000 elementos e um teste "grande", usando 100.000 elementos. Aqui estão os resultados.

Adicionar elementos a uma coleção

Parece que o .pushmétodo array é cerca de 4 vezes mais rápido do que o .addmétodo set, não importa o número de elementos sendo adicionados.

Iterando e modificando elementos em uma coleção

Para esta parte do teste, usei um forloop para iterar no array e um for ofloop para iterar no conjunto. Novamente, a iteração no array foi mais rápida. Desta vez, parece que é exponencialmente, pois demorava o dobro durante os testes "pequenos" e quase quatro vezes mais durante os testes "grandes".

Remover elementos de uma coleção

Agora é aqui que fica interessante. Usei uma combinação de um forloop e .splicepara remover alguns elementos do array e usei for ofe .deletepara remover alguns elementos do conjunto. Para os testes "pequenos", era cerca de três vezes mais rápido remover itens do conjunto (2,6 ms vs 7,1 ms), mas as coisas mudaram drasticamente para o teste "grande", em que demorou 1955,1 ms para remover itens do array enquanto ele apenas levou 83,6 ms para removê-los do conjunto, 23 vezes mais rápido.

Conclusões

Em 10k elementos, ambos os testes foram executados em tempos comparáveis ​​(matriz: 16,6 ms, conjunto: 20,7 ms), mas ao lidar com 100 mil elementos, o conjunto foi o vencedor claro (matriz: 1974,8 ms, conjunto: 83,6 ms), mas apenas por causa da remoção Operação. Caso contrário, a matriz foi mais rápida. Eu não poderia dizer exatamente por que isso acontece.

Eu brinquei com alguns cenários híbridos onde um array foi criado e preenchido e então convertido em um conjunto onde alguns elementos seriam removidos, o conjunto seria então reconvertido em um array. Embora isso proporcione um desempenho muito melhor do que remover elementos do array, o tempo de processamento adicional necessário para transferir de e para um conjunto supera os ganhos de preencher um array em vez de um conjunto. No final, é mais rápido lidar apenas com um conjunto. Ainda assim, é uma ideia interessante, que se alguém escolher usar um array como uma coleção de dados para algum big data que não tem duplicatas, pode ser vantajoso em termos de desempenho, se houver necessidade de remover muitos elementos em um operação, para converter a matriz em um conjunto, realizar a operação de remoção e converter o conjunto de volta em uma matriz.

Código de array:

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

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

OBSERVAÇÕES :

• As operações de conjunto podem ser entendidas como instantâneos dentro do fluxo de execução.
• Não estamos perante um substituto definitivo.
• Os elementos de uma classe Set não têm índices acessíveis.
• A classe Set é um complemento de classe Array , útil nos cenários em que precisamos armazenar uma coleção na qual aplicar operações básicas de adição, exclusão, verificação e iteração.

Eu compartilho alguns testes de desempenho. Tente abrir seu console e copiar e colar o código abaixo.

Criação de uma matriz (125.000)

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

1. Localizando um índice

Comparamos o método has de Set com Array indexOf:

Array / indexOf (0.281ms) | Definido / tem (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. Adicionando um novo elemento

Comparamos os métodos add e push dos objetos Set e Array, respectivamente:

Array / push (1.612ms) | Definir / adicionar (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. Excluindo um elemento

Ao excluir elementos, devemos ter em mente que Array e Set não iniciam em condições iguais. O array não possui um método nativo, portanto, uma função externa é necessária.

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

Leia o artigo completo aqui

Minha observação é que um Set é sempre melhor com duas armadilhas para grandes matrizes em mente:

a) A criação de Sets a partir de Arrays deve ser feita em um forloop com um comprimento pré-cache.

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

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

b) A iteração pode ser feita da mesma maneira porque também é mais rápida que um for ofloop ...

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

para uma comparação vida real para difference(), intersection(), union()e uniq()(+ seus companheiros iteratee etc.) com 40.000 elementos

Para a parte de iteração da sua pergunta, recentemente executei este teste e descobri que Set superou em muito um Array de 10.000 itens (cerca de 10x as operações poderiam acontecer no mesmo período de tempo). E dependendo do navegador, ou bateu ou perdeu para Object.hasOwnProperty em um teste semelhante.

Tanto Set quanto Object têm seu método "has" executando no que parece ser amortizado para O (1), mas dependendo da implementação do navegador, uma única operação pode demorar mais ou mais rápido. Parece que a maioria dos navegadores implementa a chave em Object mais rápido do que Set.has (). Mesmo Object.hasOwnProperty, que inclui uma verificação adicional na chave, é cerca de 5% mais rápido do que Set.has (), pelo menos para mim no Chrome v86.

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

Atualização: 11/11/2020: https://jsbench.me/irkhdxnoqa/2

Caso você queira executar seus próprios testes com diferentes navegadores / ambientes.

Da mesma forma, adicionarei um benchmark para adicionar itens a uma matriz em vez de definir e remover.

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

Essas três operações em itens de 10K me deram:

set: 7.787ms
array: 2.388ms