id:eel3:20100502:1272780085 や id:eel3:20100502:1272783601 で書いたRubyによる解答例を実行すると、手元の環境では3〜4分程度かかる。
| PC | DELL Latitude D630 |
| CPU | Intel(R) Core(TM)2 Duo T7250 @ 2.00GHz |
| Memory | DDR2 (PC2-6400) 2048MB*2 (Dual Channel) |
| OS | Windows XP Professional SP3 |
試しにRuby版を元にC言語で実装してみて、実行速度を比べてみた。
C言語版のコードはこんな感じ。
/* ********************************************************************** */ /** * @brief Poderosaを開発している某社の入社試験。迷路の最短経路を求める。 * @author eel3 @ TRASH BOX * @date 2010/05/02 * * @par 動作確認済み環境: * - Microsoft Windows XP Professional (32bit) SP3 * * @par 確認済みコンパイラ: * - Digital Mars C and C++ Compilers 8.49 * - Microsoft Visual Studio 2005 * - MinGW 5.0.3 (GCC 3.4.2) * * @bug * - 内部バッファが固定サイズ。 * 入力データ（迷路のテキスト）のサイズの変動を考慮していない。 * - 再帰で記述しているので、データ量が大きいと破綻する可能性が高い。 */ /* ********************************************************************** */ #define _CRT_SECURE_NO_WARNINGS #define NDEBUG #include <assert.h> #include <errno.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #define START 'S' /**< スタート */ #define GOAL 'G' /**< ゴール */ #if 0 #define WALL '*' /**< 迷路の壁 */ #endif #define WAY ' ' /**< 通路（通行可能な部分） */ #define PASSED '$' /**< 既に通った場所 */ /** 座標点 */ struct POINT { long x; /**< X軸 */ long y; /**< Y軸 */ }; /** 経路のログ情報 */ struct TRACK_LOG { /** * @brief 迷路のテキストを格納する二次元配列。 * 縦がY軸、横がX軸になる。なのでmaze[y][x]とアクセスすること。 */ char maze[256][256]; size_t hop; /**< ホップ数。経路の距離を表す。1マスにつき1。 */ }; /** 最短経路のログ情報をここに格納する */ static struct TRACK_LOG track_log; /* ====================================================================== */ /** * @brief 配列の要素数を求める * * @param[in] ary 配列の実体 * * @return 要素数 * * @attention * 必ず配列の実体そのものを引数指定すること。 * 配列へのポインタを引数指定した場合、正しい要素数は得られない。 */ /* ====================================================================== */ #define NELEMS(ary) (sizeof(ary) / sizeof((ary)[0])) /* ====================================================================== */ /** * @brief 迷路のテキストを読み込む * * @param[in,out] *in 入力ストリーム * @param[out] *tlog 経路のログ情報 * @param[out] *start スタートの位置の座標 */ /* ====================================================================== */ static void load_maze(FILE *in, struct TRACK_LOG *tlog, struct POINT *start) { size_t i, j, len; assert(in != NULL && tlog != NULL && start != NULL); (void) memset(tlog, 0 , sizeof(*tlog)); (void) memset(start, 0 , sizeof(*start)); for (i = 0; i < NELEMS(tlog->maze); ++i) { if (fgets(tlog->maze[i], (int) sizeof(tlog->maze[0]), in) == NULL) { break; } len = strlen(tlog->maze[i]); if (len > 0 && tlog->maze[i][len-1] == '\n') { tlog->maze[i][--len] = '\0'; } for (j = 0; j < len; ++j) { if (tlog->maze[i][j] == START) { start->x = (long) j; start->y = (long) i; } } } } /* ====================================================================== */ /** * @brief 最短経路を探す（しらみつぶし） * * @param[in,out] *tlog 経路のログ情報 * @param[in] *pt 今指し示している座標 */ /* ====================================================================== */ static void track(struct TRACK_LOG *tlog, const struct POINT *pt) { struct POINT tmp; assert(tlog != NULL && pt != NULL); if (pt->y < 0 || (size_t) pt->y >= NELEMS(tlog->maze) || tlog->maze[pt->y][0] == '\0') { return; } if (pt->x < 0 || (size_t) pt->x >= NELEMS(tlog->maze[0]) || tlog->maze[pt->y][pt->x] == '\0') { return; } if (track_log.hop != 0 && tlog->hop >= track_log.hop) { return; } if (tlog->maze[pt->y][pt->x] == GOAL) { track_log = *tlog; #if 0 fprintf(stderr, "%lu\n", (unsigned long) track_log.hop); #endif return; } if (tlog->maze[pt->y][pt->x] != WAY) { return; } tlog->maze[pt->y][pt->x] = PASSED; ++tlog->hop; tmp = *pt; --tmp.x; track(tlog, &tmp); tmp = *pt; ++tmp.y; track(tlog, &tmp); tmp = *pt; ++tmp.x; track(tlog, &tmp); tmp = *pt; --tmp.y; track(tlog, &tmp); --tlog->hop; tlog->maze[pt->y][pt->x] = WAY; } /* ====================================================================== */ /** * @brief 経路のログ情報をダンプ表示する * * @param[in] *tlog 経路のログ情報 * @param[in,out] *out 出力ストリーム */ /* ====================================================================== */ static void dump_track_log(const struct TRACK_LOG *tlog, FILE *out) { size_t i; assert(tlog != NULL && out != NULL); for (i = 0; i < NELEMS(tlog->maze) && tlog->maze[i][0] != '\0'; ++i) { fprintf(out, "%s\n", tlog->maze[i]); } fprintf(out, "hop count: %lu\n", (unsigned long) tlog->hop); } /* ====================================================================== */ /** * @brief 最短経路探索の処理を実行する * * @param[in,out] *in 入力ストリーム * @param[in,out] *out 出力ストリーム * * @note * 将来の拡張を考慮して、出力先も引数指定可能にしてある。 */ /* ====================================================================== */ static void doit(FILE *in, FILE *out) { static struct TRACK_LOG tlog; struct POINT start, pt; assert(in != NULL && out != NULL); load_maze(in, &tlog, &start); dump_track_log(&tlog, out); fputc('\n', out); tlog.hop = 1; pt = start; --pt.x; track(&tlog, &pt); pt = start; ++pt.y; track(&tlog, &pt); pt = start; ++pt.x; track(&tlog, &pt); pt = start; --pt.y; track(&tlog, &pt); dump_track_log(&track_log, out); } /* ********************************************************************** */ /** * @brief メインルーチン * * @retval EXIT_SUCCESS 正常終了 * @retval EXIT_FAILURE 異常終了 */ /* ********************************************************************** */ int main(int argc, char *argv[]) { int retval = EXIT_SUCCESS; if (argc <= 1) { doit(stdin, stdout); } else { FILE *in; int i; for (i = 1; i < argc; ++i) { errno = 0; if ((in = fopen(argv[i], "r")) == NULL) { perror(argv[i]); retval = EXIT_FAILURE; continue; } doit(in, stdout); (void) fclose(in); } } return retval; }
コマンドプロンプトで実行したログ。
D:\tmp>type maze_rb.bat
@echo off
echo %DATE% %TIME%
ruby -w maze.rb data.txt
echo %DATE% %TIME%
D:\tmp>ruby -v
ruby 1.8.7 (2009-06-12 patchlevel 174) [i386-mswin32]
D:\tmp>maze_rb.bat
2010/05/02 19:09:26.06
**************************
*S* * *
* * * * ************* *
* * * ************ *
* * *
************** ***********
* *
** ***********************
* * G *
* * *********** * *
* * ******* * *
* * *
**************************
start: {:y=>1, :x=>1}
goal : {:y=>8, :x=>22}
**************************
*S* * $$$ *
*$* *$$*$ ************* *
*$* $$* $ ************ *
*$$$$* $$$$$$$ *
**************$***********
* $$$$$$$$$$$$$ *
**$***********************
* $$$ * $$$$$$$$$$$$$G *
* *$$$$$$*********** * *
* * ******* * *
* * *
**************************
hop count: 60
2010/05/02 19:12:54.75
D:\tmp>type maze_c.bat
@echo off
echo %DATE% %TIME%
maze.exe data.txt
echo %DATE% %TIME%
D:\tmp>gcc --version
gcc (GCC) 3.4.2 (mingw-special)
Copyright (C) 2004 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
D:\tmp>gcc -Wall -ansi -pedantic -o maze maze.c
D:\tmp>maze_c.bat
2010/05/02 19:14:58.34
**************************
*S* * *
* * * * ************* *
* * * ************ *
* * *
************** ***********
* *
** ***********************
* * G *
* * *********** * *
* * ******* * *
* * *
**************************
hop count: 0
**************************
*S* * $$$ *
*$* *$$*$ ************* *
*$* $$* $ ************ *
*$$$$* $$$$$$$ *
**************$***********
* $$$$$$$$$$$$$ *
**$***********************
* $$$ * $$$$$$$$$$$$$G *
* *$$$$$$*********** * *
* * ******* * *
* * *
**************************
hop count: 60
2010/05/02 19:14:59.43
D:\tmp>maze_c.bat
2010/05/02 19:15:18.51
**************************
*S* * *
* * * * ************* *
* * * ************ *
* * *
************** ***********
* *
** ***********************
* * G *
* * *********** * *
* * ******* * *
* * *
**************************
hop count: 0
**************************
*S* * $$$ *
*$* *$$*$ ************* *
*$* $$* $ ************ *
*$$$$* $$$$$$$ *
**************$***********
* $$$$$$$$$$$$$ *
**$***********************
* $$$ * $$$$$$$$$$$$$G *
* *$$$$$$*********** * *
* * ******* * *
* * *
**************************
hop count: 60
2010/05/02 19:15:19.25
D:\tmp>Ruby版は3分半ぐらい、C言語版は1秒ちょっと（2回目以降の実行では0.7〜0.8秒の間）で答えが出た。
Ruby版はmatz ruby 1.8.7で実行しているので1.9系ならもう少し高速化されるかもしれないし*1、C言語版は固定配列を使っているので、単純に比較はできないのだが……それにしても随分差があるものだ。
C言語を使えば処理速度が比較的高速になりやすいが、その分色々と苦労する。Rubyだと書きやすいが、何も考えずに書くと処理速度が遅くなってしまう。
昔はマシンが貧弱だったこともあり、C言語を使っても何も考えずに書けば処理速度が遅くなってしまったらしい。そこで重要な役割を果たしていたのが色々なアルゴリズムやデータ構造だったのだろう。
CPU単体の性能向上が頭打ちになり、マルチコア化の方向に進んでいる中で、改めて「アルゴリズムやデータ構造は重要だ！」ということだろうか。
まさか、それだから『アルゴリズムクイックリファレンス』が……？
*1:1.9系でも高速化される処理と高速化されない処理があるので……。
