二次元配列で、特定Keyに対するValueが重複しているものを、1つ残して重複を無くすのではなく全部削除したい

Question

二次元配列で、中の配列の特定keyに対するvalueが重複していた時に
そのvalueを持つもの全てを削除したいです。

少しコード直してみて、動くには動いたのですが
とても無駄が多いように思っているので良い方法が知りたいです。

###実現したいこと
普通の配列だとこんなイメージ。
[1,2,2,3,4,4,4] → [1,3]
// 2と4は複数あるので全部削除

今回やりたいのは、二次元かつ連想配列でこんなイメージです。
[{a:1,b:"h"},{a:1,b:"e"},{a:2,b:"l"},{a:3,b:"l"},{a:1,b:"o"}]
→ [{a:1,b:"h"},{a:1,b:"e"},{a:1,b:"o"}]
// bが"l"のものだけ削除

単純な重複削除であればfilterを使えばできるのですが
そもそも全部消したいとなると、一度重複するものを抽出して更に突合させないといけなくて
しかもそれが二次元配列かつ連想配列だと...と混乱してきてしまいました。。

↓↓一応これでできたけど、無駄がすごく多いきがする...

var arr = [{a:1,b:"h"},{a:1,b:"e"},{a:2,b:"l"},{a:3,b:"l"},{a:1,b:"o"}] 

// 一度bだけ取り出して、重複しているものを探す
var check = [];
for(i=0; i<arr.length; i++){
	check.push(arr[i]["b"]);
}
var dubble = check.filter(function(x, i, arr){
	// check中のものが配列の中で最初にhitして、別でもhitする場合だけ抽出
	return arr.indexOf(x) === i && i !== arr.lastIndexOf(x);
});

var compArr = [];
for(i=0; i<arr.length; i++){
	var flg = false;
	for(j=0; j<dubble.length; j++){
		if(arr[i]["b"] == dubble[j]){
			flg = true;
		}
	}
	if(!flg) compArr.push(arr[i]);
}

###補足情報(言語/FW/ツール等のバージョンなど)
jQueryなどが使えないので、素の状態で書きたいです。

Comments

[kei344]

「一度重複するものを抽出して更に突合わせた」場合のコードを未完成でも良いので追記されたほうが回答が得やすいと思います。

[leila]

ありがとうございます、追記してみました！

Answer 1

こんな感じでも出来ました。重複している値を配列化して、それらをピンポイントで削除するアプローチですね。

var arr = [{a:1,b:"h"},{a:1,b:"e"},{a:2,b:"l"},{a:3,b:"l"},{a:1,b:"o"}];

var deleteDuplicateVal = function(array, key) {
  var delArr = array.map(function(e, i) {
    return e[key];
  }).filter(function(e, i, array) {
    /* 重複するものを抽出 */
    return array.indexOf(e) !== i;
  }).filter(function(e, i, array){
    /* 抽出した中での重複削除 */
    return array.indexOf(e) === i;
  });
  
  console.log(delArr); // ["l"]

  var result = array.filter(function(e, i) {
   return delArr.indexOf(e[key]) === -1;
  });

  return result;
};

var filtered = deleteDuplicateVal(arr, 'b');

console.log(filtered);

Comments

[think49]

> delete e[key];
削除対象はプロパティbではなく、該当要素自身ではないでしょうか。

