2016-05-12 7 views
15

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

С пределом 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) времени выполнения. Это имеет смысл с теорией.

+2

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

+0

Переключение вызова на него слегка влияет. Как правило, нормальная рекурсия выигрывает с n <20. Между 20 и 40, в зависимости от порядка вызова, они равны. Рекурсия хвоста выигрывает с n> 40. Таким образом, это, по-видимому, связано с накладными расходами на стек. – Joe

+0

Если я нахожу эти вызовы с модулем 'timeit', оптимизированная версия хвостового вызова выигрывает для подсчета с низким повторением, но другая версия выигрывает для большого количества повторений. – user2357112

ответ

2

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

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

+2

Это не отвечает на вопрос. Вопрос не в том, как написать код «правильно»; речь идет о том, почему происходит различие в производительности, и на вашем посту есть только несколько строк смутных предположений на этом фронте. Кроме того, memoization не обязательно уменьшает максимальный объем пространства стека, который использует функция, поэтому он не является эффективным способом предотвращения переполнения стека, а 'functools.lru_cache' по умолчанию имеет ограничение в 128 кэшированных результатов. – user2357112

+0

«рекурсия хвоста уменьшает давление на память (меньше ассигнований, возможно, меньше sbrk syscalls, поэтому меньше переключателей контекста, ...)». –

+0

Вы на самом деле ничего не проверяли. Это просто спекуляция. Это даже не совсем новые спекуляции. – user2357112