Ruby Benchmarking & Big O Notation

The Ruby Benchmark library helps us to measure how long it takes for a block of code to run. Similar to when you subtract starting time and ending time in other languages such as Java.

I was doing some Big O Notation reviewing with Ruby the other day and did some common algorithm implementations for each of the most common Big O notations, just for fun.

Using Benchmark

To start benchmarking our code, we simply need to require benchmark and use the methods provided by the Benchmark module. For me, the most practical way is to use Benchmark#bm method, where we pass a block of code we want to measure:

require 'benchmark'

Benchmark.bm do |x|
  x.report do
    # our code here
  end

end

Inside the block we are using the report method of the block’s variable, which will basically do a separate benchmark for each report.

However, we can improve this even more by adding a label to report and a label width to bm:

require 'benchmark'

Benchmark.bm(20) do |x|
  x.report("my_algorithm") do
    # our code here
  end
end

Let’s see it in action with some common algorithms.

What is Big O Notation?

Big O notation is a special notation that measures how well a computer algorithm scales, as the amount of data involved increases (becomes closer to infinity). It is not necessarily a measurement of speed, but of how well the algorithm scales.

The following are some of the most common Big O notations, with algorithms and benchmarks.

O(1)

O(1) represents constant time. This means that the algorithm will execute in the same amount of time regardless of the amount of data or input. This is an ideal time complexity, and in algorithms with a time complexity greater than O(1) it can still be achieved by using techniques such as memoization.

An example of O(1) would be simply adding an element to an array. The size of the array won’t matter when simply adding a new element at the end:

Benchmark.bm(10) do |x|
  a = [1, 2, 3, 4, 5]
  x.report("add_element") { a.push(6) }

  a = (1..9_000_000).to_a
  x.report("add_element") { a.push(6) }
end

The benchmark results are:

                 user     system      total        real
add_element  0.000000   0.000000   0.000000 (  0.000003)
add_element  0.000000   0.000000   0.000000 (  0.000012)

We can clearly see that there is practically no difference between adding to the 5 element array and adding to the 9 million element array.

O(n)

O(n) represents linear time. This means that the time to complete the algorithm is proportional to the amount of data. A good example of this is linear search, simply because looking for an element in a 9 million size array will take a lot longer than looking in a 10 size element array.

# O(N)
def linear_search(array, value)
  array.each { |i| return i if i == value }
end

Benchmark.bm(50) do |x|
  x.report("linear_search(1,000)") { linear_search(1000) }
  x.report("linear_search(10,000,000)") { linear_search(10_000_000) }
end

The benchmark results are:

                                                         user     system      total        real
linear_search(1,000)                                 0.000000   0.000000   0.000000 (  0.000102)
linear_search(10,000,000)                             0.700000   0.000000   0.700000 (  0.722858)

Still pretty fast, but the difference is very noticeable.

O(n^2)

O(n^2) indicates that the amount to complete will be proportional to the square of the amount of data. This usually happens with algorithms that have nested loops. A good example of this notation is the bubble sort algorithm.

Bubble Sort

Here is a simple implementation in Ruby, with its corresponding benchmarks:

# O(N^2)
def bubble_sort(array)
  n = array.length

  loop do
    swapped = false

    (n-1).times do |i|
      if array[i] > array[i+1]
        array[i], array[i+1] = array[i+1], array[i]
        swapped = true
      end
    end
    break if not swapped
  end

  array
end

Benchmark.bm(50) do |x|
  x.report("bubble_sort([1..10])") { bubble_sort((1..10).to_a.shuffle) }
  x.report("bubble_sort([1..10,000])") { bubble_sort((1..10_000).to_a.shuffle) }
end

The benchmark results are:

                                                         user     system      total        real
bubble_sort([1..10])                                 0.000000   0.000000   0.000000 (  0.000039)
bubble_sort([1..10,000])                            13.990000   0.010000  14.000000 ( 14.028724)