> var result = array.map(function(e, i) {
おそらく、Array#mapは配列のディープコピー目的で使われたと思いますが、実際にはシャローコピーなので、破壊的な変更が加えられています。
console.log(JSON.stringify(arr)); // [{"a":1,"b":"h"},{"a":1,"b":"e"},{"a":2},{"a":3},{"a":1,"b":"o"}]
console.log(JSON.stringify(filtered)); // [{"a":1,"b":"h"},{"a":1,"b":"e"},{"a":2},{"a":3},{"a":1,"b":"o"}]

下記コードに修正して期待通りに動作する事を確認しました。
var result = array.filter(function(e, i) { return delArr.indexOf(e[key]) === -1; });

[yamato_hikawa]

補足ありがとうございます。要件を勘違いしていました。
delArrにないものだけを返すということですね。コードを修正しました。

[leila]

ご回答ありがとうございました！そして質問解りづらくてすみません...！！＞＜
重複している値を配列化してピンポイント削除、の考え方は
最初、そんな流れで書けないかな？と思っていた形だったのでとてもしっくり来ました。

[yamato_hikawa]

{b:"l"}が存在するオブジェクトが3つ以上あるときに、delArrの配列が["l","l"...]となってしまっていたので、重複削除のロジックを追加しておきました。
ただし、delArrの要素が重複していても最終結果自体は変わりません。

[think49]

> 重複削除のロジックを追加しておきました。
参考までに、reduceを使えば「filter x 2 -> reduce x 1」に抑えられますね。
https://jsfiddle.net/0pfmffke/
また、逆転の発想で lastIndexOf で「重複しない要素」をfilterするようにしてやれば、検索しながら「重複する最後の要素のindex値」をキャッシュしてやれば済むようになり、検索効率が上がります。
https://jsfiddle.net/0pfmffke/2/

[yamato_hikawa]

その辺りはいろいろとチューニングできそうですね。ありがとうございます。

Answer 2

findIndex + findLastIndex 型

配列を前方/後方検索し、index が一致したら重複なしと見なします。
アルゴリズムは単純ですが、重複が全くないと配列全体を要素数だけ検索するのでコストがかかります。
また、Array.prototype.findLastIndex が存在しないので自前定義する必要があります。

/**
 * findIndex + findLastIndex 型
 */
var removeOverlapB1 = (function () {
  function findLastIndex (array, callbackfn, thisArg) {
    var i = array.length, hasThisArg = arguments.length > 2;

    while (i--) {
      if (hasThisArg) {
        if (callbackfn.call(thisArg, array[i], i, array)) {
          return i;
        }
      } else if (callbackfn(array[i], i, array)) {
        return i;
      }
    }

    return -1;
  }

  function findIndexfn (object) {
    return object.b === this;
  }

  function filterfn (object, i, array) {
    var b = object.b;

    return array.findIndex(findIndexfn, b) === findLastIndex(array, findIndexfn, b);
  }

  return function removeOverlapB (array) {
    return array.filter(filterfn);
  };
}());

var array = [{a:1,b:"h"},{a:1,b:"e"},{a:2,b:"l"},{a:3,b:"l"},{a:1,b:"o"}]
console.log(JSON.stringify(removeOverlapB1(array)));  // [{"a":1,"b":"h"},{"a":1,"b":"e"},{"a":2,"b":"l"},{"a":1,"b":"o"}]

findIndexAll 型

Array.prototype.findIndex を発展させ、配列全体からHITした index 値のリストを返す findIndexAll を定義し、返り値となる配列の length 値が 0 なら重複なしと見なします。
一度、重複ありと見なしたインデックスをキャッシュし、再検索しないことで検索コストを抑えます。
ただし、配列全体が検索対象であることは変わりない為、重複が少ないと検索コストが高くなる問題は依然としてあります。

/**
 * findIndexAll 型
 */
var removeOverlapB2 = (function (push) {
  function findIndexAll (array, callbackfn, thisArg) {
    var indexes = [], hasThisArg = arguments.length > 2;

    for (var i = 0, l = array.length; i < l; ++i) {
      if (hasThisArg) {
        if (callbackfn.call(thisArg, array[i], i, array)) {
          indexes.push(i);
        }
      } else if (callbackfn(array[i], i, array)) {
        indexes.push(i);
      }
    }

    return indexes;
  }

  function findIndexAllfn (object) {
    return object.b === this;
  }

  function filterfn (object, i, array) {
    if (this.indexOf(i) !== -1) {
      return false;
    }

    var indexes = findIndexAll(array, findIndexAllfn, object.b);

    if (indexes.length === 1) {
      return true;
    }

    push.apply(this, indexes);
    return false;
  }

  return function removeOverlapB (array) {
    return array.filter(filterfn, []);
  };
}(Array.prototype.push));

var array = [{a:1,b:"h"},{a:1,b:"e"},{a:2,b:"l"},{a:3,b:"l"},{a:1,b:"o"}]
console.log(JSON.stringify(removeOverlapB2(array)));  // [{"a":1,"b":"h"},{"a":1,"b":"e"},{"a":2,"b":"l"},{"a":1,"b":"o"}]

while 文 + 後方検索キャッシュ型

while 文で前方検索/後方検索し、index が同値なら重複なしと見なします。
検索時に重複値をキャッシュする為、一度重複なしと見なされればキャッシュから重複判定出来ます。
コードが複雑化していますが、私が考えうる限りでは「検索コストが最も低い(無駄が少ない)コード」です。

/**
 * while 文 + 後方検索キャッシュ型
 */
function removeOverlapB3 (array) {
  var i = -1,
      l = array.length,
      j = l,
      conflicts = [],
      values = [],
      results = [];

  if (l < 2) {
    return array;
  }

  while (++i < l) {
    var current = array[i],
        b = current.b,
        cindex = values.indexOf(b);

    if (cindex === -1) {
      values.push(b);
      cindex = conflicts.push(false) - 1;

      while (i < --j) {
        var target = array[j],
                tb = target.b;

        if (b === tb) {
          conflicts[cindex] = true;
          break;
        } else {
          var tindex = values.indexOf(tb);

          if (values.indexOf(tb) === -1) {
            values.push(tb);
            conflicts.push(false);
          } else {
            conflicts[tindex] = true;
          }
        }
      }

      if (i === j) {
        results.push(current);

        while (++i < l) {
          var current = array[i],
              b = current.b;

          if (!conflicts[values.indexOf(b)]) {
            results.push(current);
          }
        }

        break;
      }
    } else {
      conflicts[cindex] = true;
    }
  }

  return results;
}

var array = [{a:1,b:"h"},{a:1,b:"e"},{a:2,b:"l"},{a:3,b:"l"},{a:1,b:"o"}]
console.log(JSON.stringify(removeOverlapB3(array)));  // [{"a":1,"b":"h"},{"a":1,"b":"e"},{"a":2,"b":"l"},{"a":1,"b":"o"}]

Re: leila さん

Comments

[leila]

3パターンもご丁寧に、しかもコスト面までご説明ありがとうございます！
恥ずかしながらarguments知りませんでした...
1つ1つお手本にさせていただきます。

Answer 3

汚い書き方ですが、指定通りに冗長にやるとこんなかんじ

<script>
var x=[{a:1,b:"h"},{a:1,b:"e"},{a:2,b:"l"},{a:3,b:"l"},{a:1,b:"o"},{a:3,b:"l"},{a:3,b:"l"},{a:3,b:"l"},{a:3,b:"l"}];
var y=[];
var z={};
for(var i=0;i<x.length;i++){
  if(typeof z[x[i]["b"]]=="undefined"){
   z[x[i]["b"]]=i;
    y[i]=false;
  }else{
    y[z[x[i]["b"]]]=true;
    y[i]=true;
  }
}
for(var i=y.length-1;i>=0;i--){
  if(y[i]) x.splice(i,1);
}
//以下検証
for(var i=0;i<x.length;i++){
  console.log(i+":a="+x[i]["a"]+":b="+x[i]["b"]);
}
</script>

Comments

[leila]

最初のindexの位置を利用してtrue/false判断を全体でしていくのですね。
削除していく、の形でいただきありがとうございますー！

Answer 4

こんな感じとか。

var arr = [{a:1,b:"h"},{a:1,b:"e"},{a:2,b:"l"},{a:3,b:"l"},{a:1,b:"o"}];
var check = [];
arr.forEach( function ( e, i, array ) {
	check[ e.b ] = ( e.b in check ) ? true : false;
} );
var filtered = arr.filter( function ( e, i, array ) {
	return true !== check[ e.b ];
} );
console.log( filtered );

動くサンプル：https://jsfiddle.net/d5bj2s7j/1/

---

追記：

var arr = [{a:1,b:"h"},{a:1,b:"e"},{a:2,b:"l"},{a:3,b:"l"},{a:1,b:"o"}] ;
var check1 = [], check2 = [];
arr.forEach( function ( e ) {
	if ( check1.indexOf( e.b ) !== -1 ) { check2.push( e.b ); }
	check1.push( e.b );
} );
var filtered = arr.filter( function ( e ) {
	return ( check2.indexOf( e.b ) === -1 );
} );
console.log( filtered );

動くサンプル：https://jsfiddle.net/d5bj2s7j/2/

Comments

[leila]

すごい解りやすいですー！！
無理に重複のものだけとかじゃなくて、判断できる材料をちゃんと揃えれば
綺麗にできるのですね...ありがとうございます！

[think49]

このコードには次の問題があります。
　(問題点1) in 演算子はプロトタイプチェーンを辿る(Object.prototype.valueOf や Array#length を存在すると認識する)
　(問題点2) プロパティに b 値を埋め込む関係上、プロパティ b 値が String 型に変換される。つまり、{} === {} や '1' === 1 と判定される。
従って、重複が存在しない次の配列を与えても [] を返してきます。
var arr = [{a: 1, b: 'valueOf'}, {a: 1, b: {}}, {a: 2, b: {}}, {a: 3,b: 1}, {a: 1, b: '1'}];

> var check = [];
ここは var check = {}; と書きたかったのでしょうか。
配列を使うなら in 演算子ではなく、Array#indexOf を使う場面だと思います。
オブジェクト初期化子を使うなら Object.create(null) を使えば [[Prototype]] が空になります(ただし、String 型に変換される問題は残ります)。
あるいは、new Map も良いと思います。

[kei344]

To: think49
> 問題点
おっしゃるとおりです。まず、プロパティ b 値が String 型以外を想定していませんでした。in 演算子の挙動も頭から抜けていました。

> var check = [];
例示されたものをそのまま考えずに使った、というだけです。