二つの配列、それぞれに含まれるユニークな値をできるだけ高速に抽出する方法
退会済みユーザー
総合スコア0

Question

### 前提・実現したいこと質問は表題の通り。以下は理解のためのイメージコードです。 ※ただし**実際の要素はリテラルでなくObjectです**。実際のお試しコードは後述。 ```javascript const a = [0,1,2,3]; const b = [2,3,4,5]; const [onlyA, onlyB] = getUnique(a, b); console.log(onlyA) // [0,1] console.log(onlyB) // [4,5] function getUnique(a,b) { // この中身を書きたい return [onlyA, onlyB] // 戻り値も目的が達せられれば変わっても可 } ``` お題が定性的ですが、以下の「試したソースコード」のテストコードよりも早ければありがたいな、という感じです。2回for回すのを回避する方法ないのかな、という感じ。 ### 試したソースコード以下がテストコードです。for文2回で頑張るパターンとfilter2回やるパターンでやりました。[のJSFiddle](https://jsfiddle.net/35khjnsm/9/) ```javascript const test = [getUnique1, getUnique2]; function init() { const a = []; const b = []; const num = 1000; for (let i = 0; i < num; i++) { const x = i; const y = i % 20; if (i >= 100) { a.push({ x, y }) } if (i < 900) { b.push({ x, y }) } } b.sort(() => Math.random() - 0.5); // 適当にbのソートを崩す目的 return [a, b] } /** for文で頑張る */ function getUnique1(a, b) { const onlyA = []; const onlyB = []; for (let ai = 0, al = a.length; ai < al; ai++) { let hit = false; for (let bi = 0, bl = b.length; bi < bl; bi++) { if (a[ai].x === b[bi].x && a[ai].y === b[bi].y) { hit = true; break; } } if (!hit) { onlyA.push(a[ai]); } } for (let bi = 0, bl = b.length; bi < bl; bi++) { let hit = false; for (let ai = 0, al = a.length; ai < al; ai++) { if (a[ai].x === b[bi].x && a[ai].y === b[bi].y) { hit = true; break; } } if (!hit) { onlyB.push(b[bi]); } } return [onlyA, onlyB]; } /** filter使う */ function getUnique2(a, b) { return [ a.filter((av) => b.findIndex((bv) => av.x === bv.x && av.y === bv.y) === -1), b.filter((bv) => a.findIndex((av) => av.x === bv.x && av.y === bv.y) === -1) ] } const result = [] const [a, b] = init(); for (let i = 0; i < test.length; i++) { const start = Date.now(); // 一度結果のテスト const [onlyA, onlyB] = test[i](a, b); if (onlyA.length !== 100 || onlyB.length !== 100 || onlyA.map(v => v.x).reduce((a, b) => a + b) !== 94950 || onlyB.map(v => v.x).reduce((a, b) => a + b) !== 4950) { alert(`error(expect 100): onlyA.length:${onlyA.length} xSum:${onlyA.map(v => v.x).reduce((a, b) => a + b)}, onlyB.length:${onlyB.length} xSum:${onlyB.map(v => v.x).reduce((a, b) => a + b)}`) console.log(onlyA) console.log(onlyB) return; } for (let j = 0; j < 1000; j++) { test[i](a, b); } const end = Date.now(); result.push({ time: end - start, name: test[i].name }) } const strs = result.map(v => `${v.name}: ${v.time}ms`) alert(strs); ``` 私の環境でChromeにてfor文２回（getUnique1）が 931ms、filter使うのが（getUnique2） 694msでした。（for文のが早いかなと予想してたがfilterの方が早かった。しかしIEでポリフィルとか使うときっとfilterの方が遅いと思う。）

Answer

**データ構造**を見直すことを検討してみて下さい。データが作成された時点で最適化の9割は完了しています。 ```JavaScript 'use strict'; const Point = (() => { const wm = new WeakMap; return class Point { constructor (x, y) { wm.set(this, Object.create(null)); this.x = x; this.y = y; } get x () { return wm.get(this).x; } get y () { return wm.get(this).y; } set x (value) { const thisArg = wm.get(this); this.valuesAsJson = JSON.stringify([thisArg.x = value, thisArg.y]); } set y (value) { const thisArg = wm.get(this); this.valuesAsJson = JSON.stringify([thisArg.x, thisArg.y = value]); } }; })(); class PointList { constructor (points) { this.uniqueMap = new Map; this.array = []; if (arguments.length) { this.push(...points); } } push (...points) { const uniqueMap = new Map, len = points.length; for (let point of points) { const json = point.valuesAsJson, values = uniqueMap.get(json); values ? values.add(point) : uniqueMap.set(json, new Set([point])); } this.uniqueSet = new Set(uniqueMap.keys()); return this.array.push(...points); } } function getOnlyPoints (setA, setB) { setA = new Set(setA), setB = new Set(setB); for (let value of setA) { if (setB.has(value)) { setA.delete(value), setB.delete(value); } } for (let value of setB) { if (setA.has(value)) { setA.delete(value), setB.delete(value); } } return [setA, setB]; } function init() { const a = new PointList; const b = []; const num = 1000; for (let i = 0; i < num; i++) { const x = i; const y = i % 20; if (i >= 100) { a.push(new Point(x, y)) } if (i < 900) { b.push(new Point(x, y)) } } b.sort(() => Math.random() - 0.5); // 適当にbのソートを崩す目的 return [a, new PointList(b)] } const [a, b] = init(); console.time('getOnlyPoints'); const [onlyA, onlyB] = getOnlyPoints(a.uniqueSet, b.uniqueSet); console.timeEnd('getOnlyPoints'); console.log(onlyA); console.log(onlyB); ``` Re: jjj_aaa さん

