Subscribe to The Madman Scribblings        RSS Feed
-----

A Simple Memoization Function Class.

26 May 2013
Icon 1 Comments
Posted by AdamSpeight2008 Icon
A Simple Memoization Function Class.

Memoization is simply remembering the previous worked out answers for the value inputted for the function.
Public Class Memo(Of T0 , T1 )
  Private TheFunction As Func(Of Memo(of T0,T1),T0,T1)
  Private MemoizationValues As New Dictionary(Of T0,T1)
  Public Sub New ( TheFunction As Func(of Memo(Of T0 , T1), T0, T1 ) )
    Me.TheFunction = TheFunction
  End Sub
  Public Default  Property Fun(x As T0) As T1
    Set(Value As T1)
      If Not MemoizationValues.ContainsKey(x) Then MemoizationValues(x) = Value 
    End Set
    Get
      If MemoizationValues.ContainsKey(x) Then Return MemoizationValues(x)
      Dim Value = TheFunction(Me,x)
      MemoizationValues(x)=Value
      Return Value
    End Get
  End Property
End Class



Now let define a few functions.

Fibonacci
Dim fib As New Memo(Of BigInteger, BigInteger)(Function(f,x) f(x-2) + f(x-1))
fib(0) = 0
fib(1) = 1

Console.WriteLine("Fib(10) = ", Fib(10))


Factorial
Dib Fact As New Memo(Of BigInteger, BigInteger(Function(f,x) x * f(x-1))
f(0) = 1

Console.WriteLine("Fact(10) = ", Fact(10) )


Both are rather close to how you would write the mathematically.

Categories: Uncategorized

Back to The Madman Scribblings →

1 Comments On This Entry

Page 1 of 1

AdamSpeight2008 Icon

28 May 2013 - 10:21 AM
Here is also an extension method the does the same.
 <Extension>
  Public Function Memoized(Of Tin, TResult)(fn As Func(Of Tin, TResult)) As Func(Of Tin, TResult)
    Dim m As New Dictionary(Of Tin, TResult)()
    Return Function(x As Tin) As TResult
             If m.ContainsKey(x) Then Return m(x)
             Dim r = fn(x)
             m.Add(x, r)
             Return r
           End Function
  End Function

Usage
    Dim mfu as Func(Of Integer,Integer) = Function(x) If( (0 <= x) AndAlso (x < 2),x, mfu(x - 2) + mfu(x - 1))
    mfu = mfu.Memoize


Strange thing 1

Type of mfu can do not be inferred
Dim mfu = Function(x) If( (0 <= x) AndAlso (x < 2),x, mfu(x - 2) + mfu(x - 1))

Why?
Spoiler

Strange thing 2
'Memoized' is not a member of '<anonymous method> 
Dim mfu As Func(Of Integer,Integer) =( Function(x) If( (0 <= x) AndAlso (x < 2),x, mfu(x - 2) + mfu(x - 1))).Memoized
0
Page 1 of 1

Search My Blog

Recent Entries

Recent Comments