Prestazioni di accesso alle proprietà big-O Javascript

Question

Quali sono le caratteristiche delle prestazioni dell'accesso alle proprietà JavaScript (sulle attuali implementazioni)?

• È sicuro assumere l'accesso di matrice è O (1)?

• Se utilizzo un oggetto come tabella hash (con chiavi stringa), posso tranquillamente dedurre O (1) o O (log n) tempo di accesso?

• Ci sono browser o ambienti comuni che sono significativamente più veloci/lenti degli altri e che dovrei tenere d'occhio?

• Gli standard JavaScript hanno qualcosa da dire?

E, soprattutto:

• Dove posso trovare buone referenze per questo tipo di asintotica problemi di prestazioni JavaScript?

Answer 1

Ogni oggetto in JavaScript è implementato come un hash dell'oggetto, quindi non c'è alcuna differenza funzionale.

Ad esempio, controlla questo test:

var arr = []; 
arr[5] = 5; 
arr['5'] = 'not 5'; 
console.log(arr.length, arr); 
// output: 6 [undefined, undefined, undefined, undefined, undefined, "not 5"] 

numeri sono stringata quando usato come posizioni.

Vedere Crockford's website su JavaScript per ulteriori informazioni. La parte particolarmente importante è sotto la voce "array":

Arrays in JavaScript are also hashtable objects.

prestazioni non è davvero un problema a meno che non si dispone di una tonnellata di oggetti per tenere traccia di (come 500.000+), nel qual caso si' probabilmente stai facendo qualcosa di sbagliato.

Ci sono ottimizzazioni che puoi fare, ma non hanno senso se non stai facendo qualcosa di innaturale con JavaScript (come gli algoritmi di compressione ... ho lavorato su un'implementazione LZMA in JS ... cattiva idea).

Nota:

Se si dispone di un set di ricambio (come si definisce solo 10 indici su 10.000), probabilmente si dovrebbe essere utilizzando un oggetto normale. Gli array inizializzeranno tutti i 10.000 indici su "non definito", mentre lo Object.keys(obj) segnalerà solo il 10 che hai impostato. Questa è un'ottimizzazione minore che in realtà ha senso.