#4 階乗を再帰関数とループ処理で実装した時に処理時間とメモリ消費量を比較してみた。

#3の総和の処理の仕方で再帰関数は処理が遅くなることを指摘しました 。
今回はこの処理時間とメモリ使用量に着目して、再帰関数とループ処理でどのように変わるか分析します。

階乗とは？

数学において自然数 n の階乗（かいじょう、英: factorial）n ! とは、1 から n までの全ての整数の積のことである。

Wikipedia

階乗 - Wikipedia

ウィキペディアを引用しました。
数学の高校一年で習います。
1からnまで掛けた値です。

コード

今回使用するコード全文はこちら。
主に階乗を求める関数、メモリ使用量を計測する関数、計測用の処理はメイン作成しました。
結果はリストに格納し、グラフで描画します。

import time as t
import matplotlib.pyplot as plt
import tracemalloc

def factorial(n):
	if n==0:
		return 1
	else:
		return factorial(n-1)*n
	
def factorial_loop(n):
	for i in range(n-1,0,-1):
		n=n*i
	return n
	
def memory_test_fact(n):
	tracemalloc.start()
	factorial(n)
	first_size,first_peak = tracemalloc.get_traced_memory()
	tracemalloc.reset_peak()
	return first_size,first_peak
	
def memory_test_loop(n):
	tracemalloc.start()
	factorial_loop(n)
	first_size,first_peak = tracemalloc.get_traced_memory()
	tracemalloc.reset_peak()
	return first_size,first_peak
	
	
if __name__=='__main__':
	a=[]
	n=[]
	b=[]
	for i in range(1,100):
		start=t.time()
		factorial(i)
		a.append(t.time()-start)
			
		start=t.time()
		factorial_loop(i)
		b.append(t.time()-start)
		
		n.append(i)
	#print(n,a,b)
	
	plt.plot(n,a,label='factorial')
	plt.plot(n,b,label='loop')
	plt.legend()
	plt.show()
	
	fact_memsize=[]
	loop_memsize=[]
	fact_peaksize=[]
	loop_peaksize=[]
	x=[]
	
	for i in range(1,100):
		fs,fp=memory_test_fact(i)
		ls,lp=memory_test_loop(i)
		
		fact_memsize.append(fs)
		loop_memsize.append(ls)
		fact_peaksize.append(fp)
		loop_peaksize.append(lp)
		x.append(i)
		
	plt.clf()
	plt.plot(x,fact_memsize,label='factorial')
	plt.plot(x,loop_memsize,label='loop')
	plt.ylabel('mem size')
	plt.legend()
	plt.show()
	print(x,fact_memsize,loop_memsize)
	
	plt.clf()
	plt.plot(x,fact_peaksize,label='factorial')
	plt.plot(x,loop_peaksize,label='loop')
	plt.ylabel('peak size')
	plt.legend()
	plt.show()
	print(x,fact_peaksize,loop_peaksize)
	

コード解説

コード各処理のブロックごとに説明します。

インポート

使用するライブラリは、時間計測用にtime関数。
グラフ描画用にmatplotlib。
メモリサイズ測定用にtracemallocを使います。

import time as t
import matplotlib.pyplot as plt
import tracemalloc

再帰関数による階乗の処理

簡単に再帰関数を使って階乗を計算する場合はんが０になるまで、nより１少ない値を引数に関数を自身の関数を呼んで掛けていくことで求めます。
階乗を計算するコードと言えばこのコードをよくみるでしょう。
再帰関数の使い方で一緒に出てきます。

def factorial(n):
	if n==0:
		return 1
	else:
		return factorial(n-1)*n

ループによる階乗の処理

階乗はnから１ずつ少ない値を１になるまで掛けていくので、ループでnから１ずつ減らしていきながら掛けても求められます。
ループ処理を1ずつ減らしながら回すことはあまりしないのであまり書籍で出てくることはないです。

def factorial_loop(n):
	for i in range(n-1,0,-1):
		n=n*i
	return n

時間測定するための処理

時間測定する処理はmainメソッドに書いていきます。
処理時間はstart変数に時刻データを取得し、階乗関数を行い、t.time()を再度呼び出し時刻データを取得してstartで引くことで処理時間が取得できます。
処理時間は再帰関数による階乗の処理時間をaのリストにappendで追加します。
同様にループによる処理時間はbのリストに格納していきます。
nの会場のnを変数nのリストに格納していきます。
今回は1~100の階乗の処理時間をそれぞれ計測します。

	a=[]
	n=[]
	b=[]
	for i in range(1,100):
		start=t.time()
		factorial(i)
		a.append(t.time()-start)
			
		start=t.time()
		factorial_loop(i)
		b.append(t.time()-start)
		
		n.append(i)