Answer

IEのPolyfill なんて言葉もコメントされていたので、若干、古典的手法で考えてみました
意図する抽出になっていますかね？

```javascript
function getUnique(a,b) {
  let hasA = {};
  let hasB = {};

  let setPos = (oj,v) => {
    let pos = `${v.x}:${v.y}`;
    (oj[pos] || (oj[pos]={ count:0, item:v })).count++;
  };
  let filterByPos = (oj,oj2) => {
    let rslt = [];
    let keys = Object.keys( oj );
    for ( let i=0, l=keys.length; i<l; ++i ) {
      let pos = keys[i];
      if( oj2.hasOwnProperty(pos) ) {
        // 両方に存在しない
        delete oj[pos];
        delete oj2[pos]
      }
      else if( oj[pos].count > 1 ) {
        // oj内で重複しない
        delete oj[pos]
      }
      if( oj[pos] ) rslt.push(oj[pos].item);
    }
    return rslt;
  };

  a.forEach(v => {setPos(hasA,v)} );
  b.forEach(v => {setPos(hasB,v)} );
  return [
    filterByPos( hasA, hasB )
  , filterByPos( hasB, hasA )
  ];
};
```
オブジェクト(``{x: num, y:num }``)を返却してなかったのでコードを差し替えしました。
filter().map() を使うべきところforで走査回数を抑えました。

Answer

