In the past blog entries I played with an imperative IEnumerable wrapped implementation of the sequence. The mathematical definition of the Fibonacci sequence is a recursive one. It is both compact and beautiful. However if you implement this literally in C# or VB.NET you will get a terribly slow program that may even crash due to stack overflow. An imperative implementation that calculates Fib(n) for any random n may be a bit faster but is still slow. The code would be less comprehensible.
It would be great to have a Fibonacci function that caches calculated results and in definition is close to the mathematical definition. Some smart brains generalised caching in a so-called Memoize or Memento pattern.(Still wondering who invented it first.) The Memento function wraps a normal function and caches its results. When the function is called again with the same arguments the cached results will be returned.
A very clean C# solution can be found on Bart de Smet’s Blog. Here a generic extension method is defined that allows for caching any function with one argument of whatever type. The result can also be of any type. I used his implementation as a basis for my VB exploration of Memoize.
- Lambda functions did not compile on Mono 2.01’s VB.NET on Ubuntu Jaunty, so I went back to Visual Studio and Windows for the moment;
Extension methods are declared with an Extension attribute in VB.NET and not with the VB.NET equivalent of the C# this, Me; - Extension methods can only be defined in Modules in VB.NET not in classes. Why?;
- I knew it but still, the assignment operator in VB.NET does not return a result. This requires an ugly extra function which is not required in C#.
Option Strict On
Option Explicit On
Imports System
Imports System.Collections.Generic
Imports System.Runtime.CompilerServices
Namespace EUNemopolis
' Yuck Extension methods are only valid in Modules in VB.NET
Module Program
<Extension()> _
Public Function Memoize(Of T, R)(ByVal f As Func(Of T, R)) _
As Func(Of T, R)
Dim Cache As New Dictionary(Of T, R)
Return Function(i) _
(If( _
Cache.ContainsKey(i), _
Cache(i), _
CacheItAndReturn(Cache, i, f(i)) _
) _
)
End Function
' I really hate doing this in VB.NET.
' In C# Assignment operator has a result type.
' The Add method of a list returns "void"
' Sofar the only option I see is creating
' a function that adds the value to the cache
' and returns the result
Public Function CacheItAndReturn(Of T, R)( _
ByVal cache As Dictionary(Of T, R), _
ByVal i As T, _
ByVal fresult As R) _
As R
cache(i) = fresult
Return fresult
End Function
Public Sub Main()
System.Console.WriteLine("Hello World")
Dim Fib As Func(Of Int32, Int32) = Nothing
Fib = Function(n) (If(n < 2, n, Fib(n - 1) + Fib(n - 2)))
Fib = Fib.Memoize()
Dim i As Integer
For i = 0 To 45
System.Console.WriteLine(String.Format("{0:d},{1:d}", i, Fib(i)))
Next
System.Console.WriteLine("Done")
System.Console.ReadLine()
End Sub
End Module
End Namespace
First I define the Memoize function. It is pretty close to the C# version. I use the VB.NET 2008 Ternary If() operator. This does short-circuit evaluation, which the old IIF() function does not. In the false clause I unfortunately need to call the extra function mentioned before. If anyone knows a better solution in VB.NET for this please let me know. After that I define the Fib function in the Main method. I do this again using the ternary If() operator. As promised it is really close to the mathematical definition. Finally I call the Memoize extension method. And yes Memoize is really measurable.
Even after having implemented the VB.NET version and reading Bart de Smet’s explanation I did not understand why this should work. After reading it three times I understood. Maybe this helps if you are as puzzled as I was:
- The Memoize function declares and initialises a dictionary;
- The Memoize function returns a function object that refers to that dictionary;
- Since there is a reference to the dictionary in the function object the dictionary will not be garbage collected after the call to Memoize returns;
- Every call to a Memoize object will use the same dictionary instance.