sieve.rb sample

S

Siep Korteling

the sieve of Erathotenes sample (sieve.rb) in Ruby 1.9 looks like this:


max = Integer(ARGV.shift || 100)
sieve = []
for i in 2 .. max
sieve = i
end

for i in 2 .. Math.sqrt(max)
next unless sieve
(i*i).step(max, i) do |j|
sieve[j] = nil
end
end
puts sieve.compact.join(", ")


Is Math.sqrt(max) calculated every loop?
....
m=Math.sqrt(max)
for i in 2 .. m
....

runs about 20% faster on my machine.
 
G

George

Hi Siep,

max = Integer(ARGV.shift || 100)
sieve = []
for i in 2 .. max
sieve = i
end

for i in 2 .. Math.sqrt(max)
next unless sieve
(i*i).step(max, i) do |j|
sieve[j] = nil
end
end
puts sieve.compact.join(", ")


Is Math.sqrt(max) calculated every loop?


Shouldn't be, no.
....
m=Math.sqrt(max)
for i in 2 .. m
....

runs about 20% faster on my machine.

I'm not sure how you're benchmarking it, but I'm not seeing such
behavior with the current svn HEAD. What I did notice, however, was
that the first run of my Benchmark seemed to be noticably quicker than
the others, which I found rather odd:

user system total real
sieve1 1.080000 0.000000 1.080000 ( 1.082122)
sieve2 1.340000 0.010000 1.350000 ( 1.350781)
sieve1 1.360000 0.000000 1.360000 ( 1.362670)
sieve2 1.350000 0.010000 1.360000 ( 1.350056)

It was even more pronounced when I upped the iterations tenfold:

user system total real
sieve1 22.510000 0.050000 22.560000 ( 22.546830)
sieve2 50.500000 0.060000 50.560000 ( 50.510556)
sieve1 50.470000 0.070000 50.540000 ( 50.500493)
sieve2 50.480000 0.080000 50.560000 ( 50.503374)

If I added a call to #sieve2 (see comment in code below) before
running the timings, the benchmarks were brought back even again:

g@bang:~/tmp$ ruby19 sieve.rb
user system total real
sieve1 1.390000 0.000000 1.390000 ( 1.392173)
sieve2 1.370000 0.000000 1.370000 ( 1.376944)
sieve1 1.400000 0.000000 1.400000 ( 1.425670)
sieve2 1.370000 0.010000 1.380000 ( 1.393410)

Somehow calling #sieve2 is slowing down subsequent calls to #sieve1.
I don't know YARV well enough yet, but I'm curious as to what's
causing this. :-/

g@bang:~/src/ruby$ ruby19 -v
ruby 1.9.0 (2007-11-06 patchlevel 0) [i686-linux]

Regards,
George.

Code:

def sieve1
max = Integer(ARGV.shift || 1000000)
sieve = []
for i in 2 .. max
sieve = i
end

for i in 2 .. Math.sqrt(max)
next unless sieve
(i*i).step(max, i) do |j|
sieve[j] = nil
end
end
end

def sieve2
max = Integer(ARGV.shift || 1000000)
sieve = []
for i in 2 .. max
sieve = i
end

m = Math.sqrt(max)
for i in 2 .. m
next unless sieve
(i*i).step(max, i) do |j|
sieve[j] = nil
end
end
end

require 'benchmark'

Benchmark.bm do |x|
# sieve2 # uncomment to remove the anomaly
x.report('sieve1'){sieve1}
x.report('sieve2'){sieve2}
x.report('sieve1'){sieve1}
x.report('sieve2'){sieve2}
end
 
V

Victor Reyes

Note: parts of this message were removed by the gateway to make it a legal Usenet post.

Hi team,

I executed the two versions of the program and you actually can see the
difference:
I see something estrange however. It takes less time when I execute this
program with 1000 as a parameter than when I run it with the default 100.


=====================================
for i in 2 .. Math.sqrt(max)

timex ruby sieve1.rb


real 0.24
user 0.01
sys 0.00
======================================
m=Math.sqrt(max)
for i in 2 .. m

timex ruby sieve2.rb


real 0.02
user 0.01
sys 0.00
=======================================
timex ruby sieve1.rb 1000

real 0.00
user 0.01
sys 0.00
=======================================

timex ruby sieve2.rb 1000

real 0.02
user 0.01
sys 0.00
========================


Victor





Hi Siep,

max = Integer(ARGV.shift || 100)
sieve = []
for i in 2 .. max
sieve = i
end

for i in 2 .. Math.sqrt(max)
next unless sieve
(i*i).step(max, i) do |j|
sieve[j] = nil
end
end
puts sieve.compact.join(", ")


Is Math.sqrt(max) calculated every loop?


Shouldn't be, no.
....
m=Math.sqrt(max)
for i in 2 .. m
....

runs about 20% faster on my machine.

I'm not sure how you're benchmarking it, but I'm not seeing such
behavior with the current svn HEAD. What I did notice, however, was
that the first run of my Benchmark seemed to be noticably quicker than
the others, which I found rather odd:

user system total real
sieve1 1.080000 0.000000 1.080000 ( 1.082122)
sieve2 1.340000 0.010000 1.350000 ( 1.350781)
sieve1 1.360000 0.000000 1.360000 ( 1.362670)
sieve2 1.350000 0.010000 1.360000 ( 1.350056)

It was even more pronounced when I upped the iterations tenfold:

user system total real
sieve1 22.510000 0.050000 22.560000 ( 22.546830)
sieve2 50.500000 0.060000 50.560000 ( 50.510556)
sieve1 50.470000 0.070000 50.540000 ( 50.500493)
sieve2 50.480000 0.080000 50.560000 ( 50.503374)

If I added a call to #sieve2 (see comment in code below) before
running the timings, the benchmarks were brought back even again:

g@bang:~/tmp$ ruby19 sieve.rb
user system total real
sieve1 1.390000 0.000000 1.390000 ( 1.392173)
sieve2 1.370000 0.000000 1.370000 ( 1.376944)
sieve1 1.400000 0.000000 1.400000 ( 1.425670)
sieve2 1.370000 0.010000 1.380000 ( 1.393410)

Somehow calling #sieve2 is slowing down subsequent calls to #sieve1.
I don't know YARV well enough yet, but I'm curious as to what's
causing this. :-/

g@bang:~/src/ruby$ ruby19 -v
ruby 1.9.0 (2007-11-06 patchlevel 0) [i686-linux]

Regards,
George.

Code:

def sieve1
max = Integer(ARGV.shift || 1000000)
sieve = []
for i in 2 .. max
sieve = i
end

for i in 2 .. Math.sqrt(max)
next unless sieve
(i*i).step(max, i) do |j|
sieve[j] = nil
end
end
end

def sieve2
max = Integer(ARGV.shift || 1000000)
sieve = []
for i in 2 .. max
sieve = i
end

m = Math.sqrt(max)
for i in 2 .. m
next unless sieve
(i*i).step(max, i) do |j|
sieve[j] = nil
end
end
end

require 'benchmark'

Benchmark.bm do |x|
# sieve2 # uncomment to remove the anomaly
x.report('sieve1'){sieve1}
x.report('sieve2'){sieve2}
x.report('sieve1'){sieve1}
x.report('sieve2'){sieve2}
end
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,743
Messages
2,569,478
Members
44,899
Latest member
RodneyMcAu

Latest Threads

Top