ここに至るまでの経緯は昨日のメモを参考。
(追記) ここを見て加算だけを使うようにしてみた。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
| 
