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

Автор оригинала: Bret Cameron
  • Перевод
Автор материала, перевод которого мы сегодня публикуем, говорит, что уверен в том, что многие 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(N2). В результате он стал бы гораздо медленнее.

Итоги


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

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

RUVDS.com
905,00
RUVDS – хостинг VDS/VPS серверов
Поделиться публикацией

Комментарии 18

    +10
    Мне одному кажеться что глупо сравнивать array и set? Почему тогда не сравнить с object? Понятное дело что для поиска set будет намного быстрее, но в 99% случаев, где используеться array, set попросту не будет пригоден, всю статью можно было свести к тому как именно работать с set, а не сравнивать разные вещи.
      0
      Поддерживаю, сравнивают тёплое с мягким. А вот преимущество Set перед Object, в том, что в Set в качестве ключа можно хранить объекты, а не строки. А недостаток, за который периодически все запинаются, сеты не сериализуются в JSON.
        –1
        С учётом того, что в POJO можно так же иметь Symbol() в качестве ключей (а они в качестве ключей очень похожи на объекты в качестве ключей) — Set и Map на самом деле нужны весьма нечасто.
      +6
      В отличие от массивов, объекты типа Set (мы будем называть их «коллекциями») представляют собой коллекции, содержащие данные в формате ключ/значение

      Ключ/значение? Но это ведь справедливо для Map, никак не для Set.
        –3
        Ну, если совсем глубоко посмореть, то может быть и ключ/значение (привет, ES6)
        Set objects must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements in the collection


        Например, в Java так. HashSet — это просто Map, у которой values игнорируются (работа только с ключами, которые уникальны и все такое)

        В js, видимо, похожая история, раз Set имеет методы keys(), values() и entries()
        const set = new Set()
        set.keys()
        set.values()
        set.entries()
          +8
          то может быть и ключ/значение

          Нет не может. Set не позволяет получить значения по ключу, а именно это и имеется в виду под key-value хранилище.

            –1
            ну, все же Set построен поверх hash tables — прям как в спецификации

            а вообще, тут вопрос к переводчику, что он имел в виду, когда добавлял от себя «содержащие данные в формате ключ/значение»

            Оригинал статьи:
            By contrast, Sets are a keyed collection. Instead of using indices, Sets order their data using keys.

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

              Как 6 слов превратились в 21…
              Полагаю причина фантастического перевода — в неоднозначности в оригинале: ключи-то в коллекции может и есть, но доступа к ним у программиста нет. Тут следовало бы описать что такое хеш-таблица, вместо декламации подобных неоднозначностей.

        +2
        Метод indexOf() нельзя использовать для поиска значения NaN в массиве, в то время как с помощью метода коллекции has() можно выяснить, имеется ли в ней NaN.

        У массива можно использовать не indexOf, а includes()
        [NaN].includes(NaN); //true
          +2
          Изучаем ES2015 в 2019 году. Лучше поздно чем никогда.
            +2
            Подобные низкокачественные переводы вносят сумбур в терминологии. Как и зачем Set нужно было приравнивать к коллекции (именно в рамках перевода)?

            Оригинал:
            The most fundamental difference is that arrays are an indexed collection.

            By contrast, Sets are a keyed collection. Instead of using indices, Sets order their data using keys.

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

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

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

            developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Keyed_collections
            developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Indexed_collections
              0

              А как работать с сетом объектов? Как находить элементы по определенному ключу, удалять объекты ?

                +5

                Не может быть добавление в Set быстрее добавления в массив, так как при добавлении в Set проверяется уникальность. Дизайн тестов неправильный. Кто же делает тесты на одной операции да еще и на пустой коллекции? При вставке тысячи элементов вставка в массив намного быстрее.

                  0
                  Сколько я сам не экспериментировал с сэтом, он всегда медленнее и массива и просто объекта. А после случая когда производительность была ключевым фактором и я день провозился вычисляя тонкое место я сет не использую вообще никогда.
                  Если нужны уникальные значения, то в 100% случае они нужны не все время, а какой то определенный момент и лучше пересобрать массив именно в этот самый момент удаляя дубликаты.
                    0
                    var array = (new Array(100000)).fill(true).map((el, idx) => idx);
                    var set = new Set(array);
                    
                    console.time('includes');
                    array.includes(100000);
                    console.timeEnd('includes');
                    
                    console.time('has');
                    set.has(100000);
                    console.timeEnd('has');
                    
                    VM675:6 includes: 0.244140625ms
                    VM675:10 has: 0.0048828125ms

                    Что же вы такое с ними делали, что у вас Set оказывался всегда медленным? о_О

                      0
                      Ну так это логично чтение или поиск для хэш таблицы всегда быстрее, тоже самое будет работать с обычным объектом, только ключи могут быть исключительно строки.
                      А вы потестите остальные операции добавление удаление jsben.ch/HyQZB
                        0

                        Прошу прощения, я упустил слово "объекта". Подумал что у вас массив оказался быстрее. В случае с объектом под капотом, наверное, находятся примерно одного порядка структуры данных и это больше вопрос движка\оптимизации. Сегодня быстрее, завтра медленнее, затем наоборот.

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

                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                    Самое читаемое