尾调用优化Racket

Question

我正在尝试学习一些函数式编程，并在scheme（racket）中解决project euler问题以帮助我入门。目前我正在处理问题15，并且我认为我有一个正确的计算网格中路径数量的函数。但问题是对于大规模的网格大小，该函数运行时间非常长。

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

我正在尝试弄清楚如何使这个函数成为尾递归，但我不知道该怎么做。我需要一些帮助来开始思考如何使用尾调用优化来优化这样的函数。

- monostop

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

- soegaard

Answer 2

记忆化是一种方法，另一种方法是使用不同的数据表示方式。

我使用了表示为矩阵或向量的网格。

然后将顶行的值设置为1（因为在顶边上只有一条路径）。

之后，下一行中的第一个点是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-walker的调用都是尾调用。

使用符合RSR5标准的Scheme语言。

- WorBlux

---

按行操作，您可以将前一行和下一行合并，因此您只需要一个初始为 (n+1) 个 1 的行，然后可以迭代 n 次，在原地更新。 - Will Ness