配列からの重複削除

メモ javascript

JavaScript で、配列から重複した要素をとりのぞく処理は以下のように書ける（検索すると、たくさんヒットする）。

const unique = array => array.filter((value, index, self) => self.indexOf(value) === index);

これは次のように使う：

> unique([1, 3, 2, 1, 3])
=> [1, 3, 2]

手続き的な処理の解説

unique に渡す引数配列 array を、関数 `(value, index, array) => array.indexOf(value) === index` で filter する。
つまり value, index, array の三引数をとり、これで array.indexOf(value) === index を評価して、 true になる要素 value を残して配列として返す。

先の例につかった配列 `[1, 3, 2, 1, 3]` を例につかう。

filter は配列の先頭から順に値を渡してくれる。

  1. 最初の要素の値は 1、このインデックスは 0、配列は [1, 3, 2, 1, 3]。
  2. 次の要素の値は 3、インデックス 1、配列は [1, 3, 2, 1, 3]。

この調子で、入力配列を filter に順次渡される三つ組の配列として表現すると、以下のようになる。：

[(1, 0, [1,3,2,1,3]), (3, 1, [1,3,2,1,3]), (2, 2, [1,3,2,1,3]), (1, 3, [1,3,2,1,3]), (3, 4, [1,3,2,1,3])]

これを順次 `array.indexOf(value) === index` で評価すると、：

[true, true, true, false, false]

というのは、最初の要素を例にとれば以下のように評価が進むため。：

((value, index, array) => array.indexOf(value) === index))(1, 0, [1,3,2,1,3]);
=> [1,3,2,1,3].indexOf(1) === 0
=> 0 === 0
=> true

結果、先頭から順に `[1, 3, 2]` が取り出されて終わる。

オーダー

array に対する二重ループだから array の長さを n として O(n^2)。
filter に渡す関数の、その引数に array たる self がバインドされること、そして関数本体で array を self.indexOf() として使っているため。（ワーストケースは、重複がない配列への適用）