Javascript ES6 вычислительная / временная сложность коллекций

89

Какая временная сложность (в нотации большого O) предусмотрена спецификацией ES6 для Keyed Collections (Set, Map, WeakSet и WeakMap)?

Мои ожидания, и я ожидаю , что от большинства разработчиков, является то , что спецификации и реализации будут использовать широко принятые производительным алгоритмы, в этом случае Set.prototype.has, addи deleteдля всех быть O (1) в среднем случае. То же для Mapи Weak–эквивалентов.

Для меня не совсем очевидно, требовалась ли временная сложность реализаций, например, в ECMAScript 2015 Language Specification - 6th Edition - 23.2 Set Objects .

Если я не понимаю это неправильно (а это, конечно, очень возможно), похоже, что спецификация ECMA требует, чтобы реализации (например Set.prototype.has) использовали алгоритм линейного времени ( O (n) ). Мне показалось бы чрезвычайно удивительным, что более производительные алгоритмы не были бы предписаны или даже разрешены спецификацией, и мне было бы очень интересно объяснить, почему это так.

Брайан М. Хант
источник
2
Все алгоритмы O (1) также являются O (n) , поэтому использование менее эффективных реализаций не принесет никакого вреда. Вероятно, менее производительные реализации могут представлять интерес в системах с ограниченными ресурсами, поскольку, скорее всего, они требуют гораздо меньше кода / места.
Artur Grzesiak
@arturgrzesiak Производительность коллекций с ключом O (1) обычно достигается с помощью хэша O (1) плюс бакета коллизий O (n). Наихудший случай O (n) для большинства практических целей астрономически редок. Пространственная сложность этих методов обычно составляет O (n).
Брайан М. Хант,
1
«Объекты набора должны быть реализованы с использованием либо хэш-таблиц, либо других механизмов, которые, в среднем, обеспечивают время доступа, сублинейно зависящее от количества элементов в коллекции» - с той самой страницы.
georg

Ответы:

61

Прямо из того самого абзаца, на который вы ссылаетесь:

Объекты набора должны быть реализованы с использованием [механизмов], которые, в среднем, обеспечивают сублинейное время доступа к количеству элементов в коллекции.

Вы найдете такое же предложение для Maps , WeakMaps и WeakSets .

Похоже, что спецификация ECMA требует, чтобы реализации (например, Set.prototype.has) использовали O(n)алгоритм linear time ( ).

Нет:

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

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

Берги
источник
2
Спасибо, что выбрали это. К тому времени, как я добрался до этого абзаца, мои глаза, должно быть, потускнели. :) Итак, алгоритмы, которые либо O (log (n)), либо O (1), но не требуются иным образом (при условии, что они находятся под O (n))?
Брайан М. Хант
1
@ Брайан М. Хант: Верно.
Bergi
32

Для всех, кому интересно, я сделал очень быстрый тест:

const benchmarkMap = size => {
  console.time('benchmarkMap');
  var map = new Map();
  for (var i = 0; i < size; i++) map.set(i, i);
  for (var i = 0; i < size; i++) var x = map.get(i);
  console.timeEnd('benchmarkMap');
}

const benchmarkObj = size => {
  console.time('benchmarkObj');
  var obj = {};
  for (var i = 0; i < size; i++) obj[i] = i;
  for (var i = 0; i < size; i++) var x = obj[i];
  console.timeEnd('benchmarkObj');
}

var size = 1000000;

benchmarkMap(size);
benchmarkObj(size);

Я запускал это несколько раз и получил следующие результаты:

(MacBook Pro 2017 года, i7 2,5 ГГц с 16 ГБ ОЗУ)

benchmarkMap: 189.120ms
benchmarkObj: 44.214ms

benchmarkMap: 200.817ms
benchmarkObj: 38.963ms

benchmarkMap: 187.968ms
benchmarkObj: 41.633ms

benchmarkMap: 186.533ms
benchmarkObj: 35.850ms

benchmarkMap: 187.339ms
benchmarkObj: 44.515ms
Домдамброгия
источник
3
@domdambrogia , если отделить от установки получения я получаю: Map Set = 124, Карта Получить = 40, Object Set = 26, объект Get = 1 (эти отношения не мс)
AJP
@AJP Я не думал о том, чтобы разбить это на эту статистику. Спасибо за ваш вклад, это хороший вклад. Я посмотрю, смогу ли я добавить это в свой ответ, когда у меня будет секунда. Благодаря!
domdambrogia 07
Было бы интересно отделить задание от чтения, чтобы также узнать, какое из них лучше для чтения.
fernandopasik
3
« MacBook Pro 2017 года, i7 2,5 ГГц с 16 ГБ ОЗУ » - ну, это круто и все такое, но какой движок JavaScript вы тестировали?
Bergi
1
Интересно, что при добавлении deleteоперации и операции перемешиваются, Mapработает намного лучше. jsfiddle.net/23hrp0eq
Йорджон