python装飾器でアルゴリズムを最適化する
2614 ワード
要旨:最近codingでPython装飾器を使っていますが、その役割は強すぎて、しかも使用も簡単で、私のコードの中で大量に計算を繰り返すボトルネックを解決しました.以下はFibonacci数列を計算することを例に問題を説明します.
C言語版:
コンパイル:gcc-O 3-o fib fib.c
運転:3.28 sかかります.
純Python版を見てみましょう.
実行:
40.19 sを使って、もともと45を計算しようとしたが、仕方なく結果が出なかった.
上記のC版とは数百倍以上の差があります.ここで計算するのは40で、データが大きいほどfibの呼び出しは指数級に上昇するので、ここでは数百倍と見積もって誇張ではありません.以下では、ここでfibの繰り返し呼び出し回数を分析します.ここからPythonは確かにこのような大量の繰り返し計算に適していないことがわかるので、C/C++でPythonを拡張し、計算速度を高め、Pythonでbitey呼び出しCモジュールの方法で書き換えることを考えました.
Python+ctypes版:
実行:
9.88 sで、明らかに純Python版より速いが、純C版と3倍ほど差がある.
Python+bitey版を見てみましょう.
実行:
6.58 sでctypes版より良い点がわかりますが、純C版よりは悪いですが、もういいです.clang+llvmのおかげだと思います.
では、純粋なPython版がなぜこんなに遅いのかを分析してみましょう.
fibに対して331160281回呼び出されたことがわかり、遅くなくても正常ではないことが分かった.Fibonacci数列の特徴に基づいて、前回の計算後の結果を記録する方法を考えることができ、例えばf(10)を計算し、計算したf(9)とf(8)の結果を再帰せずに直接返すことができる.ちょうどPythonアクセサリーは前回計算した結果を記録するのに使えますが、Pythonアクセサリーの使用についてはPythonアクセサリーと切面向けプログラミングを見てください.
Pythonアクセサリー版:
実行:
使用時間0.02 s、純C版より150倍以上速い!これがデコレーション処理後の効果で、Cも結果をキャッシュできるが、Pythonのような簡単明瞭な方法よりは複雑すぎる.
まとめ:pythonの処理速度を向上させる場合、boost/ctypes/biteyでc/c++書き込みモジュールを呼び出したり、cythonでコンパイルしたりすることができますが、最終的には言語自体の特性を利用してアルゴリズムを最適化するのが王道です.
C言語版:
#include
//fib.c
int fib(int n)
{
if(n < 3)
{
return 1;
}
else
{
return fib(n-1) + fib(n-2);
}
}
int main(int argc, char* argv[])
{
if(argc == 2)
printf("%d
", fib(atoi(argv[1])));
else
printf("Please enter a parameter
");
}
コンパイル:gcc-O 3-o fib fib.c
運転:3.28 sかかります.
純Python版を見てみましょう.
#!/usr/bin/env python
#fib.py
import sys
def fib(n):
if n < 2:
return n
else:
return fib(n-2) + fib(n-1)
if len(sys.argv) == 2:
print fib(int(sys.argv[1]))
else:
print "Please enter a parameter"
実行:
40.19 sを使って、もともと45を計算しようとしたが、仕方なく結果が出なかった.
上記のC版とは数百倍以上の差があります.ここで計算するのは40で、データが大きいほどfibの呼び出しは指数級に上昇するので、ここでは数百倍と見積もって誇張ではありません.以下では、ここでfibの繰り返し呼び出し回数を分析します.ここからPythonは確かにこのような大量の繰り返し計算に適していないことがわかるので、C/C++でPythonを拡張し、計算速度を高め、Pythonでbitey呼び出しCモジュールの方法で書き換えることを考えました.
Python+ctypes版:
#!/usr/bin/env python
#fib_ctypes.py
import sys
import ctypes
lib = ctypes.CDLL("./fib.so")
if len(sys.argv) == 2:
print lib.fib(int(sys.argv[1]))
else:
print "Please enter a parameter"
実行:
9.88 sで、明らかに純Python版より速いが、純C版と3倍ほど差がある.
Python+bitey版を見てみましょう.
#!/usr/bin/env python
#fib_bitey.py
import sys
import bitey
import fib
if len(sys.argv) == 2:
print fib.fib(int(sys.argv[1]))
else:
print "Please enter a parameter"
実行:
6.58 sでctypes版より良い点がわかりますが、純C版よりは悪いですが、もういいです.clang+llvmのおかげだと思います.
では、純粋なPython版がなぜこんなに遅いのかを分析してみましょう.
fibに対して331160281回呼び出されたことがわかり、遅くなくても正常ではないことが分かった.Fibonacci数列の特徴に基づいて、前回の計算後の結果を記録する方法を考えることができ、例えばf(10)を計算し、計算したf(9)とf(8)の結果を再帰せずに直接返すことができる.ちょうどPythonアクセサリーは前回計算した結果を記録するのに使えますが、Pythonアクセサリーの使用についてはPythonアクセサリーと切面向けプログラミングを見てください.
Pythonアクセサリー版:
#!/usr/bin/env python
#fib_cache.py
import sys
def cache(fib):
temp = {}
def _cache(n):
if n not in temp:
temp[n] = fib(n)
return temp[n]
return _cache
@cache
def fib(n):
if n < 2:
return n
else:
return fib(n-2) + fib(n-1)
if len(sys.argv) == 2:
print fib(int(sys.argv[1]))
else:
print "Please enter a parameter"
実行:
使用時間0.02 s、純C版より150倍以上速い!これがデコレーション処理後の効果で、Cも結果をキャッシュできるが、Pythonのような簡単明瞭な方法よりは複雑すぎる.
まとめ:pythonの処理速度を向上させる場合、boost/ctypes/biteyでc/c++書き込みモジュールを呼び出したり、cythonでコンパイルしたりすることができますが、最終的には言語自体の特性を利用してアルゴリズムを最適化するのが王道です.