teaching machines

CS 330 Lecture 36 – Memoization

April 30, 2014 by . Filed under cs330, lectures, spring 2014.

Agenda

TODO

Program This

Code

fibs.hs

import Data.Function.Memoize

fib :: Int -> Int
fib n
  | n == 0 = 0
  | n == 1 || n == 2 = 1
  | otherwise = fib (n - 1) + fib (n - 2)

fastfib :: Int -> Int
fastfib = memoize fibHelper
  where
    fibHelper :: Int -> Int
    fibHelper n
      | n == 0 = 0
      | n == 1 || n == 2 = 1
      | otherwise = fastfib (n - 1) + fastfib (n - 2)

nroutes :: Int -> Int -> Int
nroutes = memoize2 nroutesHelper
  where
    nroutesHelper :: Int -> Int -> Int
    nroutesHelper x y
      | x == 0 && y == 0 = 1
      | x < 0 || y < 0 = 0
      | otherwise = nroutes (x - 1) y + nroutes x (y - 1)

memoize.rb

#!/usr/bin/env ruby

def fib n
  if n <= 1
    n
  else
    fib(n - 2) + fib(n - 1)
  end
end

def memoize symbol_to_f
  cache = Hash.new
  f = method(symbol_to_f)

  l = lambda do |*params|
    # Check cache for f(n) first. Try to reuse earlier result. 
    if not cache.has_key? params
      cache[params] = f.call(*params)
    end
    cache[params]
  end

  Object.send(:define_method, symbol_to_f, l)

  l
end

memoize :fib
(1..20).each do |n|
  puts fib(n)
end
puts fib(30)

Haiku

It’s hard to do both
“Be fruitful and multiply”
Unless you memoize

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *