A maneira mais rápida de remover itens duplicados de um array em js

Vamos supor que você tenha uma tarefa em que você precise remover itens duplicados de um array, considerando sempre o item com a data mais recente. Para simplificar, os objetos estão na estrutura { id: number, date: Date }.

Exemplo de array de entrada:

[
    { id: 3, date: '2023-01-03T00:00:00.000Z' },
    { id: 3, date: '2023-01-04T00:00:00.000Z' },
    { id: 4, date: '2023-01-02T00:00:00.000Z' },
    { id: 3, date: '2023-01-02T00:00:00.000Z' },
]

O resultado esperado seria um array com ids únicos

[
    { id: 3, date: '2023-01-04T00:00:00.000Z' },
    { id: 4, date: '2023-01-02T00:00:00.000Z' },
]

Você saberia tratar itens em larga escala com boa performance? Qual abordagem que te vem em mente para resolver o problema?

Para esse artigo, vamos gerar um array de dados aleatórios no formato de cima, pra testar a performance do código:

const randomInt = (limit) => Math.floor(Math.random() * limit);

const array = Array.from({ length: 100000 }).map((_, idx) => ({
    id: randomInt(100),
    date: new Date(2023, 0, randomInt(31), 0, 0, 0),
}));

Uma abordagem comum de se pensar para resolver esse problema é criar um método que filtre os itens do array utilizando um reduce, e/ou for. Para cada item do array verificamos se já existe aquele id no array, se não existir adicionamos ele, se existir verificamos o novo item é mais recente para substituí-lo

const removeDuplicates = (array) => {
  const uniqArray = [];
  for (let i = 0; i < array.length; i++) {
    const item = array[i];

    const index = uniqArray.findIndex((i) => i.id === item.id);

    if (index === -1) {
      uniqArray .push(item);
      continue;
    }

    if (item.date > uniqArray[index].date) {
      uniqArray[index] = item;
    }
  }
  return uniqArray;
}

Essa abordagem resolve o problema de uma forma relativamente simples. Podemos checar o tempo de execução que essa função leva para processar o arquivo de entrada que foi inicialmente gerado.

const startTime = new Date();
removeDuplicates(array);
console.log(`Took: ${new Date() - startTime}ms`)

35 milissegundos para processar 100.000 itens em um array, não é tão demorado, e pararmos pra pensar. Pois é, mas aí que vem a pegadinha do malandro. O problema dessa abordagem é que definitivamente não é a melhor. Isso porque temos 2 loops um dentro do outro, quanto maior a quantidade de dados diferentes, mais doloroso será para a triste máquina que ousar executar esse código.

Se olharmos para nossa base de dados, temos apenas 100 ids diferentes. O que significa que o segundo loop, no pior dos casos, vai fazer apenas 100 iterações. Também significa que quanto mais ids diferente existirem, maior o tempo de demora. Com 1.000 ids diferentes ele demora 170ms e com 10.000 demora 1379ms, sim, mais de um segundo.

O crescimento do tempo de execução é exponencial. Mas como melhorar esse algoritmo então?

Vamos ver o que o chatgpt acha:

Admito que por esse algoritmo eu não esperava, ele está ordenando o array pelo id. Dessa forma ele consegue fazer a checagem de um id por vez, sem necessidade de realizar o find e loopar entre todos os itens de um array desordenado. Sendo assim, para ilustrar, ele verificar primeiro o id 1, compara e percebe qual o mais recente e, quando vê que chegou no id 2, armazena o item de id 1 mais recente, aí começa a verificar o id 2 e assim segue até o fim.

Vamos começar a usar uma ferramenta para comparar os algoritmos, a que irei utilizar aqui será o perf link. Esse site permite iniciar uma massa de dados e comparar o tempo de execução entre cada uma das abordagens. O site realiza a mesma operação várias vezes, então a quantidade inicial do array que utilizaremos será um pouco menor, apenas 10.000, ao invés dos 100.000 iniciais, para minimizar o tempo de execução.

Irei comparar o caso de existirem apenas 10 ids únicos, que significa que quase toda a massa de dados consiste em itens duplicados, e com os ids variando entre 1 e 9.000, como a função gera números aleatórios pro id não dá pra garantir que apenas 1.000 estarão duplicados, mas garantimos que tem muita probabilidade de existirem muitos ids únicos.

Sem mais delongas, comparemos a performance das duas abordagens:

Cenário com apenas 10 ids:

Cenário com 9.000 ids:

A performance do código do GPT é pior nos cenários em que existem mais duplicidades e melhor nos cenários infinitamente superior nos cenários que existem pouca duplicidade.

Mas e se existisse uma terceira forma ainda melhor? Será possível?

Bom, quando criamos um objeto no javascript ele funciona como se fosse um "dicionário" de dados, trazendo referencia direta a todas as "chaves" vinculadas aos valores. Será que conseguimos tirar proveito dessa propriedade nesse caso?

const removeDuplicatesKeyMap = (array) => {
  const keyMap = {};
  for (let i = 0; i < array.length; i++) {
    const item = array[i];
    if (!keyMap[item.id]) {
      keyMap[item.id] = item;
      continue;
    }

    if (item.date > keyMap[item.id].date) {
      keyMap[item.id] = item;
    }
  }
  return Object.values(keyMap)
}

O código acima cria um objeto indexando as chaves como os ids do array e os valores como sendo a referência ao próprio objeto. Então o array se transformaria em algo como:

{
    3: { id: 3, date: '2023-01-04T00:00:00.000Z' },
    4: { id: 4, date: '2023-01-02T00:00:00.000Z' },
}

Sempre que precisarmos de um item do array podemos acessa-lo diretamente pelo seu index, como se fosse uma propriedade normal. keyMap[3] retornaria o objeto { id: 3, date: '2023-01-04T00:00:00.000Z' }. Assim seria possível facilmente acessar todos os itens de acordo com o id de cada item.

Ok, a teoria parece boa, vamos ver na prática:

Com 10 ids diferentes:

Com 9.000 ids diferentes:

💥 Booooom 💥, toma essa GPT, hoje você foi superado!!!
(só hoje hahaha)

Achei bem interessante quando descobri essa técnica, pesquisei outras abordagens para resolver esse problema, mas essa foi a melhor que consegui pensar.

Essa técnica também pode ser usada para um in memory join, quando necessário.

Lembrando que existem muitas outras formas de melhorar a arquitetura das aplicações para que não seja necessário executar tantos itens de uma vez. Mas performance de código, na minha visão, nunca é demais!

O que aconselho a levar desse artigo é sempre tentar entender e explorar formas diferentes de resolver o mesmo problema.

Você conhece conhecia essa estratégia? conhece outras estratégias para resolver o mesmo problema? compartilha com a gente aí em baixo 👇

aqui tem o link para acessar ao cenário gpt vs keymap