Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Ruby > sieve.rb sample

Reply
Thread Tools

sieve.rb sample

 
 
Siep Korteling
Guest
Posts: n/a
 
      11-06-2007
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/.

 
Reply With Quote
 
 
 
 
George
Guest
Posts: n/a
 
      11-06-2007
Hi Siep,

On Nov 6, 2007 10:14 PM, Siep Korteling <(E-Mail Removed)> 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

 
Reply With Quote
 
 
 
 
Victor Reyes
Guest
Posts: n/a
 
      11-06-2007
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 <(E-Mail Removed)> wrote:
>
> Hi Siep,
>
> On Nov 6, 2007 10:14 PM, Siep Korteling <(E-Mail Removed)> 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
>
>


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
looking for asp.net sample with vb.net backend sample is there one? Jake ASP .Net 0 02-09-2006 10:44 PM
iProvisioningProfileWireless sample code? Barbara Nelson Wireless Networking 0 08-10-2005 09:51 PM
Problem with the IBF Sample Solution =?Utf-8?B?QnJ1bW1lbA==?= ASP .Net 0 09-21-2004 09:19 AM
Help Urgently!! MSDN sample not working!! Catherine Jones ASP .Net 1 01-03-2004 10:49 AM
Need help! Sample not working in frm 1.1 Catherine Jones ASP .Net 0 12-24-2003 03:59 AM



Advertisments