11–20 of 29 posts
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.
#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
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 }
https://en.wikipedia.org/wiki/Dynamic_programming#Fibonacci_...
Earlier quoted context omitted.
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.
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-tab…
#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))))))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.
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).
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-tab…
(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.
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-tab…
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 Intellig…
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-tab…
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 Intellig…