#3 総和の処理と速度の違い

１〜nまでの総和の求め方は高校でシグマ計算で習います。

$$
\sum k = \frac{1}{2} n(n+1)
$$

ですが、プログラムで求める場合は、基本的に順に足していけば良いです。
しかし、たかが総和ですが、さまざまな求め方があり、それによって処理速度が変わってくるのを確かめようと思います。

今回は総和を求める関数を8種類用意します。

def sum1(n):
	return n*(n+1)/2

def sum2(n):
	total = 0
	for i in range(1,n+1):
		total+=i
	return total

def sum3(n):
	if n==1:
		return 1
	else:
		return sum3(n-1) + n

def sum4(n):
	return sum(range(1,1+n))

def sum5(n):
	return sum(list(i for i in range(1,n+1)))

def sum6(n):
	return sum([i for i in range(1,n+1)])

def sum7(n):
	return reduce(add,range(1,n+1))

def sum8(n):
	return reduce(lambda x, y:x+y,range(1,n+1))

それぞれ説明します。

sum1はシグマの公式です。

def sum1(n):
	return n*(n+1)/2

sum2は単純にfor文で繰り返し足していく処理です。
一般的にはこの処理の仕方でプログラムすることが多いでしょう。

def sum2(n):
	total = 0
	for i in range(1,n+1):
		total+=i
	return total

sum3は再帰関数を使って足していく方法です。
繰り返し処理をfor文ではなく自身の関数で繰り返していきます。

def sum3(n):
	if n==1:
		return 1
	else:
		return sum3(n-1) + n

sum4はsum関数とrangeを用いて総和を求める方法です。

def sum4(n):
	return sum(range(1,1+n))

sum5はリスト関数からfor文を用いてsumを使っていきます。

def sum5(n):
	return sum(list(i for i in range(1,n+1)))

sum6は基本的なリスト内包表記を用いてのsum関数で総和求めます。

def sum6(n):
	return sum([i for i in range(1,n+1)])

sum7はreduce関数とadd関数を用いて総和を求めます。

def sum7(n):
	return reduce(add,range(1,n+1))

sum8はreduce関数とlambda関数による総和の求め方です。

def sum8(n):
	return reduce(lambda x, y:x+y,range(1,n+1))

測定方法

今回の測定方法は１からnまでの総和の処理時間を求めます。
このとき、nまで足す数を10、100、1000、10000、100000、1000000とした時の処理時間を求めます。

処理結果

列をn、行を各関数として値を処理時間のピボットテーブルで結果を示します。
nが100まではほぼ違いはありません。
nが1000から違いが見え始めます。
sum3の処理時間が指数関数的に伸びていきます。
これは再帰関数を使っているからですね。
逆にnが増えても処理時間の増加が抑えられているのはsum1の総和の公式です。
単純にfor文の繰り返しで足すわけでもなく、一度公式に当てはめて計算するだけですので早いですね。
計算オーダーで言えば、O(1)ですからね。
同様にsum関数とrangeで構成されているsum4も処理時間はんを増やしても速いです。
そのほかは基本的に繰り返し足していく処理で、多少ブレがあれど大体同じくらいの処理時間です。
グラフでみると指数関数的に処理時間が増える再帰関数による求め方により、nが1000000まで違いが見にくくなっていますが、クロス集計では先ほども述べたようにんが1000から処理時間に違いが見え始め、最も速い処理と遅い処理との間には15倍くらいの差があります。
ただ総和を求めると言っても求め方によって結構変わってくるのがわかったではないでしょうか？
実際に使う際はただ早ければいいと言うものではなく、可読性や処理時間に制約があるかなどでどの方法が良いかは変わります。
基本的にはどの方法でも問題ないと思いますが、処理の仕方ひとつで処理速度が何倍も変わってくることは頭に入れておくとよいでしょう。

処理時間結果

処理時間散布図

まとめ

総和を求めるコードを８種類用意してそれぞれの処理の処理時間を計測して違いを見ました。
結果から再帰関数による処理は遅く、公式による計算で求める方法が最も速いことがわかりました。
その他の宗和の求め方でも処理時間がどうなるか実験してみるとおもしろいかもしれません。

処理コード

今回の処理コードはこちらです。
実際に処理して、時間計測した部分のコードも載せているので参考になれば幸いです。
コードは下記をコピペすれば動きます。
末尾に有料ですが、下記コードのpythonファイルをダウンロードできます。

import time as t
import matplotlib.pyplot as plt
from functools import reduce
from operator import add
import sys

sys.setrecursionlimit(10000001)

def sum1(n):
	return n*(n+1)/2

def sum2(n):
	total = 0
	for i in range(1,n+1):
		total+=i
	return total

def sum3(n):
	if n==1:
		return 1
	else:
		return sum3(n-1) + n

def sum4(n):
	return sum(range(1,1+n))

def sum5(n):
	return sum(list(i for i in range(1,n+1)))

def sum6(n):
	return sum([i for i in range(1,n+1)])

def sum7(n):
	return reduce(add,range(1,n+1))

def sum8(n):
	return reduce(lambda x, y:x+y,range(1,n+1))

if __name__ == "__main__":
	start = t.time()
	nllist = [10,100,1000,10000,100000,1000000]
	print('n function result time')
	print('-----------------------------------------------------')
	for i in nllist:
		print(i, ' sum1 ', sum1(i), " {:03f}".format(t.time()-start))
		start = t.time()
		print(i, ' sum2 ' , sum2(i) , "{:03f}".format(t.time()-start))
		start = t.time()
		print(i, ' sum3 ' , sum3(i) , "{:03f}".format(t.time()-start))
		start = t.time()
		print(i, ' sum4 ' , sum4(i) , "{:03f}".format(t.time()-start))
		start = t.time()
		print(i, ' sum5 ' , sum5(i) , "{:03f}".format(t.time()-start))
		start = t.time()
		print(i, ' sum6 ' , sum6(i) , "{:03f}".format(t.time()-start))
		start = t.time()
		print(i, ' sum7 ' , sum7(i) , "{:03f}".format(t.time()-start))
		start = t.time()
		print(i, ' sum8 ' , sum8(i) , "{:03f}".format(t.time()-start))

sigma_sum.py

1.4 KB

ファイルダウンロードについて

ダウンロード