Databases
StackOverflow2013
Postsdbo
POHow do I optimize this bit of ruby code to go faster?
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POHow do I optimize this bit of ruby code to go faster?
    text
    copied!<p>It's an implementation of <a href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="nofollow noreferrer">Sieve of Eratosthenes</a>.</p> <pre><code>class PrimeGenerator def self.get_primes_between( x, y) sieve_array = Array.new(y) {|index| (index == 0 ? 0 : index+1) } position_when_we_can_stop_checking = Math.sqrt(y).to_i (2..position_when_we_can_stop_checking).each{|factor| sieve_array[(factor).. (y-1)].each{|number| sieve_array[number-1] = 0 if isMultipleOf(number, factor) } } sieve_array.select{|element| ( (element != 0) &amp;&amp; ( (x..y).include? element) ) } end def self.isMultipleOf(x, y) return (x % y) == 0 end end </code></pre> <p>Now I did this for a 'submit solutions to problems since you have time to kill' site. I chose ruby as my impl language.. however i was declared timed out. I did some benchmarking</p> <pre><code>require 'benchmark' Benchmark.bmbm do |x| x.report ("get primes") { PrimeGenerator.get_primes_between(10000, 100000)} end </code></pre> <p>ruby 1.9.1p0 (2009-01-30 revision 21907) [i386-mswin32]</p> <pre><code>L:\Gishu\Ruby&gt;ruby prime_generator.rb Rehearsal ---------------------------------------------- get primes 33.953000 0.047000 34.000000 ( 34.343750) ------------------------------------ total: 34.000000sec user system total real get primes 33.735000 0.000000 33.735000 ( 33.843750) </code></pre> <p>ruby 1.8.6 (2007-03-13 patchlevel 0) [i386-mswin32]</p> <pre><code>Rehearsal ---------------------------------------------- get primes 65.922000 0.000000 65.922000 ( 66.110000) ------------------------------------ total: 65.922000sec user system total real get primes 67.359000 0.016000 67.375000 ( 67.656000) </code></pre> <p>So I redid the thing in C# 2.0 / VS 2008 --> <strong>722 milliseconds</strong></p> <p>So now this prods me into thinking is it a problem with my implementation or is the perf diff between languages this wide? (I was amazed with the 1.9 Ruby VM... until I had to go compare it with C# :)</p> <p><strong>UPDATE:</strong> Turned out to be my "put-eratosthenes-to-shame-adaptation" after all :) <strong>Eliminating unnecessary loop iterations</strong> was the major optimization. In case anyone is interested in the details.. you can read it <a href="http://madcoderspeak.blogspot.com/2009/04/i-wrote-up-small-program-to-find-prime.html" rel="nofollow noreferrer">here</a>; this question is too long anyways.</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload