2011-10-31 21 views
19

Esta pregunta es casi idéntica a How to efficiently count the number of keys/properties of an object in JavaScript?.Contando de manera eficiente el número de claves/propiedades de un objeto en JavaScript

Quiero saber una información adicional: ¿qué es un "constante-tiempo" forma de determinar el número de claves en un objeto? Lo que más me preocupa es hacer esto en Node.JS, ya que la mayoría de los objetos en el navegador no son demasiado grandes como para ser una gran preocupación.

EDIT: Parece que Object.keys(obj).length retornos en O tiempo lineal (n) en Google Chrome y en Node.JS (es decir, dependientes del número de llaves en obj). ¿Hay un mejor método O (1)?

Hice algunas pruebas en Node.JS (fuente está por debajo)

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

Para n = 10e3, 10e4, 10e5, 10E6 ... los resultados son los siguientes:

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

¿Has intentado probar esto? – Blender

+0

No. Me siento flojo hoy ...:/Caso de los lunes, supongo. – BMiner

+2

Sospecho que obtener el ".length" del resultado de llamar a "Object.keys()" es de tiempo constante, pero también sospecho que llamar a "Object.keys()" es lineal en el número de propiedades. – Pointy

Respuesta

1

Ver la fuente , específicamente GetLocalElementKeys

v8 objects.cc

+0

Soy demasiado vago para hacer esto. En inglés por favor. Con gusto aceptaría tu respuesta. : P – BMiner

+0

Dependiendo de lo que contenga el objeto, ellos hacen cosas diferentes, el peor caso parece estar haciendo 1 para recorrer todos los elementos. – Andrew

5

Después de un poco de investigación, no hay forma de determinar el número de claves en un objeto de JavaScript en tiempo constante, al menos no en el nodo ... y todavía no. Nodo internamente realiza un seguimiento de esta información, pero no la expone, ya que no existe un método para hacerlo en ECMA-262 5th.

Vale la pena señalar que Harmony (ECMA versión 6) puede admitir de forma nativa Maps and Sets. No estoy seguro de cuál será la especificación para estos.

Me dijeron que tenemos que mencionar esto con el comité TC39.

Informe de error de V8: http://code.google.com/p/v8/issues/detail?id=1800

1

ECMA 6 armonía introduce Map y Set clases que probablemente se puede utilizar (en el futuro :)

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

creo que debe tener la complejidad O (1), aunque no probado. Puede ejecutarlo en el nodo 0.11+ a través de node --harmony script.js.


Otra forma es utilizar Proxy clase que también se ha añadido en armonía .

Cuestiones relacionadas