3

私はいくつかの関数型プログラミングを学ぼうとしており、スキーム（ラケット）でプロジェクトのオイラー問題を行って始めています。私は現在問題 15に取り組んでおり、ラティス内のパスの数を計算するための正しい関数があると思います。問題は、 gridSize の数が多い場合、関数の実行に非常に長い時間がかかることです。

(define uniqueTraverse
  (lambda (x y gridSize)
    (cond
      ((and (eq? x gridSize) (eq? y gridSize)) 1)
      ((eq? x gridSize) (uniqueTraverse x (+ y 1) gridSize))
      ((eq? y gridSize) (uniqueTraverse (+ x 1) y gridSize))
      (else (+ (uniqueTraverse (+ x 1) y gridSize)
               (uniqueTraverse x (+ y 1) gridSize))))))

この関数の末尾呼び出しを再帰的にする方法を見つけようとしていますが、その方法がわかりません。テールコールの最適化を使用して、このような関数を最適化することについて考える方法について、いくつかの助けが必要です。

4

2 に答える 2

6

問題は、同じ結果を何度も再計算することです。これを解決するには、末尾呼び出しは必要ありません。古い結果を記憶し、再計算せずに返す必要があります。この手法はメモ化と呼ばれます。

これは 1 つの解決策です。

#lang racket

(define old-results (make-hash))

(define uniqueTraverse
  (lambda (x y gridSize)
    (define old-result (hash-ref old-results (list x y) 'unknown))
    (cond 
      ; if the result is unknown, compute and remember it
      [(eq? old-result 'unknown)
       (define new-result
         (cond
           ((and (eq? x gridSize) (eq? y gridSize)) 1)
           ((eq? x gridSize) (uniqueTraverse x (+ y 1) gridSize))
           ((eq? y gridSize) (uniqueTraverse (+ x 1) y gridSize))
           (else (+ (uniqueTraverse (+ x 1) y gridSize)
                    (uniqueTraverse x (+ y 1) gridSize)))))
       (hash-set! old-results (list x y) new-result)
       new-result]
      ; otherwise just return the old result
      [else old-result])))

(uniqueTraverse 0 0 2)
于 2013-06-23T11:29:54.797 に答える
2

メモ化は 1 つの方法であり、別の方法は別のデータ表現を使用することです。

行列、またはベクトルのベクトルとして表されるグリッドを使用しました。

次に、一番上の行の値を 1 に設定します (上端にのみパスがあるためです。

その後、次の行または行の最初の行は 1 で、2 番目の行は 1 つ上の列のエントリの値に、その行の前のエントリまたは値を加えたものです。

行の各ポイントに対して再帰し、次に各行に対して再帰します。

答えは、再帰が完了したときの最後の行の最後のポイントです。

3x3 グリッドの場合

1 1 1
1 2 3
1 3 6

6

キーが非常に接近している場合 (連続、またはそれに近い場合)、ベクトル表現はハッシュよりもパフォーマンスが高くなります。

(define (make-lattice-point-square n)
(let ((lps (make-vector (+ n 1))))
 (let loop ((i 0))
  (if (> i n)
      lps
      (begin
          (vector-set! lps i (make-vector (+ n 1)))
          (loop (++ i)))))))

(define (lattice-ref lat x y)
;; where x is row, y is column thought it's not really important
(vector-ref (vector-ref lat y) x)) 

(define (lattice-set! lat x y value)
 (vector-set! (vector-ref lat y) x value))

;; paths through a point are equal the the paths through the above point,
;; plus the paths through the left, those along the top and left edges 
;; only have one possible path through them

(define (ways-exit-lattice n)
 (let ((lps (make-lattice-point-square n)))
  (letrec 
    ((helper 
      (lambda (x y)
    (if (or (= x 0) (= y 0))
             (lattice-set! lps x y 1)
         (lattice-set! lps x y
                (+ (lattice-ref lps (- x 1) y)
              (lattice-ref lps x (- y 1)))))))
     (lattice-walker
      (lambda (x y)
      (cond ((and (= x n) (= y n)) 
                 (begin (helper x y) (lattice-ref lps x y)))
                ((= y n) 
                 (begin 
                  (helper x y)
                  (lattice-walker (++ x) 0)))
                (else 
                 (begin
                  (helper x y)
                  (lattice-walker x (++ y))))))))
   (lattice-walker 0 0))))

latice-walker へのすべての呼び出しがテール コールであることに注意してください。

RSR5準拠のスキームを使用

于 2013-06-23T11:55:21.597 に答える