Javascript ES6 вычислительная / временная сложность наборов
Во сколько сложность (в нотации "большого О") обеспечивается спецификацией ES6 для Включенных Наборов (Набор, Карта, WeakSet и WeakMap)?
Мое ожидание, и я ожидаю ожидание большинства разработчиков, то, что спецификации и реализации использовали бы широко принятые производительные алгоритмы, в этом случае Set.prototype.has, add и delete ко всем быть O (1) в среднем случае. То же для Map и Weak– эквиваленты.
Для меня не совсем очевидно, получила ли временная сложность реализаций мандат, например, в Спецификации языка 2015 года ECMAScript - 6-м Выпуске — 23.2 Объекта Набора.
Если я не неправильно понимаю его (и, конечно, очень возможно, что я делаю), это смотрит мандаты спецификации ECMA что реализации (например. Set.prototype.has) должны использовать линейное время (O (n)) алгоритм. Это показалось бы мне чрезвычайно удивительный, что больше производительных алгоритмов не получит мандат или будет даже разрешено спецификацией, и я очень интересовался бы объяснением почему дело обстоит так.
1 ответ
Для любого, кому любопытно, я сделал очень быстрый сравнительный тест:
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 w/16G RAM на 2,5 ГГц)
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