Почему оптимизация хвостовой рекурсии быстрее, чем обычная рекурсия в Python?

Question

Хотя я понимаю, что оптимизация хвостовой рекурсии не является Pythonic, я придумал быстрый взлом на вопрос, который был удален, как только я был готов опубликовать.

С пределом 1000 стека алгоритмы глубокой рекурсии не могут использоваться в Python. Но иногда это отлично подходит для начальных мыслей через решение. Поскольку функции являются первоклассными в Python, я играл с возвратом действительной функции и следующего значения. Затем вызовите процесс в цикле до тех пор, пока не будут выполнены одиночные вызовы. Я уверен, что это не ново.

Что я нашел интересным, так это то, что я ожидал дополнительных накладных расходов на передачу функции туда и обратно, чтобы сделать это медленнее, чем обычная рекурсия. Во время моего грубого тестирования я нашел, что это займет 30-50% времени обычной рекурсии. (. С дополнительным бонусом позволяет LONG рекурсии)

Вот код, который я бегу:

from contextlib import contextmanager 
import time 

# Timing code from StackOverflow 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 

Почему второй стиль быстрее?

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

Edit:

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

Итак, я, добавив это до времени, которое 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) времени выполнения. Это имеет смысл с теорией.

Answer 1

Как комментарий, надеюсь remineded меня, я не был на самом деле ответить на этот вопрос, так вот мое мнение:

В вашей оптимизации, вы выделения, распаковка и deallocating кортежей, поэтому я попытался без них:

# 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.16s
• ваша «оптимизированная» версия взяла 0.22s
• «неоптимизированный» взял 0.29s

(Обратите внимание, что для меня, ваша оптимизированная версия быстрее, что не-оптимизированный один ... но мы не делаем точно такой же тест.)

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

>>> 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 ... с более читаемым, если заявление, в другом примере deque может быть более читаемым, а для других примеров динамическое программирование может быть лучше ...

«Вы пишете для человека, читающего ваш код, а не для машины».