質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

89.50%

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

受付中

回答 7

投稿

  • 評価
  • クリップ 4
  • VIEW 975

jjj_aaa

score 408

前提・実現したいこと

質問は表題の通り。以下は理解のためのイメージコードです。
※ただし実際の要素はリテラルでなく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文2回(getUnique1)が 931ms、filter使うのが(getUnique2) 694msでした。(for文のが早いかなと予想してたがfilterの方が早かった。しかしIEでポリフィルとか使うときっとfilterの方が遅いと思う。)

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • jjj_aaa

    2019/11/12 14:32

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

    キャンセル

  • jjj_aaa

    2019/11/12 14:33

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

    キャンセル

  • jjj_aaa

    2019/11/14 16:47

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

    キャンセル

回答 7

+2

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

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/11/11 15:29

    一応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}`))
    ]
    }

    キャンセル

  • 2019/11/11 16:06

    さらに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];
    }

    キャンセル

  • 2019/11/11 16:35

    さらに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)
    ]
    }

    キャンセル

+2

こんにちは

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

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

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

追記 - 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 に作成しました。

上記は、コメントからご教示いただきました、 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 に0以上の整数の値を設定することが前提になります。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 では、1個で済ませるようにして、Set 1個分のコンストラクタ new Set() の時間を減らすことを狙っています。Setを1個にした替わりに、b の要素の id をSet にaddするときに、a の要素のidと被らない値に変換する必要がありますが、その変換のために、(整数に対する演算として速いことが期待できる)ビット反転 ~ を使っています。

以下にて、 getUnique10  と getUnique11 とを比較できます。

当方の環境(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が下記です。

当方の環境では、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];
}

参考になれば幸いです。

所感

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

{ x: number; y: number }  


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

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


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

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

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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/11/14 23:51

    @jjj_aaaさん

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

    キャンセル

  • 2019/11/16 13:48

    @jjj_aaaさん

    getUnique13 を追記しました。

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

    キャンセル

  • 2019/11/19 09:36

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

    キャンセル

+2

データ構造を見直すことを検討してみて下さい。
データが作成された時点で最適化の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 さん

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/11/12 13:34

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

    キャンセル

  • 2019/11/12 18:13

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

    キャンセル

  • 2019/11/12 18:31 編集

    @jjj_aaa さん

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

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

    > このWeakMapを使う利得

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

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

    キャンセル

  • 2019/11/12 18:51

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

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

    キャンセル

+1

順序がつくもので、量が多ければ双方ソートして頭からせーのっていうのが一番速い気がします(気がするだけ)。
※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に迫ります。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/11/12 13:26

    改造して、
    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];
    }

    キャンセル

  • 2019/11/12 13:27

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

    キャンセル

  • 2019/11/12 13:32

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

    キャンセル

+1

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

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/11/11 16:54

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

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

    キャンセル

  • 2019/11/11 17:18

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

    キャンセル

  • 2019/11/11 17:28

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

    キャンセル

0

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

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]

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/11/11 14:36

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

    キャンセル

0

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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/11/11 19:43

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

    キャンセル

  • 2019/11/12 12:50

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

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 89.50%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる