昨日のログインしたユーザーの中で今日もログインしたユーザーの一覧を取り出そうと思いました。
そこで、昨日ログインしたユーザーのIDの配列と、今日ログインしたユーザーのIDの配列を用意しました。そして、その2つの配列の共通部分を取り出しました。
全然返ってこない･･･
と、ここまで言うのは簡単なんですが、配列が大きくて「アレ･･･全然返ってこない･･･」状態でした。
数千くらいの要素数の配列の共通部分を取るのはそれほど時間がかかりませんが、数万とか数十万とかの規模の配列の共通部分を取ろうと思うとちょっとつらい雰囲気でした。
PHPの標準関数array_intersectを使ったら速かった
for文をぶん回して共通部分を算出していたんですが、PHPに標準で配列の共通部分をとる関数があることに気づきました。array_intersectという関数です。
これを試してみたところ、処理がサクっと終わりました。それで、どのくらい速いのか、計算させてみました。
測定に用いたコード
配列の規模を10〜10,000まで振って、配列を乱数生成して、3つのアルゴリズムで比較しました。
1つ目は、forの中でforを回すアルゴリズム。2つ目は、forの中でPHP標準のin_arrayを回すアルゴリズム。3つ目が、array_intersectを用いるものです。
$n_array = array(
10,
100,
1000,
10000
);
foreach ($n_array as $n) {
echo "--- n: {$n}\n";
$array1 = array();
$array2 = array();
for ($i = 0; $i < $n; $i++) {
$array1[] = $i * 10 + rand(0, 2);
$array2[] = $i * 10 + rand(0, 2);
}
BenchTimer::start();
$intersect = array();
foreach ($array1 as $val1) {
foreach ($array2 as $key => $val2) {
if ($val1 == $val2) {
$intersect[] = $val1;
}
}
}
echo 'for in for: ' . md5(serialize($intersect)) . ' ... ' . round(BenchTimer::stop() * 1000, 2) . "ms\n";
BenchTimer::start();
$intersect = array();
foreach ($array1 as $val) {
if (in_array($val, $array2))
$intersect[] = $val;
}
echo 'in_array in for: ' . md5(serialize($intersect)) . ' ... ' . round(BenchTimer::stop() * 1000, 2) . "ms\n";
BenchTimer::start();
$intersect = array_values(array_intersect($array1, $array2));
echo 'array_intersect: ' . md5(serialize($intersect)) . ' ... ' . round(BenchTimer::stop() * 1000, 2) . "ms\n";
}
結果
結果は以下です。
$ php ./bench_intersect.php
--- n: 10
for in for: 20c710d486a76ba2acad78a5b75ab7b0 ... 0.92ms
in_array in for: 20c710d486a76ba2acad78a5b75ab7b0 ... 0.07ms
array_intersect: 20c710d486a76ba2acad78a5b75ab7b0 ... 0.08ms
--- n: 100
for in for: 126d67ae63fef5e7af83f6726c90d95e ... 2.68ms
in_array in for: 126d67ae63fef5e7af83f6726c90d95e ... 0.35ms
array_intersect: 126d67ae63fef5e7af83f6726c90d95e ... 0.41ms
--- n: 1000
for in for: 0f08895345f559f9f35a669c5d57ecef ... 299.11ms
in_array in for: 0f08895345f559f9f35a669c5d57ecef ... 20.37ms
array_intersect: 0f08895345f559f9f35a669c5d57ecef ... 6.4ms
--- n: 10000
for in for: a64601d9b1d24d0c2647631d31cd1a49 ... 31834.81ms
in_array in for: a64601d9b1d24d0c2647631d31cd1a49 ... 3693.1ms
array_intersect: a64601d9b1d24d0c2647631d31cd1a49 ... 92.3ms
for in forとin_array in forは、O(n^2)のオーダーでガンガン遅くなっていくのに対して、array_intersectはO(n)のオーダーで、配列が大きくなっても極端には遅くなりません。
どういうアルゴリズムなのかはまだ見てないです。(先にソートしたら効率は良くなりそうだけど、array_intersectは配列のキーを維持してるんですよね･･･)
コメント