3 ms·

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 neve

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.)

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.)