Производительность рекурсии и стиля аккумулятора

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

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

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

Ответ 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)))

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

Ответ 2

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

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

Ответ 3

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

Ответ 4

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

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

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

(define (fact1 n) (do ([n n (- n 1)] [p 1 (* p n)]) ((= n 1) p)))

(define (fact2 n) (do ([i 1 (+ я 1)] [p 1 (* p i)]) ((< n i) p)))

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

(define (fact4 n) (пусть f ((i 1) (p 1)) (если (< n i) p (f (+ я 1) (* p i)))))