【JavaScript】配列の重複削除はSetを使うと速い【パフォーマンス比較と注意点】

こんにちは。

今回はJavaScriptで、意外と知られていないSetオブジェクトを使った配列の重複削除の実装方法を紹介します。パフォーマンスに優れていますが、何でもSetを使えばいいという話でもないということも紹介します。

Setに入れてArrayに戻す

配列の重複を削除する方法はいくつかありますが、パフォーマンス的に最も優れているのはSetオブジェクトを使う方法です。Setオブジェクトは一意の値を入れておくことができるコレクションで、複数の同じ値を入れても一意な値だけが残ります。

次のように使います。

const numbersSet = new Set([2, 5, 1, 3, 1, 2, 4])
console.log(numbersSet)
// Set(5) {2, 5, 1, 3, 4}

const namesSet = new Set(['田中', '山田', '鈴木', '田中', '森田', '山田'])
console.log(namesSet)
// Set(4) {'田中', '山田', '鈴木', '森田'}

コンストラクターに配列を入れるだけで重複が削除されたコレクションになります。出力を見て分かるように、入れた順番が保持されます。

add、delete、hasといったメソッドやsizeといったプロパティが用意されているので、基本的に配列と同じように扱うことができます。一方で、メソッドの名前が違ったりfilterやmapといった反復処理メソッドがSetには用意されていなかったりするので、全く同じように扱うことはできません。

そんなときはスプレッド構文でArrayに変換すればいいだけです。

const set = new Set([2, 5, 1, 3, 1, 2, 4])
const deduplicatedArray = [...numbersSet]
console.log(deduplicatedArray)
// (5) [2, 5, 1, 3, 4]

// 1行で書くなら
const deduplicatedArray = [...new Set([2, 5, 1, 3, 1, 2, 4])]

IE11では使えない

SetオブジェクトはInternet Explorerでは使うことができません。厳密には、コンストラクターが使えなかったり、一意性（等価性）の判定方法が他と異なったりするので実用的でないです。Internet Explorerの最新版であるIE11も2022年6月にはサポートが終了するので、よほどのことが無ければ切ってしまって問題ないはずです。EdgeのIEモードは知りません。

Setはパフォーマンス優秀

Setオブジェクトを使った重複削除は、他の方法よりもパフォーマンスに優れています。それを確認するために他によく使われている手法と比べてみましょう。

filterでインデックス比較

まず最初はfilterメソッドを使ってインデックス比較をする方法です。

const array = [2, 5, 1, 3, 1, 2, 4]
const deduplicatedArray = array.filter((element, index) => array.indexOf(element) === index)
console.log(deduplicatedArray)
// (5) [2, 5, 1, 3, 4]

コールバック関数で要素を1つずつ見ていき、その要素の値が最初に見つかったインデックス（indexOfメソッド）とその要素自体のインデックスを比較します。それが一致したときにtrueを返せば、それぞれの値で最初に見つかったもののみが取り出され、重複が無くなっているというものです。

正直直感的ではないです。また、各要素を見るループの中でインデックスを探しに行っているため二重のループになっています。計算量が多くなることは容易に想像できるでしょう。

愚直に重複チェック

次は、結果用の配列を新しく作り、その配列に存在しない値だけ追加していくという愚直な方法です。自分で重複無く配列を作れと言われたら最初に思いつく方法かもしれません。

const array = [2, 5, 1, 3, 1, 2, 4]
const deduplicatedArray = []
array.forEach(currentValue => {
  if (!deduplicatedArray.includes(currentValue)) {
    deduplicatedArray.push(currentValue)
  }
})
console.log(deduplicatedArray)
// (5) [2, 5, 1, 3, 4]

配列の各要素が結果用の配列（deduplicatedArray）に含まれていないときだけ追加します。コード量は多くなってしまいますが、filterを使う場合と比べて直感的かなと思います。計算量については同じく二重ループになっていますが、結果用の配列の要素数が少ないうちは計算量も少ないので、filterを使う場合よりは良いことが予想できます。

Setオブジェクトを使う場合

最後はおすすめのSetです。

