階乗の計算速度を比較 | Python

階乗を求める計算を3種類用意して速度比較をします。 Python3では、(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まで)値を1ずつ変えながら掛け合わせていければ良いです。

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.factorial3.331
for_factorial24.47.32
re_factorial28.98.67

※n=1000として100回計算した平均

math.factorialは、他に比べ7倍以上早い!! nが小さい場合は、さらに2桁程の差があります。 使わない理由がありませんね。

意外だったのは、再帰関数がfor文により遅いことです。 どうやら、はじめに領域を確保するfor文に対し、逐次領域を確保する再帰関数は遅くなるようです。 再帰回数の上限もあるため、使い方に気をつけましょう。

参考

こちらもどうぞ


Pythonを初めて学ぶ方へオススメの本です!
Mac、Windows環境の整え方から手を動かして実行できるようになっていきます。

合わせてオンライン学習も進めるとより理解が深まると思います。

Pythonコース

Python3の入門オンライン講座


Placeholder image

すずろく/suzu6

札幌にいるWEBアプリのエンジニア。最近はテストをもっと書きたい。

@suzu6_py Amazon ほしいものリスト

 関連記事

 新着 or 更新記事