今回は、「どうせ記憶するなら全数記憶してみればいいんじゃないか？」という発想のもと、処理速度改善を行ってみます。
あらかじめ対象とする数まで計算し、素数かどうかをリストに記憶します。その後、素数判定の際に対応するリストの値が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秒程度と大きくかかっています。
まだまだ改良する余地はありそうです。
Leave a comment