尾巴呼叫優化球拍

Question

我想學習一些功能性編程，並在計劃（球拍）中做項目歐拉問題讓我開始。我目前在problem 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)))))) 

我試圖找出如何使這個函數調用尾遞歸，但我不知道該怎麼做。我需要一些幫助，瞭解如何使用尾部呼叫優化來優化這樣的功能。

Answer 1

問題是，您一遍又一遍地重新計算相同的結果。 爲了解決這個問題，你不需要尾巴呼叫 - 你需要記住舊的 結果並返回它們而不用重新計算它們。這種技術被稱爲memoization。

這是一個解決方案：

#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) 

Answer 2

記憶化是單向的，另一個是使用不同的數據表示法。

我用表示爲一個矩陣的網格，或向量的向量。

然後，頂行的值設置爲1（因爲只有上的頂部邊緣的路徑。

該下一行療法第一行的是一個後，第二是的值條目列上一個，加的行中的條目或值之前，

遞歸每個行中的點，然後針對每行。

答案則是最後一個點在最後一行，當你完成遞歸時。

對於一個3x3柵格

1 1 1 
1 2 3 
1 3 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 - 沃克是尾調用。

使用RSR5兼容方案