IDで2つのJavascript/JSONオブジェクトを結合する最速の方法

Question

Javascript Objectsが2つあると仮定します（これらはJSON構造ですが、JSON.parse()で作成されます）。すべてのエントリには、両方のオブジェクトのエントリを一致させるユニークなIDがあります。 両方のオブジェクト（ネイティブjavascript）を結合する最も速い方法は何でしょうか。

私の頭に浮かぶ最初のものは、入れ子になったfor in loopです。

for(var i in firstJson) { 
    for(var j in secondJson) { 
     if(firstJson[i].id === secondJson[j].id) { 
      // join them 
     } 
    } 
} 

速い方法がありますか？

Answer 1

もっと効率的な方法は、それらのいずれかのうち、インデックスを作成するには、次のようになります。

var index = {}; 
for (var j in secondJson) { 
    var obj = secondJson[j]; 
    index[obj.id] = obj; 
}; 

for (var i in firstJson) { 
    var firstObj = firstJson[i]; 
    var match = index[firstObj.id]; 
    if (match) { 
     // do the stuff 
    } 
}; 

これはO(n+m)の代わりに、ネストされたループのO(n*m)です。もちろん、メモリはO(m)である。

Answer 2

両方のリストがまだソートされていない場合は、最初にIDでソートしてから比較し、最後に見つかったオブジェクトの位置を保存します。

（私は気まぐれからソリューションが高速であると信じていますが、これは余分なメモリ消費を持っていない）

これは、オーダーO（nはログ（N）+ Mログ（M）+にする必要がありますm）

first.Sort(); 
second.Sort(); 


int idx = 0; 
int lastIdx = 0; 
for (int i = 0; i < first.Count; i++) { 
    for (int j = idx; j < second.Count; j++) 
    { 
    if (first[i] == second[j]) 
    { 
     Console.WriteLine("equal " + first[i]); 
     idx = j + 1; 
     lastIdx = idx; 
     break; 
    } 
    } 
    if (idx == second.Count) 
    idx = lastIdx; 
}