処理速度を向上させる その3 そして速度向上へ

| | Comments (0) | TrackBacks (0)

前回、速度を向上させるため、素数を記憶しようということをやりましたが、失敗しました。

今回は、「どうせ記憶するなら全数記憶してみればいいんじゃないか?」という発想のもと、処理速度改善を行ってみます。



あらかじめ対象とする数まで計算し、素数かどうかをリストに記憶します。その後、素数判定の際に対応するリストの値がTrueかFalseかで素数判定を行うことにします。
---
class Primes35:
  def __init__(self):
    self.prime = [False,False]
  def is_prime(self,number):
    return self.prime[number]
  def ert(self,max):
    self.prime += (max-1) * [True]
    import math
    for p in range(2,int(math.sqrt(max))+1):
      if not self.prime[p]: continue
      for q in range(p+1,max):
        if not q % p:
          self.prime[q] = False
---

なお、呼び出し部分にも一行追加しました。
--
if __name__ == '__main__':
  max = 2*(10**6)
  p = Primes35()
  p.ert(max)
  print pe010_01(p,max)
--

結果、88.120秒。以前より遅くなりました。
しかし、素数判定部分(is_prime)の目覚ましい速度向上は見てとれます。記憶しておけば、その後の判定は速くなるというのは間違いないようです。

----
         1000242 function calls in 88.120 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000   88.120   88.120 :0(execfile)
      225   10.710    0.048   10.710    0.048 :0(range)
        1    0.000    0.000    0.000    0.000 :0(setprofile)
        1    0.000    0.000    0.000    0.000 :0(sqrt)
        1    0.000    0.000   88.120   88.120 <string>:1(?)
        1    0.000    0.000   88.120   88.120 pe010.py:1(?)
        1    0.000    0.000    0.000    0.000 pe010.py:1(Primes1)
        1    0.000    0.000    0.000    0.000 pe010.py:108(Primes8)
        1    2.170    2.170    4.230    4.230 pe010.py:129(pe010_01)
        1    0.000    0.000    0.000    0.000 pe010.py:18(Primes3)
        1    0.000    0.000    0.000    0.000 pe010.py:30(Primes35)
        1    0.000    0.000    0.000    0.000 pe010.py:31(__init__)
   999999    2.040    0.000    2.040    0.000 pe010.py:33(is_prime)
        1   73.200   73.200   83.890   83.890 pe010.py:35(ert)
        1    0.000    0.000    0.000    0.000 pe010.py:44(Primes4)
        1    0.000    0.000    0.000    0.000 pe010.py:58(Primes5)
        1    0.000    0.000    0.000    0.000 pe010.py:71(Primes6)
        1    0.000    0.000    0.000    0.000 pe010.py:8(Primes2)
        1    0.000    0.000    0.000    0.000 pe010.py:86(Primes7)
        1    0.000    0.000   88.120   88.120 profile:0(execfile('pe010.py'))
        0    0.000             0.000          profile:0(profiler)
----

課題はリスト作成部分、ert()の速度向上方法がないかどうかを探してみます。


ここで、リスト作成時に素数判定の割り算が効率悪いことに気がつきました。

たとえば、77が素数かどうかを判定するのに
77 % 2 => 1
77 % 3 => 2
77 % 5 => 2
77 % 7 => 0  not 素数

となるとすると、2,3,5で割り算をしている部分が無駄そうです。
ここを削減できれば、大きな数の素数の場合等に効果が大きそうです。

これは、エラトステネスの篩と呼ばれる手法で削減できます。エラトステネスの篩とは、リストの中の素数の倍数を除いていくことにより、素数だけを洗い出す手法です。全数リストを作ろうという発想なのだから、このほうが効率がいいです。

「割り算がだめなら掛け算すればいいじゃない」
エラトステネスの言葉が脳内で聞こえました。

---
class Primes4:
  def __init__(self):
    self.prime = [False,False]
  def is_prime(self,number):
    return self.prime[number]
  def ert(self,max):
    self.prime += (max-1) * [True]
    i=2
  for i in range(2,int(math.sqrt(max))+1):
      if self.prime[i]:
        for n in range(i*2,max+1,i):
          self.prime[n] = False
      i+=1
---

結果、5.660秒と、以前の5分の1の時間になりました。
---
         1000240 function calls in 5.660 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    5.660    5.660 :0(execfile)
      224    0.120    0.001    0.120    0.001 :0(range)
        1    0.000    0.000    0.000    0.000 :0(setprofile)
        1    0.000    0.000    5.660    5.660 <string>:1(?)
        1    0.000    0.000    5.660    5.660 pe010.py:1(?)
        1    0.000    0.000    0.000    0.000 pe010.py:1(Primes1)
        1    0.000    0.000    0.000    0.000 pe010.py:108(Primes8)
        1    2.640    2.640    4.610    4.610 pe010.py:129(pe010_01)
        1    0.000    0.000    0.000    0.000 pe010.py:18(Primes3)
        1    0.000    0.000    0.000    0.000 pe010.py:30(Primes35)
        1    0.000    0.000    0.000    0.000 pe010.py:44(Primes4)
        1    0.000    0.000    0.000    0.000 pe010.py:45(__init__)
   999999    1.940    0.000    1.940    0.000 pe010.py:47(is_prime)
        1    0.960    0.960    1.050    1.050 pe010.py:49(ert)
        1    0.000    0.000    0.000    0.000 pe010.py:58(Primes5)
        1    0.000    0.000    0.000    0.000 pe010.py:71(Primes6)
        1    0.000    0.000    0.000    0.000 pe010.py:8(Primes2)
        1    0.000    0.000    0.000    0.000 pe010.py:86(Primes7)
        1    0.000    0.000    5.660    5.660 profile:0(execfile('pe010.py'))
        0    0.000             0.000          profile:0(profiler)
---

しかし、いまだ素数判定部分で2秒もかかっています。
また、呼び出し部(pe01_01)も2.6秒程度と大きくかかっています。
まだまだ改良する余地はありそうです。

0 TrackBacks

Listed below are links to blogs that reference this entry: 処理速度を向上させる その3 そして速度向上へ.

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

Leave a comment

About this Entry

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

処理速度を向上させる その2 悪霊のアルゴリズム々 was the previous entry in this blog.

HDE Controller へのIPv6対応試験実装にともなうベータテスト開始のお知らせ is the next entry in this blog.

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