CODEWITHSUNDEEP
rubywhile-loopeachbenchmarking
Alexander Popov
Alexander Popov

Reputation: 24895

Is each slower than while in Ruby?

The following two functions, which check if a number is prime:

def prime1?(prime_candidate)
  return true if [1, 2].include? prime_candidate
  range = 2.upto(Math.sqrt(prime_candidate).ceil).to_a
  i = 0
  while i < range.count
    return false if prime_candidate % range[i] == 0
    range = range.reject { |j| j % range[i] == 0 }
  end
  true
end

def prime2?(prime_candidate)
  return true if [1, 2].include? prime_candidate
  range = 2.upto(Math.sqrt(prime_candidate).ceil).to_a
  range.each do |i|
    return false if prime_candidate % i == 0
    range = range.reject { |j| j % i == 0 }
  end
  true
end

yield the following benchamrking result when testing with a very large prime (5915587277):

              user     system      total        real
prime1:    2.500000   0.010000   2.510000 (  2.499585)
prime2:   20.700000   0.030000  20.730000 ( 20.717267)

Why is that? Is it because in the second function range does not get modified by the reject, so the each is iterating over the original long range?

Upvotes: 0

Views: 628

Answers (1)

Petr Skocik
Petr Skocik

Reputation: 60068

When you do range=range.reject {..}, you don't modify the parent range (which you shouldn't do, because it would mess up the iteration--you need reject! to do that) but rather construct a temporary array which only gets assigned to the parent range variable at the end of the iteration.

The each iteration in prime2 runs over the whole original range, not the shortened which, before the loop ends, only exist in the block.

The while version modifies the original array and is therefore quicker (BTW, you realize that i remains zero and it's the range.count that changes (decreases) in that while condition and that reject iterates over the WHOLE array again--even the beginning where there couldn't possibly be any more nonprimes to reject).

You'll get a much faster result if you improve the logic of your code. That array manipulation is costly and for this, you don't even need an array:

def prime3?(prime_candidate)
  return false if prime_candidate==1
  return true if prime_candidate==2
  range = 2..(Math.sqrt(prime_candidate).ceil)
  range.all? {|x|  prime_candidate % x !=0 }
end #about 300× times as fast for your example as prime1? on my PC

Upvotes: 2

Related Questions