pythonの再帰運転が遅すぎる原因と解決策
3354 ワード
今日pythonでフィボナッチ数列を作成しました.コードは以下の通りです.
結果はそのまま実行しても結果が出ないので、73から27秒後に変更してみましたが、数値が大きすぎて実行時間が長すぎたようです・・・pythonは再帰を実行するたびに、前の数値を使うたびに、もう一度計算し直します・・・だからこんなに遅いのです.結果をキャッシュに格納すると、実行速度が向上します.
これで73を運転しても秒で結果が出ます!
def feb(i: int):
if i == 0:
return 1
if i == 1:
return 2
return feb(i-2) + feb(i-1)
print(feb(73))
結果はそのまま実行しても結果が出ないので、73から27秒後に変更してみましたが、数値が大きすぎて実行時間が長すぎたようです・・・pythonは再帰を実行するたびに、前の数値を使うたびに、もう一度計算し直します・・・だからこんなに遅いのです.結果をキャッシュに格納すると、実行速度が向上します.
from functools import lru_cache
@lru_cache(maxsize=1024)
def feb(i: int):
if i == 0:
return 1
if i == 1:
return 2
return feb(i-2) + feb(i-1)
print(feb(73))
これで73を運転しても秒で結果が出ます!