DEV Community: Guilherme Rodrigues

Removendo itens duplicados no JavaScript ES6

Guilherme Rodrigues — Wed, 08 Sep 2021 12:00:00 +0000

Acho que todo mundo assim como eu, em algum momento já teve que remover itens duplicados de uma lista Array, mas será que a forma que aprendemos é de fato a melhor?

Nesse artigo vou mostrar o meu ponto de vista, a forma que encontrei para remover itens duplicados de uma lista com mais de 1.000.000 de itens no meu dia a dia na @squidit, seja o array de tipos primitivos ou não

O jeito comum

Acredito que a forma mais comum que conhecemos é aquela que percorremos um Array e verificamos a cada interação se aquele item está ou não no novo array.

// loop-itens.js
/**
 * @desc Gera um array de tamanho N com números aleatórios, respeitando N
 * @param {number} length 
 */
function generateRandomArray(length) {
  return Array.from(Array(length), () => parseInt(Math.random() * length));
}

const randomList = generateRandomArray(1000) // Um array com 1000 números aleatórios
const uniqueList = [] // Lista de array único

for(const value of randomList) {
  // Caso o valor não esteja no uniqueList, adicionamos
  if (!uniqueList.includes(value)) uniqueList.push(value)
}
console.log(`uniqueList has ${uniqueList.length} itens`)

Que gera a seguinte saída:

Isso pode até funcionar para uma lista pequena de alguns milhares de itens.

Se utilizarmos o console.time e o console.timeEnd para verificar quanto tempo essa operação demora, veremos que é super rápido.

// Resto do código

console.time('Remove duplicated items') // Adicionamos 
for(const value of randomList) {
  // Verificação do código anterior...
}
console.timeEnd('Remove duplicated items')

Gera a seguinte saída:

O que aconteceria se por acaso aumentássemos esse Dataset? para uma lista com 100.000 de itens por exemplo?

// Resto do código ... 

// equivale a 10^5, que é o mesmo que 100.000
const randomList = generateRandomArray(10 ** 5) 
const uniqueList = [] // Lista que conterá arrays únicos

console.time('Remove duplicated items')
for(const value of randomList) {
  // Caso o valor não esteja no uniqueList, adicionamos
  if (!uniqueList.includes(value)) uniqueList.push(value)
}
console.timeEnd('Remove duplicated items')

Gera a seguinte saída:

E se aumentarmos para 200.000 por exemplo, o tempo já aumenta drasticamente

O problema

Usando o for ou .reduce a premissa ainda seria a mesma, que seria:

Iterar pelo array.
Verificar se o valor existe no novo array.
Adicionar no array.

Para cada iteração é necessário fazer uma segunda iteração no uniqueArray para verificar se existe o valor lá dentro, isso na programação é chamado de O(n)², onde n dita o número de operações que serão executadas na sua aplicação. Portanto o número de operações para esse algoritmo cresce de forma exponencial conforme o número de itens.

Vamos exemplificar com o código a seguir:

// Resto do código

// Itera 10 vezes de 10k em 10k até chegar em 100k
for (let length = 1; length <= 100000; length += 10000) {
  // Para cada interação, gera um novo array.
  const randomList = generateRandomArray(length)
  const uniqueList = [] // Lista que contera arrays único

  console.log(`List size of ${randomList.length}`)
  console.time(`Remove ${randomList.length} duplicated items`)
  for (const value of randomList) {
    // Caso o valor não esteja no uniqueList, adicionamos
    if (!uniqueList.includes(value)) uniqueList.push(value)
  }
  console.timeEnd(`Remove ${randomList.length} duplicated items`)
  console.log('---------')
}

É possível ver o tempo crescente de forma exponencial quando printamos quanto tempo leva para que a operação seja finalizada de acordo com o número de itens

Usando o Set

No Javascript temos um objeto chamado Set, ele garante que os valores sejam guardados uma única vez, ou seja, sempre que tentarmos adicionar um valor que está na estrutura, esse valor não sera adicionado.

