В своей повседневной деятельности многие разработчики свободно обходятся лишь основными типами данных, представленными в JS: числами, строками, объектами, массивами и логическими значениями.
Но, использование только этих базовых типов не всегда может быть достаточным, если вы хотите сделать свой код максимально быстрым и масштабируемым.
В этой статье мы поговорим о том, как новые типы Set (Набор) в JavaScript могут сделать ваш код быстрее, особенно при масштабировании. Существует значительное пересечение между тем, что может делать массив, и тем, что может делать Set. Но использование наборов часто дает преимущества в скорости выполнения, которых невозможно достичь с помощью массивов. В этой статье мы рассмотрим, каким образом это достигается.
В чем главное отличие типа данных Set?
Самое принципиальное отличие состоит в том, что массивы являются индексированной коллекцией. Это означает, что значения в массиве упорядочены по индексу.
В свою очередь, Set - это набор ключей. Вместо использования индексов, Set упорядочивают свои данные, используя ключи. Элементы набора являются итеративными в порядке вставки и не могут содержать повторяющихся данных. Другими словами, каждый предмет в наборе должен быть уникальным.
Каковы основные преимущества наборов?
В прямом сравнении наборы имеют несколько преимуществ перед массивами, особенно когда дело касается скорости выполнения:
- Поиск элемента: использование indexOf () или include () для проверки наличия элемента в массиве выполняется медленно.
- Удаление элемента: в наборе вы можете удалить элемент по его значению. Массив же использует splice () на основе индекса элемента. Как и в предыдущем пункте, из-за зависимости от индексов, выполняется медленно.
- Вставка элемента: быстрее добавить элемент в набор, чем добавить элемент в массив, используя push (), unshift () или эквивалентный метод.
- Хранение NaN: Вы не можете использовать indexOf () или includes (), чтобы найти значение NaN, в то время как Set может хранить это значение.
- Удаление дубликатов: объекты Set хранят только уникальные значения. Если вы хотите избежать хранения дубликатов, это является значительным преимуществом по сравнению с массивами, где для обработки дубликатов потребуется дополнительный код.
Примечание. Для получения полного списка встроенных методов Set лучше всего обратиться к веб-документам MDN.
О временной сложности
Для поиска ключей массив использует методы, имеющие временную сложность O(N). Следовательно, время выполнения этих операций увеличивается с той же скоростью, что и размер входящих данных.
Наборы же, в свою очередь, используют для поиска, удаления и вставки элементов методы, имеющие временную сложность всего O(1) - это означает, что размер данных практически не влияет на время выполнения этих методов!
Примечание: узнать больше о временной сложности алгоритмов вы можете в статье о Big O Notation.
Итак, насколько быстрее наборы?
Хотя время выполнения может значительно различаться в зависимости от используемой системы, размера предоставленных данных и других переменных, я надеюсь, что результаты моего теста дадут вам практическое представление о том, насколько быстрыми могут быть наборы. Я поделюсь с вами тремя простыми тестами и полученными результатами.
Подготовка тестов
Прежде чем запускать какие-либо тесты, давайте создадим Array и Set из миллиона записей каждый. Для простоты я начну с 0 и буду считать до 999 999.
Тест 1: поиск элемента
Сначала давайте найдем номер 123123, который, как мы знаем, должен вернуть true.
Array: 0.173ms
Set: 0.023ms
Итак, как мы видим — набор в 7.54 раз быстрее массива.
Тест 2: добавление элемента
Теперь давайте добавим новый элемент в каждую коллекцию.
Array: 0.018ms
Set: 0.003ms
Set быстрее в 6.73 раз.
Тест 3: удаление элемента
Наконец, давайте удалим элемент из каждой коллекции (мы можем использовать тот элемент, который добавляли в предыдущем тесте). Для этого нет встроенного метода массива. Поэтому, для удобства, мы создадим вспомогательную функцию:
Далее код теста:
Array: 1.122ms
Set: 0.015ms
В этом случае Set был в 74,13 раза быстрее!
В целом, мы можем видеть, что наборы могут дать существенный прирост в скорости по сравнению с обычными массивами. Теперь давайте посмотрим на некоторые практические примеры, где наборы могут быть полезны.
Пример 1: удаление повторяющихся значений из массива
Если вы хотите быстро удалить повторяющиеся значения из массива, вы можете преобразовать его в набор. На сегодняшний день это самый краткий способ отфильтровать уникальные значения:
Пример 2: задача с интервью Google
В статье 4 Ways to Solve a Google Interview Question in JavaScript рассматриваются четыре решения вопроса, заданного интервьюером в Google. Интервью проводилось с использованием C ++, но если бы оно было в JavaScript, структура Set была бы необходимой частью окончательного решения.
Если вы хотите взглянуть на решение более подробно, я рекомендую прочитать статью, но вот краткое резюме окончательного решения.
Вопрос
Дан неупорядоченный массив целых чисел и сумма sum, верните true, если любые два элемента могут быть добавлены так, чтобы они равнялись значению sum. В противном случае верните false.
Итак, если нам дали массив [3, 5, 1, 4] и значение 9, наша функция должна вернуть true, потому что 4 + 5 = 9.
Решение
Отличной идеей для решения этого вопроса будет перебор массива и создание, по мере перебора, набора данных, в который буду добавляться значения, образующие значение sum сумме с текущим значением в переборе.
Давайте применим это мышление к примеру выше. Когда мы встречаем 3, мы можем добавить 6 в наш набор, потому что мы знаем, что нам нужно найти сумму 9. Затем, каждый раз, когда мы находим новое значением в массиве, мы можем проверить, находится ли оно в нашем наборе. Когда мы дойдем до 5, мы добавим 4 в наш Set. Затем, когда мы наконец встретимся с 4, мы также найдем его в нашем наборе и сможем вернуть true.
Вот как может выглядеть это решение:
Поскольку Set.prototype.has () имеет временную сложность всего O (1), использование Set для хранения чисел, помогает дать нашему общему решению линейное время выполнения O (N).
Если бы Set мы вместо использовали Array.prototype.indexOf () или Array.prototype.include (), оба из которых имеют временную сложность O(N), общее время выполнения будет O (N²), что, конечно же, намного медленнее.
Если вы раньше не были знакомы с новым типом Set в JavaScript, то надеюсь, я продемонстрировал, насколько они могут быть полезны!
Перевод статьи https://medium.com/@bretcameron/how-to-make-your-code-faster-using-javascript-sets-b432457a4a77