Ускорение кода – мечта любого разработчика. 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.
Комментарии
Важно помнить, что создание set, происходит медленнее, чем arr.
У вас в первом примере различия с оригинальной статьей. Либо поменяйте, либо дайте обозначение функций checkArr() и checkSet()
Точно O(1) ? Вроде всегда эти вещи O(log n) были.
Set на основе Хеш-таблицы сделан