The SOE is basically where you take all numbers (say 1-100) into an array. Cross out 1. Loop from 2-Sqrt(N) i.e. 2-10. Now cross out every multiple of 2 in the array. Next cross out every multiple of 3.. and so on. Finally all the numbers that aren't crossed out are prime.

However I did a very simplistic implementation (test-driven) to boot. All the tests did pass.. however running it to get all primes between 10K and 100K took 34 secs to execute. And I was on the new n improved ruby 1.9 with a better VM. I switched to the stable ruby 1.8.6 and it took ~60 secs. So now I turned back to my primary Weapon C#. The same steps implemented in C# took 722 msecs. So now there were 2 possibilities

1. Ruby is sloooow (the usual gripe)

2. Something in my algorithm is messed up.

So I posted my source onto StackOverflow - (my current fave time sink :) to get some eyeballs to look at the problem.

So here's my naive implementation

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) && ( (x..y).include? element) )

}

end

def self.isMultipleOf(x, y)

return (x % y) == 0

end

end

# Benchmarking code

require 'benchmark'

Benchmark.bm(30) do |r|

r.report("Gishu") { a = PrimeGenerator.get_primes_between( 1_000, 10_000) }

end

A few people got back with what might be the problem.

One of the first and most voted issue was the slicing the array to get a new subset array. That's got to be expensive inside a loop for an array of this size. Obviously I was using for loops in C# (since C# doesn't have Ruby's each)

for index in factor..y-1 do

sieve_array[index] = 0 if isMultipleOf(index+1, factor)

end

That shaved off 8 secs - 24%. But still 26 secs. Another optimization was to reduce iterations - instead of checking each number with IsMultiple(number, _loopVar), set the 'step' for the loop to equal _loopVar (so from 2 you go 4,6,8,10...)

And finally Mike Woodhouse dispatched a homer. He posted a tiny snippet that did the same thing in under 1 sec. No that's not a typo.

def sieve_to(n)

s = (0..n).to_a

s[0]=s[1]=nil

s.each do |p|

next unless p

break if p * p > n

(p*p).step(n, p) { |m| s[m] = nil }

end

s.compact

end

# Usage:

# puts sieve_to(11).select{|x| x>=3}.inspect

user system total real

Gishu 27.219000 0.000000 27.219000 ( 27.375000)

Mike 0.141000 0.000000 0.141000 ( 0.140625)

I then had to know how he did it..

- Smart#1: He skips if array[_loopvar] is already 0. whereas if array[6] is crossed out due to 3, I did a scanning run to set all multiples of 6 to 0 which were already 0.(now down to 6 secs)
- Smart#2: Use the Numeric#step trick to jump to the next multiple vs traversing entire list with an IsMultiple check (now down to 0.25 secs)
- Smart#3: He begins the inner loop with Square of p. e.g if _loopvar is 7, I used to check from 8->end. Mike checks from 49->end. This one was a little tricky to figure out.. the reason is 7x2, 7x3, 7x4, 7x5, 7x6 have already been crossed out when _loopVar was 2,3,4,5,6 respectively. (now down to 0.21 secs)
- Smart#4: Smart use of Ruby's nil for crossed out vs my choice of 0. That followed by Array#compact reduces the number of elements for the final select operation to get primes between x and y (now down to 0.18 secs.)

So after all that it's Ruby 0.15 secs and C# (with same optimizations) 0.028 secs, much more easy to take in.

An interesting thought to end this post is that even with the naive first implementation C# performed reasonably well... under a sec. I'd have moved on to the next task. Ruby on the other hand slowed to a crawl forcing me to take another look for optimizations. In a indirect sort of way, C#'s superior performance could be hiding bad/substandard solutions and letting programmers get away with it...

## No comments:

## Post a Comment