最近のキーワード

2006年06月18日

上限を決めずに素数を生成(Ruby版)

というわけで、現在の形はこう(↓)。1000000個目はまだやってないが、100000個目くらいなら最近のノートPCであれば数分内に求めることはできる。でも、古典的なアルゴリズムをちょっと変形させただけだから、あまり面白くないし、見た目もカッコ悪い。 もう少し何かを加えよう。当然、時間的にも空間的にも悪くないような実装が好ましい。
ここに至るまでの経緯は昨日のメモを参考。
(追記) ここを見て加算だけを使うようにしてみた。Rubyだとそんなに速くはならないが、掛け算2つ分は速くなり、塵も積もれば山となる。
class MyPrime
  extend Enumerable
  
  def initialize()
    @hash = {}
    @n = 1
  end
  
  def succ()
    n = @n
    while true
      n += 1
      if (s = @hash[n])
        s.call()
        @hash.delete(n)
      else
        i,j = n,n
        f = Proc.new{
          k = i + j
          if (g = @hash[k])
            g.call()
          end
          @hash[k] = f
          j += n
        }
        f.call()
        @n = n
        return n
      end
    end
  end
  alias next succ

  def self.each_succ()
    g = self.new(h)
    while (n = g.succ())
      yield(n)
    end
  end

  def self.each()
    @hash = {}
    n = 1
    while true
      n += 1
      if (s = @hash[n])
        s.call()
        @hash.delete(n)
      else
        yield(n)
        class_eval{
          i,j,m = n,n,n
          f = Proc.new{
            k = i + j
            if (g = @hash[k])
              g.call()
            end
            @hash[k] = f
            j += m
          }
          f.call()
        }
      end
    end
  end
end

require 'generator'
require 'mathn'
require 'test/unit'

class PrimeTest < Test::Unit::TestCase
  PRIMES = [
    2,  3,  5,  7,  11, 13, 17, 19, 23, 29,
    31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
    73, 79, 83, 89, 97]
  N = 10000

  def test_compare_with_mathn()
    my_generator = MyPrime.new()
    mathn_generator = Prime.new()
    for i in 0..100
      a = my_generator.next()
      b = mathn_generator.next()
      assert_equal(b, a)
    end
  end

  def test_each()
    MyPrime.each_with_index{|x,i|
      if PRIMES[i]
        assert_equal(PRIMES[i], x)
      else
        break
      end
    }
  end

  def test_mathn()
    Prime.class_eval{
        @@primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101]
        @@next_to_check = 103
        @@ulticheck_index = 3
        @@ulticheck_next_squared = 121
    }
    mathn_generator = Prime.new()
    PRIMES.each{|x|
      assert_equal(x, mathn_generator.next())
    }
    GC.start()
    t1 = Time.now
    N.times{
      mathn_generator.next()
    }
    t2 = Time.now
    p [:test_mathn, t2 - t1]
  end

  def test_primes()
    my_generator = MyPrime.new()
    PRIMES.each{|x|
      assert_equal(x, my_generator.next())
    }
    GC.start()
    t1 = Time.now
    N.times{
      my_generator.next()
    }
    t2 = Time.now
    p [:test_primes, t2 - t1]
  end

  def test_mathn_each()
    Prime.class_eval{
        @@primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101]
        @@next_to_check = 103
        @@ulticheck_index = 3
        @@ulticheck_next_squared = 121
    }
    mathn_generator = Prime.new()
    c = 1
    GC.start()
    t1 = Time.now
    mathn_generator.each{|x|
      break if c == N
      c += 1
    }
    t2 = Time.now
    p [:test_mathn_each, t2 - t1]
  end

  def test_primes_each()
    c = 1
    GC.start()
    t1 = Time.now
    MyPrime.each{|x|
      break if c == N
      c += 1
    }
    t2 = Time.now
    p [:test_primes_each, t2 - t1]
  end

  #def test_regexp()
  #  assert_equal(PRIMES, (2..100).select{|n| "1" * n !~ /^(11+)\1+$/ })
  #  t1 = Time.now
  #  (2..N).select{|n| "1" * n !~ /^(11+)\1+$/ }
  #  t2 = Time.now
  #  p [:test_regexp, t2 - t1]
  #end
end
もう一つ、今度(↓)は2の倍数をスキップしてしまうようにする。ちょっとだけ速くなる。
class MyPrime
  extend Enumerable
  
  def initialize()
    @hash = {}
    @n = nil
  end
  
  def succ()
    if (@n.nil?)
      @n = 1
      return 2
    end
    n = @n
    while true
      n += 1
      if (s = @hash[n])
        s.call()
        @hash.delete(n)
      end
      n += 1
      if (s = @hash[n])
        s.call()
        @hash.delete(n)
      else
        i,j = n,n
        f = Proc.new{
          k = i + j
          if (g = @hash[k])
            g.call()
          end
          @hash[k] = f
          j += n
        }
        f.call()
        @n = n
        return n
      end
    end
  end
  alias next succ

  def self.each_succ()
    g = self.new(h)
    while (n = g.succ())
      yield(n)
    end
  end

  def self.each()
    hash = {}
    yield(2)
    n = 1
    while true
      n += 1
      if (s = hash[n])
        s.call()
        hash.delete(n)
      end
      n += 1
      if (s = hash[n])
        s.call()
        hash.delete(n)
      else
        yield(n)
        class_eval{
          i,j,m = n,n,n
          f = Proc.new{
            k = i + j
            if (g = hash[k])
              g.call()
            end
            hash[k] = f
            j += m
          }
          f.call()
        }
      end
    end
  end
end
posted by ttate at 05:39| ☔| Comment(0) | TrackBack(0) | Ruby | このブログの読者になる | 更新情報をチェックする
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。

この記事へのトラックバック
×

この広告は180日以上新しい記事の投稿がないブログに表示されております。