PHP でのコレクション重複削除

PHP だと java.util.Set のような重複要素をもたないコレクションが見当たりせん。PHP で重複のないコレクションを組み立てるには、どうすればよいかを考えてみました。

* [Set implementations in PHP](https://gist.github.com/tachesimazzoca/e5c610c212f455ab2c2d)

元データの要素数を _N_ 個とし、ユニーク数が _R_ 個の要素を抽出するタスクを計測しています。

## in_array

要素追加前に in_array 関数で重複チェックする方法です。

```php
$keys = array();
for ($i = 0; $i < $N; $i++) {
    $key = 'KEY' . mt_rand(1, $R); 
    if (!in_array($key, $keys)) {
        $keys[] = $key; 
    }   
}
```

```:実行結果
N = 100000, R =  1000: 3.157351 sec
N = 100000, R =    10: 0.169218 sec
N =  10000, R = 10000: 2.145616 sec
```

* 長所: 必要なメモリが、ユニーク数 _R_ に収まる
* 短所: 重複チェック回数が _NR_ となってしまう

実行結果をみると、単純に配列要素を先頭から順番に比較しているようです。ユニーク数 _R_ が少ないことが分かっていれば、有効な実装方法です。

## array_unique

要素を全て追加した後に array_unique 関数で重複削除する方法です。

```php
$seq = array();
for ($i = 0; $i < $N; $i++) {
    $key = 'KEY' . mt_rand(1, $R); 
    $seq[] = $key; 
}
$keys = array_unique($seq);
```

```:実行結果
N = 100000, R =  1000: 0.392945 sec
N = 100000, R =    10: 0.373651 sec
N =  10000, R = 10000: 0.029357 sec
```

* 長所: 重複削除の意図が分かりやすい
* 短所: 元データ要素数の _N_ 個分のメモリが必要

`array_unique` 関数の内部 C コード上で重複削除するので、毎回 `in_array` を使って重複チェックするよりもパフォーマンスがよいことがわかります。とはいえ、元データの要素数 _N_ とユニーク数 _R_ の差がない場合は有効ですが、そうでない場合は不要なメモリを浪費することになります。

メモリ不足となる場合はこの方法は使えませんので、要素を追加する毎に `array_unique` を行なう方法を試してみましたが、あまりに実行時間がかかりすぎました。`array_unique` の説明を読むと

> まず文字列として値をソートし、 各値の最初のキーを保持し、2回目以降の全てのキーを無視します。

とあるので、計算量が _~N (R log R + R)_ となってしまうものと思われます。`array_unique` という名前につられて、安易にこの方法を選択するのは避けたいところです。

## array_keys

連想配列キーとして要素を追加し array_keys でキー集合を取り出す方法です。

```php
$map = array();
for ($i = 0; $i < $N; $i++) {
    $key = 'KEY' . mt_rand(1, $R); 
    $map[$key] = null; 
}
$keys = array_keys($map);
```

```:実行結果
N = 100000, R =  1000: 0.083967 sec
N = 100000, R =    10: 0.079586 sec
N =  10000, R = 10000: 0.011391 sec
```

* 長所: 連想配列キー検索のため高速
* 短所: 連想配列キーとして要素を格納するためトリッキーなコードになる

この方法は桁違いに最速ですが、データ構造を理解していないと、コードの意図が読み取りづらいのが欠点です。

この方法で注意しなければいけないのは要素が数値の場合です。PHP では、連想配列キーが `PHP_INT_MAX` に収まる数値表現 `[0-9]+` の場合は、配列インデックスとしてみなされてしまうようで、型を問わず _int_ に変換されてしまいます。

```php
// PHP_INT_MAX: 9223372036854775807 の場合
$map['9223372036854775807'] = null;
$map['9223372036854775808'] = null;
$keys = array_keys($map);

var_dump($keys);
// array(2) {
//   [0]=>
//   int(9223372036854775807)
//   [1]=>
//   string(19) "9223372036854775808"
// }

var_dump($keys[0] === '9223372036854775807'); // false
var_dump($keys[0] === 9223372036854775807); // true
var_dump($keys[1] === '9223372036854775808'); // true
```

ならば _double_ にキャストすれば？と考えてみましたが、まるで意図しないキーに変換されてしまいました。範囲外を表すキーなのでしょうか...？

```php
$map[(double) 9223372036854775807] = null;
$map[(double) 9223372036854775808] = null;
$keys = array_keys($map);

var_dump($keys);
// array(1) {
//   [0]=>
//   int(-9223372036854775808)
// }
```

数値表現 `[0-9]+` とならないように、ダミー文字列を追加して文字列キーとすれば、これらの問題は回避できます。

```php
$map['_9223372036854775807'] = null;
$map['_9223372036854775808'] = null;
$keys = array_keys($map);

var_dump($keys);
// array(2) {
//   [0]=>
//   string(20) "_9223372036854775807"
//   [1]=>
//   string(20) "_9223372036854775808"
// }

var_dump($keys[0] === '_9223372036854775807'); // true 
var_dump($keys[1] === '_9223372036854775808'); // true
```

## HashSet

ハッシュテーブルを使った [HashSet](https://gist.github.com/tachesimazzoca/e5c610c212f455ab2c2d#file-hashset-php) クラスで計測してみました。

```:実行結果
N = 100000, R = 1000
testIntHashSet: 0.210591 sec
testStringHashSet: 0.621980 sec

N = 100000, R = 10
testIntHashSet: 0.281084 sec
testStringHashSet: 0.496643 sec

N = 10000, R = 10000
testIntHashSet: 0.029540 sec
testStringHashSet: 0.073061 sec
```

値を string にキャストしてハッシュコードを生成していますが、int の場合のみ、そのままの値をハッシュコードとしています。もうちょっと早いことを期待しましたが、PHP コード上でハッシュコードを計算するコストがかかるようです。

## TreeSet

単純な二分木を使った [TreeSet](https://gist.github.com/tachesimazzoca/e5c610c212f455ab2c2d#file-treeset-php) クラスで計測してみました。

```:実行結果
N = 100000, R = 1000
testIntTreeSet: 1.922332 sec
testStringTreeSet: 3.406180 sec

N = 100000, R = 10
testIntTreeSet: 0.580253 sec
testStringTreeSet: 0.967903 sec

N = 10000, R = 10000
testIntTreeSet: 0.247157 sec
testStringTreeSet: 0.436166 sec
```

ノードをクラス [TreeSet_Node](https://gist.github.com/tachesimazzoca/e5c610c212f455ab2c2d#file-treeset-php-L42) で書いて要素 _R_ 個のオブジェクトを生成しているので、かなりコストがかかるようです。文字列の場合、比較関数として `strcmp` 関数を `call_user_func` 経由で使ってみたところ、倍の実行時間になってしまいました。

ノードを `array` で書いた [TreeSetX](https://gist.github.com/tachesimazzoca/e5c610c212f455ab2c2d#file-treesetx-php) クラスで計測してみました。

```:実行時間
N = 100000, R = 1000
testIntTreeSetX: 1.263026 sec 
testStringTreeSetX: 3.201873 sec 

N = 100000, R = 10
testIntTreeSetX: 0.394975 sec 
testStringTreeSetX: 0.750752 sec 

N = 10000, R = 10000
testIntTreeSetX: 0.171811 sec 
testStringTreeSetX: 0.530785 sec 
```

少しましになりましたが、ユーザ定義クラスからのオブジェクト生成と比較して、`array` は組み込みデータ構造である分のコストがかからないという程度に思われます。

## まとめ

割り切って連想配列キーでユニークを取るコードも PHP らしい使い方にも思えますが、ベンチマーク上のパフォーマンスが悪くても、基本的にはコードの意図を優先して in_array を使うという結論に至りました。

Java のような _Set_ を自作するとコードは見やすくはなりますが、今回のケースでは、単に API が増えてしまうだけで骨折り損とも言えそうです。