Ruby vs Python – Speed Comparison

A month or two ago (I think? between kids and Turing I have no sense of time) one of our technical practice problems was figuring out how to implement the Sieve of Eratosthenes. I got kind of obsessed over that weekend trying to figure out a more efficient way to do it than what I had originally. With this I ended up just trying to find prime numbers, but the Sieve of Eratosthenes is interesting.

For whatever reason, I was discussing this with a teacher after graduation, and she told me I should try it in Python to see the speed difference between Ruby and Python…and here we are. I’ll talk through it in Ruby because that is how I did it initially, but also do it in Python to get the comparison in how quickly it runs.

First, I needed to require the benchmark module so I could test the speed later. If you want to learn about benchmark, this link is informative. I named the method and set it to pass one parameter, the max number, so it knows what range to look for prime numbers in.

I created the array numbers to the size of max + 1 (because arrays are zero indexed and I don’t want to lose the max number). Each index is set to the initial value of true to indicate whether or not it is prime. Everything is going to start out as true but if it is found to not be a prime number, it will switch to false. Initially, I had been removing numbers from the array if they are not prime, but have since learned (and correct me if I’m wrong) that pulling something out of an array is way less efficient because it requires everything to shift over, instead of just changing something inside the array.

require 'benchmark' #to test how quick it runs later

def find_prime_numbers(max)
  numbers = Array.new(max + 1, true)
end

Next, I need to set both the first two indices, 0 and 1, to false because 0 and 1 are not prime numbers.

require 'benchmark'

def find_prime_numbers(max)
  numbers = Array.new(max + 1, true)
  numbers[0] = numbers[1] = false
end

Now it is time to do a little math. This line is going to start a loop that iterates over the numbers from 2 to whatever the square root of max is. That is used as the upper limit because if a number has a factor that is larger than the square root, it will have a corresponding factor smaller than the square root. On a side note, here is an example explaining that.

The square root of 36 is 6

The factors of 36 are 
  1, 2, 3, 6, 9, 12, 18, 36

Every factor above the square root, 6, has a corresponding factor that is less than 6
9 * 4 = 36
12 * 3 = 36
18 * 2 = 36
36 * 1 = 36
Each pair has one number larger, and one number smaller than 6

Anyway, back to the code. This next line uses the range from 2 to the square root of whatever the max is, and each of those numbers gets iterated over to check if it has a factor that is smaller than the square root. I’ll use the variable pp (because it is shorter than possible_prime) to hold the number being checked

require 'benchmark'

def find_prime_numbers(max)
  numbers = Array.new(max + 1, true)
  numbers[0] = numbers[1] = false
  (2..Math.sqrt(max)).each do |pp|
end

We need to take pp and use that to check the numbers array for whether or not it is prime. If it is still marked as true (which means it is still considered prime) then it will go through and mark the multiples as not prime. It takes pp and multiplies it by each number in the range pp..max, and uses step to go through each one in that range. Each of those that you get is iterated over separately as multiple, and multiple is used to turn any of those false.

require 'benchmark'

def find_prime_numbers(max)
  numbers = Array.new(max + 1, true)
  numbers[0] = numbers[1] = false
  (2..Math.sqrt(max)).each do |pp|
    if numbers[pp]
      (pp*pp..max).step(pp) { |multiple| numbers[multiple] = false }
    end
  end
end

Awesome, and now that all of those are found, then it iterates over the numbers array will pull out the index of each one that is true, because true tells you it’s prime.

require 'benchmark'

def find_prime_numbers(max)
  numbers = Array.new(max + 1, true)
  numbers[0] = numbers[1] = false
  (2..Math.sqrt(max)).each do |pp|
    if numbers[pp]
      (pp*pp..max).step(pp) { |multiple| numbers[multiple] = false }
    end
  end
  numbers.each_index.select { |pp| numbers[pp] }
end

And that should find all of the prime numbers between 0 and whatever you set the max as.

Time to set up benchmark

I am going to give it the variable name time and then run benchmark in there. It should run it, and return “Found (however many) prime numbers up to (whatever the max is)

time = Benchmark.measure do
  primes = find_prime_numbers(max_val)
  puts "Found #{primes.size} prime numbers up to #{max_val}."
end

I am going to set max_val at 1,000,000 and see what that gets me. If you want to look up how to read benchmark times, go here.

It took .157 seconds to run the above code with the max value being 1,000,000

It took 1.705 seconds to run it when the max value was 10,000,000

It took 18.728 seconds when the max value was 100,000,000

I’m just going to put the python code below, it is about as similar as I could get it, and then run the same two numbers to compare.

import math
import time

def find_prime_numbers(max):
    numbers = [True] * (max + 1)
    numbers[0] = numbers[1] = False
    for pp in range(2, int(math.sqrt(max)) + 1):
        if numbers[pp]:
            for multiple in range(pp * pp, max + 1, pp):
                numbers[multiple] = False
    return [pp for pp, is_prime in enumerate(numbers) if is_prime]

def benchmark_prime(max_val):
    start_time = time.time()
    numbers = find_prime_numbers(max_val)
    end_time = time.time()
    print(f"Found {len(numbers)} prime numbers up to {max_val} in {end_time - start_time} seconds.")

if __name__ == "__main__":
    max_val = 1000000  
    benchmark_prime(max_val)

When I ran that with 1,000,000 it finished in .091 seconds

It got 10,000,000 in 1.638 seconds

It got 100,000,000 in 21.066 seconds

In conclusion, my very unscientific tests show that Python got it a little bit faster, until I tried 100,000,000. I ran it a couple times and there was some variation, but it seemed to live around that same time.

Anyway, this was kind of an interesting comparison between the two languages, and something fun to play around with. As always, let me know if you know of a better way to do/explain any of this!