# Ruby Memoization Basics And Memoist

> An intro into Ruby memoization with the memoization operator and the Memoist gem.

- Canonical: https://dennisokeeffe.com/blog/2022-03-12-ruby-memoization-basics-and-memoist
- Published: 2022-03-12
- Updated: 2022-03-12
- Tags: ruby

This post will overview the `||=` operator in Ruby, as well as the [Memoist](https://github.com/matthewrudy/memoist) gem by comparing the usage with an implementation of the recursive Fibonacci function.

Source code can be found [here](https://github.com/okeeffed/ruby-memoization)

## Getting started

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

```s
# 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:

```rb
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:

```s
$ 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:

```rb
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:

```s
$ 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:

```rb
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:

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

Once we uncomment it and let it run:

```s
$ 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](https://github.com/matthewrudy/memoist)
- [Source code](https://github.com/okeeffed/ruby-memoization)

_Photo credit: [`pawel_czerwinski`](https://unsplash.com/@pawel_czerwinski)_