Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Dynamic Programming versus Memoization

blog.racket-lang.org

Post reply on HN
Print view View original

1–10 of 29 posts

Re: Dynamic Programming versus Memoization

#4

Post by nandemo »

lukev wrote: post #3

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.

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.

Re: Dynamic Programming versus Memoization

#5

Post by spaghetti »

drunkpotato wrote: post #2

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.

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
    }

Re: Dynamic Programming versus Memoization

#6

Post by mattj »

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.

Re: Dynamic Programming versus Memoization

#7

Post by ot »

nandemo wrote: post #4
lukev wrote: post #3

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.

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.

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.

Re: Dynamic Programming versus Memoization

#8

Post by pilgrim689 »

lukev wrote: post #3

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.

A DAG has directed edges, whereas a tree does not. Also, a node in a tree can only have 1 parent.

Here's an example of a DAG that can't be a tree because of the edge directions:

http://en.wikipedia.org/wiki/File:Directed_acyclic_graph_3.s...

Re: Dynamic Programming versus Memoization

#10

Post by qlkzy »

nandemo wrote: post #4
lukev wrote: post #3

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.

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.

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.

Post reply on HN