【Python】for文を使った場合とmath.factorialを使った場合の階乗計算の速度比較

Atcoder ABC_055 B - Training Campは階乗を求める問題なのですが、for文を使って階乗を求めたらTLEになってしまいました。他の方の提出例を見るとmathをimportしてfactorialというものを利用しており、この2つの計算速度がどのくらい変わるのか気になったので、比較を行いました。

計算に用いたソースコード

中身の説明はコメントで書いたので、そちらを参考にしてください
import time
import math
import matplotlib.pyplot as plt
import seaborn
n = int(input())
time_cal_factorial1 = []
ans_cal_factorial1 = []

time_cal_factorial2 = []
max_time1=0
max_time2=0
for i in range(1,n+1,10): #N = 1~nまで計算時間を求める
#for文で求めた場合
#--------------------------------------------------------------------------------------------------------------------
    ans = 1
    start1 = time.time()
    for j in range(1,i+1):
        ans *= j
    cal_time1 = time.time()-start1
    time_cal_factorial1.append(cal_time1)
#--------------------------------------------------------------------------------------------------------------------

#for文で求めた場合の最大処理時間
#--------------------------------------------------------------------------------------------------------------------
    if max_time1<cal_time1:
        max_time1=cal_time1
#--------------------------------------------------------------------------------------------------------------------

#math.factorialを使って求めた場合
#--------------------------------------------------------------------------------------------------------------------
    start2 = time.time()
    math.factorial(i)
    cal_time2 = time.time() - start2
    time_cal_factorial2.append(cal_time2)
#--------------------------------------------------------------------------------------------------------------------

#for文で求めた解とmath.factorialを使って求めた解が異なる場合値を出力し、終了
#--------------------------------------------------------------------------------------------------------------------   
    if ans != math.factorial(i):
        print("Wrong answer")
        print("i="+str(i))
        print("for="+str(ans))
        print("math="+str(math.factorial(i)))
        exit()
#--------------------------------------------------------------------------------------------------------------------    

#math.factorialで求めた場合の最大処理時間
#--------------------------------------------------------------------------------------------------------------------
    if max_time2<cal_time2:
        max_time2=cal_time2
#--------------------------------------------------------------------------------------------------------------------

#計算結果の出力
#--------------------------------------------------------------------------------------------------------------------
plt.plot(range(1,n+1,10),time_cal_factorial1,label ="for")
plt.plot(range(1,n+1,10),time_cal_factorial2,label = "math")
plt.legend()
plt.show()

print(max_time1)
print(max_time2)
#--------------------------------------------------------------------------------------------------------------------

とりあえず計算時間の差が知りたかっただけなので、色々適当です。

計算結果

n=100000として計算時間を求めたものが下の図です
for文の場合、最大計算時間は3.44秒だったのに対してmath.factorialで計算をした場合は最大でも0.24秒でした。なので、math.factorialで計算した方が約15倍程度計算時間が早いということが分かります。

また、最初に紹介した問題は2秒以上かかるとTLEとなってしまうので、for文ではダメだということが分かります。

ちなみにmath.factorialがなんで早いか調べてみたら、Cで定義されている関数だからみたいです。
(詳しくは下記のリンク参照)

競技プログラミングでは積極的にmathを使っていった方がよさそうですね。

補足(2021/04/12追記)

C言語で階上計算を実施した場合の計算時間を算出しました。こちらはAtcoderの問題に合わせて10^9 + 7 で割ったあまりとしているの為、あくまで参考です。
(C言語苦手なので、描画はできなかったです。。。)
また、一部余計なコメントが入ってますが、Atcoderのページに提出しACするか確認するためのコードなので、無視してください。

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
int main(void)
{
    int n = 1000000
    long long int ans = 1;
    // int n;
//    scanf("%d",&n);
    int max_time = 0;
    int max_n = 0;
    clock_t start,end;    
    for(int i = 1; i <= n; i +=10 ){
        start = clock();
        for (int j = 1; j <= n ; j++){
            ans =  ans * j % 1000000007;
        } 
        end = clock();
        if (max_time < end - start){
            max_time = end -start;
            max_n = i;
        }
        ans = 1;
    
    }
    printf("最大時間:%d[ms]、最大時間時のnの値:%d",max_time,max_n);   
    printf("%lld",ans % 1000000007);
}



最適化オプションを何も使わない場合のメッセージ
最大時間:171[ms]、最大時間時のnの値:2774311

-O2オプションを使った場合の出力メッセージ
最大時間:1[ms]、最大時間時のnの値:7802711

pythonのmath.factorialは最適化オプションを使わないC言語と同じくらいですかね?
Atcoderは-O2オプションを使っているみたいなので、math.factorialを使ってもC言語には計算速度の面で勝てないという事がわかりました。

0 件のコメント :

コメントを投稿