アメリエフのブログ

Amelieff Staff Blog

pythonで重い計算の実行時間を減らす発想

こんにちはhr-kです
今回はちょこっとだけ(僕の独断と偏見に基づいた)プログラミングの基本思想についてお話ししようと思います。

プログラムを書く時一番重要なのは「正しく動くこと」です。
ただなんとなく計算するにしても、研究に使うにしても、思った通りのアルゴリズムで動かないようでは結局意味がないのです。
ここまでは比較的みんなできます。

次に大事なのが、「現実的に待てる時間内に計算を終えられること」ですね。
どんなに正しい計算でも100万年かかっても終わらないようではお話にならないのです。
今回はこっちの「現実的な時間内に計算を終える」ということについて簡単に見ていこうと思います。

例えばこんな感じで

str_int_list1 =['1', '2', '3', '4', ......, '999998', '999999', '1000000']  
str_int_list2 = ['2', '4', '6', ......, '999996', '999998', '1000000']  

というような要素がそれぞれ100万個ずつある二つのリストがあったとき、何も考えずにこの二つの共通する部分を取ってくるとすると

union_list = []  
for I in str_int_list1:  
    for j in str_int_list2:  
        if i == j:  
            union_list.append(i)  
print(union_list)  

となります。はい、この時の計算回数は〜1兆回を超えますね〜
だいたい最近のコンピュータのCPUは数GHz程度の速度なので、この程度の計算に数分かかってしまうのです。
これ、リストに含まれる数が倍だとその分時間がかかるようになっていくので、ちょっと要素数が多いだけでも二重ループとか書いちゃうと計算速度は致命的なわけです。

これをサクッと終わるようにするにはどうするか。
ここで考えるのは如何にループを用いた計算しないで値を取ってこれるか。
今回は一致とか共通部分が取れればいいので、実はループなんてなくてもさくさくっと計算できるのです。

# listをsetに  
int_set1 = set(str_int_list1)  
int_set2 = set(str_int_list2)  
# setの共通部分を取り出す  
union_set = int_set1 & int_set2  

はい、loopすらしてないですね。
今回はsetを使って集合とみなして、その共通部分を取るって形でサクッと取ってきました。
それぞれの環境で実行してもらうと分かりますが、実行速度は雲泥の差があります。

正確なアルゴリズムができたら、こんな感じででできるだけループは減らして、現実的に実行を待てるタイムスケールになるように高速化していくのです。
自分で書いてるコードが遅いって感じたらちょっとこの記事にあるように、ループの中でループ回してるところとか、注意してみてあげてくださいね。
そして、自分が使ってるコードから無駄に計算時間を食ってしまっている部分を取り除いていくのです。そうすれば、(相当複雑な計算じゃない限り)だいたいの計算は待てるくらいのタイムスケールに収まるようになります。

高速化はもっと深淵に入っていく話もありますが、今回はこの辺で!