Хватит использовать массивы! Как 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.