階段クイズのつづき

id:hyukiさんよりコメントを頂きました。

段数が多くなったときは、二つの解法に違いは生じるでしょうか?

階段クイズ – 週記くらい%28BTS開発記%29のコメント欄

結城さん直々にクイズその弍を貰いました。ありがとうございます。

力技版を answer-1 という関数名で定義して、模範解答版を answer-2 という関数名で定義しました。

結果計測するまでもなく、力技版は、階段を40段にしたくらいで相当遅くなっていました。模範解答版は、まだ余裕がありました。

以下、40段の結果

CL-USER> (compile 'answer-1)
ANSWER-1
NIL
NIL
CL-USER> (compile 'answer-2)
ANSWER-2
NIL
NIL
CL-USER> (time (answer-1 40))
Real time: 112.9799 sec.
Run time: 110.846924 sec.
Space: 2380846872 Bytes
GC: 3429, GC time: 16.581068 sec.
165580141
CL-USER> (time (answer-2 40))
Real time: 19.153519 sec.
Run time: 18.693169 sec.
Space: 192 Bytes
165580141
CL-USER>

やはり、力技版は全ての組合せを試している(40階層のツリーをくまなく渡り歩いている)ので計算量が増えていることから、処理時間が長くなっているのはわかるんですが、Spaceが異常に多い(2.3G!)のは、letのレキシカル環境がlabelsで再帰のたびにコピーされまくるからかな?ちょっと今の理解力では解明できないので、また調べてみようと思います。

模範回答版は、自分で階段の登り方のパターン数を数えるのではなく、1段の場合と2段の場合に帰結するようにしているので、最低限の計算量で答が求められる様子。末尾再帰ではないけど、再帰自体の回数も力技版とは比にならないくらい少ないはずです。

しかし、力技版がスペースを使いまくっているのをどうやって調べればいいんだろう。。

一応、テストに使った関数を貼っておきます。

;力技版
(defun answer-1 (step-count)
(let ((way-count 0))
(labels ((rec (n)
(if (zerop n)
(incf way-count) ;reached.
(loop for i from 1 to 2
until (< n i)
do (rec (- n i))))))
(rec step-count)
way-count)))
;模範解答版
(defun answer-2 (step-count)
(or (plusp step-count)
(error 'step-count-msut-plus-value))
(case step-count
(1 1)
(2 2)
(otherwise (+ (answer-2 (- step-count 2))
(answer-2 (- step-count 1))))))

3件のコメント

  • 興味深いですね…。
    段数を1段ずつ増やして、スピードやスペースがどういう変化をするかグラフを描いてみると、原因の一端がわかるかもしれませんね。
    (リニアに増えているのか、二乗なのか、指数的に増えているのかという意味)

    結城が最初考えたのは、answer-2のほうが高速なんだけれど、段数を極端に大きくするとスタックオーバーフロー。というシナリオでした。

  • ちなみに、メモ化(memoize)するとさらにさらに高速になりそうです。

  • > 段数を1段ずつ増やして、スピードやスペースがどういう変化をするかグラフを描いてみると、原因の一端がわかるかもしれませんね。

    試してみます。こうゆう分析を自分でやるのは、初めてかもしれないですが、面白いですね。

    > ちなみに、メモ化(memoize)するとさらにさらに高速になりそうです。
    力技版があまりにも遅かったので、メモ化しようとしたんですが、今の構造では、メモ化できなかった(トップまで到達した地点で、到達したことしかわからないので)ので、諦めました。模範解答版は、少し効果があるかもしれませんね。こちらも試してみたいです。

コメントする

メールアドレスが公開されることはありません。 が付いている欄は必須項目です


The reCAPTCHA verification period has expired. Please reload the page.

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください