再帰とアキュムレータのスタイルの比較

Question

与えられた数の階乗を計算する2つの関数があります。最初のもの、!は、アキュムレータスタイルを使用します。第2のfactは、自然再帰を使用します。第31、HtDPの下部に

(define (! n0) 
    (local (;; accumulator is the product of all natural numbers in [n0, n) 
     (define (!-a n accumulator) 
     (cond 
      [(zero? n) accumulator] 
      [else (!-a (sub1 n) (* n accumulator))]))) 
    (!-a n0 1))) 

と

(define (fact n) 
    (cond 
    [(= 0 n) 1] 
    [else (* n (fact (- n 1)))])) 

は自然に再帰バージョンは、多くの場合のように高速であれば、アキュムレータのバージョンよりも高速ではありませんが、理由を述べていないと述べています。私はこれについていくつかの読書をしましたが、答えは'tail call optimization/elimination'だと思われますが、Wikipediaの記事は、少なくともパフォーマンスに関してHtDPが言っていることとは異なると思われます。なぜこれはそうですか？

---

再帰的なスタイルが高速です。自宅では、アキュムレータスタイルがより高速です。どのスタイルが一般的に好まれるかについての選択を導く一般的なヒューリスティックはありませんか？アキュムレータスタイルはメモリ効率が良いと私は理解していますが、ディスカッションをパフォーマンスだけに限定すれば、少なくとも私にとってはより良い選択であることは不明です。

---

私はもう少しこのことについて考えてきた、と一般的なケースアキュムレータスタイルの再帰の優位性にWikipediaの記事を左右する必要があります。スタック/ヒープ領域の使用量を減らすだけでなく、メモリアクセスは常にレジスタアクセスの背後にあるため、マルチコアがここに来るとより明白になります。それでも、HtDPは、すべてのケースで実際のテストが必要であることを証明しています。

Answer 1

答えは、ラケットシステムの詳細によって異なります。ここにそれを取ります。

自然再帰バージョンとアキュムレータバージョンの主な違いは2つあります。第1に、アキュムレータバージョンは、テールコール最適化を可能にする方法で書き込まれる。これにより、作成する必要のあるスタックフレームが少なくてすむため、アキュムレータのバージョンを高速化できます。しかし、それはHtDPで議論されていることの反対であり、あなたの仕事用コンピュータで見たことです。

他の違いは乗算の順番です。当然再帰バージョン倍数昇順に1から20までの数字、すなわち

ある

((((1 * 2) * 3) * … * 19) * 20) 

アキュムレータバージョンは、これらが同じである、すなわち数学的

((((20 * 19) * 18) * … * 2) * 1) 

で、降順で同じ数字を乗算2つの階乗関数によって同じ結果が得られます。それにもかかわらず、この違いは重要です。特に、任意の中間乗算において、中間結果は、前者の計算の場合よりも後者の計算の方が大きい。

20の階乗は大きな数字です。 32ビットの整数には収まらない。つまり、ラケットは答えを表現するために任意の長さの整数（「bignum」）と中間結果の一部を使用する必要があります。 bignumを含む乗算を含む任意の精度演算は、固定精度演算よりも遅い。

アキュムレータバージョンの中間結果は常に自然再帰バージョンよりも大きいため、アキュムレータバージョンでは再帰バージョンよりも前のbignumが必要になります。要するに、両方のバージョンが同じ数の乗算を必要とするが、アキュムレータバージョンは、より任意の精度の乗算を必要とする。これはアキュムレータのバージョンを遅くします。明らかに、算術演算の追加コストは、節約がスタックフレームの数を減らすことよりも重要である。

なぜ、同じ傾向が自宅のコンピュータに表示されないのですか？あなたはIntel iMacだと言ったので、おそらく64ビットシステムです。 20時！それは64ビット整数に収まるものに比べて小さいので、家庭用コンピュータは任意の精度演算を行わず、順序は関係ありません。 HtDPは、仕事用コンピュータ上のWindows XPと同様に、32ビットシステムを使用するほど十分に古いものです。

番号のリストの積を計算する関数になるの違いを探るために、より便利な、どちらか

(define (product numlist) 
    (* (car numlist) (product (cdr numlist))) 

またはアキュムレータバージョン。あなたは、自然に再帰的なアプローチかアキュムレータベースのアプローチを使用しているかどうかにかかわらず、昇順または降順の数字を入力することができます。

Answer 2

私はラケットコンパイラの内部を知らないが、私は推測するだろう。

テールコールは通常、通常のコールよりも高価です（これは.NETではtrue、最大7倍遅くなります）が、テールコールを削除して終了すると、while(1) { ... } Cスタイルのループになります。したがって、追加の呼び出しは不要で、ローカルジャンプだけで、プロシージャのアプリケーションオーバーヘッドを効果的に排除します。

Answer 3

良いコンパイラは再帰的なfacを尾の再帰的なものに変えます。だから、コンパイルされたコードに違いはないはずです。

Answer 4

上記の多くの良い点があります。私は何がなぜ必要でないのか、なぜそうではないのかを分析するのが大好きです。それがProject Eulerの成功の材料です。あまりに早くfixnumからの旅行に問題があるかもしれません。

数字のシーケンスは、大きいものから小さなものへ、またはその逆に掛けることができます。私たちはまた、直接的にも同様に反復を行うdoコマンドを持っています。

（（実際n）を定義する（IF（= N 1）1（* N（事実（N - 1））））） - N

（（fact1 nを定義する）（（[NN（を行います1）] [p 1（* pn）]）（（n 1）p）））

（do（[i 1（+ i 1）] [p 1 （n 1）p）f（n 1）p）f（（n 1）p））（（< ni）p）））

（p 1）（p 1））（if（< ni）p（f（+ i 1）（* pi））） ））