計算に用いたソースコード
中身の説明はコメントで書いたので、そちらを参考にしてください
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言語には計算速度の面で勝てないという事がわかりました。
.png)
0 件のコメント:
コメントを投稿