如何优化递归 Racket 函数的运行时间以确定列表中的最大元素？

Question

这是我精彩且有效的 LISP racket "intermediate with lambda" 样式递归函数，用于确定列表中符号值最高的符号。

(define maximum
  (lambda [x]
    (cond
      [(empty? x) 0]
      [(cons? x)
           (cond
             [(>= (first x) (maximum (rest x))) (first x)]
             [else (maximum (rest x))]
           )
      ]
    )
  )
)

(check-expect (maximum '(1 2 3)) 3)
(check-expect (maximum '(1)) 1)
(check-expect (maximum '(0)) 0)

如何检查和优化运行时间？

递归在运行时与迭代有什么不同吗？

感谢您的回答！

亲切的问候，

Answer 1

有一个主要的事情会大大提高性能，将它从指数时间变为线性时间。

不要重新计算递归，将其保存为中间结果。

在内部 cond 表达式中，(maximum (rest x)) 被计算了两次。一次是第一个分支的问题，一次是第二个分支的答案。

(cond
  [(>= (first x) (maximum (rest x))) (first x)]
  [else (maximum (rest x))])

在第一个问题为假的常见情况下，(maximum (rest x)) 将被重新计算，使它必须做的工作加倍。更糟糕的是，在最坏的情况下，当最大值在末尾时，这种加倍可能会在递归的每个级别发生。这就是它呈指数增长的原因。

要解决此问题，您可以使用 local 来定义和命名中间结果。

(local [(define maxrst (maximum (rest x)))]
  (cond
    [(>= (first x) maxrst) (first x)]
    [else maxrst]))

这使得 big-O 复杂度在输入长度上从指数级变为线性级。

还有其他潜在的优化，例如利用尾调用，但这些不如保存中间结果以避免重新计算递归重要。

这种使用 local 定义提高性能的方法也在如何设计程序 2e 图 100：使用本地提高性能。

Answer 2

您可以使用 time-apply 来测量运行时间。这是一个过程，它将调用一个带有大列表的给定函数和 returns time-apply 执行的结果：

(define (time-on-list f size #:initial-element (initial-element 0)
                      #:trials (trials 10)
                      #:verbose (verbose #f)
                      #:gc-times (gc-times '()))
  (define pre-gc (if (memv 'pre gc-times) #t #f))
  (define post-gc (if (memv 'post gc-times) #t #f))
  (when verbose
    (printf "trials  ~A
pre-gc  ~A (not counted in runtime)
post-gc ~A (counted-in-runtime)~%"
                        trials
                        pre-gc
                        post-gc))
  ;; Intentionally construct a nasty list
  (define ll (list (for/list ([i (in-range size)]) i)))
  (define start (current-milliseconds))
  (when (and post-gc (not pre-gc))
    (collect-garbage 'major))
  (let loop ([trial 0] [cpu 0] [real 0] [gc 0])
    (if (= trial trials)
        (values (/ cpu trials 1.0) (/ real trials 1.0) (/ gc trials 1.0))
        (begin
          (when pre-gc
            (collect-garbage 'major))
          (when verbose
            (printf "  trial ~A at ~Ams~%" (+ trial 1) (- (current-milliseconds)
                                                        start)))
          (let-values ([(result c r g)
                        (time-apply (if post-gc
                                        (λ (l)
                                          (begin0
                                            (f l)
                                            (collect-garbage 'major)))
                                        f)
                                    ll)])
            (loop (+ trial 1) (+ cpu c) (+ real r) (+ gc g)))))))

您可以将其与 size 的不同值一起使用，以感受性能。默认情况下，它平均超过 10 次试验，但这可以调整。您也可以在此过程中的各个点请求 GC，但您可能不应该这样做。这是基于我用来测试事物性能的过程：它不是特别完成的代码。

您几乎可以肯定不想运行在您的函数的大尺寸值上这样做：请参阅其他答案。特别是，这里是列表长度最多为 25 的函数的时间：

(0 0 0 0 0 0 0 0 0 0.1 0.1 0.2 0.4 0.9 1.9 3.5 
 6.7 13.6 29.7 54.3 109.8 219.7 436.6 958.1 2101.4)

这应该让您确信事情大错特错了！

如何优化递归 Racket 函数的运行时间以确定列表中的最大元素？

How to optimize runtime on recursive Racket function to determine maximum of element in list?

recursion

lisp

racket

racket-student-languages