时间戳

首页 > 解决方案 > 如何优化递归球拍函数的运行时间以确定列表中元素的最大值？

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

问题描述

这是我的精彩且有效的 LISP 球拍“中间与 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)

如何检查和优化运行时？

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

谢谢您的回答！

亲切的问候，

标签： recursionlispracketracket-student-languages

解决方案

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

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

在内部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]))

这使得输入长度的大 O 复杂度从指数变为线性。

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

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

推荐阅读