Qualcuno conosce la complessità temporale di Object.keys() di ECMAScript5 nelle implementazioni comuni? È O(n) per n chiavi? Il tempo è proporzionale alla dimensione della tabella hash, assumendo un'implementazione hash?Object.keys() complessità?
Sto cercando garanzie da parte di implementatori linguistici o alcuni benchmark reali.
Sembra essere O(n) a V8 (cromo, Node.js) almeno:
> 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
Questi risultati hanno senso per una mappa hash densa. Le prestazioni diminuiscono man mano che le chiavi diventano più rare? – hurrymaplelad
@hurrymaplelad - Cosa? Tutte le chiavi di hash JS sono stringhe. Questo codice genera in modo efficace '{'1': 1, '2': 1, '3': 1, ...}' _sparse_ vs _dense_ keys non ha senso per le implementazioni hash, solo per gli array. E non ha alcun senso per un motore implementare mai un hash come array poiché gli indici numerici sono in genere piuttosto rari. Però se vuoi metterlo alla prova per qualche ragione, cambia 'C++' in 'c + = Math.random()' che ti darà chiavi totalmente non associabili. –
@cwolves: un oggetto 'Array' è solo un oggetto le cui proprietà dovrebbero essere numeri interi. Quelle non sono terribilmente rare e ci sono certamente implementazioni JS che usano gli array per supportare le istanze di 'Array'. – Gabe
Quante chiavi si aspetta di essere avere, in modo tale che la complessità temporale di enumerazione li conta? – Gabe
Non penso che possa essere inferiore a 'O (n)' –
@PabloFernandez, la lunghezza è minore di O (n) – Joe