最近やっていること
スタッフ紹介の記事にも書いたのですが、最近Pythonの勉強をしています。
(業務でというより趣味で)
PHPのようなWebアプリケーションの開発をしたいわけではなく、
統計解析(ベイズ)がやりたいということもあり、いつもとは勉強の入り口を変えてみました。
使っている本はこれ。
Pythonではじめるアルゴリズム入門 伝統的なアルゴリズムで学ぶ定石と計算量
せっかくなので『アルゴリズム』から切り込んでみました。
これが結構面白いです。例えば、素数の洗い出し。
今回は、100,000までの素数を2つの方法で洗い出し、その処理速度の違いを紹介したいと思います。
素数を出力するアルゴリズム
パターン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問題など)が大事になってきますし、
普段の業務でも常に「処理速度」を意識してプログラムを書いていきたいと改めて思いました。
作っているときはどうしても独りよがりになりがちなので、その点も注意です。
次はフィボナッチ数列!!

再帰処理か。。。