二つの配列、それぞれに含まれるユニークな値をできるだけ高速に抽出する方法

Question

前提・実現したいこと

質問は表題の通り。以下は理解のためのイメージコードです。
※ただし実際の要素はリテラルでなくObjectです。実際のお試しコードは後述。

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

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の方が遅いと思う。）

Comments

[maisumakun]

いくつか確認したいことがあります。

・バラバラなインスタンスでも条件が整えば「同値」と判断したい、ということで間違いはないでしょうか。
・同じ配列に同じものが2つはいっていた場合の処理はどのようにすればいいでしょうか。

[maisumakun]

本題ではないのでこちらのコメントとしますが、「b.sort(() => Math.random() - 0.5);」のように値を見ずにソート関数を動かすと、同じ値の組み合わせについて順序性が保証されない状態となるので、正常にソートされることが保証されません。

[退会済みユーザー]

>バラバラなインスタンスでも条件が整えば「同値」と判断したい、ということで間違いはないでしょうか
はい、そうです。a===bでなくても、専用の条件（この場合はｘとｙの値が同値）ならばOKとしたいです。
>同じ配列に同じものが2つはいっていた場合の処理はどのようにすればいいでしょうか。
その場合は比較元の方の個数をそのまま出す感じでお願いします。[0,0,0,1,2]と[1,2,2,3]だったら、[0,0,0]と[3]が出る感じで。

randomソートについてご指摘ありがとうございます。今回はテストデータの順序を変えたかっただけなので、中身が壊れなければソートの順序はとりあえずなんでもOKとしました。

[Zuishin]

要素に大小関係はありますか？
つまり、ある要素とある要素を比べた時、どちらが大きいと一意にきまりますか？

[退会済みユーザー]

一概にはいえないです。xとyの値を持っているのですが等価です。たとえば{x:1, y:2}と{x:2,y:1}のどちらが大きい、ということは言えません。
ただ結果が良ければ、ソート目的で便宜的にxyの優先順位を設定することはやぶさかではありません。

[think49]

aが持つプロパティ名/プロパティ値の組み合わせはaの中でユニークなのでしょうか。重複はあり得ますか。

[退会済みユーザー]

重複はあり得ます。aにあってbにないもので重複がある場合は重複数分出るのが理想ですが、出なくても大丈夫です。（maisumakunさんへの返信で絶対重複のまま、という感じにしてしまいましたがよく考えれば「できれば」レベルでした）

[退会済みユーザー]

後で回答内容を基にしたまとめで質問を更新します。
ちなみにjsFiddleのURL最後尾に/showをつけてIEで試した結果が以下。これ遅すぎるけど、原因はPolyfillにあることを私は知っている。（コードをBabelのサイトでバベってjsFiddleでbabel-polyfill入れてやってる）
https://imgur.com/a/mWOJLtc

[退会済みユーザー]

findIndexとかは自前で簡易polyfill書いて対処してる

[退会済みユーザー]

すみません、今データ構造を変えたほうが良いか？変えない方が良いか？でテストと影響範囲確認と検討を進めています。BA選定もう少々お待ちください。

Answer 1

データ構造を見直すことを検討してみて下さい。
データが作成された時点で最適化の9割は完了しています。

'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 さん

Comments

[退会済みユーザー]

すみません、まず動かしたのですがonlyAが一個だけでonlyBが900個になってました。
https://jsfiddle.net/wrxc039j/
ちょっとどこが悪いのか確認してます。

[退会済みユーザー]

すみません、このWeakMapを使う利得はなんでしょうか？

[think49]

@jjj_aaa さん

> まず動かしたのですがonlyAが一個だけでonlyBが900個になってました。

すみません。initを元にした正答値が不明だったので、思いついたアルゴリズムをコードに書き起こすのみで、入念なテストをしていませんでした。
質問文の「試したソースコード」は期待値を返すとして、期待値と比較してみます。

> このWeakMapを使う利得

WeakMapはprivate propertyの代わりです。
wm.get(this).x は外部参照不可能な「プライベートプロパティx」のように扱います。

