Fork me on GitHub

Project Notes

Memo Methods

Comparing and testing various memoization methods and gems in Ruby.

Notes

Memoization is an optimization technique for storing the results of expensive function calls and returning the cached result for the same inputs. Adding memoization should ideally not change the object/function interface i.e. memoization can be added or removed without changing code that calls the memoized method.

The Memoization design pattern can be considered a specific instance of the more elaborate Memento pattern from the classic Design Patterns collection.

Running the Examples

The Gemfile specifies the gem requirements. bundle install as usual.

Memoize by Hand

Memoization is particularly clean and easy to implement in Ruby. In its simplest form, a method like the following can be used to wrap/redefine any existing method with a simple in-memory hash cache:

def memoize(name)
  cache = {}

  (class<<self; self; end).send(:define_method, name) do |*args|
    unless cache.has_key?(args)
      cache[args] = super(*args)
    end
    cache[args]
  end
  cache
end

Running the memoization_by_hand.rb example:

$ bundle exec ruby memoization_by_hand.rb
Usage: ruby memoization_by_hand.rb number_of_times_to_calc_factorial factorial_to_calc
  e.g. ruby memoization_by_hand.rb 10000 200

$ bundle exec ruby memoization_by_hand.rb 10000 200
                  user     system      total        real
without memoize  0.890000   0.010000   0.900000 (  0.900780)
with memoize  0.020000   0.000000   0.020000 (  0.022810)

Memoize

The memoize gem was early on the scene and the first I’d used. It has since bee been retired. Per the repo:

It has long been surpassed by other, better memoization gems like memoizable and memoist

It still works though! Running the memoize_example.rb example:

$ bundle exec ruby memoize_example.rb
Usage: ruby memoize_example.rb number_of_times_to_calc_factorial factorial_to_calc
  e.g. ruby memoize_example.rb 10000 200

$ bundle exec ruby memoize_example.rb 10000 200
                  user     system      total        real
without memoize  0.840000   0.010000   0.850000 (  0.846640)
with memoize  0.020000   0.000000   0.020000 (  0.020939)

Memoist

memoist is a stand-alone version of ActiveSupport::Memoizable, extracted when it was retired from core ActiveSupport.

Running the memoist_example.rb example:

$ bundle exec ruby memoist_example.rb
Usage: ruby memoist_example.rb number_of_times_to_calc_factorial factorial_to_calc
  e.g. ruby memoist_example.rb 10000 200

$ bundle exec ruby memoist_example.rb 10000 200
                  user     system      total        real
without memoist  0.840000   0.010000   0.850000 (  0.841281)
with memoist  0.030000   0.000000   0.030000 (  0.026051)

Others

Search for other memoize gems in rubygems.

Memoizable

No demo for memoizable as it has a number of limitations, the most serious being that it can only memoize methods with an arity of 0 (i.e. no parameters)

Credits and References

About LCK#161 rubydesign patterns
Project Source on GitHub Return to the Project Catalog

This page is a web-friendly rendering of my project notes shared in the LittleCodingKata GitHub repository.

LittleCodingKata is my collection of programming exercises, research and code toys broadly spanning things that relate to programming and software development (languages, frameworks and tools).

These range from the trivial to the complex and serious. Many are inspired by existing work and I'll note credits and references where applicable. The focus is quite scattered, as I variously work on things new and important in the moment, or go back to revisit things from the past.

This is primarily a personal collection for my own edification and learning, but anyone who stumbles by is welcome to borrow, steal or reference the work here. And if you spot errors or issues I'd really appreciate some feedback - create an issue, send me an email or even send a pull-request.