Forthでハノイの塔
Forthを触ってみたくなったので、試しにハノイの塔を実装してみた。
ついでにcommon lispとC++でも実装し、Forthとの処理速度を比較してみた。
※ common lispの処理系にはSBCLを、Forthの処理系にはgforth及びVFX-Forthを使用した
Forthでの実装(gforth)
gforthはバイトコードタイプのForth実装。
\ gforth-0.7.0 (linux/64bit) \ Forth版のハノイの塔 variable cnt \ 再帰呼び出しの数をカウント用の変数 : hanoi-print ( to from -- to from ) cr 2dup . ." -> " . ; : hanoi-impl ( to tmp from level -- to tmp from ) dup >r 0> if rot swap r@ 1- recurse ( tmp to from ) cnt @ 1+ cnt ! ( hanoi-print 計時用にコメントアウト ) ( tmp to from ) rot r@ 1- recurse ( to from tmp ) swap ( to tmp from ) then r> drop ; : hanoi ( to tmp from level -- ) 0 cnt ! \ カウント初期化 hanoi-impl drop drop drop cr ." count: " cnt @ . cr ; \ 再帰数表示
hanoi-printワードをコメントアウトしなかった場合の実行結果。
$ gforth # shellからgforthコマンドを起動 1 2 3 3 hanoi 3 -> 1 3 -> 2 1 -> 2 3 -> 1 2 -> 3 2 -> 1 3 -> 1 count: 7 ok
gforthでの計時。
$ gforth-fast # 高速版のコマンドを使用する \ 計時用のワードを定義 : time ( word_pointer -- ) utime drop >r execute utime drop r> - 1000 / ." elapsed " . ." ms " cr ; \ 計時 1 2 3 25 ' hanoi time count: 33554431 elapsed 3359 ms \ 結果: 3.34秒 ok
Forthでの実装(VFX-Forth)
VFX-ForthはネイティブコードタイプのForth実装(? 不確か)。
ワードの定義はgforthのそれと同様なので計時部分だけ掲載。
# VFX-Forth-4.43 (linux/32bit ?) $ vfxlin \ 計時用のワードを定義 : time ( word_pointer -- ) ticks >r execute ticks r> - ." elapsed " . ." ms " cr ; \ 計時 1 2 3 25 ' hanoi time count: 33554431 elapsed 190 ms \ 結果: 0.19秒 ok
common lispでの実装(SBCL)
実装及び計時結果。
;;;; sbcl-1.0.49 (linux/64bit) ;; 関数定義 (defvar *count*) (defun hanoi-impl (from tmp to level) (declare (fixnum level) (optimize (speed 3) (safety 0) (debug 0)) (sb-ext:unmuffle-conditions sb-ext:compiler-note)) (when (plusp level) (hanoi-impl from to tmp (1- level)) (incf (the fixnum *count*)) ; (format t "~&~a => ~a~%" from to) (hanoi-impl tmp from to (1- level)))) (defun hanoi (from tmp to level) (let ((*count* 0)) (hanoi-impl from tmp to level) `(:count ,*count*))) ;; 計時 (time (hanoi 'a 'b 'c 25)) Evaluation took: 0.403 seconds of real time ; 結果: 0.40秒 0.390000 seconds of total run time (0.390000 user, 0.000000 system) 96.77% CPU 804,338,623 processor cycles 0 bytes consed (:COUNT 33554431)
C++での実装(GCC)
/* ファイル名: hanoi.cc * コンパイル: g++ -O3 -o hanoi hanoi.cc * バージョン: gcc-4.4.3 (linux/64bit) */ #include <iostream> int count; void hanoi(int from, int tmp, int to, int level) { if(level > 0) { hanoi(from, to, tmp, level-1); count++; hanoi(tmp, from, to, level-1); } } int main() { count=0; hanoi(1, 2, 3, 25); std::cout << "count: " << count << std::endl; return 0; }
コンパイル & 実行。
$ g++ -O3 -o hanoi hanoi.cc $ time ./hanoi count: 33554431 real 0m0.168s # 結果: 0.17秒 user 0m0.170s sys 0m0.000s
ハノイの塔での処理速度比較した結果は、C++(0.17秒)、Forth-VFX(0.20秒)、lisp(0.40秒)、Forth-gforth(3.34秒)、の順となった。
Forthも処理系によっては、C++と同程度の速度がでるみたい。※ 雑な比較なので正確なところは分からないけど・・・
おまけ: 末尾再帰 => ループ変換 版
末尾再帰部分を手動でループに変換したソースコードも書いてみたので、載せておく。
variable cnt : 3dup ( a b c -- a b c a b c ) dup 2over rot ; : hanoi-impl ( to tmp from level -- ) begin dup >r 0> while rot swap 3dup r@ 1- recurse ( tmp to from ) cnt @ 1+ cnt ! rot r> 1- ( to from tmp ) repeat r> drop drop drop drop ; : hanoi ( to tmp from level -- ) 0 cnt ! hanoi-impl cr ." count: " cnt @ . cr ;
この変換によって、gforthの場合は処理時間が短く(2.32秒)なったけど、VFX-Forthでは逆に長く(0.35秒)なってしまった。