こんにちは [lodash](https://lodash.com/) を使えば、以下のように書けるかなと思います。 ```javascript const getUnique = (a,b) => _.differenceWith(a, b, _.isEqual); ``` - **例1:** [https://codepen.io/jun68ykt/pen/abbjwqM?editors=0012](https://codepen.io/jun68ykt/pen/abbjwqM?editors=0012) 要素がオブジェクトの場合の例が以下です。 - **例2:** [https://codepen.io/jun68ykt/pen/GRRBEYj?editors=0012](https://codepen.io/jun68ykt/pen/GRRBEYj?editors=0012) ### 追記 - getUnique10 上記ではlodashを使った汎用的なコードを挙げましたが、コメントから頂きましたjsFiddleのテストコードによって生成されるオブジェクトの配列を処理することに特化したコードも考えてみました。以下の `getUnique10` になります。 ```javascript function getUnique10(a, b) { const [setA, setB] = [new Set(), new Set()]; for (let e of a) setA.add(e.id); for (let e of b) setB.add(e.id); const onlyA = a.filter(e => !setB.has(e.id)); const onlyB = b.filter(e => !setA.has(e.id)); return [onlyA, onlyB] } ``` この `getUnique10` を試すコードを以下の jsFiddle に作成しました。 - **getUnique7 vs getUnique10：** [https://jsfiddle.net/jun68ykt/b501gqpj/1/](https://jsfiddle.net/jun68ykt/b501gqpj/1/) 上記は、コメントからご教示いただきました、 [https://jsfiddle.net/e9a5kvw2/](https://jsfiddle.net/e9a5kvw2/) を Forkして、テスト対象として`getUnique10` を追加したものです。 ### 追記 - getUnique11 前掲の `getUnique10` の改良案を挙げます。この改良案は、(2019/11/14 21:10のコメントに書いたとおり、）下記 ```javascript const num = 1000; for (let i = 0; i < num; i++) { const x = i; const y = Math.floor(Math.random() * num); // const id = `${x}:${y}` const id = 1000 * x + y; 　･･･ ``` のようなコードによって、 `id` に０以上の整数の値を設定することが前提になります。`getUnique11` は以下です。 ```javascript function getUnique11(a, b) { const set = new Set(); for (let e of a) set.add(e.id); for (let e of b) set.add(~e.id); const onlyA = a.filter(e => !set.has(~e.id)); const onlyB = b.filter(e => !set.has(e.id)); return [onlyA, onlyB]; } ``` `getUnique10` では 2個の Set を使っていましたが、上記の `getUnique11` では、１個で済ませるようにして、Set 1個分のコンストラクタ `new Set()` の時間を減らすことを狙っています。Setを１個にした替わりに、b の要素の id をSet にaddするときに、a の要素のidと被らない値に変換する必要がありますが、その変換のために、（整数に対する演算として速いことが期待できる）ビット反転 `~` を使っています。以下にて、 `getUnique10` と `getUnique11` とを比較できます。 - **getUnique10 vs getUnique11：** [https://jsfiddle.net/jun68ykt/ajtnd5wm/5/](https://jsfiddle.net/jun68ykt/ajtnd5wm/5/) 当方の環境（PC: Macbook Pro(Core i7 2.8GHz), ブラウザ： Chrome バージョン: 78.0.3904.97)では、以下 ![イメージ説明](09d6a8732bfc89bee7c8ea993573d46a.png) のように、`getUnique11`の所要時間のほうが、`getUnique10` の所要時間よりも短くなる結果を得ています。 ### 追記 - getUnique12 先述の `getUnique11` のループで使っている、 `for ･･･ of` および `filter` を、 (ofなしの）`for`文に変更した、 `getUnique12` を作成しました。 ```javascript function getUnique12(a, b) { const set = new Set(); const lenA = a.length; const lenB = b.length; for (let i=0; i < lenA; ++ i) set.add(a[i].id); for (let i=0; i < lenB; ++ i) set.add(~b[i].id); const onlyA = []; for (let i=0; i < lenA; ++ i) { if(!set.has(~a[i].id)) onlyA.push(a[i]); } const onlyB = []; for (let i=0; i < lenB; ++ i) { if(!set.has(b[i].id)) onlyB.push(b[i]); } return [onlyA, onlyB]; } ``` `getUnique11`との比較をするための jsFiddleが下記です。 - **getUnique11 vs getUnique12：** [https://jsfiddle.net/jun68ykt/ajtnd5wm/13/](https://jsfiddle.net/jun68ykt/ajtnd5wm/13/) 当方の環境では、`getUnique12` のほうが数ミリ〜10ミリ秒程度、短くなる結果を確認しています。　 ![イメージ説明](a7bb4474530734b107acd6d278265e54.png) ### 追記 - getUnique13 アルゴリズムとしては、`getUnique8` を拝借し、比較対象として、0以上の整数として設定される id(=`1000 * x + y`) を使うコードです。 ```javascript function getUnique13(a, b) { const lenA = a.length, lenB = b.length, onlyA = [], onlyB = []; a.sort((e1, e2) => e1.id - e2.id); b.sort((e1, e2) => e1.id - e2.id); for (let iA=0, iB=0; iA < lenA || iB < lenB; ) { if (iB === lenB || iA < lenA && a[iA].id < b[iB].id) { onlyA.push(a[iA ++]); } else if (iA === lenA || iB < lenB && b[iB].id < a[iA].id) { onlyB.push(b[iB ++]); } else { iA ++; iB ++; } } return [onlyA, onlyB]; } ``` - ** getUnique13:** [https://jsfiddle.net/jun68ykt/h2ydp9sj/11/](https://jsfiddle.net/jun68ykt/h2ydp9sj/11/) 参考になれば幸いです。 ### 所感ご質問のサンプルにあるように、配列`a` 配列 `b` ともにその要素はすべて ```typescript { x: number; y: number } ``` という型を満たしているという前提が明らかになっていれば、これを元に、問題の対象範囲に出現するオブジェクトの集合が全順序集合になるような、何らかの大小関係（つまり、ソート結果が一意になる比較関数）を定義できるかどうか検討することができて、もし（運良く）大小関係を定義できれば、Set や Map を使わない `getUnique13`やその元となっている `getUnique8`のようなコードを書けますが、もし、`a` や `b` の要素として入ってくるオブジェクトの型が不明という状況、すなわち、ご質問のタイトルにある「二つの配列、それぞれに含まれるユニークな値をできるだけ高速に抽出する方法」の一般解を求めようとすると、この回答の冒頭に挙げた ```javascript const getUnique = (a,b) => _.differenceWith(a, b, _.isEqual); ``` のような時間のかかるコードに頼らざるを得なくなるのかなという気はいたします。とはいえ、実際の何らかの問題領域においては、配列要素となるオブジェクトの型は何らか特定できるものなので、その型情報から、問題領域に出現し得るオブジェクト群が全順序を満たすような何らかの大小比較関数、あるいは大小の比較が可能な（今回の `id`プロパティのような）そのオブジェクトのプリミティブ値(※)を導入できるかどうか検討することが、ある型を要素とする配列の差分抽出には優先順位の高いタスクかなと思われました。その結果、うまく大小関係を定義できれば、`getUnique8`をベースとした速いコードを書くことができます。（※参考：このような「そのオブジェクトの値を表すプリミティブ値を返す」ために、対象とするオブジェクト群専用の [valueOf()](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Object/valueOf) メソッドが定義される場合があります。）

Answer

もしもデータに制約があったり偏りがあったりするなら、その制約を前提としたコードにしたり、偏りの弱点をついたりする方法もあります。

```javascript
function getUnique(a,b) {
  const map = new Map;
  const setA = new Set;
  const setB = new Set;

  for (const v of a) {
    const { x, y } = v;
    if (!map.has(y)) map.set(y, new Map);
    map.get(y).set(x, v);
    setA.add(v);
  }

  for (const v of b) {
    const { x, y } = v;
    if (!map.has(y)) {
      setB.add(v);
      continue;
    }
    const mapy = map.get(y);
    if (!mapy.has(x)) {
      setB.add(v);
      continue;
    }
    setA.delete(mapy.get(x));
  }

  const onlyA = [...setA];
  const onlyB = [...setB];
  return [onlyA, onlyB]
}
```

これは、`a` の各要素と `b` の各要素それぞれに重複するデータがないという制約で、かつ `y` の値域が狭いという偏りを利用したコードです。
（さらに `y` が 20未満の自然数という制約を使うなら、Map でなく配列を使う等でより高速化できますが。）

まあ、普通にやる分には、文字列エンコードできるようなデータなら素直に文字列エンコードを使うやり方でいいと思います。

Answer

順序がつくもので、量が多ければ双方ソートして頭からせーのっていうのが一番速い気がします(気がするだけ)。
※AもBもuniqueを仮定
※I/F合わせてソートするオブジェクトも変わりました
※Aが空になったときにオーバーフローするバグを修正しました

JavaScript
1function compareFunc_XXX(left, right) {
2	if (left[0] < right[0]) return -1
3	if (left[0] > right[0]) return 1
4	return 0;
5}
6
7function getUnique_XXX(a,b) {
8	const aa = a.map(v => [`${v.x}:${v.y}`,v]);
9	const bb = b.map(v => [`${v.x}:${v.y}`,v]);
10	const sortA = aa.sort(compareFunc_XXX);
11	const sortB = bb.sort(compareFunc_XXX);
12	let idxA = 0;
13	let idxB = 0;
14	const lenA = a.length;
15	const lenB = b.length;
16	const resA = [];
17	const resB = [];
18
19	while (idxA != lenA || idxB != lenB) {
20		if (idxB == lenB || (idxA != lenA && sortA[idxA][0] < sortB[idxB][0])) {
21			resA.push(sortA[idxA][1]);
22			++idxA;
23		} else if (idxA == lenA || sortA[idxA][0] > sortB[idxB][0])  {
24			resB.push(sortB[idxB][1]);
25			++idxB;
26		} else {
27			++idxA;
28			++idxB;
29		}
30	}
31	return [resA, resB];
32}

測ってみた結果はうちの環境だと、1000個で4と同じくらい、10000個で3に迫ります。

Answer

コードに起こすのは煩雑となりますのでいったんアイデアだけ書きます。

比較すべきものが数値や文字列などの値いくつかに還元できるのでしたら、その数値や文字列を特定のルール（たとえば、数値を`!`で区切って特定の順番で並べる）で**文字列エンコード**して、それを`Set`に投入するなり`Object`のキーに入れるなりをすれば、もとは2重ループで`O(N**2)`かかったものを`O(N)`まで落とせるかと思います。

（なお、JSONエンコードすると、キーの順序が保証されないので、そのままでは比較に使えません）

Answer

何をどう取ればいいのかわかりづらいのですがこういうことじゃないのですか？ ```javascript const a = [0,1,2,3]; const b = [2,3,4,5]; const onlyA=a.filter(x=>b.indexOf(x)<0); const onlyB=b.filter(x=>a.indexOf(x)<0); console.log(onlyA) // [0,1] console.log(onlyB) // [4,5] ``` # 調整命題にあわせます ```javacript const getUnique=(a,b)=>[a.filter(x=>b.indexOf(x)<0),b.filter(x=>a.indexOf(x)<0)]; const a = [0,1,2,3]; const b = [2,3,4,5]; const [onlyA,onlyB]=getUnique(a,b); console.log(onlyA) // [0,1] console.log(onlyB) // [4,5] ```

前提・実現したいこと

試したソースコード

追記 - getUnique10

追記 - getUnique11

追記 - getUnique12

追記 - getUnique13

所感

調整

関連した質問