How to optimize this ruby ​​code bit to go faster?

Question

This is the implementation of the Sieve of Eratosthenes .

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

Now I have done this to "send solutions to problems, since you have time to kill." I chose ruby ​​as my impl language .. however, I was declared a timeout. I did some benchmarking

require 'benchmark'
Benchmark.bmbm do |x|
  x.report ("get primes") { PrimeGenerator.get_primes_between(10000, 100000)}
  end

ruby 1.9.1p0 (2009-01-30 revision 21907) [i386-mswin32]

L:\Gishu\Ruby>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)

ruby 1.8.6 (2007-03-13 patchlevel 0) [i386-mswin32]

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)

So I redid the thing in C # 2.0 / VS 2008 -> 722 milliseconds

So, now it pushes me to think that this is a problem with my implementation or is the primary difference between these languages? (I was amazed at the 1.9 Ruby VM ... until I had to compare it with C # :)

UPDATE: , , "put-eratosthenes-to-shame":) . , - .. ; .

Answer 1

, , SoE, :

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

, , .

, 10_000 1_000_000

sieve_to(1_000_000) - sieve_to(9_999)

- .

, WinXP, Ruby 1.8.6 ( Xeon), :

require 'benchmark'
Benchmark.bm(30) do |r|
  r.report("Mike") { a = sieve_to(10_000) - sieve_to(1_000) } 
  r.report("Gishu") { a = PrimeGenerator.get_primes_between( 1_000, 10_000) }
end

                                    user     system      total        real
Mike                            0.016000   0.000000   0.016000 (  0.016000)
Gishu                           1.641000   0.000000   1.641000 (  1.672000)

( , ).

, , .; -)

# , .

Answer 2

. sieve_array[(factor).. (y-1)] , . .

Answer 3

, -, 50 (Ruby 1.8.6), .

factor=2
while factor < position_when_we_can_stop_checking 
    number = factor
    while number < y-1
      sieve_array[number-1] = 0 if isMultipleOf(number, factor)
      number = number + factor; # Was incrementing by 1, causing too many checks
    end
  factor = factor +1
end

Answer 4

, . , , . , , .

, , , "" .

: , ( ;)):

  public class Sieve {
    private readonly List<int> primes = new List<int>();
    private int maxProcessed;

    public Sieve() {
      primes.Add(maxProcessed = 2); // one could add more to speed things up a little, but one is required
    }

    public bool IsPrime(int i) {
      // first check if we can compare against known primes
      if (i <= primes[primes.Count-1]) {
        return primes.BinarySearch(i) >= 0;
      }
      // if not, make sure that we got all primes up to the square of i
      int maxFactor = (int)Math.Sqrt(i);
      while (maxProcessed < maxFactor) {
        maxProcessed++;
        bool isPrime = true;
        for (int primeIndex = 0; primeIndex < primes.Count; primeIndex++) {
          int prime = primes[primeIndex];
          if (maxProcessed % prime == 0) {
            isPrime = false;
            break;
          }
        }
        if (isPrime) {
          primes.Add(maxProcessed);
        }
      }
      // now apply the sieve to the number to check
      foreach (int prime in primes) {
        if (i % prime == 0) {
          return false;
        }
        if (prime > maxFactor) {
          break;
        }
      }
      return true;
    }
  }

67 .... :

class Program {
    static void Main(string[] args) {
        Stopwatch sw = new Stopwatch();
        sw.Start();
        Sieve sieve = new Sieve();
        for (int i = 10000; i <= 100000; i++) {
            sieve.IsPrime(i);
        }
        sw.Stop();
        Debug.WriteLine(sw.ElapsedMilliseconds);
    }
}

Answer 5

I would also like to point out that Ruby, in my experience, is much slower on Windows systems than on * nix. Of course, I'm not sure what speed processor you have, but running this code in my Ubuntu field in Ruby 1.9 takes about 10 seconds, and 1.8.6 - 30.

Answer 6

Check it out with ruby-prof. it can spit out tools like kcachegrind to see where your code is slow.

Then, as soon as you quickly make ruby, use RubyInline to optimize the method for you.