2015年10月7日水曜日

デフォPython高速化

Python2x系で数値読み込みループにinput()は使うな!

何故かと言うとinput()は式を求めているから。

数値を直接得るのに【 num=input() 】はメジャーな使い方である。
だが、これを数千数万とループで受ける場合話は別である。

最初に述べた通りinput()は式を求められている。
「つまりどういうこと?」と言う話だが
【 input() 】=【 eval(raw_input()) 】なのである。

たとえば300,000回程度forで数値入力の読み込みループを行い配列で受ける場合

=input()約2.1秒
=eval(raw_input())約2.1秒
=int(raw_input())約0.5秒

かなりおおざっぱな検証だがこれくらい差がでる。
【 input() 】と【 eval(raw_input()) 】が同じなのは同等の処理を行っているから当然の結果。
【 input() 】と【 int(raw_input()) 】では【 input() 】の方が簡潔に見えるが行わる処理は遠まわりしている事になる。
結果的に2倍以上の差が発生する。
※ちなみにintでは端数切捨てなのでそこは注意。


そもそも読み込みループを行うな!

何故かと言うとPython自体がもうループ処理自体が遅い。
「じゃぁどうするんだよ!」確かにそう言うのも仕方がない。

だが標準入力はほかにもある事を思い出してほしい。
具体的にはには以下のようにする。

import sys
mylist=list(map(int, sys.stdin.read().splitlines()))

readで連続で受け取りsplitlinesで分割。それをさらにmapを使い一括でintに変換する。
どれくらい早くなるのかというと

約0.17秒!int(raw_input())のさらに倍以上早い。
ただし、これは実際のケースではそんなにないのではないかと思う。
この問題に気付かされたのはPOHなので課題専用処理と言っていい。


ループはwhileよりもforを使え!

ループ回数が増える程whileよりもforのほうが処理速度が速い。
処理は処理として使いやすい方を使うのが正しいが処理速度がどうしても欲しい場合whileで行っている処理をforに置き換える事を検討すると良い。



リスト化はリスト内包を使え!

通常forでリストを追加する場合appendをチェックしている。
だがリスト内包を使った場合はリスト化前提の為その処理がない分速い。
しかもその処理時間は6割程度違う。つまり、通常forでリスト化して10秒ならリスト内包なら4秒で終わらせる事が出来る。

とにかく要素追加が遅いという事。逆にリスト等の要素追加でなければここまで差はでない。
ただしmap等forすら回さなくて良い場合はそちらの方が速い。

ループカウンタが不要なら[None]*数値を使え!

forの構造上値を渡しながらループする事になる。
通常であれば
【 for x in range(数値) 】だが、それよりも
【 for x in[0]*数値 】の方が速く、さらにそれよりも
【 for x in[None]*数値 】とした方が速い。

あくまでも大量のループを回すときにに空のリスト生成の方が速いという事。
ただし、rangeと[0]では割とさが出る様だが[0]と[None]では大きな差は無い。

ソートするならlist.sort()を使え!

自身を並べ替える為list.sort()はsorted()よりも若干ですが効率が良いです。
list.sort()の戻り値はNoneでsorted()との混乱を回避する為らしい。
といっても受けた値をソートできる為sorted()使っちゃうよなぁ。







後で追記する

0 件のコメント:

コメントを投稿