Memoization is an optimization technique that trades (a bit of) space for (a lot of) time. It comes in multiple forms, and you may already use it without knowing it. This technique cannot always be applied, but when properly used, it can speedup the running time from exponential to linear!
We’ll motivate the introduction of memoization with some examples, introduces to its origins, and mention the limitations of this technique. Although not necessary to understand this lecture, some preliminary material, as well as exercises, will be posted Saturday 01/21 at http://lacl.fr/~caubert/RH/.
Monday, January 23, 2017, 4:20 PM – 5:10 PM
Room O257, Olin Hall, Rose-Hulman institute, 5500 Wabash Avenue Terre Haute, IN .
Assume your colleague/classmate Bertrand asks you to review his (
def f(n): # Assume some clever code here pass print f(35) # Some other code # And then, after a while, print f(35), "is a nice number"
You feel like Bertrand is uselessly computing
f(35) twice, and decide to “improve” his code by doing the following:
# You leave his function f unchanged, def f(n): # Assume some clever code here pass # But you store the value of f(35) into a variable: x = f(35) # And then use that variable: print x # Some other code, unchanged print x, "is a nice number"
You send back your “optimized code” to Bertrand, but Bertrand starts complaining that you broke his program.
fwhere your optimization would be correct.
fwhere you optimization wouldn’t be correct?
fand on the system for this transformation to be indeed an optimization?
To study memoization, we’ll have a peek at the context in which it was created: automata theory. It is not needed to have an extensive knowledge of this topic to understand the lecture, but the following should help you get some familiarities with the main concepts.
Generally speaking, an automaton (a.k.a. “finite automaton”, or “finite state machine”) is
Intuitively, the automaton is given an input word n ⊆ Σ∣n∣, and then it reads the first character of n and applies its transition function: according to its initial state si, it changes its state, and move to the next character. The transition function is then applied until it is not defined for the couple (current character, current state). When there is no more character to read in n, or when the transition function can’t be applied, the automaton halts. If the automaton stops in the state sa, then we say that the automaton accepts the word n, otherwise we say that it rejects the word n.
There are plenty of variations on automaton. We are going to study two of them:
All the code showed during the lecture was in Python. You can download it, or play on-line with it at rextester or at tutorialpoint (please fork it before editing it).
Numerous resources are dedicated to this question, cf. for instance the ~700 questions tagged “memoization” on stackoverflow.com. If you are interested in using memoization for a particular language, you may be interested in the following resources:
R, consult James Balamuta’s slides on Functions, Recursion, Benchmarking, and Memoization.
Java, you can first look at a simple implementation before considering an interesting variation.
Python, this page will provide a gentle introduction to memoization, and on how to perform it using decorators.
Ruby, this article will give you some hints on how to use memoization, but the bottom line is: use memoist (which relies on ActiveSupport::Memoizable, that happens to be sometimes counter-productive!)
Perl, “memoize” is already a part of the core modules, and its regex engine actually uses memoization! For an excellent explanation of this latter point, in
Perland linking it to automaton, cf. this article.
Haskell, the wiki has a really complete page, with numerous examples and useful references.
C#, this article will give you the main keys to memoize functions with multiple arguments.
C++, memoization is one of the common technique to optimize your program.
Memoization is virtually available for every programming language. If you feel like I forgot your favorite language, if you find a better technique that the ones listed above, feel free to send a line! If you have an account on Codewars, you can also browse the memoization tag to get some hand-on experience. You can also browse the memoization tag on codereview to get a practical sense of when is this method used.
As a warm-up, to understand how memoization is used to prove that the halting problem for Pushdown Automata (called PDA) is decidable in polynomial time, this answer is probably well-suited. It is clear and compact, but assume some knowledge of automata and languages.