Цель этой статьи — поделиться с вами лучшими способами удаления повторяющихся значений PRIMITIVE (строки, числа и логические значения) из массива в Javascript и сравнить их производительность с точки зрения времени выполнения.

Скоро выйдет статья о том, как удалить повторяющиеся объекты по определенному свойству.

НАБОР

Один из моих любимых (и простых) подходов — использование структуры данных SET.

Если вы не знакомы с ним, SET похож на обычный массив с некоторыми отличиями. Одна из них заключается в том, что вам разрешено хранить там только уникальные значения, а не массив, где допускаются дубликаты.

Подробнее о SET можно прочитать здесь — https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set

Мы можем воспользоваться этим, чтобы удалить все дубликаты.

const arr = [1,2,3,4,5,5,5,5,5]; 
const uniqueArray = Array.from(new Set(arr)); 
// OR 
const uniqueArray = [...new Set(arr)]; 
// result for both of them is [1,2,3,4,5]

Здесь важно то, что при создании набора с помощью new Set(arr) возвращаемое значение имеет тип «SET». Мы должны преобразовать его обратно в массив (если захотим) с помощью метода Array.from или оператора расширения «…»

Фильтр

Второй подход, который мы можем использовать, это метод javascript .filter.

const arr = [1,2,3,4,5,5,5,5,5]; 
const uniqueArray = arr.filter((el, idx) => arr.indexOf(el) === idx);

Здесь мы перебираем исходный массив и быстро проверяем каждый элемент. Первая позиция этого элемента равна текущему индексу элемента. Если они равны, это означает, что этот элемент уникален, т.е. возвращает true и элемент будет добавлен в новый массив.

Как вы уже заметили, у нас есть вложенная итерация по массиву. Первый — .filter, а следующий — .indexOf, оба используют простые циклы for за сценой.

В случае большого массива это может стать проблемой, так как временная сложность n^n

Для/для каждого

И последний — использование цикла forEach/for и самостоятельное построение логики проверки дубликатов.

Поскольку мне действительно любопытно, есть ли разница в производительности между forEach и for, я реализую оба решения и сравню время их выполнения.

-Для каждого

const arr = [1,2,3,4,5,5,5,5,5]; 
let lookup = {}; 
let uniqueArr = []; 
arr.forEach(function(el) { 
  if(!lookup[el]) { 
    lookup[el] = true; 
    uniqueArr.push(el); 
  } 
});
  • За
const arr = [1,2,3,4,5,5,5,5,5]; 
let lookup = {}; 
let uniqueArr = []; 
for(let i=0; i<arr.length; i++) { 
  if(!lookup[arr[i]]) { 
    lookup[arr[i]] = true; 
    uniqueArr.push(arr[i]); 
  } 
}

Да, я знаю, что это выглядит немного некрасиво.. 🙂

Здесь действительно важно упомянуть, что это решение работает, как и ожидалось, для массива с элементами одного типа. С элементами типа строка ИЛИ номер типа. Не со смешанными. Я имею в виду, что если мы применим этот подход к следующему массиву [1,’1’), результатом будет [1]. Это связано с тем, что мы используем ключи объектов поиска для проверки существующих, но ключи объектов имеют тип строки.

Если ваш случай со смешанными типами, вы можете расширить его и разделить значения в разных объектах в зависимости от типа.

Вот обещанное сравнение производительности

Я сравниваю время выполнения всех вышеперечисленных методов для разных длин массивов — 10, 1 000, 10 000, 100 000 и 1 000 000.

Все приведенные ниже тесты выполняются в Google Chrome с теми же входными данными. Результаты в миллисекундах.

Вывод

Как вывод из диаграмм производительности, мы можем сказать, что SET определенно является победителем и самым быстрым для нашей задачи. Однако, как вы можете видеть, разница между всеми ними не так велика, и все четыре смогут выполнять работу по удалению дубликатов молниеносно быстро.

Имейте в виду, что SET — это структура данных, выпущенная в ES6, а Filter и ForEach — в ES5. Если вы работаете над проектом с другой (старой) версией Javscript, возможно, вам придется использовать старомодный способ For.

Удачи!

Первоначально опубликовано на firstclassjs.com 20 февраля 2019 г.