6 people like it.

Memoization for dynamic programming

The snippet shows how to implement reusable memoization function and how to use it to implement efficient Fibonacci number generator using dynamic programming.

Recursive Fibonacci

1: 
2: 
3: 
4: 
5: 
6: 
7: 
8: 
  /// Inefficient recursive implementation of Fibonacci numbers.
  /// 
  /// The problem is that 'fibs 3' will call 'fibs 1' recursively
  /// three times. To solve this, we'd like to keep the result of
  /// previously calculated function calls using dynamic programming.
  let rec fibs n = 
    if n < 1 then 1 else
    (fibs (n - 1)) + (fibs (n - 2))

Reusable memoization function

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
    open System.Collections.Generic
    
    /// The function creates a function that calls the argument 'f'
    /// only once and stores the result in a mutable dictionary (cache)
    /// Repeated calls to the resulting function return cached values.
    let memoize f =    
      // Create (mutable) cache that is used for storing results of 
      // for function arguments that were already calculated.
      let cache = new Dictionary<_, _>()
      (fun x ->
          // The returned function first performs a cache lookup
          let succ, v = cache.TryGetValue(x)
          if succ then v else 
            // If value was not found, calculate & cache it
            let v = f(x) 
            cache.Add(x, v)
            v)

Memoized Fibonacci

1: 
2: 
3: 
4: 
5: 
6: 
7: 
8: 
9: 
    /// Recursive function that implements Fibonacci using memoization.
    /// Recursive calls are made to the memoized function, so previously
    /// calculated values are retrieved from the cache.
    let rec fibs = memoize (fun n ->
      if n < 1 then 1 else
      (fibs (n - 1)) + (fibs (n - 2)))

    // Note - add #nowarn "40" to disable warning complaining about recursive
    // value reference. This is not an issue in this snippet.
val fibs : n:int -> int

Full name: Script.Simple.fibs


 Inefficient recursive implementation of Fibonacci numbers.
 
 The problem is that 'fibs 3' will call 'fibs 1' recursively
 three times. To solve this, we'd like to keep the result of
 previously calculated function calls using dynamic programming.
val n : int
namespace System
namespace System.Collections
namespace System.Collections.Generic
val memoize : f:('a -> 'b) -> ('a -> 'b) (requires equality)

Full name: Script.Memoized.memoize


 The function creates a function that calls the argument 'f'
 only once and stores the result in a mutable dictionary (cache)
 Repeated calls to the resulting function return cached values.
val f : ('a -> 'b) (requires equality)
val cache : Dictionary<'a,'b> (requires equality)
Multiple items
type Dictionary<'TKey,'TValue> =
  new : unit -> Dictionary<'TKey, 'TValue> + 5 overloads
  member Add : key:'TKey * value:'TValue -> unit
  member Clear : unit -> unit
  member Comparer : IEqualityComparer<'TKey>
  member ContainsKey : key:'TKey -> bool
  member ContainsValue : value:'TValue -> bool
  member Count : int
  member GetEnumerator : unit -> Enumerator<'TKey, 'TValue>
  member GetObjectData : info:SerializationInfo * context:StreamingContext -> unit
  member Item : 'TKey -> 'TValue with get, set
  ...
  nested type Enumerator
  nested type KeyCollection
  nested type ValueCollection

Full name: System.Collections.Generic.Dictionary<_,_>

--------------------
Dictionary() : unit
Dictionary(capacity: int) : unit
Dictionary(comparer: IEqualityComparer<'TKey>) : unit
Dictionary(dictionary: IDictionary<'TKey,'TValue>) : unit
Dictionary(capacity: int, comparer: IEqualityComparer<'TKey>) : unit
Dictionary(dictionary: IDictionary<'TKey,'TValue>, comparer: IEqualityComparer<'TKey>) : unit
val x : 'a (requires equality)
val succ : bool
val v : 'b
Dictionary.TryGetValue(key: 'a, value: byref<'b>) : bool
Dictionary.Add(key: 'a, value: 'b) : unit
val fibs : (int -> int)

Full name: Script.Memoized.fibs


 Recursive function that implements Fibonacci using memoization.
 Recursive calls are made to the memoized function, so previously
 calculated values are retrieved from the cache.
Raw view Test code New version

More information

Link:http://fssnip.net/8P
Posted:12 years ago
Author:Tomas Petricek
Tags: memoization , dynamic programming , fibonacci