id:eel3:20100502:1272798528 にて、似たようなアルゴリズムのプログラムでruby 1.8.7とC言語*1で実行速度を比べるという意味のない行為*2に手を染めた私。
その時「ruby 1.9.xならもう少し高速化されるかも」と書いた訳だが、この度Ruby-mswin32の1.9.2のバイナリを入手したので、今更ながらまた意味もなくruby 1.8.7と1.9.2で実行速度を比較してみることにした。
なおPC故障の為に前回とは再現環境が変わっている。
| PC | DELL Latitude E5400 |
|---|---|
| CPU | Intel(R) Core(TM)2 Duo P8600 @ 2.40GHz |
| Memory | DDR2 (PC2-6400) 2048MB*2 (Dual Channel) |
| OS | Windows XP Professional SP3 |
事前準備
実は以前のコードはruby 1.9.xでは正しく動作しない。文字リテラルの扱いが変わった為だ。元々のコードは、例えば「?A」がASCIIコードの65に解釈されるという前提で実装しているのだが、1.9.xでは文字列リテラル「'A'」に解釈されてしまう。
そこで1.8.7と1.9.2のどちらでも動作するように修正した。修正後のコードは以下の通り。
#!/usr/bin/ruby -w # #= Poderosaを開発している某社の入社試験。迷路の最短経路を求める。 # #author:: eel3 @ TRASH BOX #date:: 2010/10/27 # #== 関連情報 # - http://okajima.air-nifty.com/b/2010/01/post-abc6.html # #== 動作確認環境 # - ruby 1.8.7 (2010-08-16 patchlevel 302) [i386-mswin32] @ Windows XP Pro SP3 # - ruby 1.9.2p0 (2010-08-18 revision 29036) [i386-mswin32] @ Windows XP Pro SP3 # #=== 迷路 _maze_ の中から、値が _val_ である座標を返す（最初に発見したもののみ） def find_point(maze, val) x = nil y = maze.index do |line| x = line.index(val) x != nil end {:x => x, :y => y} end #=== 迷路のテキストを読み込む def load_maze maze = readlines.map {|line| line.chomp } start = find_point(maze, "S") goal = find_point(maze, "G") {:maze => maze, :start => start, :goal => goal} end #=== 最短経路のログ情報 $track_log = {:dump => nil, :hop => nil} #=== 迷路 _maze_ を文字列にダンプする def dump_out_maze(maze) maze.join("\n") end #=== 最短経路を探す（しらみつぶし） def track(maze, goal, pt, hop) # 迷路の外に出てしまったらNG return if (pt[:y] < 0 || pt[:y] >= maze.size) return if (pt[:x] < 0 || pt[:x] >= maze[pt[:y]].size) # 最短ホップ数に到達していたら、処理を打ち切る unless $track_log[:hop] == nil if hop >= $track_log[:hop] return end end # ゴールにたどり着いた場合は、ログを残しておく if pt[:x] == goal[:x] && pt[:y] == goal[:y] $track_log[:hop] = hop $track_log[:dump] = dump_out_maze(maze) return end # 未だゴールにたどり着かない場合 return unless maze[pt[:y]][pt[:x], 1] == "\s" # 壁か既に通った場所だった maze[pt[:y]][pt[:x]] = "$" track(maze, goal, {:x => pt[:x]-1, :y => pt[:y] }, hop+1) track(maze, goal, {:x => pt[:x], :y => pt[:y]+1}, hop+1) track(maze, goal, {:x => pt[:x]+1, :y => pt[:y] }, hop+1) track(maze, goal, {:x => pt[:x], :y => pt[:y]-1}, hop+1) maze[pt[:y]][pt[:x]] = "\s" end #=== メインルーチン def main maze = load_maze puts dump_out_maze(maze[:maze]) print 'start: '; p maze[:start] print 'goal : '; p maze[:goal] puts '' track(maze[:maze], maze[:goal], {:x => maze[:start][:x]-1, :y => maze[:start][:y] }, 1) track(maze[:maze], maze[:goal], {:x => maze[:start][:x], :y => maze[:start][:y]+1}, 1) track(maze[:maze], maze[:goal], {:x => maze[:start][:x]+1, :y => maze[:start][:y] }, 1) track(maze[:maze], maze[:goal], {:x => maze[:start][:x], :y => maze[:start][:y]-1}, 1) puts $track_log[:dump] print 'hop count: ', $track_log[:hop], "\n" end main
いざ実験
以下、Windows上でRuby-mswin32の1.8.7と1.9.2で比較したログ。
D:\tmp>bash
bash-2.04$ ruby.exe --version
ruby 1.8.7 (2010-08-16 patchlevel 302) [i386-mswin32]
bash-2.04$ time ruby.exe -w maze2.rb data.txt
**************************
*S* * *
* * * * ************* *
* * * ************ *
* * *
************** ***********
* *
** ***********************
* * G *
* * *********** * *
* * ******* * *
* * *
**************************
start: {:y=>1, :x=>1}
goal : {:y=>8, :x=>22}
**************************
*S* * $$$ *
*$* *$$*$ ************* *
*$* $$* $ ************ *
*$$$$* $$$$$$$ *
**************$***********
* $$$$$$$$$$$$$ *
**$***********************
* $$$ * $$$$$$$$$$$$$G *
* *$$$$$$*********** * *
* * ******* * *
* * *
**************************
hop count: 60
real 3m8.250s
user 0m0.015s
sys 0m0.015s
bash-2.04$ ruby1.9.2.exe --version
ruby 1.9.2p0 (2010-08-18 revision 29036) [i386-mswin32]
bash-2.04$ time ruby1.9.2.exe -w maze2.rb data.txt
**************************
*S* * *
* * * * ************* *
* * * ************ *
* * *
************** ***********
* *
** ***********************
* * G *
* * *********** * *
* * ******* * *
* * *
**************************
start: {:x=>1, :y=>1}
goal : {:x=>22, :y=>8}
**************************
*S* * $$$ *
*$* *$$*$ ************* *
*$* $$* $ ************ *
*$$$$* $$$$$$$ *
**************$***********
* $$$$$$$$$$$$$ *
**$***********************
* $$$ * $$$$$$$$$$$$$G *
* *$$$$$$*********** * *
* * ******* * *
* * *
**************************
hop count: 60
real 2m11.422s
user 0m0.015s
sys 0m0.015s
bash-2.04$ 1.8.7では3分8秒ぐらい、1.9.2では2分11秒ぐらい。1分近く速くなっている。
この結果は慎重に取り扱うべきだろう。処理系が高速化されたといっても、プログラムの処理の全てにおいて高速化される訳ではない。今回のプログラムでは実行時間が3分の2ぐらいに短縮されたが、処理内容によってはもっと短縮されるだろうし、その反対にそれ程短縮されないかもしれない。
とはいえ、確かに1.9は1.8よりも速くなっている。そう言っても差し支えないだろう。
まあしかし、処理系の高速化に頼る前に全体的なアルゴリズムとデータ構造を見直すのが王道な訳で……。
