Как оптимизировать время выполнения на рекурсивной функции Racket, чтобы определить максимум элемента в списке? - PullRequest
Новая
       50

Как оптимизировать время выполнения на рекурсивной функции Racket, чтобы определить максимум элемента в списке?

1 голос
/ 12 февраля 2020

вот моя замечательная и работающая рекурсивная функция в стиле «промежуточный с лямбда» LISP для определения символа с наибольшим значением символов в списке. 

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

Как проверить и оптимизировать время выполнения ?

Отличается ли рекурсия во время выполнения от итерации?

Спасибо за ваш ответ!

С уважением,

Ответы [ 2 ]

4 голосов
/ 12 февраля 2020

Есть одна главная вещь, которая значительно улучшит производительность, взяв ее от экспоненциального к линейному времени.

Не пересчитывайте рекурсию, сохраняйте ее как промежуточный результат.

Во внутреннем 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]))

Это требует большого -О сложность от экспоненциальной до линейной по длине ввода.

Существуют и другие потенциальные оптимизации, такие как использование хвостовых вызовов, но они не так важны, как сохранение промежуточного результата, чтобы избежать повторного ввода. вычисление рекурсии.

Этот метод повышения производительности с использованием определений local также описан в Как разрабатывать программы 2e Рис. 100: Использование локальных для повышения производительности .

1 голос
/ 12 февраля 2020

Вы можете использовать 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 испытаний, но это можно отрегулировать. Вы также можете запросить G C в различных точках процесса, но, вероятно, не следует. Это основано на процедуре, которую я использую для тестирования производительности вещей: это не совсем законченный код.

Вы почти наверняка не хотите запустить это при больших значениях размера для вашей функции Смотрите другой ответ. В частности, вот время для списка длиной до 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)

Это должно убедить вас, что что-то ужасно неправильно!

...