コードのこの部分を改善するには？

StackOverflow https://stackoverflow.com/questions/771013

  •  12-09-2019
  •  | 
  •  

質問

運動に

私のソリューションSICPの1.11 には、次のとおりです。

(define (f n)
  (if (< n 3)
   n
   (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3))))
   ))
予想されたように、

、のような（100°F）の評価は、長い時間を要します。 （再帰前述せず）は、このコードを改善し、及び/又はマルチコアボックスを利用する方法があった場合、私は思っていました。私は 'MIT-スキーム' を使用しています。

役に立ちましたか？

解決

私はSchemeでそれをコーディングする方法が最善わからないんだけど、このような何かに速度を改善するための一般的な手法を用いることであろう<のhref =「http://en.wikipedia.org/wiki/Memoization」 rel = "nofollowをnoreferrer">メモ化する。あなたは、F（P）を呼び出して、次回は、保存された結果はというというより、返されるように一言で言えば、アイデアは（おそらく見たすべてのpに対して、またはおそらく最後のn値）は、fの結果（p）をキャッシュすることです再計算。一般に、キャッシュは、戻り型へ（入力引数を表す）タプルから地図であろう。

他のヒント

演習では、二つの機能、「再帰的プロセスによって」fを計算し1、および「反復プロセスによって」fを計算している別のものを書くように指示します。あなたは再帰的なものをやりました。この機能は、あなたがにリンクされセクションの例で与えられたfib機能と非常に似ているので、あなたはfib関数の再帰的な反復の例を見て、これを理解することができる必要があります：

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

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

(define (fib-iter a b count)
  (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1))))

この場合、あなたはf-iter引数としてだけでなくa、b、およびcの引数を取るcount機能を定義します。

ここでf-iter関数です。 fib-iterする類似性に注目してください：

(define (f-iter a b c count)
  (if (= count 0)
      c
      (f-iter (+ a (* 2 b) (* 3 c)) a b (- count 1))))

そしてまたaとbしcと2を初期化1機能のパターンに続く、少し試行錯誤を通じて、私は0、そのfibを発見した、とaはそれぞれb、1、および0に初期化する必要があります。だから、fは次のようになります：

(define (f n)
  (f-iter 2 1 0 n))

注：f-iterはまだ再帰的なの機能のですが、理由スキームの仕組みで、それは反復のプロセスのように実行し、O(n)時間とO(1)空間で実行されます、あなたとは違って再帰関数が、再帰的プロセスだけではありませんコード。私は、この演習1.1の著者が探していたものであると考えています。

さて、あなたは私に言わせれば、数学者のように考えます。私はスキームを読んでいますが、フィボナッチ関数をコーディングするのではなく、再帰的に定義している場合、再発を解決し、閉じた形でそれを定義することはできません。フィボナッチ数列の場合は、閉じた形は、ここを例えば見つけることができます。それははるかに速くなります。

編集：おっと、あなたは再帰を取り除くの前述言っていることがわかりませんでした。その場合は、あなたのオプションは、はるかに限られています。

速いフィボナッチ機能を開発するには良いチュートリアルのこの記事を参照してください。関数型プログラミングで。これは、いくつかの局面において、スキームとは若干異なる共通LISPを使用しますが、あなたはそれをすることによって得ることができる必要があります。あなたの実装では、ファイルの先頭近くにbogo-fig機能と同等です。

別の言い方をするには：

末尾再帰を取得するには、再帰呼び出しは、手続きはありません非常に最後にする必要があります。

あなたの再帰呼び出しは、*と+の表現の中に埋め込まれたので、彼らは尾の呼び出しではありませんされている（*と+がの後にを評価されているので、再帰呼び出し。）

f-iterのジェレミーRutenのバージョンは末尾再帰ではなく反復（すなわち、それは、再帰的プロシージャのように見えるが、反復等価な限り効率的である。）

あなたが明示的に反復処理を行うことができますしかします：

(define (f n)
  (let iter
    ((a 2) (b 1) (c 0) (count n))
    (if (<= count 0)
      c
      (iter (+ a (* 2 b) (* 3 c)) a b (- count 1)))))

または

(define (f n)
  (do
    ((a 2 (+ a (* 2 b) (* 3 c)))
     (b 1 a)
     (c 0 b)
     (count n (- count 1)))
    ((<= count 0) c)))

その特定の運動は、末尾再帰を使用することによって解決することができる - の代わりに、（もし存在簡単な解決策の場合のように）各再帰呼び出しが戻るのを待っている、あなたは、このような方法で、パラメータに答えを蓄積することができます再帰はまさにそれが消費するスペースの面での繰り返しと同じように動作します。たとえばます：

(define (f n)
  (define (iter a b c count)
    (if (zero? count)
        c
        (iter (+ a (* 2 b) (* 3 c))
              a
              b
              (- count 1))))
  (if (< n 3)
      n
      (iter 2 1 0 n)))
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top