1

私はすでにこれを解決しました。ただし、変数には数千のオブジェクトがあるため、より高速なソリューションを探しています。

私はこのような2つの配列を持っています：

var full = [{a:'aa1',b:'bb1'},{a:'aa3',b:'bb2'},{a:'aa3',b:'bb3'},{a:'aa2',b:'bb3'}],
some = [{a:'aa1',b:'bb1'},{a:'aa3',b:'bb3'}];

オブジェクトがいくつかに存在する場合に呼び出される新しい属性でフラグを立てようとしています。期待される結果：cfull

 [{a:'aa1',b:'bb1',c:true},{a:'aa3',b:'bb2'},{a:'aa3',b:'bb3',c:true},{a:'aa2',b:'bb3'}]

いくつかの重要なヒント：

  • 一部は常に完全よりも少ない要素を持っています
  • 両方の配列は等しくソートされます

私の現在のアプローチは次のとおりです。

var getIndexByAB = function(arr, a,b){
     var initialIndex =  getIndexByAB.initialIndex || 0,
     len = arr.length;
     for(initialIndex; initialIndex < len ;initialIndex++ ){
         var el = arr[initialIndex];
         if( el.b === b && el.a === a ){
             getIndexByAB.initialIndex = initialIndex;
             return initialIndex;
         }
     }
     return -1;
}

var len = some.length;
for(var i = 0; i < len ; i++){
 var el=some[i],
 index = getIndexByAB(full,el.a,el.b);
 if(index > -1) full[index].c = true;
}

UPDADE：Juanコメントを使用して改善された元のソリューション。

4

3 に答える 3

1

それらはソートされているので、検索を開始するためのインデックスを渡すだけで、O（n ^ 2）を回避できます。あなたはすでにそれを行っていましたが、インデックスをグローバル変数に格納することによって。代わりに、引数としてに渡す必要がありますgetIndexByAB。

function getIndexByAB(arr, a,b , initialIndex){
    // Was tracking last index by storing it in a global 'this.initialIndex'. 
    // 'this' points to 'window' in global functions. That's bad, it 
    // means this function can't be called on different arrays without
    // resetting the global 

    // var initialIndex =  this.initialIndex || 0,

    initialIndex = initialIndex || 0;
    var len = arr.length;
    for(initialIndex; initialIndex < len ; initialIndex++ ){
        var el = arr[initialIndex];
        if( el.b === b && el.a === a ){
            // Bad globals
            // this.initialIndex = initialIndex;
            return initialIndex;
        }
    }
    return -1;
}

var len = some.length;
var lastValidIndex = 0;
for(var i = 0; i < len ; i++){
    var el = some[i];
    // Pass the index here, so it doesn't start from scratch
    var index = getIndexByAB(full, el.a, el.b, lastValidIndex);
    if(index > -1) {
        full[index].c = true;
        lastValidIndex = index;
    }
}

ちなみに、関数にいくつかの値をキャッシュさせたい場合は、グローバルを避けてそれを行う方法を次に示します。（この場合は使用しないでください）

var getIndexByAB = (function(){
     // This will only be executed once, and is private
     // to getIndexByAB (all invocations)
     var lastGoodIndex = 0;

     return function(arr, a,b, resetIndex){
         if (resetIndex) {
            lastGoodIndex = 0;
         }

         var len = arr.length;
         for(var index = lastGoodIndex; index < len ; index++ ){
             var el = arr[index];
             if( el.b === b && el.a === a ){                 
                 lastGoodIndex = index;
                 return index;
             }
         }
         return -1;
    };
})();

または、キャッシュすることで次のことを実現できますが、getIndexByAB.initialIndexあまりエレガントではありません。これを回避する主な理由は、getIndexByAB.initialIndex他の人が変更できるという事実です。

于 2013-02-21T19:47:34.690 に答える
0

配列は両方ともソートされており、some厳密に。よりも小さいためfull、異なるインデックスを使用して両方の配列を同時にトラバースすることで、時間を節約できます。fullそのままでは、毎回一致する要素のインデックスを取得するためにトラバースしているため、実行時間はO（N ^ 2）ですが、最後に一致した要素から検索を続行するだけで済みます。

于 2013-02-21T19:42:12.400 に答える
0

@Juanの回答（特にソートされた性質を利用する）ほど効率的ではありませんが、偶然にJavacriptオブジェクトのクローンを作成して比較するためのソリューションを考え出す必要があったため、ソリューションを提示したいと思いました。

ユーティリティ

// Create a copy of x without reference back to x
function clone(x){
  return JSON.parse(JSON.stringify(x));
}

// Pass any number of arguments of any type. Returns true if they are all identical.
function areEqual(){
  for(var i = 1, l = arguments.length, x = JSON.stringify(arguments[0]); i < arguments.length; ++i){
    if(x !== JSON.stringify(arguments[i])){
      return false;
    }
  }

  return true;
}

フラグ機能

// Your flagLabel being 'c'
function matchAndFlagWith(flagLabel,aFull,aSome){
  var aFlagged = clone(aFull);

  for(var i1 = 0, l1 = aSome.length, oSome; oSome = aSome[i1], i1 < l1; ++i1){
    for(var i2 = 0, l2 = aFlagged.length, oFlagged; oFlagged = aFlagged[i2], i2 < l2; ++i2){
      if(areEqual(oFlagged,oSome)){
        oFlagged[flagLabel] = true;
      }
    }
  }

  return aFlagged;
}

デモ

http://jsfiddle.net/barney/p2qsG/

于 2013-02-22T11:18:43.930 に答える