const set = new Set();

set.add(1) // [1]
set.add(2) // [1,2]
set.add(3) // [1,2,3]
set.add(2) // [1,2,3]

console.log(set) // Set(3) { 1, 2, 3 }

O set aceita objetos também, porém não vai remover a duplicidade deles porque os objetos, como sabemos, são passados via referência no JavaScript:

const set = new Set();

set.add({ a: 1, b: 2 }) // Objeto é adicionado [{}]
set.add({ a: 10, b: 20}) // [{},{}]

// Por mais que os valores são iguais,
// o objeto ainda assim é diferente,
// pois ele está referenciado 
// em outro endereço de memoria
set.add({a: 1, b: 2}) // [{}, {}, {}]

console.log(set) // Set(3) { { a: 1, b: 2 }, { a: 10, b: 20 }, { a: 1, b: 2 } }

Usando Set para remover duplicidade

Quando usamos a API Set para remover itens duplicados de array, percebemos a diferença de tempo usando Set em relação do for.

/**
 * @desc Gera um array de tamanho N com números aleatórios, respeitando N
 * @param {number} length 
 */
function generateRandomArray(length) {
  return Array.from(Array(length), () => parseInt(Math.random() * length));
}

// Itera 10 vezes de 10k em 10k até chegar em 100k
for (let length = 1; length <= 100000; length += 10000) {
  // Para cada iteração, gera um novo array.
  const randomList = generateRandomArray(length)

  console.log(`List size of ${randomList.length}`)
  console.time(`Remove ${randomList.length} duplicated items using Set API`)
  const uniqList = Array.from(new Set(randomList))
  console.timeEnd(`Remove ${randomList.length} duplicated items using Set API`)
  console.log('---------')
}

Gera a seguinte saída:

Isso acontece porque, diferente do loop, precisamos iteirar o array n vezes, e em cada iteração a API Set garante que estamos adicionando um único valor, e pelo fato do objeto Set implementar a interface iterable, podemos transforma-lo em um Array

Array.from(new Set([1,2,3,4,1,2,3,4])) // Gera [1,2,3,4]

Duplicidade em uma lista de objetos

No mundo real sabemos que listas não são compostas só do tipo primitivo, como faríamos então para os objetos?

Ao invés de usarmos o Set, usamos o Map junto com o método .reduce da API Array, mas pra isso preciso dar um panorama do que é o Map

Maps

A estrutura do Map serve como uma estrutura de dados de Chave valor, ou HashTable que, de forma resumida, é uma lista de dados composta de chave valor, onde para cada item adicionado existe um id or key relacionado, sendo possível realizar uma busca rápida apenas usando a key, sem a necessidade de percorrer toda a lista para encontrar o item

const map = new Map()

map.set(1, { a: 1, b: 2, b: 3 }) // Map(1) { 1 => { a: 1, b: 3 } }
console.log(map)

map.set(2, { a: 10, b: 20, c: 30 }) // Map(2) { 1 => { a: 1, b: 3 }, 2 => { a: 10, b: 20, c: 30 } }
console.log(map)

// Sobrescreve o objeto na chave 1.
map.set(1, { a: 100 }) // Map(2) { 1 => { a: 100 }, 2 => { a: 10, b: 20, c: 30 } }

map.get(1) // { a: 100 }
map.get(2) // { a: 10, b: 20, c: 30 }
map.get(3) // undefined, pois na chave 3 não existe nada

E claro, o valor da chave não precisa ser necessariamente um valor numérico, pode ser qualquer tipo de dado:

const map = new Map()

map.set('samsung', ['S10', 'S20']) // Map(1) { 'samsung' => ['S10', 'S20'] }

map.set('outro valor', [2, 3, 4, 5]) // Map(2) { 'samsung' => ['S10', 'S20'], 'outro valor' => [2, 3, 4, 5] }

Usando Map para remover itens duplicados

