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
というものが用意されています。需要の問題でしょうか……。