Atcoder python プログラミング 競技プログラミング

【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で定義されている関数だからみたいです。

(詳しくは下記のリンク参照)

9.2. math — 数学関数 — Python 3.6.5 ドキュメント

競技プログラミングでは積極的に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言語には計算速度の面で勝てないという事がわかりました。