JavaScriptの配列で重複しているものを除外したい

Question

JavaScriptの配列に関する質問です。
配列の重複を除去する方法を調べております。こちらのページでは重複を削除して(2つあるものを1つにする)重複のない配列を作成する方法が書かれておりますが、重複している項目を完全に除去した配列を作成する方法を模索しております(＝重複していない項目だけを残した配列を作成したい)。

具体的には以下の配列があるときに、重複している2,3を全て除去して、1と5のみ抽出した配列を作成したいと思うのですが、どのようなコードで実現できますでしょうか？

よろしくお願いいたします。

var a = [1,2,3,3,2,2,5];
// result = [1,5] ←上記の時、結果がこの配列になるようなコードを探しております

Answer 1

下記ではいかがでしょうか。
リンク頂いたページの「重複のみをリスト」の逆の出力とすれば求める結果となります。

var a = [1,2,3,3,2,2,5];

// 重複していないものをリスト
var e = a.filter(function (x, i, self) {
   return self.indexOf(x) === self.lastIndexOf(x);
});

console.log(e)

Comments

[agepan]

ご回答ありがとうございました！
最初にこちらのコードでテストいたしまして、問題無く動きました。

また、今回の質問の発端となった問題点について、別途質問として投稿いたしました。もしお時間ありましたらこちらも目を通して頂けますと幸いです。
https://teratail.com/questions/92683

Answer 2

indexOf, lastIndexOf は NaN 値を検索できない

Array#indexOf, Array#lastIndexOf には「NaN 値を検索できない」という欠点があります。
ES7 ではこの問題に対応する為に Array.prototype.includes が定義されました。

console.log([NaN].indexOf(NaN));      // -1
console.log([NaN].lastIndexOf(NaN));  // -1
console.log([NaN].includes(NaN));     // true

試行回数の問題

suyamaさんのコードにはもう一つ問題があります。

var e = a.filter(function (x, i, self) {
   return self.indexOf(x) === self.lastIndexOf(x);
});

このコードは1回検査する毎に「配列全体を検索」しています。
従って、配列の長さが長い場合は検索に時間がかかってしまいます。
要素に NaN が含まれていた場合は、indexOf, lastIndexOf でそれぞれ配列全体を検索する為、さらに時間がかかります。

ベンチマーク

試行回数を極限まで減らしたアルゴリズムでコードを書き、ベンチマークをとってみました。

'use strict';
function think49 (array) {
  var i = 0, len = array.length, value, map = new Map, unique = [];

  while (i++ < len) {
    value = array[i];
    map.set(value, map.has(value) ? map.get(value) + 1 : 1);
  }

  for (var entry of map.entries()) {
    if (entry[1] === 1) {
      unique.push(entry[0]);
    }
  }

  return unique;
}

