処理速度を向上させる その2 悪霊のアルゴリズム々

| | Comments (0) | TrackBacks (0)
こんにちは。

前回の続きです。

以前作ったコードを動かしてみました。


速度測定には-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のコストが大きいか、新たな辞書登録のコストが大きすぎたかのいずれかでしょう。おそらく。
 

 しかし、素数かどうかを記録しておくのは、無駄な数で割り算するより、速くなりそうな気がします。
 
 

0 TrackBacks

Listed below are links to blogs that reference this entry: 処理速度を向上させる その2 悪霊のアルゴリズム々.

TrackBack URL for this entry: http://lab.hde.co.jp/blog/mt-tb.cgi/172

Leave a comment

About this Entry

This page contains a single entry by shiota published on October 13, 2010 10:00 AM.

処理速度を向上させる その1 was the previous entry in this blog.

処理速度を向上させる その3 そして速度向上へ is the next entry in this blog.

Find recent content on the main index or look in the archives to find all content.