Почему оптимизация хвостовой рекурсии быстрее, чем обычная рекурсия в Python?
Хотя я понимаю, что оптимизация хвостовой рекурсии не является пифонической, я быстро взломал вопрос, который был удален, как только я был готов к публикации.
С пределом в 1000 стеков алгоритмы глубокой рекурсии не могут использоваться в Python. Но иногда это отлично подходит для первоначальных мыслей через решение. Поскольку в Python функции первого класса, я поиграл с возвращением допустимой функции и следующего значения. Затем вызовите процесс в цикле, пока не закончите с одиночными вызовами. Я уверен, что это не ново.
Что мне показалось интересным, так это то, что я ожидал, что дополнительные издержки при передаче функции туда-сюда сделают эту медленную рекурсию медленнее, чем обычно. Во время моего грубого тестирования я обнаружил, что он занимает 30-50% времени нормальной рекурсии. (С дополнительным бонусом разрешения ДЛИТЕЛЬНЫХ рекурсий.)
Вот код, который я запускаю:
from contextlib import contextmanager
import time
# Timing code from Stackru most likely.
@contextmanager
def time_block(label):
start = time.clock()
try:
yield
finally:
end = time.clock()
print ('{} : {}'.format(label, end - start))
# Purely Recursive Function
def find_zero(num):
if num == 0:
return num
return find_zero(num - 1)
# Function that returns tuple of [method], [call value]
def find_zero_tail(num):
if num == 0:
return None, num
return find_zero_tail, num - 1
# Iterative recurser
def tail_optimize(method, val):
while method:
method, val = method(val)
return val
with time_block('Pure recursion: 998'):
find_zero(998)
with time_block('Tail Optimize Hack: 998'):
tail_optimize(find_zero_tail, 998)
with time_block('Tail Optimize Hack: 1000000'):
tail_optimize(find_zero_tail, 10000000)
# One Run Result:
# Pure recursion: 998 : 0.000372791020758
# Tail Optimize Hack: 998 : 0.000163852100569
# Tail Optimize Hack: 1000000 : 1.51006975627
Почему второй стиль быстрее?
Я предполагаю, что создание записей в стеке связано с дополнительными затратами, но я не знаю, как это выяснить.
Редактировать:
Играя со счетчиком вызовов, я сделал цикл, чтобы попробовать оба при различных значениях num. Рекурсивность была намного ближе к паритету, когда я многократно повторял и звонил.
Итак, я добавил это до времени, которое find_zero под новым именем:
def unrelated_recursion(num):
if num == 0:
return num
return unrelated_recursion(num - 1)
unrelated_recursion(998)
Теперь вызов с оптимизацией хвоста составляет 85% времени полной рекурсии.
Так что моя теория заключается в том, что 15% штрафа - это накладные расходы для большего стека по сравнению с одним стеком.
Причина, по которой я увидел такое огромное несоответствие во времени выполнения, когда только запуск каждого из них был штрафом за распределение стековой памяти и структуры. Как только это выделено, стоимость их использования резко снижается.
Поскольку мой алгоритм очень прост, распределение структуры памяти занимает большую часть времени выполнения.
Когда я обрезаю свой призыв к заливке unrelated_recursion(499), Я получаю примерно половину между полностью загрунтованным и не загрунтованным find_zero(998) время исполнения. Это имеет смысл с теорией.
1 ответ
Надеюсь, мой комментарий напомнил мне, что я не отвечал на этот вопрос, так что вот мое мнение:
В вашей оптимизации вы размещаете, распаковываете и освобождаете кортежи, поэтому я попытался без них:
# Function that returns tuple of [method], [call value]
def find_zero_tail(num):
if num == 0:
return None
return num - 1
# Iterative recurser
def tail_optimize(method, val):
while val:
val = method(val)
return val
на 1000 попыток, каждая из которых начинается со значения = 998:
- эта версия займет 0,16 с
- ваша "оптимизированная" версия заняла 0,22 с
- "неоптимизированный" занял 0,29 с
(Обратите внимание, что для меня ваша оптимизированная версия быстрее, чем неоптимизированная... но мы не проводим точно такой же тест.)
Но я не думаю, что это полезно для получения этой статистики: стоимость больше на стороне Python (вызовы методов, распределение кортежей, ...), чем ваш код делает реальные вещи. В реальном приложении вы будете измерять не стоимость 1000 кортежей, а стоимость фактической реализации.
Но просто не делайте этого: это просто трудно прочитать почти даром, вы пишете для читателя, а не для машины:
# Function that returns tuple of [method], [call value]
def find_zero_tail(num):
if num == 0:
return None, num
return find_zero_tail, num - 1
# Iterative recurser
def tail_optimize(method, val):
while method:
method, val = method(val)
return val
Я не буду пытаться реализовать его более читаемую версию, потому что я, вероятно, в конечном итоге:
def find_zero(val):
return 0
Но я думаю, что в реальных случаях есть несколько хороших способов справиться с ограничениями рекурсии (как по объему памяти, так и по глубине):
Чтобы помочь с памятью (не с глубиной), lru_cache от functools обычно может очень помочь:
>>> from functools import lru_cache
>>> @lru_cache()
... def fib(x):
... return fib(x - 1) + fib(x - 2) if x > 2 else 1
...
>>> fib(100)
354224848179261915075
А для размера стека вы можете использовать list или deque, в зависимости от вашего контекста и использования, вместо использования языкового стека. В зависимости от точной реализации (когда вы на самом деле храните в своем стеке простые промежуточные вычисления для их повторного использования), это называется динамическим программированием:
>>> def fib(x):
... stack = [1, 1]
... while len(stack) < x:
... stack.append(stack[-1] + stack[-2])
... return stack[-1]
...
>>> fib(100)
354224848179261915075
Но, и здесь есть хорошая часть использования вашей собственной структуры вместо стека вызовов, вам не всегда нужно сохранять весь стек для продолжения вычислений:
>>> def fib(x):
... stack = (1, 1)
... for _ in range(x - 2):
... stack = stack[1], stack[0] + stack[1]
... return stack[1]
...
>>> fib(100)
354224848179261915075
Но в завершение сделаем приятный штрих "узнай проблему, прежде чем пытаться ее реализовать" (нечитабельно, трудно отлаживать, трудно визуально доказать, это плохой код, но это весело):
>>> def fib(n):
... return (4 << n*(3+n)) // ((4 << 2*n) - (2 << n) - 1) & ((2 << n) - 1)
...
>>>
>>> fib(99)
354224848179261915075
Если вы спросите меня, лучшая реализация - более читаемая (для примера Фибоначчи, вероятно, с кешем LRU, но с изменением ... if ... else ... с более читаемым оператором if, для другого примера deque может быть более читабельным, а для других примеров динамическое программирование может быть лучше...
"Вы пишете для человека, читающего ваш код, а не для машины".