Какая временная сложность (в нотации большого 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) ). Мне показалось бы чрезвычайно удивительным, что более производительные алгоритмы не были бы предписаны или даже разрешены спецификацией, и мне было бы очень интересно объяснить, почему это так.
источник
Ответы:
Прямо из того самого абзаца, на который вы ссылаетесь:
Вы найдете такое же предложение для Maps , WeakMaps и WeakSets .
Нет:
Наблюдаемая семантика в основном связана с предсказуемым порядком итераций (который все еще может быть реализован эффективно и быстро ). Спецификация действительно предполагает, что реализация использует хеш-таблицу или что-то подобное с постоянным доступом, хотя деревья (с логарифмической сложностью доступа) также разрешены.
источник
Для всех, кому интересно, я сделал очень быстрый тест:
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
источник
delete
операции и операции перемешиваются,Map
работает намного лучше. jsfiddle.net/23hrp0eq