Back to home

Ruby Memoization Basics And Memoist

Published: Mar 12, 2022

Last updated: Mar 12, 2022

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

Personal image

Dennis O'Keeffe

@dennisokeeffe92
  • Melbourne, Australia

Hi, I am a professional Software Engineer. Formerly of Culture Amp, UsabilityHub, Present Company and NightGuru.
I am currently working on Visibuild.

1,200+ PEOPLE ALREADY JOINED ❤️️

Get fresh posts + news direct to your inbox.

No spam. We only send you relevant content.

Ruby Memoization Basics And Memoist

Introduction

Share this post