Algorithm - Python - メモリは役に立つ(フィボナッチ数、辞書の作成と検索、例外、再帰探索でのメモ化)

問題解決のPythonプログラミング
原著
楽天ブックス(Kobo) Yahoo!

開発環境

• macOS Mojave - Apple (OS)
• Emacs (Text Editor)
• Windows 10 Pro (OS)
• Visual Studio Code (Text Editor)
• Python 3.7 (プログラミング言語)

問題解決のPythonプログラミング ―数学パズルで鍛えるアルゴリズム的思考 (Srini Devadas (著)、黒川 利明 (翻訳)、オライリージャパン)の18章(メモリは役に立つ)、練習問題(問題1)の解答を求めてみる。

コード

Python 3

#!/usr/bin/env python3
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)


def fib_memo(n, memo):
    ''' 
    >>> fib_memo(0, {})
    0
    >>> fib_memo(1, {})
    1
    >>> fib_memo(2, {})
    1
    >>> fib_memo(10, {}) == fib(10)
    True
    '''
    if n in memo:
        return memo[n]
    if n < 2:
        memo[n] = n
        return n
    result = fib_memo(n - 2, memo) + fib_memo(n - 1, memo)
    memo[n] = result
    return result


if __name__ == '__main__':
    import doctest
    doctest.testmod()

    import time
    for n in range(10, 30):
        start = time.time()
        result = fib(n)
        seconds = time.time() - start
        print(f'{seconds:.10f}s: fib({n}) -> {result}')
        start = time.time()
        result = fib_memo(n, {})
        seconds = time.time() - start
        print(f'{seconds:.10f}s: fib_memo({n}) -> {result}')
        print()

入出力結果(Terminal, cmd(コマンドプロンプト), Jupyter(IPython))

$ ./sample3.py -v
Trying:
    fib_memo(0, {})
Expecting:
    0
ok
Trying:
    fib_memo(1, {})
Expecting:
    1
ok
Trying:
    fib_memo(2, {})
Expecting:
    1
ok
Trying:
    fib_memo(10, {}) == fib(10)
Expecting:
    True
ok
2 items had no tests:
    __main__
    __main__.fib
1 items passed all tests:
   4 tests in __main__.fib_memo
4 tests in 3 items.
4 passed and 0 failed.
Test passed.
0.0000231266s: fib(10) -> 55
0.0000057220s: fib_memo(10) -> 55

0.0000371933s: fib(11) -> 89
0.0000052452s: fib_memo(11) -> 89

0.0000588894s: fib(12) -> 144
0.0000052452s: fib_memo(12) -> 144

0.0000951290s: fib(13) -> 233
0.0000052452s: fib_memo(13) -> 233

0.0001542568s: fib(14) -> 377
0.0000059605s: fib_memo(14) -> 377

0.0002491474s: fib(15) -> 610
0.0000057220s: fib_memo(15) -> 610

0.0004029274s: fib(16) -> 987
0.0000069141s: fib_memo(16) -> 987

0.0007090569s: fib(17) -> 1597
0.0000100136s: fib_memo(17) -> 1597

0.0011267662s: fib(18) -> 2584
0.0000102520s: fib_memo(18) -> 2584

0.0018413067s: fib(19) -> 4181
0.0000119209s: fib_memo(19) -> 4181

0.0029067993s: fib(20) -> 6765
0.0000100136s: fib_memo(20) -> 6765

0.0044846535s: fib(21) -> 10946
0.0000112057s: fib_memo(21) -> 10946

0.0072760582s: fib(22) -> 17711
0.0000100136s: fib_memo(22) -> 17711

0.0117549896s: fib(23) -> 28657
0.0000088215s: fib_memo(23) -> 28657

0.0194749832s: fib(24) -> 46368
0.0000140667s: fib_memo(24) -> 46368

0.0313711166s: fib(25) -> 75025
0.0000188351s: fib_memo(25) -> 75025

0.0503151417s: fib(26) -> 121393
0.0000169277s: fib_memo(26) -> 121393

0.0809721947s: fib(27) -> 196418
0.0000152588s: fib_memo(27) -> 196418

0.1315467358s: fib(28) -> 317811
0.0000138283s: fib_memo(28) -> 317811

0.2130439281s: fib(29) -> 514229
0.0000202656s: fib_memo(29) -> 514229

$

メモ化した方が速いことを確認できた。