速度測定には-m profileオプションを使用しました。
表の見方については、http://docs.python.org/library/profile.html参照
1行目にトータルでどのくらいのCPU時間が使われたかが表示されます。
その後、各関数ごとに呼ばれた回数や処理時間などが出ます。
下記であれば、is_prime()という関数が999999回呼ばれ、合計45.880秒かかっていることが分かります。
---
# python -m profile pe010.py
1000007 function calls in 48.800 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 48.800 48.800 :0(execfile)
1 0.040 0.040 0.040 0.040 :0(range)
1 0.000 0.000 0.000 0.000 :0(setprofile)
1 0.000 0.000 48.800 48.800 <string>:1(?)
1 0.000 0.000 48.800 48.800 pe010.py:1(?)
1 0.000 0.000 0.000 0.000 pe010.py:1(Primes1)
999999 45.880 0.000 45.880 0.000 pe010.py:2(is_prime)
1 2.880 2.880 48.800 48.800 pe010.py:9(pe010_01)
1 0.000 0.000 48.800 48.800 profile:0(execfile('pe010.py'))
0 0.000 0.000 profile:0(profiler)
---
計48.88秒、これが速いのか遅いのか、とりあえずこれよりだいぶ早くすることを目標にします。
なお、状況により速度にばらつきが出ることもあるので、実際に行う場合は何度か測定します。
処理内容を変える前に、品質担保をしておくことが重要です。
「速く終わるようになったけど正常な動作でなくなった」となると意味がありません。
今回は、「答えが正解であること」で正常動作と判断することにします。
上記に表示されているtottimeを基準に、速度向上対象を決めます。
999999 45.880 0.000 45.880 0.000 pe010.py:2(is_prime)
↑こいつが半分の速度になれば、23秒くらい削減(全体の47%削減)できそうです。
1 0.040 0.040 0.040 0.040 :0(range)
↑こういうものを半分にしても、0.02秒(全体の0.1%未満)くらいしか削減できません。そのうち対象とするかもしれませんが、今は放っておきます。
削減できる処理がないか眺めてみました。
素数は、2以外は奇数です。
素数を判定する際、2で割りきれないのに4で割り切れるか試すことは、意味がないことです。
ということで、奇数だけで割り算するようにしてみました。
----
class Primes2:
def is_prime(self,number):
if number == 2:return True
if not number % 2:return False
i=3
while number >= i*i:
if not number % i: return False
i+=2
return True
----
結果、21.450秒削減できました。
------
# python -m profile pe010.py
1000008 function calls in 27.430 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 27.430 27.430 :0(execfile)
1 0.030 0.030 0.030 0.030 :0(range)
1 0.000 0.000 0.000 0.000 :0(setprofile)
1 0.000 0.000 27.430 27.430 <string>:1(?)
1 0.000 0.000 27.430 27.430 pe010.py:1(?)
1 0.000 0.000 0.000 0.000 pe010.py:1(Primes1)
1 2.800 2.800 27.430 27.430 pe010.py:18(pe010_01)
1 0.000 0.000 0.000 0.000 pe010.py:8(Primes2)
999999 24.600 0.000 24.600 0.000 pe010.py:9(is_prime)
1 0.000 0.000 27.430 27.430 profile:0(execfile('pe010.py'))
0 0.000 0.000 profile:0(profiler)
-----
2以外でも素数と分かったものだけで割り算したほうが早いだろうということから、素数と分かったものは辞書を使って記憶するようにしてみました。
----
class Primes3:
def __init__(self):
self.prime = {}
def is_prime(self,number):
if number < 2: return False
for i in self.prime.keys():
if not number % i : return False
self.prime[number] = True
return True
----
結果、終わりませんでした。つまり遅くなりました。
これは、keysのコストが大きいか、新たな辞書登録のコストが大きすぎたかのいずれかでしょう。おそらく。
しかし、素数かどうかを記録しておくのは、無駄な数で割り算するより、速くなりそうな気がします。
Leave a comment