Memoizzazione efficiente degli argomenti dell'oggetto

Question

Sommario: Esiste un modo più veloce per gli oggetti hash rispetto a JSON.stringify?

Dettagli: Ho una libreria Ruby e JavaScript (NeatJSON) che fornisce una buona stampa dei valori JavaScript. Recentemente ho risolto un problema in cui oggetti profondamente nidificati causavano prestazioni O (n!) (n come livello di nidificazione) utilizzando la memoizzazione in base all'oggetto serializzato e all'importo dell'indentazione.

In Ruby, the fix stato davvero facile, perché si può hash indice di array di gruppi unici di oggetti:

build = ->(object,indent) do 
    memoizer[[object,indent]] ||= <all the rest of the code> 
end 

in JavaScript, tuttavia, non possono indicizzare un oggetto da un altro oggetto (in una modo unico). Seguendo l'esempio di diversi articoli che ho trovato on-line, decido di fix the problem genericamente, usando JSON.stringify sulla serie completa di argomenti per la funzione di creare una chiave univoca per Memoizzazione:

function memoize(f){ 
    var memo = {}; 
    var slice = Array.prototype.slice; 
    return function(){ 
    var args = slice.call(arguments); 
    var mkey = JSON.stringify(args); 
    if (!(mkey in memo)) memo[mkey] = f.apply(this,args); 
    return memo[mkey]; 
    } 
} 

function rawBuild(o,indent){ .. } 
var build = memoize(rawBuild); 

Questo funziona, ma (a) E ' un po 'più lentamente di quanto mi piacerebbe, e (b) sembra selvaggiamente inefficiente (e poco elegante) per eseguire una serializzazione (ingenua) di ogni oggetto e valore che sto per serializzare in modo intelligente. L'atto di serializzare un oggetto grande con molti valori memorizzerà una stringa e un risultato di formattazione per OGNI valore univoco (non solo valori foglia) nell'intero oggetto.

Esiste un moderno trucco JavaScript che consenta di identificare univocamente un valore? Ad esempio, un modo per accedere a un ID interno o associare in altro modo oggetti complessi con numeri interi univoci che richiede O (1) tempo per trovare l'identificatore per un valore?

Answer 1

Se stai cercando di memoizzare i tuoi oggetti per identità (non per contenuto), allora ti consigliamo di utilizzare uno WeakMap che è stato progettato esattamente per questo scopo. Tuttavia non funzionano per i valori primitivi, quindi avrai bisogno di una soluzione diversa per tali argomenti.

Answer 2

Se hai solo bisogno di memoise oggetti, allora ha senso assegnare un ID univoco ai tuoi oggetti.

var gID = 0; 

function createNode() { 
    var obj = ... 
    obj.id = (++gID).toString(); 
} 

e utilizzare tali obj.id 's come chiavi nella vostra collezione memo.

Questa sarebbe la soluzione più veloce e meno avida.

Aggiornamento:

Se si desidera che la proprietà ID per non scontrarsi con le proprietà esistenti quindi è possibile creare non enumerabile proprietà utilizzando ES5.1 serie Object.createProperty() (con qualche nome unico) o di utilizzare ES6 symbols:

var gID = 0; 
var gUidSym = Symbol("uid"); 

function getUidOf(obj) { 
    return obj[gUidSym] 
     || (obj[gUidSym] = (++gID).toString()); 
} 

Answer 3

utilizzando @ suggerimento di Bergi di un WeakMap ho scoperto circa Map, che consente di utilizzare qualsiasi tipo valore come la chiave (non solo gli oggetti).Perché ho bisogno di chiave univoco memoizing la combinazione del valore passato e il rientro un composto stringa Ho creato una struttura Memoizzazione gerarchica:

function memoizedBuild(){ 
    var memo = new Map; 
    return function(value,indent){ 
    var byIndent=memo.get(value); 
    if (!byIndent) memo.set(value,byIndent={}); 
    if (!byIndent[indent]) byIndent[indent] = rawBuild(value,indent); 
    return byIndent[indent]; 
    } 
} 

Questo si è rivelato essere di circa 4 × più veloce rispetto alla memoization code I had been using durante la serializzazione un grande oggetto JSON da 270kB.

Si noti che nel codice sopra sono in grado di utilizzare !byIndent[indent] solo perché so che rawBuild non potrà mai restituire un valore Falsey (null, undefined, false, NaN, 0, ""). La riga di codice più sicuro sarebbe simile:

if (!(indent in byIndent)) byIndent[indent] = rawBuild(value,indent);