const array = [2, 5, 1, 3, 1, 2, 4]
const deduplicatedArray = [...new Set(array)]
console.log(deduplicatedArray)
// (5) [2, 5, 1, 3, 4]

コードもシンプルですね。重複削除のコードに見えるかはSetでの重複削除を知っているか次第な気はしますが、少なくともすっきりしています。

パフォーマンス比較

今回は、0～1000の数値をN個ランダムに入れた配列を用意し、それを重複削除するのにかかった処理実行時間を計測しました。5種類のシード値で生成した乱数表を用いた配列で3つの実装を実行し、5回の平均を取っています。配列の要素数は100個、1000個、10000個、100000個、1000000個、10000000個で試しました。その結果がこちらです。

重複削除の実行時間の比較グラフ
処理方法によって桁違いの実行時間になる

Setオブジェクトを使う方法が圧倒的に実行時間が短いことが分かります。100万個の要素の重複削除でも200ミリ秒もかかっていません。filterでインデックス比較する方法では10秒近くもかかっています。桁違いです。ちなみに横軸を対数目盛にすると綺麗に直線になります（それはそう）。

ちなみに愚直に重複チェックをする方法では、前述の通り重複する個数が増えるほど重複チェックの計算量がfilterの場合よりも減っていくので、1000個まではほぼ同じところが桁が増えるにつれて大きく差が開いてきます。

Setの弱点

この結果を見ると重複削除は問答無用でSetオブジェクトを使うのがいいと思ってしまいますが、Setオブジェクトにも弱点はあります。それは厳密等価演算子（===）で比較できるプリミティブしか正しく重複削除できないということです。例を見てみましょう。

const array = [
  {x: 2, y: 3},
  {x: 1, y: -2},
  {x: 2, y: 3}
]
const deduplicatedArray = [...new Set(array)]
console.log(deduplicatedArray)
// (3) [{x: 2, y: 3}, {x: 1, y: -2}, {x: 2, y: 3}]

座標を想定したxとyの2つのプロパティを持つオブジェクトの配列で重複削除するコードです。座標が一致すれば重複としてほしいところですが、残念ながら{x: 2, y: 3} === {x: 2, y: 3}はtrueにはなってくれません。Setにはオブジェクトを入れることもできますが、オブジェクト参照が入るため同一のオブジェクトを指す場合でないと一意にはなりません。

この場合はおとなしく愚直に比較するのが良いでしょう。

const array = [
  {x: 2, y: 3},
  {x: 1, y: -2},
  {x: 2, y: 3}
]
const deduplicatedArray = []
array.forEach(currentValue => {
  if (!deduplicatedArray.find(element => element.x === currentValue.x && element.y === currentValue.y)) {
    deduplicatedArray.push(currentValue)
  }
})
console.log(deduplicatedArray)
// (2) [{x: 2, y: 3}, {x: 1, y: -2}]

比較ロジックを自分で書きたい場合やはり愚直に比較していくしかないですね。

大事なこと

配列の重複削除には圧倒的パフォーマンスを理由にSetを使うことをおすすめしておきながら、愚直な方法のほうがより実用的な場合もあるのを見てきました。大事なのは、どれか1つの方法にこだわるのではなくその時々に合った方法を使うことです。

とんでもなく大量のデータを扱うとか、とんでもない頻度で処理を行うみたいな場合であればパフォーマンスに全振りした書き方が良いでしょう。しかしJavaScriptで書く程度の重さの処理であれば、上の実験でも分かるように1ミリ秒も無い体感できない差としてしか表れてきません。であれば、コードの可読性・一貫性のほうが大事になってきます。

個人的には愚直な方法が分かりやすくて好きです。もちろんSetでの重複削除を知った今となってはSetを使って書きたくなりますが、その方法を知らない人が見ても分かりやすいかと言われると微妙です（一言コメントを書けばいいですが）。

というわけで今回は、JavaScriptのSetオブジェクトを使って配列の重複削除を実装する方法を紹介しました。画期的な方法でも向き不向きはあるので、パフォーマンスと可読性のバランスを見て実装方法を決められると良いですね。

それではまた。

関連記事