sieve.rb sample
 

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] = i
end

for i in 2 .. Math.sqrt(max)
next unless sieve[i]
(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.
--
Posted via http://www.ruby-forum.com/.

Re: sieve.rb sample
 

Hi Siep,

On Nov 6, 2007 10:14 PM, Siep Korteling <s.korteling@gmail.com> wrote:
>
> max = Integer(ARGV.shift || 100)
> sieve = []
> for i in 2 .. max
> sieve[i] = i
> end
>
> for i in 2 .. Math.sqrt(max)
> next unless sieve[i]
> (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] = i
end

for i in 2 .. Math.sqrt(max)
next unless sieve[i]
(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] = i
end

m = Math.sqrt(max)
for i in 2 .. m
next unless sieve[i]
(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

Re: sieve.rb sample
 

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





On 11/6/07, George <george.ogata@gmail.com> wrote:
>
> Hi Siep,
>
> On Nov 6, 2007 10:14 PM, Siep Korteling <s.korteling@gmail.com> wrote:
> >
> > max = Integer(ARGV.shift || 100)
> > sieve = []
> > for i in 2 .. max
> > sieve[i] = i
> > end
> >
> > for i in 2 .. Math.sqrt(max)
> > next unless sieve[i]
> > (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] = i
> end
>
> for i in 2 .. Math.sqrt(max)
> next unless sieve[i]
> (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] = i
> end
>
> m = Math.sqrt(max)
> for i in 2 .. m
> next unless sieve[i]
> (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
>
>