![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
裏メニュー第七週 †簡易ベンチマーク †PHPのmicrotime関数を使用して、プログラムの実行時間に関する簡易的なベンチマークを取ることができます*1。 microtime: 現在の Unix タイムスタンプをマイクロ秒まで返す (PHP: microtime - Manual) ベンチマークを取りたい箇所をmicrotime関数で囲み、差分を取ることで「どのくらい実行に時間がかかっているか」がわかります。 <?php // 全く意味のない計算をする関数 function useless_calculations($times) { for ($i = 0; $i < $times; $i++) { rand() * rand(); } } $start = microtime(true); // 現在の時間を取得 useless_calculations(1000); echo '1000回の無意味な計算には' . (microtime(true) - $start) . "秒かかりました。\n"; $start = microtime(true); // 現在の時間を取得 useless_calculations(1000000); echo '1000000回の無意味な計算には' . (microtime(true) - $start) . "秒かかりました。\n"; ?> これを手元の環境で実行すると、次のような結果になりました。 $ php sample.php 1000回の無意味な計算には0.00190210342407秒かかりました。 1000000回の無意味な計算には1.99042391777秒かかりました。 アルゴリズム †アルゴリズムとは何でしょうか? ある特定の問題を解いたり、課題を解決したりするための計算手順や処理手順のこと。 これを図式化したものがフローチャートであり、 コンピューターで処理するための具体的な手順を記述したものがプログラムである。 イランの数学者・天文学者、アル＝フワーリズミーにちなむ。 (アルゴリズム とは - コトバンク) また、Wikipediaでは次のように記述されています。 アルゴリズムとは、数学、コンピューティング、言語学、あるいは関連する分野において、 問題を解くための効率的手順を定式化した形で表現したものを意味する。 算法（さんぽう）と訳されることもある。 コンピュータにアルゴリズムを指示するための（電子）文書をプログラムという。 人間より速く大量に正しい結果を導くことができるのがコンピュータの強みであるが、 そのためには正しいアルゴリズムに基づくプログラムが必要である。 アルゴリズムとは「問題を解くための効率的手順を定式化した形で表現したもの」であるそうです。 先ほど引用した内容から考えると、「良い」アルゴリズムとは次のようなものでしょう。
また「コンピュータにアルゴリズムを指示するための（電子）文書をプログラムという」のであれば、
以降では、良いアルゴリズムについて「ソート」を例にして考えていきます。 ソート †「ソート」とは「並び換え」のことです。 PHP標準関数sort †PHP標準関数のsortにはクイックソートというアルゴリズムが使用されています。 サンプルとして小さいプログラムを示します。 <?php $array = array(12, 22, 3, 44, 13, 40, 58, 8); sort($array, SORT_NUMERIC); print_r($array); // 実行結果 // Array // ( // [0] => 3 // [1] => 8 // [2] => 12 // [3] => 13 // [4] => 22 // [5] => 40 // [6] => 44 // [7] => 58 // ) ?> シンプルなソート †sort関数と同等の機能を実現したいとしましょう。
すごくシンプルですね。 <?php // シンプルなソート(名前は知らない) function simple_sort($array) { $size = count($array); for ($i = 0; $i < ($size - 1); $i++) { $suffix = $i; $smallest = $array[$i]; // 配列(の残り)から最も小さい値を探す for ($j = ($i + 1); $j < $size; $j++) { if ($smallest > $array[$j]) { $smallest = $array[$j]; $suffix = $j; } } // 配列(の残り)の最も小さい値を交換する $tmp = $array[$i]; $array[$i] = $smallest; $array[$suffix] = $tmp; } return $array; } $array = array(12, 22, 3, 44, 13, 40, 58, 8); $array = simple_sort($array); print_r($array); // 実行結果 // Array // ( // [0] => 3 // [1] => 8 // [2] => 12 // [3] => 13 // [4] => 22 // [5] => 40 // [6] => 44 // [7] => 58 // ) ?> バブルソート †「バブルソート」は単純なソートのアルゴリズムとしてよく知られています。 Wikipediaには次のように記述されています。 1番目と2番目を比較し、順番が逆であれば入れ換える。 次に2番目と3番目を比較して入れ換える。 これを最後まで行うと、最後の数だけが最小または最大の数として確定するので、 確定していない部分について1つずつ減らしながら繰り返す。 (バブルソート - Wikipedia) これをプログラムとして実現すると次のようになります。 <?php // 典型的なバブルソート function bubble_sort($array) { $size = count($array); for ($i = 0; $i < ($size - 1); $i++) { for ($j = 0; $j < ($size - $i - 1); $j++) { if ($array[$j] > $array[$j + 1]) { // 値を交換 $tmp = $array[$j]; $array[$j] = $array[$j + 1]; $array[$j + 1] = $tmp; } } } return $array; } $array = array(12, 22, 3, 44, 13, 40, 58, 8); $array = bubble_sort($array); print_r($array); // 実行結果 // Array // ( // [0] => 3 // [1] => 8 // [2] => 12 // [3] => 13 // [4] => 22 // [5] => 40 // [6] => 44 // [7] => 58 // ) ?> マージソート †「マージソート」は分割統治法を用いたソートのアルゴリズムの一つとしてよく知られています。
どこまで分割するかは特に規定されませんが、多くの場合「データ数が2以下になるまで」分割します。 これをプログラムとして実現すると次のようになります。 <?php // 典型的なマージソート function merge_sort(&$array, $left, $right) { // 配列の要素が一つなら戻る if ($left >= $right) { return; } // 配列を真中で分割して左側と右側で再帰的に呼出す $median = (int)(($left + $right) / 2); merge_sort($array, $left, $median); merge_sort($array, $median + 1, $right); // $tはテンポラリ $t = array(); // $array[$left] から $array[$median]をテンポラリへ for ($i = $left; $i <= $median; $i++) { $t[$i] = $array[$i]; } // $array[$median + 1] から $array[$right]をテンポラリへ for ($i = $median + 1, $j = $right; $i <= $right; $i++, $j--) { $t[$i] = $array[$j]; } $i = $left; $j = $right; // 小さい方から配列に戻す for ($k = $left; $k <= $right; $k++) { if ($t[$i] <= $t[$j]) { $array[$k] = $t[$i++]; } else { $array[$k] = $t[$j--]; } } } $array = array(12, 22, 3, 44, 13, 40, 58, 8); merge_sort($array, 0, count($array) -1); print_r($array); // 実行結果 // Array // ( // [0] => 3 // [1] => 8 // [2] => 12 // [3] => 13 // [4] => 22 // [5] => 40 // [6] => 44 // [7] => 58 // ) ?> それぞれのソートのベンチマーク †<?php // 引数で指定した数の要素を持つ配列 function init_random_array($size = 2000) { $ret = array(); for ($i = 0; $i < $size; $i++) { $ret[] = rand(); } return $ret; } // シンプルなソート(名前は知らない) function simple_sort($array) { $size = count($array); for ($i = 0; $i < ($size - 1); $i++) { $suffix = $i; $smallest = $array[$i]; // 配列(の残り)から最も小さい値を探す for ($j = ($i + 1); $j < $size; $j++) { if ($smallest > $array[$j]) { $smallest = $array[$j]; $suffix = $j; } } // 配列(の残り)の最も小さい値を交換する $tmp = $array[$i]; $array[$i] = $smallest; $array[$suffix] = $tmp; } return $array; } // 典型的なバブルソート function bubble_sort($array) { $size = count($array); for ($i = 0; $i < ($size - 1); $i++) { for ($j = 0; $j < ($size - $i - 1); $j++) { if ($array[$j] > $array[$j + 1]) { // 値を交換 $tmp = $array[$j]; $array[$j] = $array[$j + 1]; $array[$j + 1] = $tmp; } } } return $array; } // 典型的なマージソート function merge_sort(&$array, $left, $right) { // 配列の要素が一つなら戻る if ($left >= $right) { return; } // 配列を真中で分割して左側と右側で再帰的に呼出す $median = (int)(($left + $right) / 2); merge_sort($array, $left, $median); merge_sort($array, $median + 1, $right); // $tはテンポラリ $t = array(); // $array[$left] から $array[$median]をテンポラリへ for ($i = $left; $i <= $median; $i++) { $t[$i] = $array[$i]; } // $array[$median + 1] から $array[$right]をテンポラリへ for ($i = $median + 1, $j = $right; $i <= $right; $i++, $j--) { $t[$i] = $array[$j]; } $i = $left; $j = $right; // 小さい方から配列に戻す for ($k = $left; $k <= $right; $k++) { if ($t[$i] <= $t[$j]) { $array[$k] = $t[$i++]; } else { $array[$k] = $t[$j--]; } } } $numbers = init_random_array(); // 組込み関数でのソート $start = microtime(true); // print_r(sort($numbers, SORT_NUMERIC)); sort($numbers, SORT_NUMERIC); printf("組込み関数 sort では %s 秒かかりました。\n", microtime(true) - $start); // シンプルなソート $start = microtime(true); // print_r(simple_sort($numbers)); simple_sort($numbers); printf("シンプルなソートでは %s 秒かかりました。\n", microtime(true) - $start); // バブルソート $start = microtime(true); // print_r(bubble_sort($numbers)); bubble_sort($numbers); printf("バブルソートでは %s 秒かかりました。\n", microtime(true) - $start); // マージソート $start = microtime(true); // merge_sort($numbers, 0, count($numbers) - 1); merge_sort($numbers, 0, count($numbers) - 1); printf("マージソートでは %s 秒かかりました。\n", microtime(true) - $start); ?> これを手元の環境で実行すると、次のような結果になりました。 $ php sample.php 組込み関数 sort では 0.00717711448669 秒かかりました。 シンプルなソートでは 2.22329187393 秒かかりました。 バブルソートでは 3.04475808144 秒かかりました。 マージソートでは 0.114268064499 秒かかりました。 組込み関数が圧倒的な速度であることと、自前の関数でもアルゴリズム次第で大きな差が出ることを確認してください。 追記 †優れたアルゴリズムを知ること、または考案することこそプログラミングの醍醐味です。 宿題 †
参考資料 † |
