オブジェクト引数の効率的なメモ帳

Question

要約：オブジェクトをハッシュする高速な方法はJSON.stringifyですか？

詳細：JavaScript値をきれいに印刷できるRubyおよびJavaScriptライブラリ（NeatJSON）があります。私は最近、深くネストされたオブジェクトが、直列化されるオブジェクトとインデント量に基づいてメモを使用して、O（n！）のパフォーマンス（ネストレベルであるn）を引き起こした問題を修正しました。ルビー、the fixで

は、本当に簡単だったことができますオブジェクトの一意のセットの配列によってインデックスハッシュ理由：内のJavaScriptで

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

、しかし、私は、インデックス別のオブジェクトによって、オブジェクトをすることはできません（ユニークな方法）。私はオンラインで見つけるいくつかの記事のリードに続いて、私はメモ化のためのユニークなキーを作成する関数に引数のフルセットにJSON.stringifyを使用して、一般的にfix the problemに決める：

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); 

これは動作しますが、（a）はこれです（b）私がスマートにシリアル化しようとしているすべてのオブジェクトと値を（単純な）直列化を実行することは、非常に非効率的で（そして控えめで）思われます。多くの値を持つラージオブジェクトをシリアライズする行為は、文字列を格納し、オブジェクト全体にEVERY一意の値（葉の値だけではない）の結果を書式設定することになります。

値を一意に識別できる最新のJavaScriptトリックはありますか？たとえば、内部IDにアクセスする方法や、複雑なオブジェクトをO（1）時間を費やして値の識別子を見つけるユニークな整数に関連付ける方法はありますか？

Answer 1

あなたのオブジェクトをアイデンティティ（コンテンツではなく）でメモしたい場合は、この目的のために設計されたWeakMapを使用します。これらは基本的な値では機能しませんので、そのような引数に対しては別の解決策が必要です。

Answer 2

オブジェクトをメモする必要がある場合は、オブジェクトに一意のIDを割り当てるのが理にかなっています。

var gID = 0; 

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

とあなたのmemoコレクションのキーとしてそれらobj.id年代を使用しています。

これは、最も速く、最も欲張りのない解決策です。

更新：

あなたはそのidプロパティは、あなたが（いくつかのユニークな名前を持つ）非可算標準ES5.1 Object.createProperty()を使用してプロパティを作成することができ、既存のプロパティ と衝突していないか、または使用したい場合はES6 symbols：

私はおよそ Map、キー（だけではなくオブジェクト）として いかなる値の型を使用して可能になるのが分かった WeakMapのBergiの提案@使用

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

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

Answer 3

。シリアライズ時に

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]; 
    } 
} 

これはmemoization code I had been using比べて約4倍に高速であることが証明された：私は、キーを一意とインデントに渡された値の組み合わせmemoizing化合物を必要なので、文字列を-Iは、階層的なメモ化構造を作成しました大きな270kBのJSONオブジェクト

私はrawBuildがfalsey値を返すことはありませんことを知っているので、上記のコードでは、私が唯一!byIndent[indent]を使用することができるよという注意（null、undefinedを、false、NaN、0、""）。より安全なコード行は次のようになります。

[JavaScriptのオブジェクトID]の（ではない、非常にDUP）と非常に類似し

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