Now we are starting to see a lot more difference. This is because we initially have to loop through the whole array, and for each element in the iteration, we loop through the whole array again. Hence resulting in: O(n) x O(n) = O(n^2).

When the amount of input is relatively small, O(n^2) algorithm’s bad performance will not be that obvious. But as the input size grows, it will become more evident, and that is why O(n^2) algorithms are generally avoided for big inputs.

O(log n)

O(log n) is a much more efficient algorithm. This is because the input used is decreased by around 50% each time through the algorithm. These kind of algorithms are very fast and efficient because increases in the amount of data have little to no effect at some point early on because the amount of data is half each time.

A good example of an O(log n) algorithm is the binary search algorithm:

Binary Search vs Linear Search

In Ruby, we can implement a binary search in the following way (NOTE: The array must be initially sorted for the algorithm to work.):

# O( log N )
def binary_search(array, element, low=0, high=array.length-1)
  return nil if high < low

  mid = ( low + high ) / 2

  if array[mid] > element
    return binary_search(array, element, low, mid - 1)
  elsif array[mid] < element
    return binary_search(array, element, mid + 1, high)
  else
    return mid
  end
end

Benchmark.bm(50) do |x|
  x.report("binary_search([1..10])") { binary_search((1..10).to_a, 4) }
  x.report("binary_search([1..5,000,000])") { binary_search((1..5_000_000).to_a, 4_999_999) }
end

The benchmark results are:

                                                         user     system      total        real
binary_search([1..10])                               0.000000   0.000000   0.000000 (  0.000011)
binary_search([1..5,000,000])                        0.190000   0.000000   0.190000 (  0.192921)

It is clearly obvious that the performance difference of the algorithm with an array of size 10 compared to that of with an array of size 5,000,000 is almost non-existent, even when using a “worst case” (in this case, the element before the last one).

O(n log n)

In sorting algorithms, a time complexity of at least O(n) is unavoidable (at least in theory). This is because we have to look at each element in the array at least once in order to properly sort it. At the same time, an order of O(n^2) is to be avoided.

O(n log n) sorting algorithms are more efficient because values are only compared once, instead of being compared to each other repeatedly. This means that each comparison will reduce the possible final sorted list in half.

In other words, we can calculate the number of comparisons like this:

number_comparisons = log(n!)
      log(n) + log(n-1) + ... + log(1)
      nlog(n)
      log n + log (n-1) + ... + log (n/2)
      n/2 * log (n/2)
  =>  nlog(n)

A good example of a O(n log n) algorithm is the quick sort algorithm:

Quicksort

In Ruby, we can implement Quicksort like this:

# O( N log N )
def quick_sort(array)
  return array if array.length <= 1

  pivot = array[0]

  less, greatereq = array[1..-1].partition { |x| x < pivot }
  quick_sort(less) + [pivot] + quick_sort(greatereq)
end

Benchmark.bm(50) do |x|
  x.report("quick_sort([1..20])") { quick_sort((1..20).to_a.shuffle) }
  x.report("quick_sort([1..400,000])") { quick_sort((1..400_000).to_a.shuffle) }
end

Notice how multiple assignment and the partition method from Enumerable is used. This method will return two arrays: the first array will contain elements for which the block evaluates to true, and the second one containing the rest.

The benchmark yields the following results:

                                                         user     system      total        real
quick_sort([1..20])                                  0.000000   0.000000   0.000000 (  0.000048)
quick_sort([1..400,000])                             1.400000   0.020000   1.420000 (  1.430095)

Closing Thoughts

Even though those are the most common Big O time complexity notations, there are even more complicated complexities (lol?) out there.

Moreover, there are also other asymptotic notations that use different symbols to describe different kinds of bounds. I hope to cover these sometime in the future.

ruby algorithms programming benchmarking mathematics computerscience

Comments

comments powered by Disqus