タグ : Emacs

SICP reading #6 [1.2.4] べき乗

wp-emacsという最強の助っ人が現れたので、ブログの投稿作業自体が楽しくなってきた。
wp-emacsについては別なエントリにあげるとして、とりあえずsicpの問題とくよ!

q1.16

sicp勉強会で、問題を読んで即実装に取りかかって小一時間ハマってしまった問題。
逐次平方で対数的ステップ数の反復的な羃乗プロセスを実装しろとのこと。(長!

逐次平方で対数的ステップ数っていうのは、例題であったように2の羃乗の指数の場合指数を1/2した結果を2乗すれば乗算のステップが半分になるという上手い方法。
普通に再帰で実装すれば羃乗は以下のように

(define (expt b n)
  (if (= n 0)
      1
      (* b (expt b (- n 1)))))

これは、ステップ/スペース数ともにO(n)な実装。

逐次平方を用いた再帰的羃乗プロセスは

(define (square n) (* n n))
(define (fast-expt-recr b n)
  (cond ((= n 0) 1)
        ((even? n) (square (fast-expt b (/ n 2))))
        (else (* b (fast-expt b (- n 1))))))

これだと、指数が2の乗数の場合に最小の計算量が見込め、O(log(n))となる。

ただ、再帰的な実装のためスペース数もO(log(n))となる。
で、q1.16ではそれを反復的に実装しろとのこと。

ハマった

問題を読んで感覚的に実装すると、以下のようなコードに

(define (fast-expt-iter b n)
  (define (iter b n a)
    (cond ((= n 0) a)
          ((even? n) (iter b (/ n 2) (square (* b a))))
          (else (iter b (- n 1) (* b a)))))
  (iter b n 1))

指数nが偶数の時引数としてのnを1/2にするのは正しいけれど底bと結果aが間違ってる。
結果を一回きり2乗して指数を半分にしているため、実際の羃乗よりはるかに小さい値となる。

で、逐次平方で反復的な羃乗のプロセスの生成具合を書き下してみると、指数を半分にしたときに底を2倍すればよいことに気付いた(簡単だよね!最初っから書いておけば。。)

以下、正しい実装。

(define (fast-expt-iter b n)
  (define (iter b n a)
    (cond ((= n 0) a) ;;偶数なら底を2乗 and 指数を/2
          ((even? n) (iter (square b) (/ n 2) a))
          (else (iter b (- n 1) (* b a)))))
  (iter b n 1))

以下、動作確認

(use srfi-1)
(map (lambda (n) (print 2 "^" n "=" (fast-expt-iter 2 n))) (iota 11 0))
;;実行結果
gosh> 2^0=1
2^1=2
2^2=4
2^3=8
2^4=16
2^5=32
2^6=64
2^7=128
2^8=256
2^9=512
2^10=1024
(#<undef> #<undef> #<undef> #<undef> #<undef> #<undef> #<undef> #<undef> #<undef> #<unde\f> #<undef>)
gosh>

上では(というか今ままで全部)、実装と同一ファイルに直接テストコードを埋め込んで確認している。
勉強会を一緒にしてるid:yamanetoshiさんからgauche.testの使い方を教えてもらったので、使ってみた。

gauche.testでのテスト

(use gauche.test)
(add-load-path ".")
(load "q-1-16")

(test-start "expt")
(test-section "expt")
(test* "2^0"
       1
       (fast-expt-iter 2 0))
(test* "2^1"
       2
       (fast-expt-iter 2 1))
(test* "2^2"
       4
       (fast-expt-iter 2 2))
(test* "2^3"
       8
       (fast-expt-iter 2 3))
(test* "2^4"
       16
       (fast-expt-iter 2 4))
(test* "2^5"
       32
       (fast-expt-iter 2 5))
(test* "2^6"
       64
       (fast-expt-iter 2 6))
(test* "2^7"
       128
       (fast-expt-iter 2 7))
(test* "2^8"
       256
       (fast-expt-iter 2 8))
(test* "2^9"
       512
       (fast-expt-iter 2 9))
(test* "2^10"
       1024
       (fast-expt-iter 2 10))

(test-end)
で、実行
SHINYA% gosh q-1-16-test.scm
Testing expt ...
<expt>-------------------------------------------------------------------------
test 2^0, expects 1 ==> ok
test 2^1, expects 2 ==> ok
test 2^2, expects 4 ==> ok
test 2^3, expects 8 ==> ok
test 2^4, expects 16 ==> ok
test 2^5, expects 32 ==> ok
test 2^6, expects 64 ==> ok
test 2^7, expects 128 ==> ok
test 2^8, expects 256 ==> ok
test 2^9, expects 512 ==> ok
test 2^10, expects 1024 ==> ok
passed.

うぉぉ、楽しい!passed!

q1.17

羃乗の次は乗算を対数ステップ数で実装しろという問題。
羃乗の場合は指数を1/2して平方をとっていたから逐次平方、ということはこの場合は逐次2倍?

以下、線形/対数オーダーなそれぞれの実装

;;線形オーダーな実装
(define (* a b)
  (if (= b 0)
      0
      (+ a (* a (- b 1)))))

(define (double n) (+ n n))
(define (halve  n) (/ n 2))
;;対数オーダーな実装
(define (fast-* a b)
  (cond ((= b 0) 0)
        ((even? b) (fast-* (double a) (halve b)))
        (else (+ a (fast-* a (- b 1))))))

gauche profiler

さっきの問題でもスルーしてたけど、実際に対数的かどうかgaucheのprofilerを使って確認してみた。

;;profiler便利
(profiler-reset)
(profiler-start)
(fast-* 2 0)
(profiler-show)
;;以下、実行結果(抜粋)
gosh> Profiler statistics (total 0 samples, 0.0 seconds)
                                                    num    time/    total
Name                                                calls  call(ms) samples
---------------------------------------------------+------+-------+-----------
fast-*                                                  12  0.0000     0(  0%)
even?                                                   11  0.0000     0(  0%)
double                                                  10  0.0000     0(  0%)
halve                                                   10  0.0000     0(  0%)

実際にはprofiler-showでの結果はgaucheの内部っぽい関数(compiled-code-emit1i!とか)も拾ってくるけど、ここでは自分で実装した関数の結果のみ表示。

そのまま実装すると1024回の加算が必要だけどfast-*の呼び出しは12回。これは、最初の1回目の呼び出しとさらにbが0になったとき0を返す分の呼び出しが1回あるので10+2=12。
bが1になった時そのままaを返せば1回分呼び出しが減るけど、(fast-* 2 0)のとき0を返してほしかったのでこう実装しました。

q1.18

q1.16,q1,17の復習問題。ここまで復習すると逐次平方的な考えはバッチリ。

以下、実装

(define (double n) (+ n n))
(define (halve  n) (/ n 2))

(define (fast-* a b)
 (let i ((a a) (b b) (r 0))
   (cond ((= b 0) r)
         ((even? b) (i (double a) (halve b) r))
         (else (i a (- b 1) (+ r a))))))

試験ではmapの手続きにさらにmapを仕込んで9×9の掛け算を生成。

試験(test & profile)

;;試験
(let ((1to9 '(1 2 3 4 5 6 7 8 9)))
  (map (lambda (a)
         (map (lambda (b) (if (= (fast-* a b) (* a b))
                              (* a b) 'error))
              1to9)) 1to9))
;;even?の数で把握
(profiler-reset)
(profiler-start)
(fast-* 10 2048)
(profiler-show)
;;以下、実行結果(test)
gosh> ((1 2 3 4 5 6 7 8 9) (2 4 6 8 10 12 14 16 18) (3 6 9 12 15 18 21 24 27) (4 8 12 16\
 20 24 28 32 36) (5 10 15 20 25 30 35 40 45) (6 12 18 24 30 36 42 48 54) (7 14 21 28 35 \
42 49 56 63) (8 16 24 32 40 48 56 64 72) (9 18 27 36 45 54 63 72 81))
;;profile
gosh> Profiler statistics (total 0 samples, 0.0 seconds)
                                                    num    time/    total
Name                                                calls  call(ms) samples
---------------------------------------------------+------+-------+-----------
even?                                                   12  0.0000     0(  0%)
double                                                  11  0.0000     0(  0%)
halve                                                   11  0.0000     0(  0%)

うーん、素晴らしい。emacs & scheme最高!

q1.19

フィボナッチ数を求めるプロセスを、変換Tの特殊な場合としてTを

みたいに定義している。
p=0,q=1の場合は確かに

となるね。Tに名前はついてるのかな?(誰か教えて

この問題ではT_p_qによる2回変換をT_p’_q’で表せと問うている。実際に計算を行なってp’,q’をp,qで表せば良いので、結構簡単。

手書きで計算したので、画像up。(文字が汚いのは仕様です。

手計算で

手計算で

計算結果をそのままコードに落とし込むと

(define (fib n)
  (fib-iter 1 0 0 1 n))

(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
         (fib-iter a
                   b
                   (+ (* p p) (* q q))
                   (* q (+ q (* 2 p)))
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

(map fib '(1 2 3 4 5 6 7 8 9 10))

(profiler-reset)
(profiler-start)
(fib 2048)
(profiler-show)

終了!

まとめ?

ここ最近、emacsの操作方法が色々分かってきたので作業効率が異常なまでに良くなってきている。
wp-emacsとかtwittering-modeとか、emacsは便利なプラグインもさることながら基本操作が半端無く充実しているなー。いずれエントリにもまとめてみたいかも。オライリーのemacs本読もっと。

入門 GNU Emacs 第3版
計算機プログラムの構造と解釈

Ruby on Rails インストール & emacs-railsの設定

アルバイト先の出勤表 作成/管理を行なうページを作成することに。

Railsで作成しよう!とのことで、Railsの開発環境を整えてみた。

Railsのインストール

と思ったら、すでにRailsは入っていた。

SHINYA% which rails
/usr/bin/rails
SHINYA% rails -v
Rails 2.3.2

とりあえず、RailsはOK。

emacs-railsの設定

開発マシンは、先輩がたてているサーバで行なうことに。端末上での開発がメインとなるので、emacs-railsはかなり便利とのことで設定。

http://d.hatena.ne.jp/higepon/20061222/1166774270を参考に、必要な.el一式をそろえて、emacsに読み込ませる。

これで、モデル-ビュー-コントローラ間の対応/関連するファイル移動がかなり楽に。(これは便利)

ちょっと問題が

Rails 2.0からだと、ビューの定義ファイル拡張子が*.html.erbになっているため、コントローラ-ビュー間の移動で対応するビューが検出されない。(*.html.erbには未対応)

自分の落としてきたのemacs-rails(0.5.99.5)では*.html.erb形式に対応していない様子。

対応していないといっても、emacs-rails/rails.elに*.html.erbをテンプレート拡張子として追加するだけでOKだった。

emacs-rails/rails.elの149行めの

(defvar rails-templates-list '("erb" "rhtml" "rxml" "rjs" "haml" "liquid"))

にhtml.erbを追加↓すればOK

(defvar rails-templates-list '("html.erb" "erb" "rhtml" "rxml" "rjs" "haml" "liquid"))

Railsでちょっと開発してみた

Railsに詳しい先輩と、ペアプログラミングで開発をちょっと進めてみた。

出勤表の管理ということで、とりあえずメンバーのモデルとスケジュールのモデルを作成。

scaffold,CRUDってなんぞ?って感じだったけど、実際に開発を進めていくともの凄く簡単に日程管理の下地が出来た。SQLとか意識しなくても、簡単にデータベース/モデルが定義できるって素敵。

また、ペアプログラミングはサーバ上で同一アカウントでログインしている先輩と、screenを共有して開発した。曰く、「screen と skypeがあればどこでも勉強会できる」とのこと^^

これから

とりあえず、大学図書館でRails関連の本を借りてきた。

開発メインでRailsを勉強していこう。


(defvar rails-templates-list ‘(“html.erb” “erb” “rhtml” “rxml” “rjs” “haml” “liquid”))↓
 
Better Tag Cloud