Цель этой статьи — поделиться с вами лучшими способами удаления повторяющихся значений 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 г.