Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Efficiently counting the number of keys / properties of an Object in JavaScript

Tags:

This question is almost identical to How to efficiently count the number of keys/properties of an object in JavaScript?.

I want to know one extra piece of information: what is a "constant-time" way of determining the number of keys in an Object? I am mostly concerned with doing this in Node.JS, as most Objects on the browser aren't too large to be of great concern.

EDIT: It appears that Object.keys(obj).length returns in linear time O(n) in Google Chrome and in Node.JS (i.e. dependent on the number of keys in obj). Is there a better O(1) method?

I did some testing in Node.JS (source is below)

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]); } 

For n = 10e3, 10e4, 10e5, 10e6... results are:

test10000: 5ms test100000: 20ms test1000000: 371ms test10000000: 4009ms 
like image 272
BMiner Avatar asked Oct 31 '11 16:10

BMiner


1 Answers

After a bit of research, there is no way to determine the number of keys in a JavaScript Object in constant time, at least not in Node... and not quite yet. Node internally keeps track of this information, but it does not expose it, since there is no method to do so in ECMA-262 5th.

It's worth noting that Harmony (ECMA version 6) may natively support Maps and Sets. Not sure what the spec for these will turn out to be.

I am told that we need to bring this up with TC39 committee.

Bug report for V8: http://code.google.com/p/v8/issues/detail?id=1800

like image 113
BMiner Avatar answered Nov 27 '22 05:11

BMiner