PHPで配列の和集合を高速に求める

PHPで複数の配列の和集合（union）を高速に求める方法を考えてみました。

前提

集合Aと集合Bの和集合（A∪B）とは、集合AとBの少なくともどちらか一方に属する要素（数学的には元）の全体のことです。具体的には

A = {1, 3, 5}
B = {1, 7}

というような集合A,Bを考えた場合、和集合A∪Bは

A∪B = {1, 3, 5, 7}

となります。

ここで先の集合A, BをPHPで表現すると、配列を使って、以下のような $a と$bとして定義できます。

$a = [1, 3, 5];
$b = [1, 7];

なので、今回の問題は以下のような出力を得ることができる関数array_unionを考えるということになります。

$a = [1, 3, 5];
$b = [1, 7];

print_r(array_union($a, $b));

/* 
Array
(
    [0] => 1
    [1] => 3
    [2] => 5
    [3] => 7
)
*/

アイデアと実装

それでは具体的な実装について考えます。今回は3つの方法で和集合を求めてみます。

方法1. in_array を使う

まずはin_array関数を使って、同一の値が存在していないかを確認し、存在しなければ、格納していく方法です。アイデアとしては最も単純かと思います。

function array_union(array $a, array $b) {
    foreach ($b as $val) {
        if (in_array($val, $a, true)) {
            continue;
        }
        $a[] = $val;
    }
    return $a;
}

方法2. array_unique を使う

2番目は値を無条件で格納していき、最後に array_unique 関数で重複を取り除く方法です。これも比較的わかりやすいと思います。

function array_union(array $a, array $b) {
    foreach ($b as $val) {
        $a[] = $val;
    }

    return array_unique($a);
}

方法3. array_flip, +, array_keysを使う

最後は複雑で、値が整数または文字列の配列にしか使えません。

function array_union(array $a, array $b) {
    return array_keys(
        array_flip($a) + array_flip($b)
    );
}

まずarray_flip関数により、キーと要素を入れ替えます。次に + 演算子で配列を結合します（array_mergeだと数字添字配列ではキーが振り直されるため期待通りに動きません）。最後に array_keys でキーを取り出して完了となります。

測定方法

今回は以下の関数で配列 $a, $bを生成し、それらに対する計算時間とメモリの最大使用量を測定します。配列の最大要素数 $nをパラメータとすることで、要素数がどう影響するかを確認します（配列の平均要素数は$n / 10）。また対象の配列による影響を考慮して、乱数のシード $seedを1, 2, ..., 100として100サンプルでの統計値を求めることにしました。

function generate_set(int $n, int $seed) {
    mt_srand($seed);
    $a = $b = [];
    for ($i = 1; $i < $n; $i++) {
        if (mt_rand(0, 9) === 0) {
            $a[] = $i;
        }
        if (mt_rand(0, 9) === 0) {
            $b[] = $i;
        }
    }
    return [$a, $b];
}

結果

計算時間の平均

計算時間の平均です。単位はマイクロ秒

最大要素数＼方法	方法1	方法2	方法3
1,000	42	18	14
10,000	3,411	151	88
100,000	314,176	1,508	1,072
1,000,000	31,256,512	18,893	11,479

計算時間に関しては、方法3 < 方法2 < 方法1 となりました。特に方法2, 3 は配列長に比例する形で時間が増加しているのに対して、方法1は配列長の2乗に比例して、計算時間が増加しています。これはループの内部に使用しているin_arrayの計算量のオーダーがO(n)であり、全体の計算量のオーダーがO(n^2)となっているからと思われます。

メモリ最大使用量の平均

最大要素数＼方法	方法1	方法2	方法3
1,000	426	446	440
10,000	543	779	687
100,000	2,448	5,350	4,696
1,000,000	16,784	41,157	34,802

メモリ使用量に関しては、方法1 < 方法3 < 方法2となりました。方法1は重複を都度確認するため、メモリの使用量が少なくて済みます。

まとめ

PHPで数字添字配列を集合とみなしたときに、複数の配列の和集合（union）を求める関数を考えました。使用できる場合は限定されますが、array_flip, +, array_keysを組み合わせる方法が、計算時間とメモリ使用量のバランスが良いかと思います。

ちなみに共通部分（intersection）を求める関数は、array_intersectというものが用意されています。需要の問題でしょうか……。