teaching machines

CS 330 Lecture 36 – Memoization

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

Agenda

• what ?s
• program this
• the benefits of no side-effects
• memoization in Haskell
• memoization in Ruby

TODO

• Read about tool selection and the lack of silver bullets: http://blog.awe.sm/2012/12/10/how-to-choose-the-right-tool-for-the-job-awe-sms-language-journey and http://frankchimero.com/blog/no-new-tools.
• Read on laziness in D: http://dlang.org/lazy-evaluation.html.
• Go to CERCA (Ojibwe Ballroom, 3rd floor Davies) and talk to some student researchers.
• Pick one or two or three. 1/4 sheet.

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