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

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

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

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

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

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

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

const arr = [A, B, C, D];
console.log(arr.indexOf(A)); // Результат: 0
console.log(arr.indexOf(C)); // Результат: 2

А вот объекты 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.

let arr = [], set = new Set(), n = 1000000;
for (let i = 0; i < n; i++) {
  arr.push(i);
  set.add(i);
}

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

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

console.time('Array'); 
result = checkArr(arr, 123123); 
console.timeEnd('Array');
console.time('Set'); 
result = checkSet(set, 123123); 
console.timeEnd('Set');

• Массив: 0,173 мс
• Set: 0,023 мс

• Set в 7,54 раза быстрее

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

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

console.time('Array'); 
arr.push(n);
console.timeEnd('Array');
console.time('Set'); 
set.add(n);
console.timeEnd('Set');

• Массив: 0,018 мс
• Set: 0,003 мс

• Set в 6,73 раза быстрее

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

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

const deleteFromArr = (arr, item) => {
  let index = arr.indexOf(item);
  return index !== -1 && arr.splice(index, 1);
};

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

console.time('Array'); 
deleteFromArr(arr, n);
console.timeEnd('Array');
console.time('Set'); 
set.delete(n);
console.timeEnd('Set');

• Массив: 1,122 мс
• Set: 0,015 мс

• В этом случае Set оказался в 74,13 раза быстрее!

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

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

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

const duplicateCollection = ['A', 'B', 'B', 'C', 'D', 'B', 'C'];
// Если хотите превратить массив в Set
let uniqueCollection = new Set(duplicateCollection);
console.log(uniqueCollection) // Результат: Set(4) {"A", "B", "C", "D"}
// Если хотите сохранить значения в массиве
let uniqueCollection = [...new Set(duplicateCollection)];
console.log(uniqueCollection) // Результат: ["A", "B", "C", "D"]

Случай 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 основы и получаем решение:

const findSum = (arr, val) => {
  let searchValues = new Set();
  searchValues.add(val - arr[0]);
  for (let i = 1, length = arr.length; i < length; i++) {
    let searchVal = val - arr[i];
    if (searchValues.has(arr[i])) {
      return true;
    } else {
      searchValues.add(searchVal);
    }
  };
  return false;
};

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

const findSum = (arr, sum) =>
  arr.some((set => n => set.has(n) || !set.add(sum - n))(new Set));

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

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

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

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

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

• 12 JavaScript-трюков, которым не учат новичков
• TOП-12 JavaScript-концепций: от ссылок до асинхронных операций
• Токенизатор математических выражений на JavaScript