http://cou929.nu/data/google_javascript_style_guide/#id29
コーディング規約の命名で縛るだけでは、外部参照を防げないので。

[退会済みユーザー]

なるほど、「WeakMap private property」で調べたら出てきました（think49さんが）。そういう手法があるんですね。
私はTypeScript使ってるのでprivateメンバを持たせてますが、コンパイラ突破後はJSなので普通にアクセスできちゃうのはその通りなんですよね。（てかブラケット構文使えばTypeScriptでもアクセスできるけど（anyだけど））

明日くらいにもう一度チャレンジします。

Answer 2

こんにちは

lodash を使えば、以下のように書けるかなと思います。

const getUnique = (a,b) => _.differenceWith(a, b, _.isEqual);

• 例1: https://codepen.io/jun68ykt/pen/abbjwqM?editors=0012

要素がオブジェクトの場合の例が以下です。

• 例2: https://codepen.io/jun68ykt/pen/GRRBEYj?editors=0012

追記 - getUnique10

上記ではlodashを使った汎用的なコードを挙げましたが、コメントから頂きましたjsFiddleのテストコードによって生成されるオブジェクトの配列を処理することに特化したコードも考えてみました。以下の getUnique10 になります。

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/e9a5kvw2/ を Forkして、テスト対象としてgetUnique10 を追加したものです。

追記 - getUnique11

前掲の getUnique10 の改良案を挙げます。この改良案は、(2019/11/14 21:10のコメントに書いたとおり、） 下記

  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 は以下です。

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/

当方の環境（PC: Macbook Pro(Core i7 2.8GHz), ブラウザ： Chrome バージョン: 78.0.3904.97)では、以下

のように、getUnique11の所要時間のほうが、getUnique10 の所要時間よりも短くなる結果を得ています。

追記 - getUnique12

