Рекурсия, запоминание и изменяемые аргументы по умолчанию в Python - PullRequest
Новая
       37

Рекурсия, запоминание и изменяемые аргументы по умолчанию в Python

4 голосов
/ 08 марта 2019

«Базовый» смысл без использования lru_cache.Все это «достаточно быстро» - я не ищу самый быстрый алгоритм - но время меня удивило, поэтому я надеялся, что смогу кое-что узнать о том, как «работает» Python.

Простой цикл (/ хвостовая рекурсия): 

def fibonacci(n):
    a, b = 0, 1
    if n in (a, b): return n
    for _ in range(n - 1):
        a, b = b, a + b
    return b

Простое запоминание: 

def fibonacci(n, memo={0:0, 1:1}):
    if len(memo) <= n:
        memo[n] = fibonacci(n - 1) + fibonacci(n - 2)
    return memo[n]

Использование генератора: 

def fib_seq():
    a, b = 0, 1
    yield a
    yield b
    while True:
        a, b = b, a + b
        yield b

def fibonacci(n):
    return next(x for (i, x) in enumerate(fib_seq()) if i == n)

Я ожидал, что первое, простое до смерти, будетсамый быстрый.Это не.Второй, безусловно, самый быстрый, несмотря на рекурсию и множество вызовов функций.Третий классный и использует «современные» функции, но еще медленнее, что разочаровывает.(У меня было искушение думать о генераторах как о некоторой альтернативе запоминанию - так как они помнят свое состояние - и поскольку они реализованы в CI, надеялись, что они будут быстрее.)

Типичные результаты: 

loop: about 140 μs
memo: about 430 ns
genr: about 250 μs

Так может кто-нибудь объяснить, в частности, почему запоминание на порядок быстрее простого цикла?

РЕДАКТИРОВАТЬ:

Теперь ясно, что я (как и многие другие до меня) просто наткнулся на изменяемые аргументы Python по умолчанию .Такое поведение объясняет реальное и видимое увеличение скорости выполнения.

1 Ответ

1 голос
/ 08 марта 2019

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

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

fibonacci(100, {0:0, 1:1})
...