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

[WanSpi]

Мне одному кажеться что глупо сравнивать array и set? Почему тогда не сравнить с object? Понятное дело что для поиска set будет намного быстрее, но в 99% случаев, где используеться array, set попросту не будет пригоден, всю статью можно было свести к тому как именно работать с set, а не сравнивать разные вещи.

[force]

Поддерживаю, сравнивают тёплое с мягким. А вот преимущество Set перед Object, в том, что в Set в качестве ключа можно хранить объекты, а не строки. А недостаток, за который периодически все запинаются, сеты не сериализуются в JSON.

[JustDont]

С учётом того, что в POJO можно так же иметь Symbol() в качестве ключей (а они в качестве ключей очень похожи на объекты в качестве ключей) — Set и Map на самом деле нужны весьма нечасто.

[dmitry_luzanov]

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

Ключ/значение? Но это ведь справедливо для Map, никак не для Set.

[EreminD]

Ну, если совсем глубоко посмореть, то может быть и ключ/значение (привет, 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()

[homm]

то может быть и ключ/значение

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

[EreminD]

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

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

Оригинал статьи:

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

Фантастический перевод:

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

[metalim]

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

[triton]

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

У массива можно использовать не indexOf, а includes()
[NaN].includes(NaN); //true

[web_devel]

Подобные низкокачественные переводы вносят сумбур в терминологии. Как и зачем 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

[polRk]

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

[DarkGenius]

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

[xPomaHx]

Сколько я сам не экспериментировал с сэтом, он всегда медленнее и массива и просто объекта. А после случая когда производительность была ключевым фактором и я день провозился вычисляя тонкое место я сет не использую вообще никогда.
Если нужны уникальные значения, то в 100% случае они нужны не все время, а какой то определенный момент и лучше пересобрать массив именно в этот самый момент удаляя дубликаты.

[faiwer]

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 оказывался всегда медленным? о_О

[xPomaHx]

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

[faiwer]

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

[milast]

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

[nicky1038]

Заметил неточность, она есть и в оригинальной статье.

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

Это не совсем верно. Спецификация ECMAScript 2015 только требует, чтобы методы для этих коллекций (1, 2, 3, 4) выполнялись за сублинейное время, и в разных движках они могут быть реализованы по-разному. Исходя из этого, в какой-то реализации может оказаться и сложность O(logN), например, хоть это и было бы не лучшим решением.