先述の getUnique11 のループで使っている、 for ･･･ of および filter を、 (ofなしの）for文に変更した、 getUnique12 を作成しました。

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/

当方の環境では、getUnique12 のほうが数ミリ〜10ミリ秒程度、短くなる結果を確認しています。　

追記 - getUnique13

アルゴリズムとしては、getUnique8 を拝借し、比較対象として、0以上の整数として設定される id(=1000 * x + y) を使うコードです。

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/

参考になれば幸いです。

所感

ご質問のサンプルにあるように、配列a 配列 b ともにその要素はすべて

{ x: number; y: number }  

という型を満たしているという前提が明らかになっていれば、これを元に、問題の対象範囲に出現するオブジェクトの集合が全順序集合になるような、何らかの大小関係（つまり、ソート結果が一意になる比較関数）を定義できるかどうか検討することができて、もし（運良く）大小関係を定義できれば、Set や Map を使わない getUnique13やその元となっている getUnique8のようなコードを書けますが、もし、a や b の要素として入ってくるオブジェクトの型が不明という状況、すなわち、ご質問のタイトルにある
「二つの配列、それぞれに含まれるユニークな値をできるだけ高速に抽出する方法」
の一般解を求めようとすると、この回答の冒頭に挙げた

const getUnique = (a,b) => _.differenceWith(a, b, _.isEqual);

のような時間のかかるコードに頼らざるを得なくなるのかなという気はいたします。

とはいえ、実際の何らかの問題領域においては、配列要素となるオブジェクトの型は何らか特定できるものなので、その型情報から、問題領域に出現し得るオブジェクト群が全順序を満たすような何らかの大小比較関数、あるいは大小の比較が可能な（今回の idプロパティ のような）そのオブジェクトのプリミティブ値(※)を導入できるかどうか検討することが、ある型を要素とする配列の差分抽出には優先順位の高いタスクかなと思われました。その結果、うまく大小関係を定義できれば、getUnique8をベースとした速いコードを書くことができます。

（※参考：このような「そのオブジェクトの値を表すプリミティブ値を返す」ために、対象とするオブジェクト群専用の valueOf() メソッドが定義される場合があります。）

Comments

[退会済みユーザー]

ありがとうございます。
jsFiddleでlodahをインポートいただいたコードをgetUnique9として実装してみましたが、どうもハングしてしまいます。
https://jsfiddle.net/e9a5kvw2/
※test変数の中の変数名を変えればテストできます。
221行目の最初の動作チェックは動いたのを確認できたのですが、その後の1000回ループでハングしている様子。

[2KOH]

横から失礼。ループ回数を10回くらいに減らせば動くと思います。

[jun68ykt]

@jjj_aaaさん

コメントありがとうございます。
そちらの jsFiddle をforkして、２つのオブジェクトの同値判定に、汎用的な _.isEqual ではなく、このご質問に特化した

function eq(a, b) { return a.x === b.x && a.y === b.y; }

を使い、getUnique9 を

function getUnique9_2(a,b) {
return [_.differenceWith(a, b, eq), _.differenceWith(b, a, eq)];
}

に修正したものが以下です。
https://jsfiddle.net/jun68ykt/cp34udr8/18/

[jun68ykt]

@2KOHさん
コメントありがとうございます。
> ループ回数を10回くらいに減らせば動くと思います。
動きましたが、かなり時間がかかりましたので、オブジェクトの同値判定を見直しました。

[退会済みユーザー]

修正いただきありがとうございます。
getUnique7: 252ms, //2KOHの回答のもの
getUnique9_2: 1271ms
lodashは便利ですが、汎用的なため今回のような速度を求める場所では適用しないほうが良さそうです。
可読性は高く品質も磨かれていると思うので、ループなどなく性能要求が厳しくない部分では積極的に使おうと思いました。

[jun68ykt]

@jjj_aaaさん
はい。そのような方針で良いかと思います。

[jun68ykt]

@jjj_aaaさん

lodashを使わずに、なるべく高速に処理するコードも考えて、回答のほうに、getUnique10 として追記しました。また、ご教示のjsFiddleをForkした、

https://jsfiddle.net/jun68ykt/b501gqpj/1/

にてgetUnique10をテストしましたので、ご確認頂けますと幸いです。

[jun68ykt]

@jjj_aaaさん

当方の環境（PC: Macbook Pro(2.8GHz Core i7), ブラウザ： Chrome バージョン: 78.0.3904.97) にて、上記のgetUnique10 　を追加した、 https://jsfiddle.net/jun68ykt/b501gqpj/1/ を表示し、５回テストを試行したときの画面キャプチャを、以下に挙げておきます。

1回目：　https://git.io/Jerr4 (166ms)
2回目： https://git.io/Jerr0 (171ms)
3回目： https://git.io/Jerrg (165ms)
4回目： https://git.io/Jerr2 (179ms)
5回目： https://git.io/Jerra (170ms)

※()内は getUnique10 の要した時間です。

[jun68ykt]

@jjj_aaaさん

もう一点だけ、改良できる部分を挙げますと、 id を文字列から数値にすると若干速くなります。function init() 　の中で、

const num = 1000;
for (let i = 0; i < num; i++) {
const x = i;
const y = Math.floor(Math.random() * num);

となっているので、 x と y はともに 0以上999以下であることをふまえて、id を

`${x}:${y}`

から、

1000 * x + y

に修正したものが以下です。（※ getUnique10は、回答に追記したものから変更していません）

https://jsfiddle.net/jun68ykt/sgqx4zey/1/

上記の jsFiddle を先に挙げた、当方の環境で表示させた画面キャプチャが、以下です。

https://git.io/Jerrx (122ms)

[jun68ykt]

@jjj_aaaさん

getUnique10 では2つの Set を使っていたのを、1つのSetで済ませる getUnique11 を追記しました。

[jun68ykt]

@jjj_aaaさん

getUnique13　を追記しました。

追伸
今回、このご質問の回答を通じて、lodash, Map, Set などの便利なものを使ったときの時間的コストをあらためて確認することができました。御礼申し上げます。（質問に +1)

[退会済みユーザー]

@jun68yktさん
すみません、別問題にハマっていて見れていませんでした。。
たくさん書いていただきありがとうございます。後ほど検証します。

Answer 3

