Qual è la complessità del recupero/inserimento negli array associativi JavaScript (proprietà degli oggetti dinamici) nei principali motori javascript?

Question

Prendiamo il seguente esempio di codice:

var myObject = {}; 
var i = 100; 

while (i--) { 
    myObject["foo"+i] = new Foo(i); 
} 

console.log(myObject["foo42"].bar()); 

Ho un paio di domande.

Quale tipo di struttura dati utilizza i principali motori (IE, Mozilla, Chrome, Safari) per la memorizzazione di coppie chiave-valore? Mi auguro che sia un albero di ricerca binaria gentile, ma penso che possano usare liste collegate (a causa del fatto che l'iterazione viene eseguita in ordine di inserimento).

Se usano un albero di ricerca, è auto-bilanciamento? Poiché il codice precedente con un albero di ricerca convenzionale creerà un albero sbilanciato, causando lo scenario peggiore di O (n) per la ricerca, piuttosto che O (log n) per un albero bilanciato.

Sto solo chiedendo questo perché scriverò una libreria che richiederà un efficiente recupero delle chiavi da una struttura dati, e mentre potrei implementare il mio o un albero rosso-nero esistente preferirei usare le proprietà degli oggetti nativi se sono abbastanza efficienti.

Answer 1

La domanda è difficile da rispondere per un paio di motivi. Innanzitutto, i browser moderni ottimizzano il codice in modo pesante e dinamico mentre è in esecuzione, quindi gli algoritmi scelti per accedere alle proprietà potrebbero essere diversi per lo stesso codice. In secondo luogo, ciascun motore utilizza algoritmi e euristica diversi per determinare quale algoritmo di accesso utilizzare. In terzo luogo, le specifiche ECMA dettano quale sia il risultato di deve essere, non come il risultato è raggiunto in modo che i motori hanno molta libertà di innovare in questo settore.

Detto questo, dato il tuo esempio tutti i motori con cui ho familiarità utilizzeranno una qualche forma di tabella hash per recuperare il valore associato a foo42 da myobject. Se si utilizza un oggetto come un array associativo, i motori JavaScript tenderanno a favorire una tabella hash. Nessuno che io sappia utilizzare un albero per le proprietà delle stringhe. Le tabelle hash sono nel caso peggiore O (N), best case O (1) e tendono ad essere più vicine a O (1) rispetto a O (N) se il generatore di chiavi è buono. Ogni motore avrà un modello che è possibile utilizzare per ottenere O (N) ma che sarà diverso per ogni motore. Un albero bilanciato garantisce il caso peggiore O (log N) ma la modifica di un albero bilanciato pur mantenendolo bilanciato non è O (log N) e le tabelle hash sono più spesso migliori di O (log N) per le chiavi stringa e sono O (1) per aggiornare (una volta stabilito che è necessario, che è lo stesso O grande come letto) se c'è spazio nella tabella (periodicamente O (N) per ricostruire la tabella ma le tabelle di solito raddoppiano nello spazio, il che significa che pagherai solo O (N) 7 o 8 volte per la vita del tavolo).

Le proprietà numeriche sono speciali, tuttavia. Se si accede a un oggetto utilizzando proprietà numeriche di numeri interi che presentano pochi o nessun intervallo nell'intervallo, ovvero l'utilizzo dell'oggetto come se fosse un array, i valori tenderanno ad essere memorizzati in un blocco lineare di memoria con accesso O (1). Anche se il tuo accesso ha degli spazi vuoti, i motori probabilmente passeranno a un accesso sparse di array che probabilmente sarà, nella peggiore delle ipotesi, O (log N).

Anche l'accesso a una proprietà tramite identificatore è speciale. Se si accede alla proprietà come,

myObject.foo42 

ed eseguire questo codice spesso (cioè la velocità di questa materia), e con la stessa o simile oggetto questo rischia di essere ottimizzato in uno o due istruzioni macchina. Ciò che rende gli oggetti simili si differenzia anche per ciascun motore, ma se sono costruiti con lo stesso valore letterale o funzione, è più probabile che vengano trattati come simili.

Nessun motore che funziona bene sui benchmark JavaScript utilizzerà lo stesso algoritmo per ogni oggetto.Tutti devono determinare dinamicamente come viene utilizzato l'oggetto e provare a regolare l'algoritmo di accesso di conseguenza.