Ruby Memoization Basics And Memoist

This post will overview the ||= operator in Ruby, as well as the Memoist gem by comparing the usage with an implementation of the recursive Fibonacci function.

Source code can be found here

Getting started

We will create our own project in the folder ruby-memoization:

# Create a new rails project
$ mkdir ruby-memoization
$ cd ruby-memoization

# Create file we will work from
$ touch memoization.rb

# Add required Gem
$ bundler init
$ bundler add memoist

At this stage, our project is now ready to start working with.

Running a function without memoization

At first, let's take a look at how long it takes to run an expensive calculation for finding the 40th number in the Fibonacci sequence.

Inside of memoization.rb, add the following:

require 'memoist'

arg = 40

# Basic example
class BasicExample
  def fibonacci(n)
    return 1 if n < 2

    fibonacci(n - 1) + fibonacci(n - 2)
  end
end

basic_example = BasicExample.new

start = Time.now
res = basic_example.fibonacci(arg)
finish = Time.now
puts "Basic example #1: #{finish - start} seconds #{res}"

start = Time.now
res = basic_example.fibonacci(arg)
finish = Time.now
puts "Basic example #2: #{finish - start} seconds #{res}"

In this particular example, we are looking to make an expensive calculation and run the same calculation twice without memoization.

We log out how many seconds it took for each.

Let's run it and see what happens:

$ ruby memoization.rb
Basic example #1: 10.659713 seconds 165580141
Basic example #2: 10.932316 seconds 165580141

For both runs of the operation, it took about 10.5 to 11 seconds. Very expensive.

If we were to keep invoking the same function with the same function, it would take us around the same time for each invocation.

This is the problem that memoization can help us solve. Let's take a look at that now.

Memoization with the ||= operator

Update memoization.rb to the following:

require 'memoist'

arg = 40

# Basic example
class BasicExample
  def fibonacci(n)
    return 1 if n < 2

    fibonacci(n - 1) + fibonacci(n - 2)
  end

  def memoize_fibonacci(n)
    @value ||= fibonacci(n)
  end
end

basic_example = BasicExample.new

start = Time.now
res = basic_example.memoize_fibonacci(arg)
finish = Time.now
puts "Basic example #1: #{finish - start} seconds #{res}"

start = Time.now
res = basic_example.memoize_fibonacci(arg)
finish = Time.now
puts "Basic example #2: #{finish - start} seconds #{res}"

This time, we write a public memoize_fibonacci function that will memoize the results from the fibonacci function for us using the ||= operator.

If we now run this example, we get the following:

$ ruby memoization.rb
Basic example #1: 12.2039 seconds
Basic example #2: 2.0e-06 seconds

The second invocation now has been memoized since we have the same argument 40 and a rough estimate of the time take to run the function was in the microseconds!

We still need to manage the fact that the expensive operation is required for the first invocation but we can save ourselves a lot of trouble in subsequent calls that happen frequently.

Using the Memoist gem

If our memoization becomes more complex, we can turn to the Memoist gem as an alternative to help with easily memoizing functions in our classes.

Let's write another class with the same example:

require 'memoist'

arg = 40

# With gem
class GemExample
  extend Memoist

  def fibonacci(n)
    return 1 if n < 2

    fibonacci(n - 1) + fibonacci(n - 2)
  end
  memoize :fibonacci
end

gem_example = GemExample.new

start = Time.now
res = gem_example.fibonacci(arg)
finish = Time.now
puts "Gem example #1: #{finish - start} seconds #{res}"

start = Time.now
res = gem_example.fibonacci(arg)
finish = Time.now
puts "Gem example #2: #{finish - start} seconds #{res}"

In our new example, we can memoize the function using the memoize keyword in our class.

If you were to comment out the line memoize :fibonacci and run the script, you will the function run without memoization:

$ ruby memoization.rb
Gem example #1: 11.227355 seconds
Gem example #2: 11.41459 seconds

Once we uncomment it and let it run:

$ ruby memoization.rb
Gem example #1: 0.000213 seconds 165580141
Gem example #2: 2.3e-05 seconds 165580141

The second invocation again is significantly faster than the first.

Something to note is that with the memoist gem, the first invocation is also significantly faster. Full disclosure: I have absolutely no idea why that is the case, but I suspect that memoist must have some optimizations involved.

Summary

Today's post demonstrated how to memoize Ruby functions using the built-in ||= memoization operator as well as using the memoist gem.

Memoization is paramount to speeding up expensive calculations that are called often.

Resources and further reading

• Memoist
• Source code

Photo credit: pawel_czerwinski