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

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

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

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

Ответы

Ответ 1

Прямо из этого самого абзаца, связанного с:

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

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

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

<Не p > Нет:

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

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

Ответ 2

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

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, 2,5 ГГц i7 с 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