カテゴリー

最新の記事

最近のコメント

最近のトラックバック

月別アーカイブ

ブログ検索

RSSフィード

ブロとも申請フォーム

この人とブロともになる

スポンサーサイト

スポンサー広告
--.--.--
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

ベンチャーブログのランキングに参加しています。
下のバナーをクリックして応援していただけると嬉しいです。
にほんブログ村 ベンチャーブログへ

SICP Chapter 1を読了

Scheme/Gauche
2008.12.13
今週の火曜日(2008年12月9日)から「Structure and Interpretation of Computer Programs (SICP)」 を読み始めている。あらかじめ日本語訳の書籍もAmazonで購入しておいたのだが、英文の原著がネット上に全文掲載されているのを見つけたため、英語で読み進んでいる。英語のリーディングの訓練もできるので、一石二鳥だと思ったからだ。

で、昨日、5章構成のうちのChapter 1を読了した。実に面白い。Chapter 1のテーマはプロシジャの抽象化。すでに他のLISPチュートリアルや「プログラミング Gauche」、東京大学の「Scheme 演習」に掲載されていた内容もあったが、私にとって新鮮なネタも数多くあった。まだ足を踏み出したばかりの段階だが、この内容の濃さは素晴らしいの一言である。

例題としては様々な数学ネタが取り上げられていたが、私が特に面白いと思ったのが、フィボナッチ数列の計算法だった。「またフィボナッチ数列かい?」などとおっしゃるなかれ。アルゴリズムによって必要なリソースが大幅に変わってくるということが、非常に明確な形で示されているのだ。

フィボナッチ数列とは何かについては前回触れているので省略。これをごく普通にコード化すると、以下のようになる。(これも前回掲載したが、こちらは再掲させていただく)

(define (fib n)
  (cond ((= n 1) 1)
     ((= n 2) 1)
     (else (+ (fib (- n 1)) (fib (- n 2))))))


さて、このような「再帰型」アルゴリズムの場合、フィボナッチ数の計算量はnの二乗に比例する形で大きくなるらしい。そのためPentium 4/2.4GHzのマシンでは、n=35で2.47秒、n=40で28秒かかるようになり、もはやそれ以上の値では計算したくなくなるのである。

しかしこれを「再帰型」ではなく「反復型」に置き換えると、処理量は一気に減り、nに比例するようになる。

(define (fib n)
 (define (fib-iter a b count)
  (if (< count 2)
     a
     (fib-iter (+ b a) a (- count 1))))
 (fib-iter 1 0 n))


やっていることは、fibの中に反復用の関数を定義し、以下のように処理を進めるように変更しただけである。

Step.1
まず b = 0, a = 1 とする。これは n = 0, n = 1 の時のフィボナッチ数である。

Step.2
与えられたnをカウンター(count)にセット。

Step.3
カウンターの値が2より小さければ、aの値を答えとする。

Step.4
もしカウンターが2以上であれば、以下の処理を行う。

a ← b + a
b ← a
count ← count - 1

Step.5
上記のStep.3~4を繰り返す。

これで n = 35 の場合を計算すると、計算時間は1ミリ秒未満となり、time関数では計測不能になる。ちなみに n = 100000(十万)で、ようやく計算時間が3.585秒となる。つまり計算方法をちょこっと変えるだけで、莫大な効率化を達成できるわけである。

とはいえ、このレベルのリファクタリングは難しいものではない。他のLISP本や「プログラミング Gauche」でも紹介されている。本当に面白いのはここからだ。

実はさらに処理をスケールできる方法がある。それが次の方法だ。基本的な考え方はChapter 1のExercise 1.19に掲載されているのだが、その内容をここで簡単に紹介しておく。

Step.1
まず次のような変換を考える。

a ← bq + aq + ap
b ← bp + aq

なぜこのような式が出てくるのかは、私に聞かないで欲しい。ひょっとすると群論の基本的な知識なのかもしれないが、大学で群論に挫折した私には正直いってよくわからない。それはともかくこの「飛躍」を行うことで、フィボナッチ数の計算をより抽象化できるのである。

フィボナッチ数の計算を行う場合には、p = 0、q = 1 とすればいい。そうすれば上記の式は

a ← b + a
b ← a

となる。

Step.2
上記の変換を「Tpq」と定義しよう。この変換を2回行ったのと等価な変換を「Tp'q'」とすると(つまり「Tp'q'=(Tpq)^2」ということ)、p、q、p'、q'の間には次の関係が成立する。(この関係は計算してみればすぐにわかる)

p' = p^2 + q^2
q' = 2pq + q^2

Step.3
ここまで導けば、ある条件ではTpqではなく、Tp'q'を使うことで、処理量を一気に半分にできることがわかる。つまり「Tpqを実行する回数nが偶数回である」場合には、Tpqをn回実行する代わりに、Tp'q'をn/2回実行することで、目的の値が得られるのだ。n/2 が偶数なら、(Tp'q')^2を求めることで、さらに処理量を半分にできる。後はこれを、nが奇数になるまで繰り返せばいい。

つまり、nが偶数の場合

p ← p^2 + q^2
q ← 2pq + q^2
n ← n/2

を実行するのである。

Step.4
それではnが奇数になったら?その場合は「現時点の」p、qを使い、Tpqを適用した上で、n=n-1とすればいい。なおnが奇数の場合、n=n-1を行った時点で偶数になる。

Step.5
上記のStep.3~4を、nが0になるまで適宜実行する。

これらの処理を組み合わせると、次のような関数が書ける。

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


これを使ってn=100000(十万)の値を求めると、0.237秒で処理が終わる。つまり単なる反復型より、1桁速くなるわけだ。

ちなみにこのアルゴリズムでは、処理量は log(n)に比例するようになるという。ということは、nが大きいほど効果が大きいというわけである。

n=百万にすると、第3のコードは27秒で答えを出した。反復型では460秒だった。n=十万の時よりは若干差が広がっている。再帰型は気が遠くなりそうなので試していない。

処理内容によってはアルゴリズムをちょっと工夫するだけで、これだけスケーラビリティが変わってしまうのである。再帰型と比べれば、3つ目のコードは2万5000倍もスケールしている。これは本当に面白いと思う。
スポンサーサイト

ベンチャーブログのランキングに参加しています。
下のバナーをクリックして応援していただけると嬉しいです。
にほんブログ村 ベンチャーブログへ

FC2Ad

相続 会社設立

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。