Эффективный подсчет количества ключей / свойств объекта в JavaScript

Question

Этот вопрос почти идентичен Как эффективно подсчитать количество ключей / свойств объекта в JavaScript? .

Я хочу знать одну дополнительную информацию: что такое « постоянное время » способ определения количества ключей в объекте? В основном я занимаюсь этим в Node.JS, так как большинство объектов в браузере не слишком велики, чтобы вызывать большую озабоченность.

EDIT: Похоже, что Object.keys(obj).length возвращает в линейном времени O (n) в Google Chrome и в Node.JS (т.е. зависит от количества ключей в obj). Есть ли лучший метод O (1)?

Я провел некоторое тестирование в Node.JS (источник ниже)

var tests = [10e3, 10e4, 10e5, 10e6]
for(j in tests) {
    var obj = {};
    for(i = 0; i < tests[j]; i++)
        obj[i] = i;
    console.time('test' + tests[j]);
    Object.keys(obj).length;
    console.timeEnd('test' + tests[j]);
}

Для n = 10e3, 10e4, 10e5, 10e6 ... результаты:

test10000: 5ms
test100000: 20ms
test1000000: 371ms
test10000000: 4009ms

Answer 1

После небольшого исследования не существует способа определить количество ключей в объекте JavaScript за постоянное время, по крайней мере, не в Node ... и еще не совсем. Узел внутренне отслеживает эту информацию, но не раскрывает ее, поскольку в ECMA-262 5-й метод не существует.

Стоит отметить, что Harmony (версия 6 ECMA) может изначально поддерживать Карты и Наборы. Не уверен, что спецификация для них окажется.

Мне сказали, что мы должны обсудить это с комитетом TC39.

Отчет об ошибке для V8: http://code.google.com/p/v8/issues/detail?id=1800

Answer 2

ECMA 6 гармония вводит Map и Set классы, которые вы, вероятно, можете использовать (в будущем:)

var map = new Map;
map.set('a', 'b');
console.log(map.size); // prints 1

Я считаю, что это должно иметь сложность O (1), но не пытался.Вы можете запустить его в узле 0.11+ через node --harmony script.js.

---

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

Answer 3

См. Источник, в частности GetLocalElementKeys

v8 objects.cc