Ускоряем JavaScript-код с использованием типа данных Set

Автор материала, перевод которого мы сегодня публикуем, говорит, что уверен в том, что многие JavaScript-разработчики пользуются, в основном, такими типами данных, как Number, String, Object, Array и Boolean. В большинстве случаев этого вполне достаточно. Но если нужно сделать код как можно более быстрым и масштабируемым, применение этих типов данных не всегда оправдано.



В этом материале мы поговорим о том, как, пользуясь типом данных Set, предоставляющим возможность работать с коллекциями уникальных значений, сделать код быстрее. Особенно это актуально для кода крупномасштабных проектов. У типов Array и Set много общего, но использование типа данных Set способно дать программисту такие возможности, ярко проявляющиеся во время выполнения программ, которых нет у типа Array.

Чем различаются типы данных Array и Set?

Главной особенностью типа данных Array (мы будем называть объекты этого типа «массивами») заключается в том, что массивы — это индексированные коллекции значений. Это означает, что данные в массивах хранятся с использованием индексов.

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

В отличие от массивов, объекты типа Set (мы будем называть их «коллекциями») представляют собой коллекции, содержащие данные в формате ключ/значение. Вместо использования индексов коллекции хранят элементы, пользуясь ключами. Элементы, хранящиеся в коллекции, можно перебирать в порядке их добавления в коллекцию, при этом коллекция не может хранить одинаковые элементы. Другими словами, все элементы коллекции должны быть уникальными.

В чём заключаются основные сильные стороны коллекций?

Если сравнить коллекции и массивы, то у коллекций можно обнаружить некоторые преимущества перед массивами, особенно заметные в ситуациях, в которых важна производительность программ:

• Поиск элементов. Методы массивов indexOf() и includes(), используемые для поиска элементов и проверки того, имеется ли в массиве некий элемент, работают медленно.
• Удаление элементов. В коллекции элемент можно удалить, опираясь на его значение. В массиве эквивалентом подобного действия будет использование метода splice(), основанное на индексе элемента. Как и в случае с поиском элементов, удаление элементов с использованием индексов это медленная операция.
• Вставка элемента. Гораздо быстрее добавить элемент в коллекцию, чем, используя методы наподобие push() и unshift(), в массив.
• Работа со значением NaN. Метод indexOf() нельзя использовать для поиска значения NaN в массиве, в то время как с помощью метода коллекции has() можно выяснить, имеется ли в ней NaN.
• Удаление дублирующихся элементов. Объекты типа Set хранят только уникальные значения. Если вам нужно избежать сохранения в некоей структуре данных дублирующихся элементов, то в этом заключается их значительное преимущество перед массивами. При работе с массивами для удаления дублирующихся элементов пришлось бы писать дополнительный код.

Полный список встроенных методов объектов типа Set можно найти здесь.

О временной сложности алгоритмов

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

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

Здесь можно почитать подробности о временной сложности алгоритмов.

Насколько коллекции быстрее массивов?

Хотя на показатели производительности JavaScript-кода сильно влияют самые разные факторы, в частности, они зависят от системы, на которой запускают код, от используемой среды выполнения кода, от размера обрабатываемых данных, я надеюсь, результаты моих тестов дадут вам возможность сравнить массивы и коллекции с практической точки зрения, и понять, насколько коллекции быстрее массивов. Сейчас мы рассмотрим три простых теста и проанализируем их результаты.

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

Прежде чем выполнять какие-либо тесты, давайте создадим массив с миллионом элементов и такую же коллекцию. Ради простоты мы будем пользоваться циклом, первым значением счётчика которого будет 0, а последним — 999999:

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

▍Тест №1: проверка наличия элемента в массиве и в коллекции

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

let result;

console.time('Array');
result = arr.indexOf(123123) !== -1;
console.timeEnd('Array');

console.time('Set');
result = set.has(123123);
console.timeEnd('Set');

Вот каковы результаты этого теста:

Array: 0.173ms
Set: 0.023ms

Коллекция в 7.54 раза быстрее массива.

▍Тест №2: вставка элемента

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

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

Вот что получилось:

Array: 0.018ms
Set: 0.003ms

Коллекция в 6.73 раза быстрее массива.

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

Теперь давайте удалим элемент из каждой структуры данных (например — тот, который добавляли в предыдущем испытании). У массивов нет встроенного метода для удаления элементов, поэтому мы создадим вспомогательную функцию для того, чтобы поддерживать наш код в приличном состоянии:

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

А вот код теста:

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

В результате получилось следующее:

Array: 1.122ms
Set: 0.015ms

В данном случае коллекция оказалась в 74.13 раза быстрее массива!

В целом можно отметить, что производительность кода можно значительно увеличить, используя коллекции вместо массивов. Рассмотрим несколько практических примеров.

Пример №1: удаление дублирующихся значений из массива

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

const duplicateCollection = ['A', 'B', 'B', 'C', 'D', 'B', 'C'];
// Если нужно превратить массив в коллекцию
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

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

Если вам хочется более глубоко разобраться в ответе на этот вопрос — почитайте вышеупомянутую статью. Здесь я просто покажу готовое решение.

▍Задача

Дан неотсортированный массив целых чисел и значение sum. Напишите функцию, которая возвращает true в том случае, если в результате сложения двух любых элементов этого массива получится значение sum. Если таких элементов в массиве нет — функция должна возвратить false.

Получается, например, что если нам дан массив [3, 5, 1, 4] и значение sum, равное 9, то функция должна возвратить true, так как 4+5=9.

▍Решение

К решению этой задачи можно подойти, используя следующую идею: нужно перебирать массив, создавая по мере его перебора структуру данных Set, в которую будут добавляться значения, дополняющие найденные значения до значения sum.

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

Вот как может выглядеть решение этой задачи:

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, то, надеемся, теперь вы, получив представление о нём, сможете с пользой применить его в своих проектах.

Уважаемые читатели! Как вы применили бы структуру данных Set в своём коде?