アルゴリズム学習 #2 メモ化
今回は、「メモ化」です。
メモ化とは、「プログラムの高速化のための最適化技法の一種」で、
「結果を後で再利用するために保持し、関数の呼び出し毎の再計算を防ぐ手法」らしいです。
良く一緒に出されるアルゴリズムとして動的計画法がありますが、それはまた次の機会に…。
フィボナッチ数列を例にしていますが、一つの要素に対して、
ある値もしくはその数列に対して、何回も同じような計算をするようなものに使えるやり方のようです。
memo = {
1:1,
2:1
}
def fibonacci(n):
# 辞書のキーに特定の値が含まれているかを判定する
if n in memo:
return memo[n]
memo[n] = fibonacci(n-2) + fibonacci(n-1)
return memo[n]
fibonacci(100)
print(memo)
ちなみに、100まででやってみました。
$ time python memoka.py
{1: 1, 2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144, 13: 233, 14: 377, 15: 610, 16: 987, 17: 1597, 18: 2584, 19: 4181, 20: 6765, 21: 10946, 22: 17711, 23: 28657, 24: 46368, 25: 75025, 26: 121393, 27: 196418, 28: 317811, 29: 514229, 30: 832040, 31: 1346269, 32: 2178309, 33: 3524578, 34: 5702887, 35: 9227465, 36: 14930352, 37: 24157817, 38: 39088169, 39: 63245986, 40: 102334155, 41: 165580141, 42: 267914296, 43: 433494437, 44: 701408733, 45: 1134903170, 46: 1836311903, 47: 2971215073, 48: 4807526976, 49: 7778742049, 50: 12586269025, 51: 20365011074, 52: 32951280099, 53: 53316291173, 54: 86267571272, 55: 139583862445, 56: 225851433717, 57: 365435296162, 58: 591286729879, 59: 956722026041, 60: 1548008755920, 61: 2504730781961, 62: 4052739537881, 63: 6557470319842, 64: 10610209857723, 65: 17167680177565, 66: 27777890035288, 67: 44945570212853, 68: 72723460248141, 69: 117669030460994, 70: 190392490709135, 71: 308061521170129, 72: 498454011879264, 73: 806515533049393, 74: 1304969544928657, 75: 2111485077978050, 76: 3416454622906707, 77: 5527939700884757, 78: 8944394323791464, 79: 14472334024676221, 80: 23416728348467685, 81: 37889062373143906, 82: 61305790721611591, 83: 99194853094755497, 84: 160500643816367088, 85: 259695496911122585, 86: 420196140727489673, 87: 679891637638612258, 88: 1100087778366101931, 89: 1779979416004714189, 90: 2880067194370816120, 91: 4660046610375530309, 92: 7540113804746346429, 93: 12200160415121876738, 94: 19740274219868223167, 95: 31940434634990099905, 96: 51680708854858323072, 97: 83621143489848422977, 98: 135301852344706746049, 99: 218922995834555169026, 100: 354224848179261915075}
real 0m0.080s
user 0m0.000s
sys 0m0.015s簡単な実装の時間も図ってみましたが・・・5分経っても終わらず…
def fibonacci(n): if (n==1) or (n==2): return 1 return fibonacci(n-2) + fibonacci(n-1) print(fibonacci(10))
[まとめ]
メモ化をすれば一瞬で終わるものでも、何度も計算すると終わらないということを痛感しました…。
[参考]
- 書籍