Agora tendo uma ideia de como usar o Map podemos tirar vantagem do .reduce para gerar um array único a partir de uma lista com duplicidades.

Primeiro vamos criar uma função que gera uma lista com o mesmo objeto, variando apenas o id de cada item.

/**
 * @desc Gera uma lista com o mesmo objeto,
 * onde o id sera aleatório
 * @param {number} length 
 */
function generateRandomObjectList(length) {
  const defaultObject = {
    name: 'Guilherme',
    developer: true
  }
  return Array.from(Array(length), () => {
    const randomId = parseInt(Math.random() * length)
    return {
      ...defaultObject,
      id: randomId
    }
  });
}

Agora vamos criar um objeto Map a partir do array gerado,

onde o id do Map sera o id do usuario, assim removemos IDs duplicados da lista:

const listObjectWithRandomId = generateRandomObjectList(10 ** 5) // 100k
const objectMap = listObjectWithRandomId.reduce((map, object) => {
  map.set(object.id, object);
  return map
}, new Map())

Como o Map também um objeto iterável, basta usar a função Array.from:

const uniqList = Array.from(objectMap, ([_, value]) => value)

O código todo ficaria assim:

/**
 * @desc Gera uma lista com o mesmo objeto,
 * onde o id sera randômico
 * @param {number} length 
 */
function generateRandomObjectList(length) {
  const defaultObject = {
    name: 'Guilherme',
    developer: true
  }
  return Array.from(Array(length), () => {
    const randomId = parseInt(Math.random() * length)
    return {
      ...defaultObject,
      id: randomId
    }
  });
}

const listObjectWithRandomId = generateRandomObjectList(10 ** 5) // 100k

console.time('uniq List usando Map') // Pra contabilizar o tempo da operação
const objectMap = listObjectWithRandomId.reduce((map, object) => {
  map.set(object.id, object);
  return map
}, new Map())

const uniqList = Array.from(objectMap, ([_, value]) => value)
console.timeEnd('uniq List usando Map')
console.log(`Lista duplicada: ${listObjectWithRandomId.length}`)
console.log(`Lista duplicada: ${uniqList.length}`)

Conclusão

Por mais que libs como o lodash tenham funções para remover itens duplicados, importar uma lib inteira para resolver um problema que pode ser resolvido em algumas linhas de código de forma nativa acaba sendo não necessário.

Clonando objetos de forma segura no Javascript

Guilherme Rodrigues — Sat, 07 Mar 2020 04:52:48 +0000

Acredito que todos, assim como eu, já precisaram fazer uma cópia de um objeto no Javascript e, felizmente, temos diversas formas de copiar um objeto. Dentre as mais conhecidas temos o Object.assing e o Spread Operator

Object.assign

A primeira forma, e também a mais conhecida, é através do Object.assign que, basicamente, consiste em 2 argumentos. O primeiro é o objeto de destino, ou seja, o novo objeto que irá receber os valores do objeto original, o segundo é o objeto que você deseja copiar (que vamos chamar de objetoOrigem)..

var objetoOrigem = { name: 'Chandler Bing', animal: 'dog' }

var objetoClonado = Object.assign({}, objetoOrigem)

O método .assign retorna um novo objeto, sendo assim podemos alterar as propriedades do novo objeto sem alterar o objetoOrigem.

objetClonado.name = 'Joey Tribbiani'

console.log(objetoOrigem)
// { name: 'Chandler Bing', animal: 'dog' }

console.log(objetoClonado)
//  { name: 'Joey Tribbiani', animal: 'dog' }

Spread Operator

A segunda forma é conhecida como Spread Operator, que consiste em expandir as propriedades dentro do objeto (como string, números e array) para 1 ou n propriedades, em outras palavras, consiste em expandir um objeto maior em várias propriedades daquele objeto, no exemplo fica mais claro.

var array = [1,2,3]

var fn = function(a,b,c) {
  console.log(a,b,c)
  //  1 2 3
}

fn(...array)

