Выполнение рекурсии против стиля аккумулятора

Question

У нас есть две функции, которые вычисляют факториал данного числа.Первый, !, использует стиль аккумулятора.Второй, fact, использует естественную рекурсию.

(define (! n0)
  (local (;; accumulator is the product of all natural numbers in [n0, n)
      (define (!-a n accumulator)
        (cond
          [(zero? n) accumulator]
          [else (!-a (sub1 n) (* n accumulator))])))
    (!-a n0 1)))

и

(define (fact n)
  (cond
    [(= 0 n) 1]
    [else (* n (fact (- n 1)))]))

В нижней части раздела 31 HtDP указывает, что естественно-рекурсивная версиячасто так же быстро, если не быстрее, чем версия аккумулятора, но не указывает причины этого.Я немного читал об этом, и кажется, что ответ 'Оптимизация / устранение хвостовых вызовов' , но статья в Википедии, кажется, расходится с тем, что говорит HtDP, по крайней мере, в отношении производительности.Почему это так?

---

На работе рекурсивный стиль работает быстрее.Дома стиль аккумулятора быстрее.Не существует ли общей эвристики, которая бы направляла выбор в отношении того, какой стиль обычно предпочитается?Я понимаю, что стиль аккумулятора более эффективен для памяти, но если мы ограничимся обсуждением только производительностью, то, по крайней мере для меня, будет неясно, какой вариант лучше.

---

Я имеюмы немного подумаем об этом и должны были бы принять сторону статьи Wikipedia о превосходстве рекурсии в стиле аккумулятора в общем случае .Это не только сокращает использование пространства стека / кучи, но и доступ к памяти всегда будет отставать от доступа к регистру, и его можно будет сделать более очевидным только сейчас, когда многоядерность здесь.Тем не менее, HtDP доказывает, что во всех случаях требуется проведение реальных испытаний.

Answer 1

Ответ будет зависеть от деталей системы Racket.Вот мой взгляд на это.

Существует два основных различия между естественно-рекурсивной версией и версией аккумулятора.Во-первых, версия аккумулятора написана таким образом, что позволяет оптимизировать хвостовой вызов.Это помогает сделать версию аккумулятора более быстрой, поскольку требуется создавать меньше кадров стека.Но это противоположно тому, что обсуждается в HtDP и тому, что вы видели на своем рабочем компьютере.

Другое отличие - порядок умножения.Естественно рекурсивная версия умножает числа от 1 до 20 в порядке возрастания, то есть

((((1 * 2) * 3) * … * 19) * 20)

Версия с накопителем умножает те же числа в порядке убывания, то есть

((((20 * 19) * 18) * … * 2) * 1)

Математически,они одинаковы, и две факторные функции дадут одинаковый результат.Тем не менее, эта разница может иметь значение.В частности, при любом промежуточном умножении промежуточный результат будет больше для последнего вычисления, чем для первого вычисления.

Факториал 20 - это большое число.Это не поместится в 32-битное целое число.Это означает, что ракетке нужно будет использовать целое число произвольной длины («bignum») для представления ответа и некоторые промежуточные результаты.Арифметика произвольной точности, включая умножение с участием бигнумов, медленнее, чем арифметика с фиксированной точностью.

Поскольку промежуточные результаты в версии с аккумулятором всегда больше, чем у естественно-рекурсивной версии, версия с аккумулятором потребует бигнум раньше, чем рекурсивная версия.Короче говоря, хотя обе версии требуют одинакового количества умножений, версия с накопителем требует большего умножения произвольной точности.Это замедляет работу версии аккумулятора.По-видимому, дополнительные затраты на арифметику перевешивают экономию от уменьшения количества кадров стека.

Так почему бы не увидеть ту же тенденцию на вашем домашнем компьютере?Вы сказали, что это Intel iMac, так что это, вероятно, 64-битная система.Пока 20!это большое число, оно мало по сравнению с 64-разрядным целым числом, поэтому ваш домашний компьютер не выполняет произвольную арифметику точности, и порядок не имеет значения.HtDP достаточно стар, чтобы использовать 32-битную систему, как и Windows XP на вашем рабочем компьютере.

Более полезной для изучения различий будет функция, которая вычисляет произведение списка чисел, либо

(define (product numlist)
  (* (car numlist) (product (cdr numlist)))

, либо в версии с аккумулятором.Затем вы можете вводить числа в порядке возрастания или убывания, независимо от того, используете ли вы естественно-рекурсивный или накопительный подход.

Answer 2

Я не знаю внутренностей компилятора Racket, но я буду размышлять.

Хвостовые вызовы, как правило, стоят дороже, чем обычные вызовы (это верно в .NET, до 7 раз медленнее), но в некоторых случаях хвостовой вызов может быть исключен, и в итоге он становится циклом в стиле while(1) { ... } C следовательно, не будет никаких дополнительных вызовов, просто локальный переход, эффективно устраняющий издержки приложения процедуры.

Answer 3

Много хороших моментов выше. Мне нравится анализ того, что должно быть, и почему это не так. Это то, из чего сделан успех Project Euler. Слишком ранняя поездка из фикснумов может быть проблематичной.

Последовательность чисел можно умножить с большого на маленькое или наоборот. У нас также есть команда do, которая выполняет итерацию напрямую и аналогично.

(определить (факт n) (если (= n 1) 1 (* n (факт (- n 1)))))

(определить (fact1 n) (do ([n n (- n 1)] [p 1 (* p n)]) ((= n 1) p)))

(определить (fact2 n) (do ([i 1 (+ i 1)] [p 1 (* p i)]) ((

(определить (fact3 n) (пусть f ((n n) (p 1)) (если (= n 1) p (f (- n 1) (* p n)))))

(определить (fact4 n) (пусть f ((i 1) (p 1)) (если (

Answer 4

Хороший компилятор превратит рекурсивный интерфейс в хвостовой. Так что не должно быть никакой разницы в скомпилированном коде.