12

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

(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)))]))

セクション31の下部で、HtDPは、自然再帰バージョンは、アキュムレータバージョンよりも高速ではないにしても、多くの場合高速であると述べていますが、その理由については述べていません。これについて読んだところ、答えは「末尾呼び出しの最適化/削除」のようですが、ウィキペディアの記事は、少なくともパフォーマンスに関しては、HtDPの発言と矛盾しているようです。なんでそうなの？

職場では、再帰的なスタイルの方が高速です。自宅では、アキュムレータスタイルの方が高速です。どのスタイルが一般的に好まれるのかを選択するための一般的なヒューリスティックはありませんか？アキュムレータスタイルの方がメモリ効率が高いことは理解していますが、議論をパフォーマンスだけに限定すると、少なくとも私にはわかりません。どちらがより良い選択です。

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

4

4 に答える 4

10

答えは、ラケット システムの詳細に依存します。これが私の見解です。

自然再帰バージョンとアキュムレータ バージョンの間には 2 つの大きな違いがあります。まず、アキュムレータ バージョンは、テール コールの最適化を可能にする方法で記述されます。これにより、作成する必要のあるスタック フレームが少なくなるため、アキュムレータ バージョンの高速化に役立ちます。しかし、これは、HtDP で説明されていることと、職場のコンピューターで見られたことの反対です。

もう 1 つの違いは、乗算の順序です。自然に再帰的なバージョンでは、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)))

またはアキュムレータバージョン。次に、自然に再帰的なアプローチを使用しているかアキュムレータベースのアプローチを使用しているかに関係なく、数値を昇順または降順で入力できます。

于 2011-01-21T12:37:48.337 に答える
2

Racket コンパイラの内部はわかりませんが、推測します。

一般に、テール コールは通常のコールよりもコストがかかります (これは .NET の場合に当てはまり、最大 7 倍遅くなります) が、場合によってはテール コールをなくすことができwhile(1) { ... }、最終的に C スタイルのループになるため、単純にローカル ジャンプを行うだけで、プロシージャ アプリケーションのオーバーヘッドを効果的に排除できます。

于 2011-01-19T09:24:24.680 に答える
0

上記の良い点がたくさんあります。あるべきものとそうでない理由の分析が大好きです。これこそが、Project Euler の成功の元となったものです。fixnums からのトリップが早すぎると、問題が発生する可能性があります。

数列は、大きいものから小さいものへ、またはその逆に掛けることができます。また、反復を直接かつ同様に行う「do」コマンドもあります。

(define (fact n)  (if (= n 1) 1 (* n (fact (- n 1)))))

(define (fact1 n) (do ([n n (- n 1)] [p 1 (* p n)]) ((= n 1) p)))

(define (fact2 n) (do ([i 1 (+ i 1)] [p 1 (* p i)]) ((< n i) p)))

(define (fact3 n) (let f ((n n) (p 1)) (if (= n 1) p (f (- n 1) (* p n)))))

(define (fact4 n) (let f ((i 1) (p 1)) (if (< n i) p (f (+ i 1) (* p i)))))
于 2011-02-28T05:24:41.780 に答える
0

優れたコンパイラは、再帰 fac を末尾再帰 fac に変換します。したがって、コンパイルされたコードに違いはないはずです。

于 2011-01-20T22:42:33.090 に答える