Sunday, July 12, 2015

Memoize OR How to Trim Your Function Budget

"Roman, remember by your strength to rule
Earth’s peoples—for your arts are to be these:
To pacify, to impose the rule of law,
To spare the conquered, battle down the proud.
-- Virgil, Aeneid
Book 6, Lines 1151 - 1154

Problem Statement

Say you have an operation in a function that cost a lot, like reading from a database or launching a missile.  You would like to be able to call the function as often as you need to for your algorithm but you would like to only do the database read or missile launch once if the arguments have not changed.  This is what memoize is used for.

How Memoize Works

Returns a memoized version of a referentially transparent function. The memoized version of the function keeps a cache of the mapping from arguments to results and, when calls with the same arguments are repeated often, has higher performance at the expense of higher memory use.
-- Memoize's doc string in clojure/core.clj

In my own words (yeah, I think in pictures).

In the image above we see that we always check to see if the cache for the function has a result already for the arguments given.  If it does already contain the arguments then return that result.  If it does not already have a result for the given arguments then: calculate it, store the result in the cache, and return the result.


In the example above we see that we have a function with the side effect of printing the string "Calculating...", thus when the function is called it will print the string and then return the result (think read from database or launch missiles).  When we wrap the function with a memoize and see that on the second call to the function we do not have any side effects!


There you have it, you can freely read from your database or launch missiles in your function without worrying about the number of times you call said function with the same arguments.