コードに起こすのは煩雑となりますのでいったんアイデアだけ書きます。

比較すべきものが数値や文字列などの値いくつかに還元できるのでしたら、その数値や文字列を特定のルール（たとえば、数値を!で区切って特定の順番で並べる）で文字列エンコードして、それをSetに投入するなりObjectのキーに入れるなりをすれば、もとは2重ループでO(N**2)かかったものをO(N)まで落とせるかと思います。

（なお、JSONエンコードすると、キーの順序が保証されないので、そのままでは比較に使えません）

Comments

[退会済みユーザー]

ありがとうございます。
なんか良さそうなので理解したいのですが、これはAにしかなかったものとBにしかなかったものを判別するのはどういう感じになりますか？
一つのSetにAの文字列表現配列をつっこみ、Bの文字列表現配列を突っ込むと重複排除はしてくれそうですが、どれがAにしかないものでどれがBにしかないものか分からなくないかな～と思って質問しました。
＃多分私の理解が間違っていると思う

[maisumakun]

「Aの中身からSetを起こす」→「Bの要素について1つずつ、「AのSetにあればそっちからは削除、なければBのSetに追加」としていく」とすれば、「Aにしかない要素のSet」と「Bにしかない要素のSet」が出来上がります。

（重複については別にハンドリングする必要がありますが）

[退会済みユーザー]

なるほど。意味IDになる文字列起こしを先に実施しておくことができれば早くなるかも。そしてこの案での追加コストはSet生成ですね。
文字列起こしのコストは外に出す前提で（じゃないと多分負ける）、ちょっと試してみます。

[退会済みユーザー]

早くなりました！
文字列変換を外でやるものをgetUnique3、文字列変換を逐次やるものをgetUnique4として実装しました。
https://jsfiddle.net/jx3co5tw/4/
getUnique1: 962ms,
getUnique2: 730ms,
getUnique3: 170ms,
getUnique4: 367ms
文字列変換も含むパターンでもfilterより早かったので、結構おどろきました。
元データ構成をいじるgetUnique3はキツイかもなので、getUnique4の採用を検討してみます。（重複の検討、あとIEでもPolyfill使って試したりしてから）
ありがとうございます。

[退会済みユーザー]

一応3と4のコードも載せとこう。コメントでもシンタックスハイライトしてほしい。

/** Set使うパターン(文字列生成外だし) */
function getUnique3(a, b) {
const aSet = new Set(a.map(v => v.id));
const bSet = new Set();
for (let i = 0, l = b.length; i < l; i++) {
if (aSet.has(b[i].id)) {
aSet.delete(b[i].id);
} else {
bSet.add(b[i].id)
}
}
return [
a.filter(v => aSet.has(v.id)),
b.filter(v => bSet.has(v.id))
]
}

/** 文字列生成含む */
function getUnique4(a, b) {
const aa = a.map(v => `${v.x}:${v.y}`)
const bb = b.map(v => `${v.x}:${v.y}`)
const aSet = new Set(aa);
const bSet = new Set();
for (let i = 0, l = bb.length; i < l; i++) {
if (aSet.has(bb[i])) {
aSet.delete(bb[i]);
} else {
bSet.add(bb[i])
}
}
return [
a.filter(v => aSet.has(`${v.x}:${v.y}`)),
b.filter(v => bSet.has(`${v.x}:${v.y}`))
]
}

[退会済みユーザー]

さらにSetを介さず配列コピーと削除(getUnique5)も試しましたが、これよりもSetの方が早い！（1,2よりは5の方が早いけど）
getUnique3: 184ms,
getUnique4: 372ms,
getUnique5: 417ms
/** 配列コピーして削除していく方策 */
function getUnique5(a, b) {
const copyA = a.slice();
const copyB = [];
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) {
delete copyA[ai];
hit = true;
break;
}
}
if (!hit) {
copyB.push(b[bi]);
}
}
return [copyA.filter(v => v), copyB];
}

[退会済みユーザー]

