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

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

• Set implementations in PHP

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

in_array

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

$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 関数で重複削除する方法です。

$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 でキー集合を取り出す方法です。

$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_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 にキャストすれば？と考えてみましたが、まるで意図しないキーに変換されてしまいました。範囲外を表すキーなのでしょうか...？

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

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

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

$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 クラスで計測してみました。

実行結果

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 クラスで計測してみました。

実行結果

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 で書いて要素 R 個のオブジェクトを生成しているので、かなりコストがかかるようです。文字列の場合、比較関数として strcmp 関数を call_user_func 経由で使ってみたところ、倍の実行時間になってしまいました。

ノードを array で書いた TreeSetX クラスで計測してみました。

実行時間

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 が増えてしまうだけで骨折り損とも言えそうです。