Хватит использовать массивы! Как JavaScript Set ускоряет код

10
13381
Добавить в избранное

Ускорение кода – мечта любого разработчика. JavaScript Set делает код быстрее. Не верите? Тогда смотрите, как и насколько.

Разработчики, которые знают JavaScript основы, придерживаются базовых глобальных объектов: чисел, строк, объектов, массивов и логических значений.

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

Вот JavaScript примеры, что покажут, как объекты Set делают код быстрее. Поведение массивов и объектов Set пересекается. Однако использование Set часто приносит преимущества во времени выполнения, которых невозможно достичь с помощью массивов.

Чем отличаются объекты Set?

Главное отличие в том, что массивы – индексированные коллекции. Так что значения в массиве упорядочиваются по индексу.

А вот объекты Set – коллекция ключей. Вместо использования индексов, Set упорядочивает значения с использованием ключей. Элементы Set итерируются в порядке вставки. Дубликаты значений не вставляются. Таким образом, каждый элемент в коллекции уникальный.

Как объекты Set улучшают программирование JavaScript?

В прямом сравнении Set превосходят массивы, особенно когда дело касается ускорения времени выполнения:

  • Поиск элемента: использование indexOf() или includes() для проверки элемента в массиве выполняется медленно.
  • Удаление элемента: в Set удаляем элемент по значению. В массиве используем эквивалент splice() на основе индекса элемента. Как и в предыдущем пункте, получаем замедление из-за зависимости от индексов.
  • Вставка элемента: быстрее добавить элемент в Set, чем добавить элемент в массив с использованием push(), unshift() или аналогичного метода.
  • Хранение NaN: нельзя использовать indexOf() или includes(), чтобы найти значение NaN в массиве, а Set способен хранить это значение.
  • Удаление дубликатов: объекты Set хранят только уникальные значения. Не нужны дубликаты? Пользуйтесь этим преимуществом в сравнении с массивами, где для обработки дубликатов потребуется дополнительный код.

Примечание. Для получения полного списка встроенных методов Set лучше обратиться к веб-документации MDN.

Чему равна временная сложность?

Методы, которые массив использует для поиска, удаления и вставки элементов, работают с линейной временной сложностью O(N). Другими словами, время выполнения увеличивается с той же скоростью, что и размер данных.

Эквивалентные методы, которые используются по отношению к объектам Set, характеризуются временной сложностью O(1) . Это означает, что размер данных мало влияет на время выполнения методов.

Насколько быстрее объекты Set?

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

Подготовка тестов

Прежде чем запускать тесты, давайте создадим массив и Set из миллиона записей каждый. Для простоты начнём с 0 и будем считать до 999 999.

Тест 1: поиск элемента

Сначала найдём номер 123123, который, как знаем, вернёт true.

  • Массив: 0,173 мс
  • Set: 0,023 мс
  • Set в 7,54 раза быстрее

Тест 2: добавление элемента

Теперь добавим новый элемент в каждую коллекцию.

  • Массив: 0,018 мс
  • Set: 0,003 мс
  • Set в 6,73 раза быстрее

Тест 3: удаление элемента

В завершение удалим элемент из каждой коллекции. Используем только что добавленный. Для этого у массива нет встроенного метода, поэтому создадим вспомогательную функцию для чистоты:

А вот код JavaScript JS для теста:

  • Массив: 1,122 мс
  • Set: 0,015 мс
  • В этом случае Set оказался в 74,13 раза быстрее!

Оценили, как использование объектов Set вместо массивов положительно сказывается на времени выполнения? Теперь давайте посмотрим на JavaScript примеры кода и полезность Set с практической точки зрения.

Случай 1: удаление повторяющихся значений из массива

Если хотите быстро удалить повторяющиеся значения из массива, преобразуйте его в Set. Это общепринятый и краткий способ отфильтровать уникальные значения:

Случай 2: вопрос с интервью Google

Интервью проводилось с использованием C++, но если бы там использовался язык программирования JavaScript, Set стал бы необходимой частью окончательного решения.

Вопрос

Дано неупорядоченный массив целых чисел и значение sum. Верните true, если сумма любых двух элементов равняется значению sum. В противном случае верните false.

Итак, если получили массив [3, 5, 1, 4] и значение 9, наша функция вернёт true, потому что 4 + 5 = 9.

Решение

Правильный подход к этому вопросу – перебирать JavaScript массив и параллельно заполнять Set комплементарными дополнениями.

Теперь применим это к примеру выше. Когда сталкиваемся с 3, добавляем 6 к нашей коллекции комплементов, потому что знаем, что искомое значение sum равно 9. Затем для каждого нового элемента в массиве проверяем, входит ли это значение в Set дополнений. Когда дойдём до 5, добавим 4 к набору комплементов. Когда же встретимся с 4, также находим значение в Set и возвращаем true.

Далее используем JavaScript основы и получаем решение:

И сокращённый вариант:

Поскольку Set.prototype.has() работает с временной сложностью O(1), использование Set для хранения комплементов вместо массива даёт нашему общему решению линейное время выполнения O(N).

Если бы вместо этого зависели от Array.prototype.indexOf() или Array.prototype.includes(), оба из которых с временной сложностью O(N), итоговое время выполнения составило бы O(N²). Намного медленнее.

Никогда не интересовали объекты Set языка JavaScript? Надеемся, теперь вы увидели, насколько полезны коллекции.

Это перевод статьи на Medium.

Ещё интересные материалы по теме:

Интересуетесь фронтендом?

Подпишитесь на нашу рассылку, чтобы получать больше интересных материалов:

И не беспокойтесь, мы тоже не любим спам. Отписаться можно в любое время.




Комментариев: 10

  1. Андрей Захаров

    Такие тесты производительности не работают. Чтобы получить хотя бы какой-то осмысленный результат, можно замерить, например, добавление/удаление 1000 или 1000000 элементов. Тогда станет видно, что, например, в Тесте 2 реально быстрее работает Array, а не Set. Что логично, так как добавление в Set не может работать быстрее, чем добавление в конец списка

  2. Есть же метод .pop() удаляющий последнее значение из массива

  3. Roman Kuznetsov

    Это все хорошо работает с простыми типами, пока нет коллекции объектов.
    Хранить объекты в Set нет смысла.
    А ведь чаще всего мы получаем именно сложные json данные и с ними работаем.

  4. Irina Nikolaidi

    Опечатка. Метод называется includes, а не include.

    1. Спасибо за внимательность 🙂

  5. Но ведь это фундаментально разные коллекции! В сет ты два одинаковых элемента не добавишь( Смысл их сравнивать вообще тогда?

    1. Вы правы. Но зачастую люди юзают привычный им инструмент, и чаще всего это именно массивы. Там, где можно использовать сет, лучше использовать сет.

  6. Не хватает сравнение скорости итерации…

  7. Сергей Некрасов

    Почему нет теста при заполнении массива и набора? Или результат не в пользу набора?

    1. В англоязычном источнике данный тест, увы, отсутствует.

Добавить комментарий