さらにobjectでも試してみました(getUnique6)。これはSetの文字列生成版(4)よりは早い感じ。これがいいかもしれない。
getUnique3: 194ms,
getUnique4: 411ms,
getUnique5: 409ms,
getUnique6: 357ms
/** objectのキーバリューを利用*/
function getUnique6(a, b) {
const aa = {}; a.map(v => aa[`${v.x}:${v.y}`] = v);
const bb = {};
for (let i = 0, l = b.length; i < l; i++) {
const id = `${b[i].x}:${b[i].y}`;
if (aa[id]) {
delete aa[id];
} else {
bb[id] = b[i];
}
}
return [
Object.values(aa),
Object.values(bb)
]
}

Answer 4

もしもデータに制約があったり偏りがあったりするなら、その制約を前提としたコードにしたり、偏りの弱点をついたりする方法もあります。

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 でなく配列を使う等でより高速化できますが。）

まあ、普通にやる分には、文字列エンコードできるようなデータなら素直に文字列エンコードを使うやり方でいいと思います。

Comments

[退会済みユーザー]

ありがとうございます。
いただいたコードをためしてみましたが、元のものよりかなりいい数値がでました！（getUnique7がそれ）
getUnique3: 193ms, // maisumakunさんの回答参照
getUnique4: 368ms, // maisumakunさんの回答参照
getUnique6: 364ms, // maisumakunさんの回答参照
getUnique7: 189ms // 今回の

実はyが20未満という制約はないので（元のコードが悪かったです。すみません）yの値はrandom値にするように変更して試してみましたが、getUnique3並みに早かったです！
Mapをネストするのは見た瞬間はためらいましたが、これはいいですね。
getUnique3と比べ疑似IDとして文字列を生成するコストもなくなるので、こちらも検証の上検討してみようと思います！（getUnique3か6か7というところ）

[2KOH]

回答にも書きましたが、特別な理由がないなら素直に文字列エンコードの方法でいいと思いますよ。
割と自己満足で書いたコードですし、実際に使う際は文字列エンコードの方がコードが単純なため保守が楽ですし。
文字列エンコードの方法でもまだ速度が足りないとか、とにかく1ミリ秒でも速くしたいとか、そういうときにだけこの回答のような方法を検討してください。

[退会済みユーザー]

ありがとうございます。トータルコスト考えて検討します！

Answer 5

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

function compareFunc_XXX(left, right) {
	if (left[0] < right[0]) return -1
	if (left[0] > right[0]) return 1
	return 0;
}

function getUnique_XXX(a,b) {
	const aa = a.map(v => [`${v.x}:${v.y}`,v]);
	const bb = b.map(v => [`${v.x}:${v.y}`,v]);
	const sortA = aa.sort(compareFunc_XXX);
	const sortB = bb.sort(compareFunc_XXX);
	let idxA = 0;
	let idxB = 0;
	const lenA = a.length;
	const lenB = b.length;
	const resA = [];
	const resB = [];

	while (idxA != lenA || idxB != lenB) {
		if (idxB == lenB || (idxA != lenA && sortA[idxA][0] < sortB[idxB][0])) {
			resA.push(sortA[idxA][1]);
			++idxA;
		} else if (idxA == lenA || sortA[idxA][0] > sortB[idxB][0])  {
			resB.push(sortB[idxB][1]);
			++idxB;
		} else {
			++idxA;
			++idxB;
		}
	}
	return [resA, resB];
}

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

Comments

[退会済みユーザー]

ありがとうございます。
要素がリテラルならいけそうな感じありますね。要素飛ばしとか配列長異なる場合の動作が大丈夫かは確認が必要そうですね。
今回は要素がObjectかつ順序性は確立できないので、ちょっと適用は難しそうです。

[dameo]

順序は他のと同様につけられると思います。
null値相当とuniqueでないものはこの実装では対応できていません。
配列長は違っていても問題ありません。
バグは当然あるかもしれません。
ハッシュを使う方式で済む量であれば、こちらを考える必要はないと思いますが、何にせよ決めるのは質問者なので、気にせず自由に選んでください。

[退会済みユーザー]

いまI/F合わせてdiff関数作ってやってみてるのですが、インデックスのオーバーランがおきますね・・・もう少しやってみます。

