処理速度を向上させる その1

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

私は、最近、よくProject Euler※(http://projecteuler.net/)の問題を解いています。
one-minute rule は努力目標で、問題が解けりゃいいや(=うごけばいいや)レベルでコードを書いているので、できたコードの処理速度には目も当てられない状態になっています。。

「これではいかん」と一念発起し、処理速度向上の試みをしてみましたので、紹介します。

※プログラムで解く問題集です。
【処理速度向上対象】
 今回は以下の一つのコードの高速化をすることを目的とします。
 今回の処理速度向上の対象は、Project Euler 第10問(http://projecteuler.net/index.php?section=problems&id=10)に対する解答コードとしました。
python2.4で書いています。 

 メインは素数判定部分(is_prime())の高速化です。(のちに全体の高速化も行います)

【開発環境】
 Intel(R) Xeon(R) CPU  5130  @ 2.00GHz
メモリ 2GB
OS CentOS 5.5 64bit

【処理課題】
 200万以下の素数の和を求めよ。
 ここで、素数とは、2以上その数未満の自然数で割りきれない自然数のことです。

【最初のコード】
 200万以下の奇数について、Primes.is_prime()で素数かどうかを判定し、素数であればsumに加算するという方法で答えを求めます。
 素数の判定方法は、「その数の平方根以下の自然数で割ってみて、どれでも割り切れなければ素数、そうでなければ素数でない」というものです。

--------コード開始--------
class Primes1:
  def is_prime(self,number):
    i=2
    while number >= i*i:
      if not number % i: return False
      i+=1
    return True

def pe010_01(p):
  sum = 2
  for n in range(3,2*(10**6),2):
    if p.is_prime(n) : sum+=n
  return sum

if __name__ == '__main__':
  p = Primes1()
  print pe010_01(p)
--------コード終わり--------

0 TrackBacks

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

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

Leave a comment

About this Entry

This page contains a single entry by shiota published on October 4, 2010 3:11 PM.

Scala勉強会第2回目 was the previous entry in this blog.

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

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