JavaScript中高效计算对象键/属性数量

Question

这个问题与如何高效地计算JavaScript对象中键/属性的数量？几乎相同。

我想知道一个额外的信息：如何以“常数时间”确定对象中键的数量？ 我主要关心在Node.JS中执行此操作，因为大多数浏览器上的对象并不太大，不会成为主要问题。

编辑： 在Google Chrome和Node.JS中，Object.keys(obj).length按线性时间O(n)返回（即取决于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

- BMiner

---

不行，今天我感觉懒洋洋的... :/ 估计是星期一的缘故。 - BMiner

我怀疑从调用“Object.keys()”的结果中获取“.length”是常数时间，但我也怀疑调用“Object.keys()”与属性数量成线性关系。 - Pointy

在Chrome浏览器中，对象中的项目增加100倍会导致其变慢200倍。请参考：http://jsperf.com/object-keys-performance - pimvdb

@BMiner，您可以使用代理手动计数。但这会在其他地方产生开销。是的，.length 是 O(n)。 - Raynos

@BMiner 对不起，我的意思是 Object.keys(o).length 的时间复杂度是O(n)。 在数组上使用.length的时间复杂度是O(1)。 - Raynos

Answer 1

经过一番研究，目前没有办法在Node中以常数时间确定JavaScript对象中键的数量，至少不是在ECMA-262第5版中，并且现在还没有。Node在内部跟踪此信息，但它不会公开它，因为在ECMA-262第5版中没有这样做的方法。

值得注意的是，Harmony（ECMA第6版）可能本地支持Maps和Sets。不确定这些规范最终会变成什么样子。

我被告知我们需要与TC39委员会讨论此问题。

V8的错误报告：http://code.google.com/p/v8/issues/detail?id=1800

- BMiner

Answer 2

ECMA 6 harmony引入了Map和Set类，你将来可能会用到它们。

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

我认为这个应该是复杂度O(1)，但我没有尝试过。你可以在node 0.11+中通过node --harmony script.js运行它。

---

另一种方法是使用Proxy类，这也是在harmony中添加的。

- deadrunk

Answer 3

查看源代码，特别是GetLocalElementKeys

v8 objects.cc

- Andrew

---

我太懒了，还是用英语吧。不过我很乐意接受你的回答。 :P - BMiner

根据对象包含的内容，它们会执行不同的操作，最坏情况似乎是通过所有元素进行1个循环。 - Andrew