O autor do material, cuja tradução publicamos hoje, diz estar confiante de que muitos desenvolvedores de JavaScript usam principalmente tipos de dados como
Number ,
String ,
Object ,
Array e
Boolean . Na maioria dos casos, isso é suficiente. Mas se você precisar tornar o código o mais rápido e escalável possível, o uso desses tipos de dados nem sempre é justificado.
Neste artigo, falaremos sobre como, usando o tipo de dados
Set , que fornece a capacidade de trabalhar com coleções de valores exclusivos, tornar o código mais rápido. Isto é especialmente verdade para o código de projetos de grande escala. Os tipos
Array e
Set têm muito em comum, mas o uso do tipo de dados
Set pode fornecer ao programador recursos claramente manifestos durante a execução de programas que o tipo
Array não possui.
Qual é a diferença entre os tipos de dados Matriz e Conjunto?
A principal característica do tipo de dados
Array (chamaremos objetos desse tipo de "matrizes") é que matrizes são coleções de valores indexadas. Isso significa que os dados nas matrizes são armazenados usando índices.
const arr = [A, B, C, D]; console.log(arr.indexOf(A));
Diferentemente das matrizes, os objetos do tipo
Set (nós os chamaremos de "coleções") são coleções que contêm dados no formato de chave / valor. Em vez de usar índices, as coleções armazenam itens usando chaves. Os elementos armazenados na coleção podem ser classificados na ordem em que foram adicionados à coleção, enquanto a coleção não pode armazenar os mesmos elementos. Em outras palavras, todos os elementos da coleção devem ser exclusivos.
Quais são os principais pontos fortes das coleções?
Se você comparar coleções e matrizes, poderá encontrar algumas vantagens sobre coleções sobre matrizes, especialmente visíveis em situações nas quais o desempenho do programa é importante:
- Pesquise itens. Os métodos de matriz
indexOf() e includes() , usados para procurar elementos e verificar se um elemento tem um elemento, funcionam lentamente. - Removendo itens. Um item pode ser excluído na coleção com base em seu valor. Em uma matriz, o equivalente a essa ação seria usar o método
splice() , com base no índice do elemento. Como na pesquisa de itens, remover itens usando índices é uma operação lenta. - Inserir um item. É muito mais rápido adicionar um elemento à coleção do que usar métodos como
push() e unshift() em uma matriz. - Trabalhe com valor
NaN . O método indexOf() não pode ser usado para encontrar o valor de NaN em uma matriz. Ao usar o método de coleção has() , você pode descobrir se ele possui NaN . - Removendo itens duplicados. Objetos
Set armazenam apenas valores exclusivos. Se você precisar evitar salvar elementos duplicados em alguma estrutura de dados, essa é sua vantagem significativa sobre matrizes. Ao trabalhar com matrizes para remover elementos duplicados, seria necessário escrever um código adicional.
Uma lista completa de métodos internos de objetos do tipo
Set pode ser encontrada
aqui .
Sobre a complexidade temporal dos algoritmos
Os métodos que as matrizes usam para procurar elementos têm complexidade de tempo linear - O (N). Em outras palavras, o tempo de pesquisa do elemento é proporcional ao tamanho da matriz.
Diferentemente das matrizes, os métodos usados pelas coleções para localizar, excluir e adicionar elementos têm complexidade de tempo O (1). Isso significa que o tamanho da coleção praticamente não afeta o tempo de trabalho desses métodos.
Aqui você pode ler mais sobre a complexidade de tempo dos algoritmos.
Quão mais rápidas são as coleções do que as matrizes?
Embora os indicadores de desempenho do código JavaScript sejam fortemente influenciados por uma variedade de fatores, em particular, eles dependem do sistema em que o código é executado, do tempo de execução do código usado, do tamanho dos dados processados, espero que os resultados dos meus testes lhe dêem a oportunidade de comparar matrizes e coleções do ponto de vista prático, e entenda como as coleções são mais rápidas que as matrizes. Agora vamos considerar três testes simples e analisar seus resultados.
PreparationPreparação do teste
Antes de fazer qualquer teste, vamos criar uma matriz com um milhão de elementos e a mesma coleção. Por uma questão de simplicidade, usaremos um ciclo, cujo primeiro valor de contador será 0 e o último - 999999:
let arr = [], set = new Set(), n = 1000000; for (let i = 0; i < n; i++) { arr.push(i); set.add(i); }
No.Test No. 1: verificando a presença de um elemento em uma matriz e em uma coleção
Primeiro, verificamos a presença do elemento
123123 na matriz e na coleção, sabendo antecipadamente que esse elemento existe nessas estruturas de dados.
let result; console.time('Array'); result = arr.indexOf(123123) !== -1; console.timeEnd('Array'); console.time('Set'); result = set.has(123123); console.timeEnd('Set');
Aqui estão os resultados deste teste:
Array: 0.173ms Set: 0.023ms
A coleção é 7,54 vezes mais rápida que a matriz.
▍Teste n ° 2: inserção de um elemento
Agora vamos tentar adicionar elementos a matrizes e coleções.
console.time('Array'); arr.push(n); console.timeEnd('Array'); console.time('Set'); set.add(n); console.timeEnd('Set');
Aqui está o que aconteceu:
Array: 0.018ms Set: 0.003ms
A coleção é 6,73 vezes mais rápida que a matriz.
3Teste 3: excluir um item
Agora vamos remover o item de cada estrutura de dados (por exemplo, a que foi adicionada no teste anterior). As matrizes não possuem um método interno para excluir elementos; portanto, criaremos uma função auxiliar para manter nosso código em boas condições:
const deleteFromArr = (arr, item) => { let index = arr.indexOf(item); return index !== -1 && arr.splice(index, 1); };
E aqui está o código de teste:
console.time('Array'); deleteFromArr(arr, n); console.timeEnd('Array'); console.time('Set'); set.delete(n); console.timeEnd('Set');
O resultado é o seguinte:
Array: 1.122ms Set: 0.015ms
Nesse caso, a coleção foi 74,13 vezes mais rápida que a matriz!
Em geral, pode-se observar que o desempenho do código pode ser significativamente aumentado usando coleções em vez de matrizes. Considere alguns exemplos práticos.
Exemplo # 1: removendo valores duplicados de uma matriz
Se você precisar remover rapidamente valores duplicados de uma matriz, poderá convertê-lo em uma coleção. Esta é talvez a maneira mais fácil de se livrar de valores duplicados:
const duplicateCollection = ['A', 'B', 'B', 'C', 'D', 'B', 'C'];
Exemplo 2: tarefa de entrevista no Google
Em um dos meus
materiais, examinei quatro opções para responder à pergunta feita por um entrevistador do Google. A entrevista foi conduzida usando C ++, mas se o JavaScript fosse usado no lugar dessa linguagem, a estrutura de dados do
Set seria necessariamente usada na solução do problema.
Se você quiser entender a resposta a esta pergunta mais profundamente - leia o artigo acima. Aqui apenas mostro uma solução pronta.
▍ Tarefa
Dada uma matriz não classificada de números inteiros e um valor de
sum . Escreva uma função que retorne
true se, como resultado da adição de dois elementos dessa matriz, obtivermos o valor da
sum . Se não houver tais elementos na matriz, a função deve retornar
false .
Acontece, por exemplo, que se recebermos uma matriz
[3, 5, 1, 4] e o valor da
sum for
9 , a função retornará
true , pois
4+5=9 .
▍Solução
Você pode abordar esse problema usando a seguinte idéia: é necessário iterar sobre a matriz, criando a estrutura de dados
Set medida que ela passa, na qual serão adicionados valores que complementam os valores encontrados no valor da
sum .
Vamos analisar essa ideia usando o exemplo da matriz acima. Quando encontramos
3 , podemos adicionar o número
6 à coleção, pois sabemos que precisamos encontrar dois números que totalizam
9 . Então, toda vez que encontramos um novo valor da matriz, podemos verificar a coleção e ver se ela existe. Quando encontrarmos o número
5 , adicionaremos
4 à coleção. E quando, finalmente, chegamos ao número
4 , encontramos na coleção e podemos retornar
true .
Aqui está a aparência de uma solução para esse problema:
const findSum = (arr, val) => { let searchValues = new Set(); searchValues.add(val - arr[0]); for (let i = 1, length = arr.length; i < length; i++) { let searchVal = val - arr[i]; if (searchValues.has(arr[i])) { return true; } else { searchValues.add(searchVal); } }; return false; };
E aqui está uma solução mais concisa:
const findSum = (arr, sum) => arr.some((set => n => set.has(n) || !set.add(sum - n))(new Set));
Como a complexidade de tempo do método
Set.prototype.has() é O (1), o uso da estrutura de dados
Set para armazenar números que complementam os números encontrados na matriz com um determinado valor permite encontrar uma solução em tempo linear (O (N)).
Se a solução dependesse do método
Array.prototype.indexOf() ou do método
Array.prototype.includes() , a complexidade do tempo de cada um dos quais é O (N), a complexidade total do tempo do algoritmo seria O (N
2 ). Como resultado, ele se tornaria muito mais lento.
Sumário
Se você não encontrou o tipo de dados
Set em JavaScript antes, esperamos que agora, tendo uma idéia, você possa usá-lo com benefícios em seus projetos.
Caros leitores! Como você aplicaria a estrutura de dados do
Set no seu código?