functoolsとは
https://docs.python.org/ja/3/library/functools.html
functoolsモジュールは高階関数、つまり関数に影響を及ぼしたり他の関数を返したりする関数のためのものです。一般に、どんな呼び出し可能オブジェクトでもこのモジュールの目的には関数として扱えます。
簡単に言うと、関数に対する便利ツールです。
cacheとは
cacheとは、一般的にはデータ伝送高速化のための一時データのことです。
functoolsにおけるcacheとは
簡単で軽量な無制限の関数キャッシュです。 “メモ化 (memoize)” とも呼ばれることがあります。
https://docs.python.org/ja/3/library/functools.html#functools.cache
lru_cache(maxsize=None)と同じ関数を返し、関数の引数に対するルックアップ辞書を含む薄いラッパーを生成します。キャッシュ上の古い値を追い出す必要がないため、キャッシュサイズに制限のあるlru_cache()よりも軽量で高速です。
メモ化という手法を用いて再帰関数を高速に処理するデコレータのことです。
Python 3.9 以上で使用可能です。
メモ化とは
簡単に言うと、一度した計算を記録しておいて再計算分の時間を削減しようという高速化手法のことです。
例えば、以下のようなフィボナッチ数を求める関数があったとします。
int fib(int n)
{
if (n < 2){
return n;
}
return fib(n - 1) + fib(n - 2);
}仮に３７個のフィボナッチ数を求めるとすると、この関数は126491933回呼び出されます。
これを以下のようにメモ化すると
int memo_fib(int n)
{
if (n < 2){
return n;
}
if (memo[n]){
return memo[n];
}
memo[n] = memo_fib(n - 1) + memo_fib(n - 2);
return memo[n];
}たったの107回の呼び出しで済みます。
実際に高速化してみる
実際に以下のコードを用いて実行時間を計測してみようと思います。
from functools import cache
from utils import timer
@cache
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
@timer
def main():
n = 37
for i in range(n):
print(f"{fib(i)} ", end="")
print("")
if __name__ == '__main__':
main()utilsのtimerは自作の時間計測デコレータです。
@cacheなし
$ python .\main.py
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352
elapsed : 8.392 s@cacheあり
$ python .\main.py
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352
elapsed : 0.188 ms約44,638倍高速化しました。
蛇足
Pythonには最大再帰深度が設定されているので無闇矢鱈に再帰はできません。
$ python
Python 3.11.2 (tags/v3.11.2:878ead1, Feb 7 2023, 16:38:35) [MSC v.1934 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> import sys
>>> print(sys.getrecursionlimit())
1000どうしても再帰深度を変更したい場合は以下のように変更することもできるにはできますが、あまりに深い再帰関数はエンジニアが把握しきれないバグのもとになり得るので個人的には好きではありません。
import sys
sys.setrecursionlimit(2000)まとめ
今回のメモ化による高速化の大部分はプログラムの機能ではなくアルゴリズムによる高速化です。
プログラマはプログラムを書くだけでなく、数学的思考も持ち合わせていないといけないと思います。
コメント