var suyama = (function () {
  function filterfn (x, i, self) {
    return self.indexOf(x) === self.lastIndexOf(x);
  }

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

function shuffle (array) {
  var k, t, len;

  len = array.length;

  if (len < 2) {
    return array;
  }

  while (len) {
    k = Math.floor(Math.random() * len--);
    t = array[k];
    array[k] = array[len];
    array[len] = t;
  }

  return array;
};

function createArray (uniqueLength, duplicateLength, NaNLength) {
  uniqueLength = arguments.length > 0 ? uniqueLength : 0;
  duplicateLength = arguments.length > 1 ? duplicateLength : 0;
  NaNLength = arguments.length > 2 ? NaNLength : 0;

  var array = [...Array(uniqueLength + duplicateLength).keys()],
      duplicateArray = array.slice(uniqueLength);

  return array.slice(0, uniqueLength).concat(shuffle(duplicateArray.concat(duplicateArray).concat(Array(NaNLength).fill(NaN))));
}

function benchmark (fn, createArg, i) {
  console.time(fn.name);

  while (i--) {
    fn(createArg());
  }

  console.timeEnd(fn.name);
}

benchmark(think49, createArray.bind(null, 100, 20000, 100), 10);
benchmark(think49, createArray.bind(null, 20000), 10);
benchmark(think49, createArray.bind(null, 0, 0, 20000), 10);

benchmark(suyama, createArray.bind(null, 100, 20000, 100), 10);
benchmark(suyama, createArray.bind(null, 20000), 10);
benchmark(suyama, createArray.bind(null, 0, 0, 20000), 10);

結果は次の通りです。

引数に指定した配列コード	コード	実行時間
非重複要素100個 + 重複要素20000個 + NaN値の要素10個	think49	228.81396484375ms
非重複要素100個 + 重複要素20000個 + NaN値の要素10個	suyama	19696.505859375ms
非重複要素20000個	think49	81.341064453125ms
非重複要素20000個	suyama	7361.458984375ms
NaN値の要素20000個	think49	41.86279296875ms
NaN値の要素20000個	suyama	7258.05810546875ms

最後の「NaN値の要素20000個」は意地悪問題でした。
NaN値は重複していますが、前述の通り、indexOf, lastIndexOf は NaN 値を検出できない為、配列全体を検索する過程を 2 * 20000 回行います。
(正確には一つ重複要素がある為、20001 個の要素を持つ配列を検索しているのと等価です。)

Re: agepan さん

Comments

[agepan]

ご回答ありがとうございました！
とても詳しく検証までしていただきありがたく思います。様々な方法があるようですので、今回の要件に合いそうな物を選び実装させていただきたいと思います。

また、今回の質問の発端となった問題点について、別途質問として投稿いたしました。もしお時間ありましたらこちらも目を通して頂けますと幸いです。
https://teratail.com/questions/92683

ありがとうございました！

Answer 3

IEはかなぐり捨ててます。

const a = [1, 2, 3, 3, 2, 2, 5];
const result = Array.from(a).sort().concat(Symbol()).reduce(
    (obj, v) => ((same) => ({
        pre: v,
        count: same ? obj.count + 1 : 1,
        list: (!same && obj.count === 1) ? obj.list.concat(obj.pre) : obj.list,
    }))(obj.pre === v || (Number.isNaN(obj.pre) && Number.isNaN(v))),
    {pre: Symbol(), count: 0, list: []}).list;
console.log(result);

sort()はたぶんO(n log n)だろうけど、ネイティブな実装なので高速と仮定すれば、それ以外はたぶんO(n)なので巨大な配列でもそこそこ速く行けるかも知れない。(concat()ってO(1)なのだろうかという疑問はあるけど)

const a = [1, 2, 3, 3, 2, 2, 5];
const result = new Set;
const looked = new Set;
for (const v of a) {
    if (looked.has(v)) {
        result.delete(v);
    } else {
        result.add(v);
        looked.add(v);
    }
}
console.log(Array.from(result));

Setの実装がすごくよくできたハッシュテーブルであれば各メソッドは約O(1)になるはず。そうなると、正真正銘のO(n)となるかと思います。

Comments

[think49]

上のコードは速く動くイメージが出てこなくて、ベンチマークを取ってみたら速くありませんでした。
https://jsfiddle.net/81m6t12p/
出力値の配列の順序が変わってしまうのは、人に依っては気にするかもしれません。
(重複チェックの機構としては問題ないですが、[1,2,3,10,100].sort() が [1, 10, 100, 2, 3] になるのは期待通りでしょうか)

下のコードは安定して速く、特に重複が多いと高速ですね。
(ケアレスミスだと思いますが、v で ReferenceError が返ってきます。)

[raccy]

あ、constを付け忘れてますね。paiza.ioだとエラーにならなかったので気付かなかったです。

上のコードは全てimmutableにしているため、オブジェクト生成コストがかかるので、実装次第ではたぶん遅いです。JavaScriptで関数型プログラミングはやっぱりやりにくいです。

[agepan]

回答ありがとうございました！
こちらのコードでも実装テストを現在行っております（正しく動作しているようです）。また、今回の質問の発端となった問題点について、別途質問として投稿いたしました。もしお時間ありましたらこちらも目を通して頂けますと幸いです。
https://teratail.com/questions/92683

Answer 4

要件を誤読していたため、下記方法は要件を満たしません。コメント欄にてthink49さんmiyabi-sunさんがreduceを利用する方法を書いていただいています。

---

reduceを使う方法。

let arr = [ 3, 4, 10, 4, 3, 2, 4, 3, 1, 6, 2, 7, 4, 7, 1 ].reduce( ( prev, curr ) => {
	if ( !prev.includes( curr ) ) {
		prev.push( curr );
	}
	return prev;
}, [] );
console.log( arr );

【Array.prototype.reduce() - JavaScript | MDN】
https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Array/reduce

【Array.prototype.includes() - JavaScript | MDN】
https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Array/includes

Comments

[think49]

要件を誤解していると思います。

> let arr = [ 3, 4, 10, 4, 3, 2, 4, 3, 1, 6, 2, 7, 4, 7, 1 ]
この配列に対して、[10, 6] が返ってくることを質問者さんは期待しています。
reduce を使うのなら、「重複リスト」と「非重複リスト」を作って2回チェックする必要があると思われます(bindを併用するか、スコープチェーン上にもう一つ変数が必要)。

[think49]

例えば、こんな感じでしょうか。
https://jsfiddle.net/qw10jfg9/

[kei344]

To: think49さん
指摘ありがとうございます。質問文を読めていませんでした･･･。

[miyabi-sun]

```JavaScript
let is_uniq_in = arr => it => arr.reduce((a, that) => it === that ? a + 1 : a, 0) === 1
let arr = [ 3, 4, 10, 4, 3, 2, 4, 3, 1, 6, 2, 7, 4, 7, 1 ]
console.log(arr.filter(is_uniq_in(arr)))
// [10, 6]
```

reduceだとこれが限界かも？
ライブラリなしだとすやまさんアプローチが最善っぽいですね。

[kei344]

To: miyabi-sunさん
> ライブラリなしだとすやまさんアプローチが最善っぽいですね。
その通りだと思います。

誤読した上で「（特に意味はないけど）reduceでも書けそう」と考えて回答しました･･･。

[think49]

suyamaさんの方法は
- NaN値をチェック出来ない
- 重複のない大きなlength値を持つ配列においての処理が遅い(100の要素があれば、100 * 200 回テストする)
という欠点がある為、必ずしも最善ではないと思います。
reduce は上手く使えば、試行回数を減らす事が出来ます。

[miyabi-sun]

think49さん
なるほどー、groupBy→keysの方向でやれば*2n程度の計算量に収まりそうですね。

[think49]

To: miyabi-sun さん
> groupBy→keysの方向でやれば*2n程度の計算量に収まりそうですね。
groupBy は lodash の関数でしょうか。
いろいろ考えましたが、最終的には *2n の範囲におさまりました。
*1n を目指したかったのですが、上手い方法が思い浮かびませんでした。

[agepan]

回答ありがとうございました！
こちらの内容も、別の課題で役に立ちそうな有益な情報でありましたのでありがたく参考にさせて頂きます！

また、今回の質問の発端となった問題点について、別途質問として投稿いたしました。もしお時間ありましたらこちらも目を通して頂けますと幸いです。
https://teratail.com/questions/92683