Com o Spread Operator, eu posso quebrar o objeto original em n propriedades. Seguindo essa lógica poderiamos recuperar os atributos do objetoOrigem e construir um novo objeto chamado objetoClonado, veja no exemlo a seguir:

var objetoOrigem = { name: 'Chandler Bing' }

var objetoClonado = { ...objetoOrigem }

Beleza, então quando tentamos alterar o nome do novo objeto clonado, o objeto original ainda manteria com os mesmos valores.

objetoOrigem.name = 'Joey Tribbiani'

console.log(objetoOrigem)
//  { name: 'Chandler Bing' }

console.log(objetoClonado)
//  { name: 'Joey Tribbiani' }

No fim das contas o Spread Operator acaba se tornando um substituto para o Object.assing

Shallow clone

Tanto Objetct.assign quanto Spread, fazem um clone que chamamos de Shallow clone. Shallow clone copia apenas valores enumerados como String, Number e Array. Quando clonamos um objeto que possui uma chave cujo valor é outro objeto, o que o Shallow clone faz é copiar a referencia de memória para o novo objeto clonado, sendo assim, os dois objetos compartilham a mesma referência.

Deep clone

Deep clone se baseia em criar um novo objeto a partir do objeto original, criando uma nova referência de memória para os nested objects, caso exista. Existem algumas formas de fazer.

Shallow Clone vs Deep Clone

As duas formas funcionam muito bem, mas só quando estamos lidando com objetos simples, ou seja, objetos compostos de valores primitivos, quando começamos a lidar com objetos mais complexos onde temos nested objects ou funcões, qualquer uma das abordagens listada a cima se tornam inviáveis, o por que ? bem podemos ver em um exemplo real, vamos considerar o seguinte objeto.

var objetoOrigem = {
  name: 'Chandler Bing',
  age: 25,
  job: {
    name: 'Unknown'
  }
}

Ao clonarmos o objeto e modificar o nome do objeto clonado obteremos o seguinte resultado.

var objetoClonado = { ...objetoOrigem }

objetoClonado.name = 'Joey Tribbianiy'

console.log(objetoOrigem)
//  { name: 'Chandler Bing', age: 25, job: { name: 'Unknown' } }

console.log(objetoClonado)
//  { name: 'Joey Tribbiani', age: 25, job: { name: 'Unknown' }

Modificamos o objetoClonado sem alterar o objetoOrigem. Perfeito!

Agora vamos tentar modificar a propriedade job do objeto clonado

objetoClonado.job.name = 'Actor'

E ao verificar o valor temos a seguinte saida:

console.log(objetoOrigem)
//  { name: 'Chandler', age: 25, job: { name: 'Actor' } }

console.log(objetoClonado)
//  { name: 'Joe', age: 25, job: { name: 'Actor' } }

Ao alterar a propriedade objetoClonado.job alterou tanto para objetoClonado quanto para o objetoOrigem.

Deep Clone utilizando `JSON.stringify` e `JSON.parse`

Em alguns lugares você pode ter visto um deep clone usando o a implementaçãoJSON.stringify e JSON.parse. que consiste em transformar o seu objeto origem em JSON, e em seguida utilizando o JSON.parse para criar um novo objeto, como mostra o código a baixo.

var objetoOrigem = {
  name: 'Chandler',
  age: 25,
  job: {
    name: 'Unknown'
  },
  myNameAndJob() {
    return `My name is ${this.name} and I work as ${this.job.name}`
  }
}

Dessa vez criamos um objeto que possui uma função que retorna o name e o job em uma única string, agora vamos clonar o objeto.

var objetoClonado = JSON.parse(JSON.stringify(objetoOrigem))

E ao tentar modificar as propriedades do objeto clonado e executar a função myNameAndJob, gera a seguinte saída.

objetoClonado.name = 'Joe'
objetoClonado.job.name = 'Actor'

console.log(objetoOrigem.myNameAndJob())
//  My name is Chandler and I work as Unknown

