---
title: Remember to Use Memoization!
subtitle: Seminar at Lenoir-Rhyne University
author: ClĂ©ment Aubert
date: 10/02/2017
dir: ltr
keywords:
- Computer Science
- Optimization Techniques
- Memoization
- Automata Theory
- Software Engineering
documentclass: scrartcl
---
* * *
## Abstract
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 at [http://lacl.fr/~caubert/LR/](http://lacl.fr/~caubert/LR/).
## When and Where?
### When
Friday, February 10, 2017, 2:30 PM -- 3:30 PM
### Where
Rhyne 161, [Lenoir-Rhyne University](http://www.lr.edu/), 625 7th Ave NE, Hickory, NC 28601.
* * *
## Preliminary Material
### Motivational Example
Assume your colleague/classmate Bertrand asks you to review his (`java`) code:
```java
public class Example{
public static int f(int n){
int x = 0;
// Assume some code here, possibly changing the value of x
return x;
}
public static void main(String[] args){
System.out.println(f(35));
// Some other code.
// And then, after a while
System.out.println(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:
```java
public class Example{
// You leave his function f unchanged,
public static int f(int n){
int x = 0;
// Assume some code here, possibly changing the value of x
return x;
}
public static void main(String[] args){
// But you store the value of f(35) into a variable:
int x = f(35);
// And then use that variable:
System.out.println(x);
// Some other code, unchaged
System.out.println(x + "is a nice number");
}
}
```
You send back your "optimized code" to Bertrand, but Bertrand starts complaining that you broke his program.
#. Is Bertrand right, could it be that you broke his program?
#. Give two examples of definition of the function `f` where your optimization would be correct.
#. Can you give three examples of definition of the function `f` where you optimization _wouldn't be_ correct?
#. What are the condition on `f` and on the system for this transformation to be indeed an optimization?
Solutions:
[](#spoiler "Come to the lecture to discover them!")
### Automata Theory
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.
#### Definition of Automata
Generally speaking, an _automaton_ (a.k.a. "finite automaton", or "finite state machine") is
* A _finite alphabet_ $\Sigma$,
* A _finite set of states_ $S$, including an _initial state_ $s_i$ and an _accepting state_ $s_a$,
* A _transition function_ $\delta : \Sigma \times S \to S$.
Intuitively, the automaton is given an input word $n \subseteq \Sigma^{|n|}$, and then it reads the first character of $n$ and applies its transition function: according to its initial state $s_i$, 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 $s_a$, 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:
#. The addition of the capacity to move back and forth on the input word,
#. The addition of a "pushdown stack".
#### Exercises:
#. Try to write the definition of a "Two-way finite automata", i.e., of an automaton capable of moving back-and-forth on the input word.
*Hint: in a first approximation, you only need to change the co-domain of the transition function, and the definition of halting.*
#. You want to prevent your automaton from "falling out of the input", i.e., to read an instruction "go fetch the previous character" when you're already at the first character. How to do that?
*Hint: suppose the input word is surrounded by "end markers", that tell the automaton that it reaches the beginning or end of the word, and impose a condition on the transition function.*
#. Now, you supposedly have the correct definition of a "Two-way finite automaton".
Compare your definition with the one [on Wikipedia](https://en.wikipedia.org/wiki/Two-way_deterministic_finite_automaton#Formal_description).
* * *
## Code Used During the Lecture
All the code showed during the lecture was in `Java`.
You can [download it](Fib.java), or play on-line with it at [rextester](http://rextester.com/XTXVX32422) or at [tutorialpoint](https://www.tutorialspoint.com/compile_java_online.php?PID=0Bw_CjBb95KQMNUVwMllVdTFIQmc) (please fork it before editing it).
* * *
## To Go Further
### How to Use Memoization with your Favorite Language?
Numerous resources are dedicated to this question, cf. for instance the ~700 questions tagged "memoization" [on stackoverflow.com](https://stackoverflow.com/questions/tagged/memoization).
If you are interested in using memoization for a particular language, you may be interested in the following resources:
* __In `C++`__, memoization is one of [the common technique](https://en.wikibooks.org/wiki/Optimizing_C%2B%2B/General_optimization_techniques/Memoization) to optimize your program.
* __In `C#`__, [this article](https://spin.atomicobject.com/2011/10/27/generic-memoization-in-c/) will give you the main keys to memoize functions with multiple arguments.
* __In `Haskell`__, [the wiki](https://wiki.haskell.org/Memoization) has a really complete page, with numerous examples and useful references.
* __In `Java`__, in complement of [the code I gave](Fib.java), [you can first look at a simple implementation](https://www.interviewcake.com/concept/java/memoization) before [considering an interesting variation](https://ycpcs.github.io/cs201-fall2016/lectures/lecture22.html).
* __For `Javascript`__, [a very complete article](https://addyosmani.com/blog/faster-javascript-memoization/), including benchmarking and comparisons of implementation techniques, should get you started.
* __In `Perl`__, ["memoize"](http://perldoc.perl.org/Memoize.html) is already a part of the core modules, and its [regex engine](http://perlmonks.org/index.pl?node_id=502408) actually uses memoization! For an excellent explanation of this latter point, in `Perl` and linking it to automaton, cf. [this article](https://swtch.com/~rsc/regexp/regexp1.html).
* __In `Python`__, [this page](http://www.python-course.eu/python3_memoization.php) will provide a gentle introduction to memoization, and on how to perform it using decorators.
* __In `R`__, consult [James Balamuta's slides](http://stat385.thecoatlessprofessor.com/assets/lectures/lec5/lec5_functions_recursion_memoization_benchmarking.pdf) on _Functions, Recursion, Benchmarking, and Memoization_.
* __In `Ruby`__, [this article](http://www.justinweiss.com/articles/4-simple-memoization-patterns-in-ruby-and-one-gem/) will give you some hints on how to use memoization, but the bottom line is: [use memoist](https://github.com/matthewrudy/memoist) (which relies on [ActiveSupport::Memoizable](http://apidock.com/rails/v3.2.13/ActiveSupport/Memoizable/memoize), that happens to be sometimes [counter-productive](https://bibwild.wordpress.com/2011/07/14/beware-of-activesupportmemoizable/)!)
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](#misc.)!
If you have an account on Codewars, you can also browse the [memoization tag](https://www.codewars.com/kata/search/my-languages?&tags=Memoization) to get some hand-on experience.
You can also browse [the memoization tag](https://codereview.stackexchange.com/questions/tagged/memoization) on codereview to get a practical sense of when is this method used.
### Research Papers
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](http://cs.stackexchange.com/a/60058/20161) is probably well-suited. It is clear and compact, but assume some knowledge of automata and languages.
* *[Simulation of Two-Way Pushdown Automata Revisited](http://dx.doi.org/10.4204/EPTCS.129.15)* is a clear, brilliant, and compact presentation of the memoization technique used to simulate Two-way pushdown automata.
* *[Partial memoization for obtaining linear time behavior of a 2DPDA](http://dx.doi.org/10.1016/0304-3975(92)90008-4)* is an accessible, self-contained and relatively short (10 pages) paper that introduces a generalization of memoization called "partial memoization".
* *[Compile-Time Function Memoization](https://hal.inria.fr/hal-01423811)* is a recent (it was presented at [CC 2017](http://conf.researchr.org/home/CC-2017), a conference be held last week at Austin!) paper that proposes to implement memoization in `C++` compilators!
* * *
## Misc.
* Download [a `pdf` version](index.pdf) or [the `md` source](index.md) of this page
* [HTML5](https://validator.w3.org/check?uri=http%3A%2F%2Flacl.fr%2F~caubert%2Fnotes%2Fexemples_cand_tt%2FLR%2F&charset=%28detect+automatically%29&doctype=Inline&group=0) and [CSS3](https://jigsaw.w3.org/css-validator/validator?uri=http%3A%2F%2Flacl.fr%2F~caubert%2Fnotes%2Fexemples_cand_tt%2FLR%2F&profile=css3&usermedium=all&warning=1&vextwarning=&lang=en) valid
* [Creative Commons Attribution 4.0 International License](http://creativecommons.org/licenses/by/4.0/)
* []("contact")Contact: [aubertc@appstate.edu](mailto:aubertc@appstate.edu "contact")
* Created with [debian](https://www.debian.org/), [pandoc](http://pandoc.org/), [latex](https://www.latex-project.org/) and [emacs](https://www.gnu.org/software/emacs/).