## 2019年1月4日金曜日

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

コード

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()
```

```\$ ./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

\$
```

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