6 ms·

The Racket Blog: Dynamic Programming versus Memoization

drunkpotato 14y ago
This is a really interesting way to think about computations. I mostly think of memoization for I/O things like database lookups, or long computations. I'd never thought of it in comparison to dynamic programming algorithms.
- spaghetti 14y ago
  Memoization and dynamic programming come together in top down DP algorithms. These are also referred to as recursion with memoization. The recursive function often looks something like: f(arguments) { results = memoTable[arguments] if(results) // use results else results = // expensive recursive call to f memoTable[arguments] = results }
  - oskarkv 14y ago
    As far as I have understood, this is just regular memoization. I mean, often in functional languages one just turns a regular function into a memoized version by calling memoize(function). Sometimes that works to create a function that does what your code does, and sometimes it does not. When it does not I think that's a shortcoming of the language/implementation.
- irahul 14y ago
  > I'd never thought of it in comparison to dynamic programming algorithms. The blog post is using a different terminology. Memoization isn't part of dynamic programming - it's just that the top-down dynamic programming benefits from memoization. The top-down fibonacci is defined as fib(n) = fib(n-1) + fib(n-2) Since fib(n-1) and fib(n-2) are overlapping(they have to overlap for it to be an example of dynamic programming), memoization reduces the number of computations. But that's not to say that a non-memoizing solution isn't an example of dynamic programming. The bottom-up dynamic programming is the iterative solution. The blog post is calling the top-down DP as memoization, and bottom-up DP as dynamic programming. I don't think this terminology is common(or correct).
  - cyarvin 14y ago
    I don't know that the terminology is common (or correct), but I find it pretty useful. It also corresponds intuitively to the way people in practice use these terms. I say keep it. TLDR for OP: in both "DP" and "memoization" you construct a name-value table for a given function. In "memoization" you construct it reactively, in "DP" proactively - where "reactively" means "lazily as we need it," and "proactively" means "any way that isn't reactively." (A dag being just one way of storing this data structure. Generally it is just a cache of function results - which can be stored as a table, derivation graph, or whatever.)
lukev 14y ago
My lack of a formal CS background is hurting me here. Could someone speak to the distinction between a tree and a DAG they make here? I was under the impression that the terms were more or less synonymous.
- nandemo 14y ago
  A tree is a DAG that is connected: if a and b are nodes of a tree, there is a path between a and b. But in general a DAG doesn't have to be connected. So all trees are DAGs but not all DAGs are trees: some are forests i.e. unions of trees.
  - ot 14y ago
    That's wrong, not all connected DAGs are trees. A DAG is a directed graph that has no (directed) loops. Consider the following: A / \ v v B C \ / v v D This is a DAG but not a tree, because it has an undirected loop but no directed loops.
    - nandemo 14y ago
      You're totally right (I had a thinko and managed to miss the D in the DAG). My apologies for the misinformation.
  - qlkzy 14y ago
    Trees are, in general, undirected (although it is often convenient to treat edges in rooted trees as being all directed towards or away from the root, to determine whether or not a graph is a tree it is necessary to consider the edges as undirected). A tree is a connected undirected acyclic graph (or, equivalently, an undirected graph in which there is exactly one path between any pair of vertices). A DAG may represent a tree (usually rooted) or it may not. Not all connected DAGs are trees e.g.: a->b, a->c, b->d, c->d is a DAG, but not a tree.
  - deleted 14y ago
    [deleted]
  - 14y ago
mattj 14y ago
I think this neglects a performance consideration: dynamic programming is often simpler for a compiler to optimize, since it's generally a set of nested loops. Sometimes you can vectorize operations, but often you can just exploit locality to keep all the active set in l1 cache (not a compiler optimization per-se). Memoization, however, is much more of a black-box. Very few compilers will handle the branching present in memoized function calls in the same way they'd handle a loop (which is also a branch, but a more predictable one). That all being said, memoization is often simpler to reason about and great for infrequent computations.
- rcfox 14y ago
  This won't help everywhere, but sometimes you can give the compiler a hint that a certain branch is less likely to be taken. The computation branch is going to be slower anyway, and only happen once, so tell the compiler to assume the lookup branch will be taken most of the time.
tbenst 14y ago
I had Shriram as a professor - great lecturer. Here's a racket implementation for the memoize function based off of class notes: #lang racket (define memo-table (box empty)) (define-struct memo (key ans)) (define (memoize f) (lambda args (local ([define lookup (filter (lambda (v) (equal? args (memo-key v))) (unbox memo-table))]) (if (empty? lookup) (begin (local ([define ans (apply f args)]) (begin (set-box! memo-table (cons (make-memo args ans) (unbox memo-table))) ans))) (memo-ans (first lookup)))))) Edit: I guess HN doesn't like my formatting. Here's a readable version http://pastie.org/4591751 http://pastie.org/4591751
- gus_massa 14y ago
  You should use an empty line to make a new paragraph, and then start every line with two spaces: #lang racket (define memo-table (box empty)) (define-struct memo (key ans)) (define (memoize f) (lambda args (local ([define lookup (filter (lambda (v) (equal? args (memo-key v))) (unbox memo-table))]) (if (empty? lookup) (begin (local ([define ans (apply f args)]) (begin (set-box! memo-table (cons (make-memo args ans) (unbox memo-table))) ans))) (memo-ans (first lookup))))))
- Fixnum 14y ago
  Be careful -- this doesn't fully memoize recursive functions unless you force the computation of intermediate results, since the recursive calls don't use memoization: (define memo-fib (memoize fib)) ;; example from SICP (memo-fib 40) ;; long wait I would love to see a good general-purpose 'memoize but rather doubt it's possible, though I think I remember seeing one in Common Lisp in "Paradigms of Artificial Intelligence Programming" that exploited CL's weird namespacing rules for functions to make recursive functions like 'fib run fast.
  - kenko 14y ago
ced 14y ago
Wikipedia has an implementation of Fibonacci with DP, and another with memoization. It's a clearer explanation than the blog provides. https://en.wikipedia.org/wiki/Dynamic_programming#Fibonacci_sequence https://en.wikipedia.org/wiki/Dynamic_programming#Fibonacci_...
hobbyist 14y ago
Dynamic programming is an optimization technique using divide and conquer, whereas memoization is an added optimization in the dynamic programming paradigm. An optimization we do while calculating fibonacci sequence is memoization, to prevent from going down the tree to the leaf every time.

This is a really interesting way to think about computations. I mostly think of memoization for I/O things like database lookups, or long computations. I'd never thought of it in comparison to dynamic programming algorithms.

spaghetti 14y ago
Memoization and dynamic programming come together in top down DP algorithms. These are also referred to as recursion with memoization. The recursive function often looks something like: f(arguments) { results = memoTable[arguments] if(results) // use results else results = // expensive recursive call to f memoTable[arguments] = results }
- oskarkv 14y ago
  As far as I have understood, this is just regular memoization. I mean, often in functional languages one just turns a regular function into a memoized version by calling memoize(function). Sometimes that works to create a function that does what your code does, and sometimes it does not. When it does not I think that's a shortcoming of the language/implementation.
irahul 14y ago
> I'd never thought of it in comparison to dynamic programming algorithms. The blog post is using a different terminology. Memoization isn't part of dynamic programming - it's just that the top-down dynamic programming benefits from memoization. The top-down fibonacci is defined as fib(n) = fib(n-1) + fib(n-2) Since fib(n-1) and fib(n-2) are overlapping(they have to overlap for it to be an example of dynamic programming), memoization reduces the number of computations. But that's not to say that a non-memoizing solution isn't an example of dynamic programming. The bottom-up dynamic programming is the iterative solution. The blog post is calling the top-down DP as memoization, and bottom-up DP as dynamic programming. I don't think this terminology is common(or correct).
- cyarvin 14y ago
  I don't know that the terminology is common (or correct), but I find it pretty useful. It also corresponds intuitively to the way people in practice use these terms. I say keep it. TLDR for OP: in both "DP" and "memoization" you construct a name-value table for a given function. In "memoization" you construct it reactively, in "DP" proactively - where "reactively" means "lazily as we need it," and "proactively" means "any way that isn't reactively." (A dag being just one way of storing this data structure. Generally it is just a cache of function results - which can be stored as a table, derivation graph, or whatever.)

lukev 14y ago

My lack of a formal CS background is hurting me here. Could someone speak to the distinction between a tree and a DAG they make here? I was under the impression that the terms were more or less synonymous.

nandemo 14y ago
A tree is a DAG that is connected: if a and b are nodes of a tree, there is a path between a and b. But in general a DAG doesn't have to be connected. So all trees are DAGs but not all DAGs are trees: some are forests i.e. unions of trees.
- ot 14y ago
  That's wrong, not all connected DAGs are trees. A DAG is a directed graph that has no (directed) loops. Consider the following: A / \ v v B C \ / v v D This is a DAG but not a tree, because it has an undirected loop but no directed loops.
  - nandemo 14y ago
    You're totally right (I had a thinko and managed to miss the D in the DAG). My apologies for the misinformation.
- qlkzy 14y ago
  Trees are, in general, undirected (although it is often convenient to treat edges in rooted trees as being all directed towards or away from the root, to determine whether or not a graph is a tree it is necessary to consider the edges as undirected). A tree is a connected undirected acyclic graph (or, equivalently, an undirected graph in which there is exactly one path between any pair of vertices). A DAG may represent a tree (usually rooted) or it may not. Not all connected DAGs are trees e.g.: a->b, a->c, b->d, c->d is a DAG, but not a tree.
- deleted 14y ago
  [deleted]
- 14y ago

mattj 14y ago

I think this neglects a performance consideration: dynamic programming is often simpler for a compiler to optimize, since it's generally a set of nested loops. Sometimes you can vectorize operations, but often you can just exploit locality to keep all the active set in l1 cache (not a compiler optimization per-se). Memoization, however, is much more of a black-box. Very few compilers will handle the branching present in memoized function calls in the same way they'd handle a loop (which is also a branch, but a more predictable one). That all being said, memoization is often simpler to reason about and great for infrequent computations.

rcfox 14y ago
This won't help everywhere, but sometimes you can give the compiler a hint that a certain branch is less likely to be taken. The computation branch is going to be slower anyway, and only happen once, so tell the compiler to assume the lookup branch will be taken most of the time.

tbenst 14y ago

I had Shriram as a professor - great lecturer. Here's a racket implementation for the memoize function based off of class notes: #lang racket (define memo-table (box empty)) (define-struct memo (key ans)) (define (memoize f) (lambda args (local ([define lookup (filter (lambda (v) (equal? args (memo-key v))) (unbox memo-table))]) (if (empty? lookup) (begin (local ([define ans (apply f args)]) (begin (set-box! memo-table (cons (make-memo args ans) (unbox memo-table))) ans))) (memo-ans (first lookup)))))) Edit: I guess HN doesn't like my formatting. Here's a readable version http://pastie.org/4591751 http://pastie.org/4591751

gus_massa 14y ago
You should use an empty line to make a new paragraph, and then start every line with two spaces: #lang racket (define memo-table (box empty)) (define-struct memo (key ans)) (define (memoize f) (lambda args (local ([define lookup (filter (lambda (v) (equal? args (memo-key v))) (unbox memo-table))]) (if (empty? lookup) (begin (local ([define ans (apply f args)]) (begin (set-box! memo-table (cons (make-memo args ans) (unbox memo-table))) ans))) (memo-ans (first lookup))))))
Fixnum 14y ago
Be careful -- this doesn't fully memoize recursive functions unless you force the computation of intermediate results, since the recursive calls don't use memoization: (define memo-fib (memoize fib)) ;; example from SICP (memo-fib 40) ;; long wait I would love to see a good general-purpose 'memoize but rather doubt it's possible, though I think I remember seeing one in Common Lisp in "Paradigms of Artificial Intelligence Programming" that exploited CL's weird namespacing rules for functions to make recursive functions like 'fib run fast.
- kenko 14y ago

ced 14y ago

Wikipedia has an implementation of Fibonacci with DP, and another with memoization. It's a clearer explanation than the blog provides. https://en.wikipedia.org/wiki/Dynamic_programming#Fibonacci_sequence https://en.wikipedia.org/wiki/Dynamic_programming#Fibonacci_...

hobbyist 14y ago

Dynamic programming is an optimization technique using divide and conquer, whereas memoization is an added optimization in the dynamic programming paradigm. An optimization we do while calculating fibonacci sequence is memoization, to prevent from going down the tree to the leaf every time.