4

私は SICP演習 2.28を行っていて、次のコードの奇妙な動作に出くわしました。

(define (fringe tree)
  (cond
    ((null? tree) '())
    ((not (pair? tree)) (list tree))
    (else (append (fringe (car tree)) (fringe (cdr tree))))))

(define (fringe-tail tree)
  (define (fringe-iter tree result)
    (cond
      ((null? tree) result)
      ((not (pair? tree)) (list tree))
      (else (fringe-iter (cdr tree) (append result (fringe-tail (car tree)))))))
  (fringe-iter tree '()))

(define x (make-list (expt 10 4) 4))
(time (fringe x))
(time (fringe-tail x))

通常fringeのバージョンは、反復バージョンよりもはるかに高速に実行されますfringe-tail。

cpu time: 4 real time: 2 gc time: 0

対。

cpu time: 1063 real time: 1071 gc time: 191

fringeループに最適化されているように見え、割り当てを回避しますが、fringe-tail実行ははるかに遅くなり、オブジェクトの作成と破棄に時間を費やします。

誰かが私にこれを説明できますか? （ラケット5.2.1を使用している場合に備えて）

4

2 に答える 2

6

最後の句を次のように置き換える場合：

(else (fringe-iter (cdr tree) (append (fringe-tail (car tree)) result)))

次に、それらはその入力に対して同じ速度で実行され、末尾再帰バージョンはより大きな入力に対してより高速になります。

問題は、前面にオンのフリンジを追加するナイーブバージョンよりもはるかに多くをトラバースして割り当てる、前面appendのオンのリストがはるかに長いことです。cdrcar

于 2012-07-16T17:07:15.603 に答える
4

指定されたコードには非テール位置のアプリケーションがあるため、その名前にもかかわらず、関数は反復的ではありません。:)

これを試して：

(define (fringe-tail tree)
  (define (iter tree k)
    (cond
      [(null? tree)
       (k '())]
      [(not (pair? tree)) 
       (k (list tree))]
      [else
       (iter (car tree)
             (lambda (v1)
               (iter (cdr tree)
                     (lambda (v2)
                       (k (append v1 v2))))))]))
  (iter tree (lambda (a-fringe) a-fringe)))

ただし、それでも最初の引数の長さと同じくらい高価なappendを使用します。フリンジとフリンジテールへの特定の縮退入力は、多くの計算上の問題を引き起こします。

そのような縮退した入力の例を挙げましょう：

(define (build-evil-struct n)
  (if (= n 0)
      (list 0)
      (list (list (build-evil-struct (sub1 n)))
            (build-evil-struct (sub1 n))
            (list n))))

(define evil-struct (build-evil-struct 20))

フリンジとフリンジイターの両方に適用すると、パフォーマンスが非常に悪くなります。私は、フリンジとフリンジテールについて、自分のシステムで数秒の計算時間を観察しています。これらのテストは、デバッグを無効にしてDrRacketで実行されました。デバッグを有効にすると、数値が大幅に異なります。

> (time (void (fringe evil-struct)))
cpu time: 2600 real time: 2602 gc time: 1212

> (time (void (fringe-tail evil-struct)))
cpu time: 4156 real time: 4155 gc time: 2740

これらの両方で、appendを使用すると、これらが特定の縮退入力の影響を受けやすくなります。フリンジの累積バージョンを作成すると、一定時間の短所操作を使用できるようになるため、そのコストを削減できます。

(define (fringe/acc tree)
  (define (iter tree acc)
    (cond [(null? tree)
           acc]
          [(not (pair? tree))
           (cons tree acc)]
          [else
           (iter (car tree) (iter (cdr tree) acc))]))
  (iter tree '()))

この構造でのフリンジ/accのパフォーマンスを見てみましょう。

> (time (void (fringe/acc evil-struct)))
cpu time: 272 real time: 274 gc time: 92

ずっといい！そして、ここですべての呼び出しを末尾呼び出しに変えるのは簡単なことです。

(define (fringe/acc/tail tree)
  (define (iter tree acc k)
    (cond [(null? tree)
           (k acc)]
          [(not (pair? tree))
           (k (cons tree acc))]
          [else
           (iter (cdr tree) acc
                 (lambda (v1)
                   (iter (car tree) v1 k)))]))
  (iter tree '() (lambda (v) v)))

> (time (void (fringe/acc/tail evil-struct)))
cpu time: 488 real time: 488 gc time: 280

この特定のケースでは、Racketのスタックの実装は、継続で表す具体化されたスタックよりも少し速いため、フリンジ/accはフリンジ/acc/tailよりも高速です。それでも、これらは両方とも、追加を回避するため、フリンジよりも大幅に優れています。

このすべてが言われています：この関数は、フラット化関数としてすでにラケットに組み込まれています！したがって、車輪の再発明をしたくない場合は、それを使用する方がよいでしょう。:)

于 2012-07-17T20:56:40.580 に答える