A maneira mais rápida de remover itens duplicados de um array em js
Tags: javascript, performance, typescript
Published: 2023-08-02 23:09:05

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

![Tempo de execução 35ms](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/cvxq3l5skeqvslusyxac.png)
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. 

![gráfico execução](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/9w80k1mhracx4q0hziua.png)

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

Vamos ver o que o chatgpt acha: 

![Ideia do gpt](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/apxlb8xtazrta45rmoyo.png)

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](https://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:
![array_find_100_gpt_56](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/g0if58r61zoggmiqyuu8.png)

Cenário com 9.000 ids: 
![array_find_2_gpt_100](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/sgtl3038rigy9e0cxq6b.png)

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:
![gpt_40_keymap_100](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/sel7wph0huhkpf7qlbcq.png)

Com 9.000 ids diferentes:
![gpt_88_keymap_100](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/aikjkqlt567xrr9emmuh.png)

💥  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](https://perf.link/#eyJpZCI6IjJtZjBvaTNhdGdsIiwidGl0bGUiOiJHUFQgU29ydCB2cyBLZXlNYXAiLCJiZWZvcmUiOiJjb25zdCByYW5kb21JbnQgPSAobGltaXQpID0%2BIE1hdGguZmxvb3IoTWF0aC5yYW5kb20oKSAqIGxpbWl0KTtcblxuY29uc3QgYmFzZUFycmF5ID0gQXJyYXkuZnJvbSh7IGxlbmd0aDogMTAwMDAgfSk7XG5jb25zdCBhcnJheSA9IGJhc2VBcnJheS5tYXAoKF8sIGlkeCkgPT4gKHtcbiAgICBpZDogcmFuZG9tSW50KDkwMDApLFxuICAgIGRhdGU6IG5ldyBEYXRlKDIwMjMsIDAsIHJhbmRvbUludCgzMSksIDAsIDAsIDApLFxufSkpOyIsInRlc3RzIjpbeyJuYW1lIjoic29ydGVkIiwiY29kZSI6ImNvbnN0IHJlbW92ZUR1cGxpY2F0ZVdpdGhMYXRlc3REYXRlID0gKGFycikgPT4ge1xuICBjb25zdCBzb3J0ZWRBcnJheSA9IGFyci5zb3J0KChhLCBiKSA9PiB7XG4gICAgaWYgKGEuaWQgIT09IGIuaWQpIHtcbiAgICAgIHJldHVybiBhLmlkIC0gYi5pZDtcbiAgICB9XG4gICAgcmV0dXJuIGIuZGF0ZSAtIGEuZGF0ZTtcbiAgfSk7XG5cbiAgY29uc3QgdW5pcXVlQXJyYXkgPSBbXTtcbiAgbGV0IGN1cnJlbnRJZCA9IG51bGw7XG4gIGxldCBsYXRlc3RJdGVtID0gbnVsbDtcblxuICBmb3IgKGNvbnN0IGl0ZW0gb2Ygc29ydGVkQXJyYXkpIHtcbiAgICBpZiAoY3VycmVudElkICE9PSBpdGVtLmlkKSB7XG4gICAgICBpZiAobGF0ZXN0SXRlbSkge1xuICAgICAgICB1bmlxdWVBcnJheS5wdXNoKGxhdGVzdEl0ZW0pO1xuICAgICAgfVxuICAgICAgY3VycmVudElkID0gaXRlbS5pZDtcbiAgICAgIGxhdGVzdEl0ZW0gPSBpdGVtO1xuICAgIH1cbiAgfVxuXG4gIGlmIChsYXRlc3RJdGVtKSB7XG4gICAgdW5pcXVlQXJyYXkucHVzaChsYXRlc3RJdGVtKTtcbiAgfVxuXG4gIHJldHVybiB1bmlxdWVBcnJheTtcbn07XG5jb25zdCB1bmlxdWVBcnJheSA9IHJlbW92ZUR1cGxpY2F0ZVdpdGhMYXRlc3REYXRlKGFycmF5KTsiLCJydW5zIjpbNTIzLDU3MSw0NzYsNDI4LDQ3Niw1NzEsNTIzLDQ3Niw2MTksMzgwLDYxOSw1NzEsNDc2LDUyMywzMzMsMzMzLDQyOCw1MjMsNTcxLDUyMyw1NzEsNDc2LDUyMyw1MjMsNTcxLDQ3Niw2MTksNTcxLDYxOSw0NzYsNTcxLDU3MSw1MjMsNTIzLDQyOCw2MTksNTcxLDQ3Niw0NzYsNjE5LDYxOSw1NzEsNTcxLDM4MCw1NzEsNTIzLDU3MSw1NzEsNTIzLDUyMyw1NzEsNTcxLDQyOCw2MTksNTcxLDU3MSw0NzYsMzMzLDU3MSw1NzEsNTcxLDYxOSw1NzEsNTcxLDUyMyw1MjMsNTcxLDYxOSw1NzEsNTIzLDYxOSw0MjgsNTcxLDYxOSwzMzMsNTcxLDM4MCw1MjMsNTIzLDUyMyw0NzYsNTcxLDU3MSw1MjMsNjE5LDYxOSw1MjMsNTcxLDUyMyw1MjMsNjE5LDUyMyw2NjYsNTIzLDI4NSwxOTAsMjM4LDIzOCwyMzgsMzgwXSwib3BzIjo1MTZ9LHsibmFtZSI6IktleU1hcCIsImNvZGUiOiJjb25zdCBrZXlNYXAgPSB7fTtcbmZvciAobGV0IGkgPSAwOyBpIDwgYXJyYXkubGVuZ3RoOyBpKyspIHtcbiAgICBjb25zdCBpdGVtID0gYXJyYXlbaV07XG4gICAgaWYgKCFrZXlNYXBbaXRlbS5pZF0pIHtcbiAgICAgICAga2V5TWFwW2l0ZW0uaWRdID0gaXRlbTtcbiAgICAgICAgY29udGludWU7XG4gICAgfVxuXG4gICAgaWYgKGtleU1hcFtpdGVtLmlkXS5kYXRlIDwgaXRlbS5kYXRlKSB7XG4gICAgICAgIGtleU1hcFtpdGVtLmlkXSA9IGl0ZW07XG4gICAgfVxufVxuY29uc3QgdW5pcXVlQXJyYXkgPSBPYmplY3QudmFsdWVzKGtleU1hcCkiLCJydW5zIjpbNjE5LDU3MSw1NzEsNTIzLDUyMyw2MTksNTcxLDU3MSw1MjMsNDc2LDYxOSw2NjYsNTcxLDY2Niw1MjMsMzgwLDYxOSw1NzEsNjY2LDYxOSw2MTksNTcxLDY2Niw2MTksNjE5LDU3MSw2NjYsNjE5LDY2Niw1MjMsNjY2LDYxOSw1NzEsNTIzLDQ3Niw2NjYsNTIzLDYxOSw1NzEsNzE0LDY2Niw2MTksNjE5LDU3MSw2MTksNjY2LDY2Niw1NzEsNjE5LDYxOSw2NjYsNjY2LDU3MSw2MTksNjE5LDYxOSw1NzEsNDI4LDY2Niw1NzEsNjY2LDY2Niw2MTksNjE5LDYxOSw2MTksNjE5LDcxNCw2NjYsNTcxLDYxOSw2MTksNTcxLDY2Niw1NzEsNjE5LDUyMyw2MTksNjE5LDYxOSw1MjMsNTIzLDYxOSw1NzEsNjY2LDYxOSw2MTksNjE5LDYxOSw2MTksNjE5LDU3MSw3MTQsNTcxLDQyOCwzMzMsMzMzLDM4MCwzODAsNDc2XSwib3BzIjo1OTB9XSwidXBkYXRlZCI6IjIwMjMtMDgtMDJUMjM6MDk6MzEuNjI1WiJ9)