suzu6階乗を求める計算を３種類用意して速度比較をします。 Python３では、（nの大きさにもよりますが）再帰とfor文がほぼ同じ速度となりました。 ただし、有名な計算であれば最適化されたモジュールがあるはずですので、そちらを使いましょう。
階乗
正の整数nに対して1からnまでの整数を全てかけあわせたものをnの階乗と言い，n! で表します。
例
- 1!=1
- 2!=2×1=2
- 3!=3×2×1=6
- 4!=4×3×2×1=24
ただし、0! = 1とする
プログラムを書くときの考え方としては、 2からnまで（もしくはnから2まで）値を１ずつ変えながら掛け合わせていければ良いです。
for文
def for_factorial(n):
val = 1
for i in range(2, n + 1):
val *= i
return val
print(for_factorial(0))
# => 120
print(for_factorial(0))
# => 1
2からnまで順番に掛け合わせます。
n=0のとき、range(2,1) = []と空のリストになるためfor内が計算されずvalの初期値1が返ります。
再帰関数
def re_factorial(n):
if n < 2:
return 1
return n * re_factorial(n-1)
print(re_factorial(0))
# => 120
print(re_factorial(0))
# => 1
再帰関数ではn * (n-1)を返すようにします。
n < 2のとき1を返せばn=0にも対応できます。
print(re_factorial(1000))
# RecursionError: maximum recursion depth exceeded in comparison
n=1000とすると再帰回数の上限を超えてエラーになりました。
import sys
sys.setrecursionlimit(100000)
print(re_factorial(1000))
# => 4023872600770937735437024339230039857193748642107...........
そんな時は、sys.setrecursionlimit()を使って上限を増やしましょう。
math.factrial
import math
print(math.factorial(5))
# => 120
print(math.factorial(0))
# => 1
一番良いのは、math.factrialを使うことです。
内部処理が最適化されているため、自作するよりも良い速度です。
print(math.factorial(-10))
# ValueError: factorial() not defined for negative values
print(math.factorial(3.14))
# ValueError: factorial() only accepts integral values
しかも、負の値や少数を入力チェックもあり、エラーで教えてくれます。 自分でここまで作るのは大変なので、素直に先人からの恩恵に預かりましょう。
速度の比較のための準備
速度を比較するため、計算速度を測る関数を作りました。
import time
def speed(func, loop, n):
t = 0.0
for _ in range(loop):
start = time.time()
func(n)
t += time.time() - start
return t / loop
関数をコールバック関数として渡し、繰り返し計算した速度の平均値を返します。
N = 100
L = 100
print(speed(math.factorial, L, N))
print(speed(for_factorial, L, N))
print(speed(re_factorial, L, N))
使い方はこんな感じ。
計算速度の結果
| 関数 | 計算時間(ミリ秒) ※ | math.factorial()を1とした比率 |
|---|---|---|
| math.factorial | 3.33 | 1 |
| for_factorial | 24.4 | 7.32 |
| re_factorial | 28.9 | 8.67 |
※n=1000として100回計算した平均
math.factorialは、他に比べ７倍以上早い!! nが小さい場合は、さらに2桁程の差があります。 使わない理由がありませんね。
意外だったのは、再帰関数がfor文により遅いことです。 どうやら、はじめに領域を確保するfor文に対し、逐次領域を確保する再帰関数は遅くなるようです。 再帰回数の上限もあるため、使い方に気をつけましょう。
参考
こちらもどうぞ
Pythonを初めて学ぶ方へオススメの本です！
Mac、Windows環境の整え方から手を動かして実行できるようになっていきます。
合わせてオンライン学習も進めるとより理解が深まると思います。
Pythonコース
Python3の入門オンライン講座