Блог

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

 import time

known = {0:0,1:1}
def fibonacci_memo(n):
    """return the nth number of fibonacci sequence
    using memo to raise efficiency"""
    if n in known:
        return known[n]

    res = fibonacci(n-1)   fibonacci(n-2)
    known[n] = res
    return res

def fibonacci(n):
    """return the nth number of fibonacci sequence
    without using memo"""
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n-1)   fibonacci(n-2)

if __name__ == '__main__':
    start = time.clock()
    print fibonacci_memo(32)
    elaspsed = time.clock() - start
    print 'using memo time used: '   str(elaspsed)

    start = time.clock()
    print fibonacci(32)
    elaspsed = time.clock() - start
    print 'without using memo time used: '   str(elaspsed)
 

Результат выглядит примерно так:

 2178309
using memo time used: 1.83040345779
2178309
without using memo time used: 1.792043347
 

Ваша функция fibonacci_memo не вызывает себя рекурсивно, она вызывает исходную (не запоминаемую) функцию Фибоначчи.

Рекурсия вашей записанной функции вызывает другую функцию. Попробуйте заменить fibonacci_memo на это:

 def fibonacci_memo(n):
    """return the nth number of fibonacci sequence
    using memo to raise efficiency"""
    if n in known:
        return known[n]

    res = fibonacci_memo(n-1)   fibonacci_memo(n-2)
    known[n] = res
    return res