Removing duplicate items in JavaScript ES6

I think everyone, like me, has had to remove duplicate items from an Array list at some point, but is the way we learned really the best?

In this article I’ll show my point of view, the way I found to remove duplicate items from a list with more than 1,000,000 items in my day-to-day work at @squidit, whether the array is of primitive types or not

The common way#

I believe the most common way we know is the one where we traverse an Array and check at each iteration whether that item is or is not in the new array.

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

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

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

Which generates the following output:

This might work for a small list of a few thousand items.

If we use console.time and console.timeEnd to check how long this operation takes, we’ll see it’s very fast.

1
//  Resto do código
2

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

Generates the following output:

Print-Tempo-Para-Remover-Itens-Duplicados

What would happen if we increased that dataset, for example, to a list with 100,000 items?

1
//  Resto do código ...
2

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

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

Generates the following output:

Print-tempo-para-remover-itens-duplicados-com-100k

And if we increase it to 200,000, for example, the time increases drastically

Print-tempo-para-remover-itens-duplicados-com-200k

The problem#

Using for or .reduce, the premise would still be the same, which is:

Iterate through the array.
Check if the value exists in the new array.
Add to the array.

For each iteration it is necessary to do a second iteration in uniqueArray to check if the value exists there, this in programming is called O(n)², where n dictates the number of operations that will be executed in your application. Therefore the number of operations for this algorithm grows exponentially as the number of items increases.

Let’s illustrate with the following code:

1
// Resto do código
2

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

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

It’s possible to see the time growing exponentially when we print how long it takes for the operation to finish according to the number of items

Print-duracao-tempo-para-remover-itens-duplicadas-de-forma-exponencial

Using Set#

In JavaScript we have an object called Set, it guarantees that values are stored only once, that is, whenever we try to add a value that is in the structure, that value will not be added.

1
const set = new Set();
2

3
set.add(1) // [1]
4
set.add(2) // [1,2]
5
set.add(3) // [1,2,3]
6
set.add(2) // [1,2,3]
7

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

The set accepts objects as well, but it won’t remove the duplicates because objects, as we know, are passed by reference in JavaScript:

1
const set = new Set();
2

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

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

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

Using Set to remove duplicates#

When we use the Set API to remove duplicate items from an array, we notice the time difference using Set compared to for.

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

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

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

Generates the following output:

Print de tempo para remover itens duplicados usando Set

This happens because, unlike the loop, we need to iterate the array n times, and in each iteration the Set API guarantees that we are adding a single value, and because the Set object implements the iterable interface, we can transform it into an Array

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

Duplicates in an object list#

In the real world we know that lists are not composed only of primitive type, so how would we do it for objects?

Instead of using Set, we use Map together with the .reduce method from the Array API, but for that I need to give an overview of what Map is

Maps#

The Map structure serves as a key-value data structure, or HashTable that, in short, is a list of key-value data, where for each item added there is a related id or key, making it possible to perform a quick search just by using the key, without the need to traverse the entire list to find the item

1
const map = new Map()
2

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

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

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

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

And of course, the key value doesn’t necessarily have to be a numeric value, it can be any type of data:

1
const map = new Map()
2

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

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

Using Map to remove duplicate items#

Now that we have an idea of how to use Map we can take advantage of .reduce to generate a unique array from a list with duplicates.

First let’s create a function that generates a list with the same object, varying only the id of each item.

1
/**
2
 * @desc Gera uma lista com o mesmo objeto,
3
 * onde o id sera aleatório
4
 * @param {number} length
5
 */
6
function generateRandomObjectList(length) {
7
  const defaultObject = {
8
    name: 'Guilherme',
9
    developer: true
10
  }
11
  return Array.from(Array(length), () => {
12
    const randomId = parseInt(Math.random() * length)
13
    return {
14
      ...defaultObject,
15
      id: randomId
16
    }
17
  });
18
}

Now let’s create a Map object from the generated array, where the id of the Map will be the id of the user, so we remove duplicate IDs from the list:

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

Since Map is also an iterable object, we just need to use the Array.from function:

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

The complete code would look like this:

1
/**
2
 * @desc Gera uma lista com o mesmo objeto,
3
 * onde o id sera randômico
4
 * @param {number} length
5
 */
6
function generateRandomObjectList(length) {
7
  const defaultObject = {
8
    name: 'Guilherme',
9
    developer: true
10
  }
11
  return Array.from(Array(length), () => {
12
    const randomId = parseInt(Math.random() * length)
13
    return {
14
      ...defaultObject,
15
      id: randomId
16
    }
17
  });
18
}
19

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

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

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

Print do tempo para remover itens duplicados usando Map

Conclusion#

Even though libraries like lodash have functions to remove duplicate items, importing an entire lib to solve a problem that can be solved in a few lines of code natively ends up being unnecessary.