メモリ使用量の測定するための関数

tracemalloc.start()から関数や処理を行い、tracemalloc.get_traced_memory()でメモリ使用量を取得します。
メモリ使用量はfirst_sizeに現在のメモリサイズ、first_peakにピーク時のメモリサイズを取得します。

tracemalloc --- メモリ割り当ての追跡

def memory_test_fact(n):
	tracemalloc.start()
	factorial(n)
	first_size,first_peak = tracemalloc.get_traced_memory()
	tracemalloc.reset_peak()
	return first_size,first_peak

同様にループ処理による階乗処理のメモリサイズの取得するための関数です。

def memory_test_loop(n):
	tracemalloc.start()
	factorial_loop(n)
	first_size,first_peak = tracemalloc.get_traced_memory()
	tracemalloc.reset_peak()
	return first_size,first_peak

メモリ使用量を計測するための処理

計測時は各階乗の計算に使用したメモリサイズを取得します。
fs,lpに再帰関数による階乗処理に使用したメモリサイズを取得し、ls,lpにループによる階乗処理のメモリサイズを取得します。
各計測したメモリサイズをリストに格納していきます。
fact_memsizeに階乗処理の現在のメモリサイズ、fact_peaksizeに最大のメモリサイズを格納します。
同様にloop_memsizeにループ処理による階乗処理を行った時のメモリサイズ、loop_peaksizeに最大のメモリサイズを格納します。
xに1〜100の数を格納します。
いくつの階乗処理をしているかを記録するために格納しておきます。
グラフ描画時に使います。

	fact_memsize=[]
	loop_memsize=[]
	fact_peaksize=[]
	loop_peaksize=[]
	x=[]
	
	for i in range(1,100):
		fs,fp=memory_test_fact(i)
		ls,lp=memory_test_loop(i)
		
		fact_memsize.append(fs)
		loop_memsize.append(ls)
		fact_peaksize.append(fp)
		loop_peaksize.append(lp)
		x.append(i)

処理時間結果グラフ描画処理

グラフ描画の処理はmatplotlibのplotを使って描画します。

	plt.plot(n,a,label='factorial')
	plt.plot(n,b,label='loop')
	plt.legend()
	plt.show()

メモリサイズ結果描画処理

メモリサイズの結果のグラフ描画処理も同様にmaatplotlibを使用します。

	plt.clf()
	plt.plot(x,fact_memsize,label='factorial')
	plt.plot(x,loop_memsize,label='loop')
	plt.ylabel('mem size')
	plt.legend()
	plt.show()
	print(x,fact_memsize,loop_memsize)
	
	plt.clf()
	plt.plot(x,fact_peaksize,label='factorial')
	plt.plot(x,loop_peaksize,label='loop')
	plt.ylabel('peak size')
	plt.legend()
	plt.show()
	print(x,fact_peaksize,loop_peaksize)

処理結果

まず処理時間ですが、10の階乗までの計算までは処理時間に差はあまりありませんが、20より大きい階乗計算から差が大きくなります。
100の階乗計算では３倍の差があります。

処理時間結果

メモリサイズについては差がほとんどありません。
60の階乗から急激にメモリサイズが増えます。

メモリー使用量

最大メモリは最初の処理の時に取得するメモリサイズの最大が大きくなりますが差はほとんどありません。
メモリサイズに関しては再帰関数もループも大きな違いはありません。

最大メモリ使用量

計算時間には大きく影響はありますが、基本的に同じ計算をしていますのでメモリサイズに違いはありません。
同じ階乗の計算でも処理の仕方で処理時間が大きく変わることが体感できたのではないでしょうか。

参考書籍

アルゴリズムに関する参考書籍を載せておきます。
コードが簡単でわかりやすいので理解しやすいです。

Pythonで学ぶアルゴリズムの教科書 一生モノの知識と技術を身につける

アルゴリズム図鑑 増補改訂版 絵で見てわかる33のアルゴリズム

プログラムDL

本記事で使用したプログラムを販売します。
※コード内容は記事に記載されたものですので、コードをコピペすれば使えます。