[Python]アルゴリズムと処理速度

最近やっていること

スタッフ紹介の記事にも書いたのですが、最近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問題など)が大事になってきますし、
普段の業務でも常に「処理速度」を意識してプログラムを書いていきたいと改めて思いました。

作っているときはどうしても独りよがりになりがちなので、その点も注意です。

次はフィボナッチ数列!!

再帰処理か。。。