¿Alguien conoce la complejidad de tiempo de Object.keys() de ECMAScript5 en implementaciones comunes? ¿Es O(n) para las claves n? ¿El tiempo es proporcional al tamaño de la tabla hash, suponiendo una implementación hash?Object.keys() complejidad?
Estoy buscando ya sea garantías por parte de los implementadores del lenguaje o algún punto de referencia del mundo real.
Parece ser O(n) en V8 (cromo, Node.js) al menos:
> var hash = {}
> , c = 0;
>
> var s = +new Date();Object.keys(hash);console.log(+new Date() - s);
0
> for(var i=0; i<100000; i++, c++){ hash[c] = 1; }
> var s = +new Date();Object.keys(hash);console.log(+new Date() - s);
26
> for(var i=0; i<100000; i++, c++){ hash[c] = 1; }
> var s = +new Date();Object.keys(hash);console.log(+new Date() - s);
49
> for(var i=0; i<100000; i++, c++){ hash[c] = 1; }
> var s = +new Date();Object.keys(hash);console.log(+new Date() - s);
75
> for(var i=0; i<100000; i++, c++){ hash[c] = 1; }
> var s = +new Date();Object.keys(hash);console.log(+new Date() - s);
102
Esos resultados tienen sentido para un mapa hash denso. ¿Se degrada el rendimiento a medida que las claves se vuelven más dispersas? – hurrymaplelad
@hurrymaplelad - ¿Qué? Todas las teclas hash JS son cadenas. Este código genera efectivamente '{'1': 1, '2': 1, '3': 1, ...}' _sparse_ vs _dense_ claves no tienen sentido para las implementaciones de hash, solo para las matrices. Y realmente no tiene sentido que un motor implemente un hash como una matriz, ya que los índices numéricos generalmente son bastante raros. Aunque si quieres probar eso por alguna razón, simplemente cambia 'C++' a 'c + = Math.random()' que te dará claves totalmente no asociables. –
@cwolves: un objeto 'Array' es simplemente un objeto cuyas propiedades se espera que sean números enteros. Esos no son terriblemente raros, y ciertamente hay implementaciones JS que usan matrices para respaldar instancias 'Array'. – Gabe
¿Cuántas llaves qué se puede esperar estar teniendo, de tal manera que la complejidad del tiempo de enumerar sus principales intereses? – Gabe
No creo que pueda ser menor que 'O (n)' –
@PabloFernandez, la longitud es menor que O (n) – Joe