[退会済みユーザー]

Aが無くなっててBが残ってるときにオーバーランするんだ。修正中・・・

[dameo]

流石にそこまでやらなくても…申し訳ないっす…
こっちは確認すらしてないし、そちらのコードはチラ見しかしてないので…
サッサと諦めてしまってください笑
夜に時間が出来たら少しこちらでも見てみます

[退会済みユーザー]

すみません、理屈は分かっているのですがきれいに通らず断念してしまいました。

[dameo]

回答修正しました。取り込めるようにはなったはず。
不具合の方はおっしゃるとおりオーバーランしてましたね。
対称に書いて安心したら判定が先でダメだったようです。
気付かないもんですね。
お手数おかけしてすみません。

[退会済みユーザー]

修正ありがとうございます。通りました！
getUnique2: 868ms, //元のfilter使ったやつ
getUnique7: 229ms,//2KOHさんの回答
getUnique8: 486ms//今回の
https://jsfiddle.net/3zs6j24t/
元のものより倍速かったです！が、MapやSetを使うパターンよりは遅くなりました。
私的にも実はこれが一番速いかな？と思っていたので、少し意外でした。やってみないと分からないものだ。（きっとブラウザにも依ってしまうだろうが。。。）

[dameo]

内部を測ってないので、時間がかかっている部分に依りますね。
比較を文字列キーでなくx,yに順番つけて…にすれば(キーが他の方法と変わりますが)もっと速くなるとは思います。
他の方法はチューニングとかしてないようなので、キーくらい合わせてたんですけどね。
でもMapやSetで使われるようなHashTableやTreeの生成/探索が有効に機能してるうちは、こんな方法に拘らなくていいと思います。
方式を量に合わせて適応的に入れ替えるのもありですが、メンテナンスも面倒だし、難しいですね。
このデータ形式で個数が10000近くまで行くとかなら考え始めた方がいいかもです。

[退会済みユーザー]

改造して、
getUnique2: 911ms,
getUnique7: 239ms,
getUnique8: 54ms
まで行きました。やっぱこれが早いじゃん！
https://jsfiddle.net/3zs6j24t/2/
以下の感じ、ID用の文字列生成を削りました。

/** dameoの回答 */
function getUnique8(a,b) {
const diff = (a, b) => a.x === b.x ? a.y - b.y : a.x - b.x;
const sortA = a.sort(diff);
const sortB = b.sort(diff);
let idxA = 0;
let idxB = 0;
const lenA = a.length;
const lenB = b.length;
const resA = [];
const resB = [];

while (idxA != lenA || idxB != lenB) {
if (idxB == lenB || (idxA != lenA && diff(sortA[idxA],sortB[idxB]) < 0)) {
resA.push(sortA[idxA]);
++idxA;
} else if (idxA == lenA || diff(sortA[idxA], sortB[idxB]) >0) {
resB.push(sortB[idxB]);
++idxB;
} else {
++idxA;
++idxB;
}
}
return [resA, resB];
}

[退会済みユーザー]

あとは見た目キレイにしてみます。

[dameo]

確認されちゃいましたか…すみません笑

Answer 6

IEのPolyfill なんて言葉もコメントされていたので、若干、古典的手法で考えてみました
意図する抽出になっていますかね？

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で走査回数を抑えました。

Comments

[AkitoshiManabe]

https://jsfiddle.net/e9a5kvw2/ に貼り付けて Run してみると全然遅かった orz

[退会済みユーザー]

検証までやっていただき、ありがとうございました。

Answer 7

何をどう取ればいいのかわかりづらいのですが
こういうことじゃないのですか？

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]

調整

命題にあわせます

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]

Comments

[退会済みユーザー]

ご回答ありがとうございます。
最初のコードは動作のイメージ用のコードで、解決したいのはリテラルの配列でなくオブジェクトの配列です。「試したソースコード」のinit()で生成される2つの配列について解決したく。
追記いただいたものは、元コードのgetUnique2と同じっぽい感じですね。（リテラルとオブジェクトの違い）