1

这是我的精彩且有效的 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)

如何检查和优化运行时？

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

谢谢您的回答！

亲切的问候，

4

2 回答 2

4

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

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

在内部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：使用本地来提高性能中进行了描述。

于 2020-02-12T15:32:18.940 回答
1

您可以使用它time-apply来测量运行时间。这是一个过程，它将调用具有大列表的给定函数并返回执行结果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)

这应该使您确信某些事情是非常错误的！

于 2020-02-12T16:14:15.257 回答