Python - 再帰と辞書 - 反復とインデックスを超えて - フィボナッチ数列、メモ化

Head First はじめてのプログラミング
頭とからだで覚えるPythonプログラミング入門
原著
楽天ブックス Yahoo!

開発環境

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

Head First はじめてのプログラミング ―頭とからだで覚えるPythonプログラミング入門 (Eric Freeman(著)、嶋田 健志(監修)、木下 哲也(翻訳)、株式会社オライリー・ジャパン)を8章(再帰と辞書 - 反復とインデックスを超えて)の能力発揮(374ページ)の解答を求めてみる。

コード

Python 3

#!/usr/bin/env python3
from collections import defaultdict
from unittest import TestCase, main
from typing import Callable, Dict


class MyTestCase(TestCase):
    def setUp(self):
        pass

    def tearDown(self):
        pass

    def test(self):
        nums = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
        fib = fib_memo()
        for i, n in enumerate(nums):
            self.assertEqual(fib(i), n)


def fib_memo() -> Callable[[int], int]:
    memo: Dict[int, int] = {0: 0, 1: 1}

    def inner(n: int) -> int:
        if n in memo:
            return memo[n]
        memo[n] = inner(n - 1) + inner(n - 2)
        return memo[n]
    return inner


if __name__ == '__main__':
    fib: Callable[[int], int] = fib_memo()
    for n in range(100):
        print(f'fib({n}) = {fib(n)}')
    main()

入出力結果(Bash、cmd.exe(コマンドプロンプト)、Terminal、Jupyter(IPython))

$ ./sample6.py
fib(0) = 0
fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(6) = 8
fib(7) = 13
fib(8) = 21
fib(9) = 34
fib(10) = 55
fib(11) = 89
fib(12) = 144
fib(13) = 233
fib(14) = 377
fib(15) = 610
fib(16) = 987
fib(17) = 1597
fib(18) = 2584
fib(19) = 4181
fib(20) = 6765
fib(21) = 10946
fib(22) = 17711
fib(23) = 28657
fib(24) = 46368
fib(25) = 75025
fib(26) = 121393
fib(27) = 196418
fib(28) = 317811
fib(29) = 514229
fib(30) = 832040
fib(31) = 1346269
fib(32) = 2178309
fib(33) = 3524578
fib(34) = 5702887
fib(35) = 9227465
fib(36) = 14930352
fib(37) = 24157817
fib(38) = 39088169
fib(39) = 63245986
fib(40) = 102334155
fib(41) = 165580141
fib(42) = 267914296
fib(43) = 433494437
fib(44) = 701408733
fib(45) = 1134903170
fib(46) = 1836311903
fib(47) = 2971215073
fib(48) = 4807526976
fib(49) = 7778742049
fib(50) = 12586269025
fib(51) = 20365011074
fib(52) = 32951280099
fib(53) = 53316291173
fib(54) = 86267571272
fib(55) = 139583862445
fib(56) = 225851433717
fib(57) = 365435296162
fib(58) = 591286729879
fib(59) = 956722026041
fib(60) = 1548008755920
fib(61) = 2504730781961
fib(62) = 4052739537881
fib(63) = 6557470319842
fib(64) = 10610209857723
fib(65) = 17167680177565
fib(66) = 27777890035288
fib(67) = 44945570212853
fib(68) = 72723460248141
fib(69) = 117669030460994
fib(70) = 190392490709135
fib(71) = 308061521170129
fib(72) = 498454011879264
fib(73) = 806515533049393
fib(74) = 1304969544928657
fib(75) = 2111485077978050
fib(76) = 3416454622906707
fib(77) = 5527939700884757
fib(78) = 8944394323791464
fib(79) = 14472334024676221
fib(80) = 23416728348467685
fib(81) = 37889062373143906
fib(82) = 61305790721611591
fib(83) = 99194853094755497
fib(84) = 160500643816367088
fib(85) = 259695496911122585
fib(86) = 420196140727489673
fib(87) = 679891637638612258
fib(88) = 1100087778366101931
fib(89) = 1779979416004714189
fib(90) = 2880067194370816120
fib(91) = 4660046610375530309
fib(92) = 7540113804746346429
fib(93) = 12200160415121876738
fib(94) = 19740274219868223167
fib(95) = 31940434634990099905
fib(96) = 51680708854858323072
fib(97) = 83621143489848422977
fib(98) = 135301852344706746049
fib(99) = 218922995834555169026
.
----------------------------------------------------------------------
Ran 1 test in 0.000s

OK
$ 

メモ化したら一気に高速化した。