console.log(objetoClonado.myNameAndJob())
//  console.log(objetoClonado.myNameAndJob())
//  TypeError: objetoClonado.myNameAndJob is not a function

O Erro foi gerado porque, ao utilizar o JSON.stringify no objeto criado, o resultado foi uma string da estrutura de dados do objeto original, ou seja, não existe funções no novo objeto, foi copiado apenas os atributos e os nested objects.

Isso também se torna um problema quando o seu objeto possui propriedades do tipo Date, por exemplo.

var objetoComDate = {
  name: 'Chandler',
  birthday: new Date('1994-01-01T00:00:00')
}

var objetoClonado = JSON.parse(JSON.stringify(objetoComDate))

Ao exibir os dois objetos, note a diferença

O Objeto objetoComDate possui a propriedade birthday como tipo Date, enquanto o objetoClonado transformou a propriedade Date em uma String contendo o valor da data.

Lodash

A forma mais indicada é usando funcionalidades de bibliotecas maduras, testadas e mantida pela comunidade como o Lodash, Lodash é uma biblioteca em Javascript que contém métodos utilitários para trabalhar com Arrays, Objects, String e Numbers.
Podemos instalar o lodash com o comando npm install lodash --save, o legal do Lodash é que podemos importar somente os métodos que vamos usar, assim não carregamos toda a biblioteca de forma necessária.
No Lodash temos um método que faz um deepClone de um objeto, podemos importar o cloneDeep de duas formas

A primeira forma é importar toda a biblioteca e usar o método desejado, como no exemplo abaixo.

var _ = require('lodash')

var objetoOrigem = {
  name: 'Chandler',
  age: 25,
  job: {
    name: 'Unknown'
  },
  myNameAndJob() {
    return `My name is ${this.name} and I work as ${this.job.name}`
  }
}

const objetoClonado = _.cloneDeep(objetoOrigem, {}, true)

A segunda forma é importando somente o método desejado da biblioteca

var _cloneDeep = require('lodash/cloneDeep')

var objetoOrigem = {
  name: 'Chandler',
  age: 25,
  job: {
    name: 'Unknown'
  },
  myNameAndJob() {
    return `My name is ${this.name} and I work as ${this.job.name}`
  }
}

const objetoClonado = _cloneDeep(objetoOrigem, {}, true)

Para qualquer uma das formas, o resultado final será o mesmo, ja que com o cloneDeep é possível clonar o objeto e seus nested objects de forma que o objeto clonado não possua nenhuma referencia compartilhada com o objetoOrigem, como no código abaixo.

var _cloneDeep = require('lodash/cloneDeep')

var objetoOrigem = {
  name: 'Chandler',
  age: 25,
  job: {
    name: 'Unknown'
  },
  myNameAndJob() {
    return `My name is ${this.name} and I work as ${this.job.name}`
  }
}

const objetoClonado = _cloneDeep(objetoOrigem, {}, true)

objetoClonado.name = 'Joe'
objetoClonado.job.name = 'Actor'

console.log(objetoOrigem.myNameAndJob())
//  My name is Chandler and I work as Unknown

console.log(objetoClonadoComClone.myNameAndJob())
//  My name is Joe and I work as Actor

Referencias

https://alligator.io/js/deep-cloning-javascript-objects/

https://flaviocopes.com/how-to-clone-javascript-object/

https://www.samanthaming.com/tidbits/70-3-ways-to-clone-objects/

DEV Community: Guilherme Rodrigues

Removendo itens duplicados no JavaScript ES6

O jeito comum

O problema

Usando o Set

Usando Set para remover duplicidade

Duplicidade em uma lista de objetos

Maps

Usando Map para remover itens duplicados

Conclusão

Clonando objetos de forma segura no Javascript

Object.assign

Spread Operator

Shallow clone

Deep clone

Shallow Clone vs Deep Clone

Deep Clone utilizando JSON.stringify e JSON.parse

Lodash

Deep Clone utilizando `JSON.stringify` e `JSON.parse`