第７回 二分探索（バイナリサーチ）
力まかせ探索は でした。二分探索（バイナリサーチ）は
です。クイックソートは
でしたが、「半分、また半分」のときにlog nが登場します。二分探索も「半分、また半分」です。
詳しい説明はwikipediaで。
力まかせ探索と違い、二分探索はソート済みであることが前提になります。まずはデータに重複がないパターンを書きます。
<?php // $haystackはソート済みとする。 function binary_search_unique($needle, $haystack) { $left = 0; $right = count($haystack) - 1; while ($left <= $right) { $p = (int)(($left + $right) / 2); // $p は探索範囲のまんなか echo "左:$left, 右:$right, 探索位置:$p\n"; // 見つかったら位置を返す。 // 見つからなかった場合、チェックした値が$needleより小さければ、目標は右側半分のなかにあるはず。 // チェックした値が$needleより大きければ、目標は左側半分のなかにあるはず。 if ($haystack[$p] === $needle) { return $p; } elseif ($haystack[$p] < $needle) { $left = $p + 1; } else { $right = $p - 1; } // $haystackの中に$needleがない場合は、この時点で$left > $rightになるのでループから抜ける。 } return false; } $array = array(1, 5, 9, 7, 3, 2, 6, 4, 8); sort($array); echo '処理対象：' . join(', ', $array) . "\n"; echo "処理中...\n"; $output = binary_search_unique(2, $array); echo '2の位置：' . $output . "\n";
実行結果は
処理対象：1, 2, 3, 4, 5, 6, 7, 8, 9 処理中... 左:0, 右:8, 探索位置:4 左:0, 右:3, 探索位置:1 2の位置：1
国語辞典を引くときの調べ方に似ています。目的の単語が開いたページの右側にあるのか左側にあるのか。そういう調べ方ができるのは、辞書の単語が整列されているからです。
同じ読みの単語が複数ある時は、もうちょっと工夫が必要です。
function binary_search($needle, $haystack)
{
$ret = array();
// まず１つでもヒットする位置を探す。
// １つでもヒットすれば、その前後が候補位置になる。
$point = binary_search_unique($needle, $haystack);
if ($point !== false) {
$ret[] = $point;
for ($i = $point - 1; $i >= 0; $i--) {
if ($haystack[$i] === $needle) {
$ret[] = $i;
} else {
break;
}
}
for ($i = $point + 1; $i < count($haystack); $i++) {
if ($haystack[$i] === $needle) {
$ret[] = $i;
} else {
break;
}
}
}
return $ret;
}
$array = array(1, 5, 9, 7, 3, 2, 6, 4, 8, 1, 5, 9, 7, 3, 2, 6, 4, 8, 1, 5, 9, 7, 3, 2, 6, 4, 8);
sort($array);
echo '処理対象：' . join(', ', $array) . "\n";
echo "処理中...\n";
$output = binary_search(2, $array);
echo '2の位置：' . join(',', $output) . "\n";
実行結果は
処理対象：1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8, 9, 9, 9 処理中... 左:0, 右:26, 探索位置:13 左:0, 右:12, 探索位置:6 左:0, 右:5, 探索位置:2 左:3, 右:5, 探索位置:4 2の位置：4,3,5
ソートしてあるデータを使うことで から
になり、データ量が増えても速く見つかるようになりました。これを基本にもっと工夫すると、データベースの「インデックス」が出来上がります。インデックスはあらかじめソートしたデータを用意することで検索を速くしています。
「ソートしてから検索しよう！」という発想が出てきますが、クイックソートでも なので力まかせ探索（フルスキャン）より遅いです。「インデックスは更新が遅い」というのは、更新のたびにソートしなければいけないからです*1。バランスを取る必要があります。
*1:ソートの計算が発生するのに加え、そのデータをディスクに保存する必要があります。ソート自体は「ほぼソートされているデータ」という特性を生かすことで速くできたりもしますが、ディスクアクセスは計算よりはるかに遅いです
第６回 力まかせ探索（フルスキャン）
何かを検索するプログラムを書く場合に、一番簡単かつ分かりやすい方法が「力まかせ探索」とか呼ばれる方法です。「力まかせ探索」はどちらかといえば通称で、正確には名称は存在しないかもしれません。データベースではフルスキャンと呼ばれます。
<?php function fullscan($needle, $haystack) { $ret = array(); foreach ($haystack as $key => $val) { if ($val === $needle) { $ret[] = $key; } } return $ret; } $array = array(5, 2, 4, 3, 4, 8, 7, 2, 1); echo '処理対象：' . join(', ', $array) . "\n"; echo "処理中...\n"; $output = fullscan(2, $array); echo '2の位置：' . join(', ', $output) . "\n";
処理結果は
処理対象：5, 2, 4, 3, 4, 8, 7, 2, 1 処理中... 2の位置：1, 7
位置は0始まりなので「1, 7」になります。
単純にループを回して全部舐める、単純素朴な方法です。しかし、計算量は探索アルゴリズムで最大の になります。あえてメリットをあげるなら、バグが入り込む余地がほとんどないことです。
入力データに重複がないなら、見つかったところで処理を中断しても良いでしょう。
<?php function fullscan_unique($needle, $haystack) { foreach ($haystack as $key => $val) { if ($val === $needle) { return $key; } } return false; } $array = array(1, 5, 9, 7, 3, 2, 6, 4, 8); echo '処理対象：' . join(', ', $array) . "\n"; echo "処理中...\n"; $output = fullscan_unique(2, $array); echo '2の位置：' . $output . "\n";
処理対象：1, 5, 9, 7, 3, 2, 6, 4, 8 処理中... 2の位置：5
次回は「二分探索」をこれと比較しながら進めます。
第５回 エラトステネスのふるい
エラトステネスのふるいとは、素数を見つけ出すための方法です。解説はwikipediaにおまかせです。wikipediaのgif動画はすごいですね。
<?php function furui() { // 作業テーブルの初期化。trueなら素数、falseなら素数でないとする。 $array = array(); for ($i = 0; $i <= 100; $i++) { $array[$i] = true; } // 0と1は素数の定義上、素数ではない。 $array[0] = false; $array[1] = false; // 2以上について素数を探す。 for ($n = 2; $n <= 100; $n++) { // $nは素数候補。$nの２倍から素数ではなくなる。 for ($m = $n + $n; $m <= 100; $m += $n) { $array[$m] = false; } } // 素数一覧を整形して返す。 $ret = array(); for ($j = 0; $j <= 100; $j++) { if ($array[$j]) { $ret[] = $j; } } return $ret; } echo "実行結果：\n"; echo join(', ', furui()) . "\n";
実行結果は
実行結果： 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
計算量は より小さく
より大きいですが……すみません、正確な数式がパッと出てこないです。$mのループを回す前に
if($array[$n] == false) {
continue;
}
とすればもっと早くなります（たとえば$n = 4の場合、4の倍数は2の倍数なので、$n = 2のときのループで処理が終わっています。それは$array[$n] == falseで見つかります）。
素数を見つけるのに足し算だけでいける、というのはなかなか興味深いです。
配列を使ったアルゴリズムはメモリを使う代わりに問題をすんなりと解かせてくれることが多いです。「A+D=P」という言葉がありますが、「Algorithms + Data Structures = Programs」（アルゴリズム＋データ構造＝プログラム）の略です。プログラムは処理（≒手順＝アルゴリズム）をガリガリ書くだけでは分かりにくくなりがちです。適切なデータ構造と組み合わせることで分かりやすく処理の速いプログラムになります。どういうデータ構造なら処理がしやすいか、を考えるのは設計のアプローチの１つで、データベース設計が重要な所以です。
次回からは探索アルゴリズムです。次回はデータ構造を考えない の「力まかせ探索（フルスキャン）」、次々回はデータの並びを利用した
の「二分探索（バイナリサーチ）」、その次はデータ構造に工夫を持たせた
の「ハッシュテーブル」です。
第４回 分布数え上げソート
最速とされているクイックソートの計算量は ですが、分布数え上げソートは
です。その速さはクイックソートを上回ります。
<?php function counting_sort($array, $min, $max) { // 値の出現回数を数え上げる。 $count_list = array(); foreach ($array as $i) { if (isset($count_list[$i])) { $count_list[$i]++; } else { $count_list[$i] = 1; } } // 出現回数だけ出力をすれば並べ替えたことと同じになる $ret = array(); for ($key = $min; $key <= $max; $key++) { if (isset($count_list[$key])) { for($n = 0; $n < $count_list[$key]; $n++) { $ret[] = $key; } } } return $ret; } $input = array(5, 2, 4, 3, 4, 8, 7, 2, 1); echo '処理前：' . join(', ', $input) . "\n"; echo "処理中...\n"; $output = counting_sort($input, 1, 10); echo '処理後：' . join(', ', $output) . "\n";
実行結果はこうなります。
処理前：5, 2, 4, 3, 4, 8, 7, 2, 1 処理中... 処理後：1, 2, 2, 3, 4, 4, 5, 7, 8
結果としてソートされていますが、値の入れ替えを行っていないのが計算量 を実現するポイントです。ループを２回回しているだけなので、計算回数はデータ数×２回で済んでいます。
これができるのは、値のminとmaxがわかっているからになります。クイックソートは値の上限下限を気にしませんが、分布数え上げソートは出力するときに「小さい方から出力」というのを実現するために下限から上限へのforループを回しています。
「上限下限が事前にわかっている」という制約条件を生かすことでより速くなっているということです。現実にも「テストの点数は0〜100点」など、事前にわかっていることは多いと思います。
個人的には一番好きなアルゴリズムです。特にPHPとの相性がよく、実際に応用を使用することもあります。ソート実装としては反則ですが、ksort()を使うと制約条件なしで使えます。
<?php function counting_sort_kai($array) { // 値の出現回数を数え上げる。 $count_list = array(); foreach ($array as $i) { if (isset($count_list[$i])) { $count_list[$i]++; } else { $count_list[$i] = 1; } } // 出現回数だけ出力をすれば並べ替えたことと同じになる $ret = array(); ksort($count_list); foreach ($count_list as $key => $val) { for($n = 0; $n < $val; $n++) { $ret[] = $key; } } return $ret; }
これが何に使えるかというと、例えば「UserAgentを数え上げてソートしてCSV出力する」という作業がある場合です。
- ksort()ではなくrsort()を使う
- forループを回して$retを作る代わりにcsv１行をechoする
に作り変えればすぐできます。配列（連想配列）のキーには文字列を使えるので、出現回数のカウントにはもってこいです。
基本のアルゴリズムは直接使うことはありませんが、応用がいろいろあります。基本があってはじめて応用があるものです。
次は同じく配列を使ったアルゴリズムである「エラトステネスのふるい」です。
第３回 計算量
計算量とは、アルゴリズムの速さの目安になるものです。入力データの個数をnとしたときの処理回数を大雑把に表します。
先のバブルソートだと 、クイックソートだと
と書きます。
第１回のデータは
$input = array(5, 2, 4, 3, 4, 8, 7, 2, 1);
だったので、n = 9です。
計算量となる処理回数ですが、ループで何度もまわすので
2, 4, 3, 4, 5, 7, 2, 1, 8 2, 3, 4, 4, 5, 2, 1, 7, 8 2, 3, 4, 4, 2, 1, 5, 7, 8 2, 3, 4, 2, 1, 4, 5, 7, 8 2, 3, 2, 1, 4, 4, 5, 7, 8 2, 2, 1, 3, 4, 4, 5, 7, 8 2, 1, 2, 3, 4, 4, 5, 7, 8 1, 2, 2, 3, 4, 4, 5, 7, 8
で、台形の面積の公式に当てはめると (9 + 2) * 8 / 2 = 44 回です。
nで書くと (n + 2) * (n - 1) / 2 ですが、めんどくさいので
1, 2, 2, 3, 4, 4, 5, 7, 8
を足して三角形の面積の公式 n * n / 2 としましょう。 ですが,計算量で書くときは係数の1/2は無視して
と書きます。
これは「このアルゴリズムは個数nの２乗に比例した処理回数ですよ」ということを表しており、データ数が増えれば増えるほど爆発的に処理時間がかかるということです。中学で習った放物線のグラフになります。
台形に戻ると、(n + 2) * (n - 1) / 2 = ですが、結局のところ放物線なので、一番次数の高い
だけを書いて
と書きます。
つまり、計算量はデータ量の増加に対する処理回数の増え方の程度を表します。
ではクイックソートの というのはどうなのかというと、一番効率よく処理されると
1, 2, 4, 3, 5, 6, 8, 7 1, 2, 3, 4, 5, 6, 7, 8 1, 2, 3, 4, 5, 6, 7, 8
というように、半分、また半分、と分割されるのでループ回数がかなり少なくなります。
正方形の面積の公式になりますが、横は n 、縦は log n になるので処理回数は n log n 、計算量は になります（ log n は対数関数です。wikipediaのグラフを見ると、nの増加に対してあんまり上に伸びていかないのがわかります）。
さて、この例は「一番効率よく処理されると」という前提でした。では一番効率悪いとどうなるかというと「たまたま基準値に対し常に小さい状態だった」とかなると
1, 2, 3, 4, 5, 6, 7, 8 1, 2, 3, 4, 5, 6, 7, 8 1, 2, 3, 4, 5, 6, 7, 8 1, 2, 3, 4, 5, 6, 7, 8 1, 2, 3, 4, 5, 6, 7, 8 1, 2, 3, 4, 5, 6, 7, 8 1, 2, 3, 4, 5, 6, 7, 8 1, 2, 3, 4, 5, 6, 7, 8
という不幸な状態になり、これは です。最悪なことにすでに整列されているデータに対してクイックソートかけるとこうなります（実際には実装の工夫によりこういう事態が起こらないようにします）。
一方、これにバブルソートをかけるとやっぱり ではあるのですが、一度もデータ入れ替えが発生しないため処理１回あたりのスピードがむちゃくちゃ速く終わり、クイックソートの最速パターンより速く処理されます。
つまり、計算量は処理１回あたりの重さを考慮していないので、あくまで目安ということになります。たとえばマージソートというものはどんなデータが来ても ですが、処理１回の重さでクイックソートに劣ります。
数学の難しいことはわからんという人は、 の順に軽いということと、log nが「半分また半分」であるということを押さえておけば良いと思います。
データが少ないうちはどのアルゴリズムでもすぐ処理が終わるので気にすることはありません。しかし「処理が重い」とユーザから言われるのはデータ量が多いときです。計算量を把握しておくと、実装するときのパフォーマンスの目安として良いものになります。
次は「最速」であるはずのクイックソートより速い を実現する「分布数え上げソート」です。
第２回 クイックソート
クイックソートはPHPに限らずいろんな言語でライブラリとして実装されており、例えばC言語ではqsort()として標準ライブラリとして用意されています。
その名の通り「速いソート」で、実装時の工夫等もあり汎用ソートアルゴリズムとしては最速とされています。
解説はやっぱりwikipediaにおまかせとして、そのgifアニメで表示されている方法で実装してみます。
<?php function quick_sort(&$array) { _qsort($array, 0, count($array) - 1); } function _qsort(&$array, $start, $end) { // ソート対象が１個以下なら何もしない if ($start >= $end) { return; } $lt = $start; // 左端のポインタ $ge = $end - 1; // 右端のポインタ $pivot = $array[$end]; // 基準値 // ポインタがクロスするまでループを回す while ($lt < $ge) { // 左端のポインタが右端にくるまで右に移動させる。 // 基準値以上の値が現れたらそこでストップ。 while ($lt < $end) { if ($array[$lt] >= $pivot) { break; } $lt++; } // 右端のポインタが左端にくるまで左に移動させる。 // 基準値より小さい値が現れたらそこでストップ。 while ($ge > $start) { if ($array[$ge] < $pivot) { break; } $ge--; } // ポインタがクロスしていなければ、値を入れ替える（値の小さいものを左へ、大きいものを右へ移動させる） if ($lt < $ge) { $temp = $array[$lt]; $array[$lt] = $array[$ge]; $array[$ge] = $temp; $lt++; $ge--; } } // 一番右にある基準値を真ん中へ移動させる $array[$end] = $array[$lt]; $array[$lt] = $pivot; echo join(', ', array_slice($array, $start, $end - $start + 1)) . " (pivot: $pivot)\n"; // 基準値より小さいグループに対してさらにソートする。 // 基準値より大きいグループに対してさらにソートする。 // グループ内の値が１個以下になっていれば呼び出した先で処理は終了する（１個以下＝常にソート済み） _qsort($array, $start, $lt - 1); _qsort($array, $lt + 1, $end); } $input = array(5, 2, 4, 3, 4, 8, 7, 2, 1, 6); echo '処理前：' . join(', ', $input) . "\n"; echo "処理中...\n"; quick_sort($input); echo '処理後：' . join(', ', $input) . "\n";
出力結果は以下。
処理前：5, 2, 4, 3, 4, 8, 7, 2, 1, 6 処理中... 5, 2, 4, 3, 4, 1, 2, 6, 8, 7 (pivot: 6) 1, 2, 4, 3, 4, 5, 2 (pivot: 2) 2, 3, 4, 5, 4 (pivot: 2) 3, 4, 5, 4 (pivot: 4) 4, 5 (pivot: 4) 7, 8 (pivot: 7) 処理後：1, 2, 2, 3, 4, 4, 5, 6, 7, 8
やっていることは「基準値より小さい値を左側に、大きい値を右側に移動させる」ということです。そして、その小さい値のグループに対して再度同じことを、大きい値のグループにも再度同じことをしてやる。そうするうちに最終的にすべてがソートされていきます。
_qsort()の中でさらに_qsort()を呼び出していますが、これを「再帰呼び出し」といいます。再帰について理解できるかどうかがアルゴリズムの勉強の成否を分けますので、がんばって咀嚼してみてください。以下にソート処理中の出力を整理したものを用意しておきます。
5, 2, 4, 3, 4, 1, 2, 6, 8, 7 1, 2, 4, 3, 4, 5, 2, 6, 7, 8 1, 2, 2, 3, 4, 5, 4, 6, 7, 8 1, 2, 2, 3, 4, 5, 4, 6, 7, 8 1, 2, 2, 3, 4, 4, 5, 6, 7, 8
第１回 バブルソート
10番煎じぐらいな気がしなくもないですが、PHPでアルゴリズムのお勉強です。
初回はおなじみバブルソート。バブルソートそのものの解説はwikipediaでどうぞ。
<?php function bubble_sort(&$array) { $count = count($array); for ($n = $count - 1; $n > 0; $n--) { // $n はソート対象範囲の最大 for ($i = 0; $i < $n; $i++) { // $i はソートのポインタ // ポインタの数値がポインタ右側より大きければ入れ替える。 if ($array[$i] > $array[$i+1]) { $temp = $array[$i]; $array[$i] = $array[$i+1]; $array[$i+1] = $temp; } } echo join(', ', $array) . "\n"; } } $input = array(5, 2, 4, 3, 4, 8, 7, 2, 1); echo '処理前：' . join(', ', $input) . "\n"; echo "処理中...\n"; bubble_sort($input); echo '処理後：' . join(', ', $input) . "\n";
出力結果は以下。
処理前：5, 2, 4, 3, 4, 8, 7, 2, 1 処理中... 2, 4, 3, 4, 5, 7, 2, 1, 8 2, 3, 4, 4, 5, 2, 1, 7, 8 2, 3, 4, 4, 2, 1, 5, 7, 8 2, 3, 4, 2, 1, 4, 5, 7, 8 2, 3, 2, 1, 4, 4, 5, 7, 8 2, 2, 1, 3, 4, 4, 5, 7, 8 2, 1, 2, 3, 4, 4, 5, 7, 8 1, 2, 2, 3, 4, 4, 5, 7, 8 処理後：1, 2, 2, 3, 4, 4, 5, 7, 8
一番単純なソートアルゴリズムですが、実際にはこれではなく「クイックソート」が使われることが多いです。PHPのsort()関数もクイックソートで実装されています。というわけで次回はクイックソートです。
