最近やっていること
スタッフ紹介の記事にも書いたのですが、最近Pythonの勉強をしています。
(業務でというより趣味で)
PHPのようなWebアプリケーションの開発をしたいわけではなく、
統計解析(ベイズ)がやりたいということもあり、いつもとは勉強の入り口を変えてみました。
使っている本はこれ。
Pythonではじめるアルゴリズム入門 伝統的なアルゴリズムで学ぶ定石と計算量
せっかくなので『アルゴリズム』から切り込んでみました。
これが結構面白いです。例えば、素数の洗い出し。
今回は、100,000までの素数を２つの方法で洗い出し、その処理速度の違いを紹介したいと思います。
素数を出力するアルゴリズム
パターン1
小さい方から割り切れるかどうか順番にチェックする
import math
import time
def is_prime(n):
# nが1以下であれば処理をする必要はない(1以下は素数ではない)
if n <= 1:
return False
# range(start, stop)
# iの平方根から先の約数は折り返しとなるので評価する必要はない(6の場合なら2*3と3*2みたいに)
for i in range(2, int(math.sqrt(n) + 1)):
if n % i == 0:
return False
return True
# 【Python】処理にかかる時間を計測して表示を参照
# 処理の開始と終了を記録し処理時間を計算
if __name__ == '__main__':
start = time.time()
for i in range(100000):
if is_prime(i):
print(i, end=' ')
elapsed_time = time.time() - start
print ("\n" + "elapsed_time:{0}".format(elapsed_time) + "[sec]")
パターン2
エラトステネスの篩(ふるい)
import math
import time
def get_prime(n):
# nが1以下であれば処理をする必要はない
if n <= 1:
return False
# 最小の素数である2が入った素数リストを準備
prime = [2]
# 処理の上限は対象の数の平方根まで
limit = int(math.sqrt(n))
# range(start, stop, step)
# nまでの奇数のリストを作成する -> 偶数は素数ではないので対象外
data = [i + 1 for i in range(2, n, 2)]
# 上限 >= 奇数リストの先頭(繰り返し処理の中で再生成される)
while limit > data[0]:
# 素数リストに奇数の先頭要素を追加
prime.append(data[0])
# 奇数リストのうち、先頭の奇数で割り切れないもので奇数リストを再生成
data = [j for j in data if j % data[0] != 0]
return prime + data
# 【Python】処理にかかる時間を計測して表示を参照
# 処理の開始と終了を記録し処理時間を計算
if __name__ == '__main__':
start = time.time()
print(get_prime(100000))
elapsed_time = time.time() - start
print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")
で、計測結果は・・・
パターン1 : elapsed_time:1.7766509056091309[sec]
パターン2 : elapsed_time:0.08391904830932617[sec]
『圧倒的ではないか』って声が聞こえてきそうな差です。
おわりに
webサイトの表示速度は大切な指標の1つであり、処理速度の改善ってのは永遠の課題です。
プログラムの書き方やMySQLの切り方(N+1問題など)が大事になってきますし、
普段の業務でも常に「処理速度」を意識してプログラムを書いていきたいと改めて思いました。
作っているときはどうしても独りよがりになりがちなので、その点も注意です。
次はフィボナッチ数列!!
再帰処理か。。。
