練習問題 (6) - yamanetoshi's diary

ピアソン scheme 本の 3.3 節は継続になっている。そろそろ独習 scheme 三週間方面に戻るかどうするか。とりあえずペンディングにしている問題を。

練習問題 3.2.7 (factor の効率化)

サンプルの factor は以下のような定義。

(define factor
  (lambda (n)
    (let f ((n n) (i 2))
      (cond
       ((> i n) '())
       ((integer? (/ n i))
	(cons i (f (/ n i) i)))
       (else (f n (+ i 1)))))))

三点の問題が提起されている。

n 自身を除けば √n を超える n の因数は存在しない
因数を発見した際に除算 (/ n i) が二度実行されている
偶数の因数は 2 以外には存在しない

これらの問題を修正せよ、と。又、一番重要な問題はどれか、とある。

(and 類推で勘弁してもらう関数呼び出しと繰り返しはどっちがコスト高か微妙) を前提にさせて頂きますと

ループ脱出の条件の改善 (√n を超える因数は存在しない)
i の増分の改善 (偶数の因数は 2 のみ)
重複した演算の統合

って順かなぁ。ちなみに根拠はないです。類推です。

うーん。数学あまり得意じゃないだよなぁ。高校では数学Ｉまでしか勉強していません。単位修得云々じゃなくて勉強した、しないなレベルですが (大体高校には寝に行ってましたし)。
それを前提に言わせてもらうと (恥ずかしいなぁ)、例えば 31 という素数を素因数分解した結果は 1 * 31 ではない、とゆー事で良いのかなぁ。それとも 2 以上 (√n 未満) の素数で割れない場合の解としては例えば 31 だと 31 になるのかなぁ。

テキストにある実行例を前提に考えれば良いのか。

guile> (factor 12)
(2 2 3)
guile> (factor 3628800)
(2 2 2 2 2 2 2 2 3 3 3 3 5 5 7)
guile> (factor 9239)
(9239)
guile>

正解を導き出せてはいませんが経過を含めてしたコトを控えときます。まず試してみたのは √n を超えたら終了な判定の盛り込み

(define (p x) (display x) (newline))

(define (factor n)
  (let f ((n n) (i 2) (m (ceiling (sqrt n))))
    (define j (/ n i))

    (p (list "f " n i m)) ;; debug

    (cond
     ((or (> i n) (> i m)) '())
     ((integer? j)
      (cons i (f j i m)))
     (else (f n (+ i 1) m)))))

なんか一文字の変数が飛び交っておりまして可読性の低い事この上無ひ。あ、除算を一箇所で、というのも盛り込まれていますが微妙。このケースは素数の場合に空リストが返却されます。

次は機能はそのままで integer? な場合も末尾再帰にしてみた。

(define (p x) (display x) (newline))

(define (factor n)
  (let f ((n n) (i 2) (m (ceiling (sqrt n))) (l '()))
    (define j (/ n i))

    (p (list "f " n i m l)) ;; debug

    (cond
     ((or (> i n) (> i m)) l)
     ((integer? j)
      (f j i m (cons i l)))
     (else (f n (+ i 1) m l)))))

自分で書いときながらアレですが読みにくいなぁ。原因が他にあるとか??

次は素数で空リストが返却されないようにしてみたもの。

(define (p x) (display x) (newline))

(define (factor n)
  (let f ((n n) (i 2) (m (ceiling (sqrt n))) (l '()) (o n))
    (define j (/ n i))

    (p (list "f " n i m l)) ;; debug

    (cond
     ((or (> i n) (> i m))
      (if (null? l)
	  (list o)
	  (reverse l)))
     ((integer? j)
      (f j i m (cons i l) o))
     (else (f n (+ i 1) m l o)))))

なんと言えばよいのか分かりませんが、アルゴリズム的な工夫が皆無なのが駄目です。

最後は再帰手続きに渡す引数が多すぎなのでいくつか減らしてみたもの。

(define (p x) (display x) (newline))

(define (factor n)
  (let f ((n n) (i 2) (m (ceiling (sqrt n))) (l '()) (o n) (j 0))

    (p (list "f " n i m l o)) ;; debug

    (let g ((n n) (i i) (l l))
      (set! j (/ n i))

      (p (list "g " n i l))   ;; debug

      (cond
       ((or (> i n) (> i m))
	(if (null? l)
	    (list o)
	    (reverse l)))
       ((integer? j)
	(g j i (cons i l)))
       (else (g n (+ i 1) l))))))

最初のナニは名前付き let じゃなくても問題ないかも。

上記の解は「偶数の因数は 2 以外 (以下略)」な問題解決はしてません。解としては√n までの素数のリストを作って car で取りだしながら、な処理かなぁ。でもこれって処理対象の数値が大きくなってくると大変だと思う。偶数は取り除きます、というのは実装がわりと簡単にも思えますが ...

他の問題としては重複した因数の処理、かなぁ。例えば 8 の因数分解なナニでもう少し賢そうな方法がありそげな気もしますし、元の数値がでっかくなったら大変なコトになる、とも思う。方法とゆーかアルゴリズム自体に問題あり、とゆーか。

しかし、コードを見直してみるに微妙感満載スギ。