два метода составления функций, насколько отличаются по эффективности?

Question

Пусть f преобразует одно значение в другое, тогда я пишу функцию, которая повторяет преобразование n раз.

Я придумал два разных способа:

• Один очевидный способ буквально применяет функцию п раз, поэтому повтор (f, 4) означает x → е (е (е (е (х))))
• Другой путь вдохновлен быстрый способ питания, что означает разделив проблему на две части проблемы вдвое меньше всякий раз, когда п четный. Итак, повтор (f, 4) означает x → g (g (x)) , где g (x) = е (е (х))

Сначала я подумал, что второй метод не так сильно повысит эффективность. В конце концов, мы все равно должны были бы подать заявку n раз, не так ли? В приведенном выше примере g будет по-прежнему переводиться в f o f без дальнейшего упрощения, верно?

Однако, когда я опробовал методы, последний метод был заметен быстрее.

;; computes the composite of two functions
(define (compose f g)
  (lambda (x) (f (g x))))

;; identify function
(define (id x) x)

;; repeats the application of a function, naive way
(define (repeat1 f n)
  (define (iter k acc)
    (if (= k 0)
        acc
        (iter (- k 1) (compose f acc))))
  (iter n id))

;; repeats the application of a function, divide n conquer way
(define (repeat2 f n)
  (define (iter f k acc)
    (cond ((= k 0) acc)
          ((even? k) (iter (compose f f) (/ k 2) acc))
          (else (iter f (- k 1) (compose f acc)))))
  (iter f n id))

;; increment function used for testing
(define (inc x) (+ x 1))

На самом деле ((repeat2 inc 1000000) 0) было намного быстрее, чем ((repeat1 inc 1000000) 0) . У меня вопрос, в каком аспекте второй метод был более эффективным, чем первый? Сохраняет ли повторное использование одного и того же функционального объекта память и сокращает время, затрачиваемое на создание новых объектов?

В конце концов, приложение должно повторяться n раз, или, говоря иначе, x → ((x + 1) +1) не может быть автоматически уменьшено до x → (x +2) , верно?

Я использую DrScheme 4.2.1.

Большое спасибо.

Answer 1

Вы правы, что обе версии делают одинаковое количество звонков на inc - но есть еще накладные расходы, чем в вашем коде. В частности, первая версия создает N замыканий, тогда как второй создает только замыкания журнала (N) - и если создание замыкания - большая часть работы тогда вы увидите большую разницу в производительности.

Есть три вещи, которые вы можете использовать, чтобы увидеть это более подробно:

1. Используйте специальную форму DrScheme time для измерения скорости. В дополнение к тому времени, когда это Потребуется выполнить некоторые вычисления, он также скажет вам, сколько времени было потрачено в GC. Вы увидите, что первая версия выполняет некоторую работу с GC, а вторая - нет. (Ну, это так, но это так мало, что, вероятно, не будет отображаться.)

2. Ваша функция inc делает так мало, что вы измеряете только издержки зацикливания. Например, когда я использую эту плохую версию:

   (define (slow-inc x)
     (define (plus1 x)
       (/ (if (< (random 10) 5)
            (* (+ x 1) 2)
            (+ (* x 2) 2))
          2))
     (- (plus1 (plus1 (plus1 x))) 2))
   

   разница между этими двумя показателями уменьшается с ~ 11 до 1,6.

3. Наконец, попробуйте эту версию:

   (define (repeat3 f n)
     (lambda (x)
       (define (iter n x)
         (if (zero? n) x (iter (sub1 n) (f x))))
       (iter n x)))
   

   Это не делает никаких композиций, и это работает примерно та же скорость, что и у вашей второй версии.

Answer 2

Первый метод по существу применяет функцию n раз, таким образом, это O (n). Но второй метод фактически не применяет функцию n раз. Каждый раз, когда вызывается repeat2, он делит n на 2, когда n четно. Таким образом, большую часть времени размер проблемы уменьшается вдвое, а не просто уменьшается на 1. Это дает общее время выполнения O (log (n)).

Как и Мартиньо Фернандес , статья в Википедии о возведении в квадрат на квадрате объясняет это очень ясно.