Какая сложность, если передавать массив в конструктор new Set()?

Question

[lil_web]

У меня есть массив с числами для примера. Я хочу получить из него коллекцию с уникальными числами.

const nums = [1, 1, 2, 3];
const set = new Set(nums); // Set { 1, 2, 3 }

Подскажите, пожалуйста, какая сложность по времени и памяти этого алгоритма. Желательно с ссылками на источник. Мне кажется, линейная.

Такая же сложность у остальных коллекций по ключу: Map, WeakMap, WeakSet?

Конструктор Set в спеке

Answer 1

[Robur]

Разная.
во первых, есть спека, которая описывает что должно произойти при вызове конструктора с коллекцией в качестве аргумента. Это абстрактное алгоритмическое описание, у него сложность как видим O(n) при условии что adder имеет сложность O(1). Если adder имеет другую сложность - то соответственно сложность конструктора так же поменяется, вполне может быть и O(n^2) например. копаться что там может быть в adder мне уже лень, можете выяснить самостоятельно.
https://tc39.es/ecma262/#sec-set-iterable

Дальше, есть движок, в котором реализована эта спека. хоть мы и живем во времена дефолт-движка v8, но предполагать что это единственная реализация в мире не правильно. Напимер в файрфоксе - не он. В мобилках - по моему тоже (как минимум на ios).
Поэтому второй вопрос - в каком движке?

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

Поэтому третий вопрос - для каких данных?

Скорее всего, во всех адекватных реализациях так же будет O(n), но утверждать что так оно и есть тоже не корректно, максимум можно предположить с большой степенью уверенности.

Чтобы сказать точно - надо смотреть в код движка.

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

Comments

[lil_web]

Спасибо за подробный ответ.

Извините за наглость, хотелось бы, чтобы нашли код Сета в V8. Может, у кого-то под рукой.

[Robur]

Извиняю. Может кто-то и дополнит ссылкой на v8.

Answer 2

[juxifo]

Какая разница? Вы делаете большую ошибку, занимаясь микро оптимизациями.

Быстрее всего будет используя {}, наверное, потому что он использует хеш, но большого отличия от Set нету.

// https://stackoverflow.com/questions/1960473/get-all-unique-values-in-a-javascript-array-remove-duplicates
function uniqueArray1( ar ) {
  var j = {};

  ar.forEach( function(v) {
    j[v+ '::' + typeof v] = v;
  });

  return Object.keys(j).map(function(v){
    return j[v];
  });
}

https://docs.google.com/spreadsheets/d/1-Vr4dD0GE0...

Смотрите на время для конкретно ваших задач.

Comments

[lil_web]

Интересно, спасибо. Но для стажировки в Яндекс нужно знать сложность функций языка.

[juxifo]

lil_web, Можете попытаться сами оценить https://habr.com/ru/post/104219/

[lil_web]

juxifo, хотелось бы найти файл в репе V8.

[juxifo]

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

[lil_web]

juxifo, спасибо. Мой вопрос встал как раз, когда я решал задачки на Литкоде. Всё-таки хочется узнать.

[Ярослав Иванов]

lil_web, Так пишите свой аналог set'a если парит сложность алгоритма.