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

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

o4ibr_dcy23melkuz-4r3ijjhr0.jpeg

В этом материале мы поговорим о том, как, пользуясь типом данных 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 (N2). В результате он стал бы гораздо медленнее.

Итоги


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

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

1ba550d25e8846ce8805de564da6aa63.png

© Habrahabr.ru