開発環境
- OS X Mavericks - Apple(OS)
- Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
- Scheme (プログラミング言語)
- MIT/GNU Scheme (処理系)
計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の5(レジスタ計算機での計算)、5.4(積極制御評価器)、5.4.4(評価の実行)、評価器の性能監視、問題 5.27.を解いてみる。
その他参考書籍
問題 5.27.
コード(BBEdit)
sample.scm
(load "./eval.scm") (load "./register.scm") (load "./eceval.scm") (start eceval)
入出力結果(Terminal, REPL(Read, Eval, Print, Loop))
$ scheme MIT/GNU Scheme running under MacOSX Type `^C' (control-C) followed by `H' to obtain information about interrupts. Copyright (C) 2011 Massachusetts Institute of Technology This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. Image saved on Saturday October 26, 2013 at 11:02:50 PM Release 9.1.1 || Microcode 15.3 || Runtime 15.7 || SF 4.41 || LIAR/C 4.118 Edwin 3.116 1 ]=> (load "./sample.scm") ;Loading "./sample.scm"... ; Loading "eval.scm"... done ; Loading "register.scm"... done ; Loading "eceval.scm"... done ;;; EC-Eval input: (define (factorial n) (if (= n 1) 1 (* (factorial (- n 1)) n))) (total-pushes = 3 maximum-depth = 3) ;;; EC-Eval value: ok ;;; EC-Eval input: (factorial 1) (total-pushes = 16 maximum-depth = 8) ;;; EC-Eval value: 1 ;;; EC-Eval input: (factorial 2) (total-pushes = 48 maximum-depth = 13) ;;; EC-Eval value: 2 ;;; EC-Eval input: (factorial 3) (total-pushes = 80 maximum-depth = 18) ;;; EC-Eval value: 6 ;;; EC-Eval input: (factorial 4) (total-pushes = 112 maximum-depth = 23) ;;; EC-Eval value: 24 ;;; EC-Eval input: (factorial 5) (total-pushes = 144 maximum-depth = 28) ;;; EC-Eval value: 120 ;;; EC-Eval input: End of input stream reached. Moriturus te saluto. $
反復的階乗については前問より。
最大深さ | プッシュ回数 | |
---|---|---|
再帰的階乗 | 3 + 5n | -16 + 32n |
反復的階乗 | 10 | 29 + 35n |
総括。
最大深さは評価器が計算を実行するのに使うスペース量の大きさで、プッシュの回数は必要な時間とよい相関関係があることから、nが十分に大きい値の場合、再帰的階乗は使うスペースの量が大きく、必要な時間は速い、反復的階乗は使うスペースは10で、速度は再帰的階乗と比べると遅くなる。
0 コメント:
コメントを投稿