menu-icon

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 
メモリ最大使用量の平均(KB)

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

まとめ

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

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