4

I was thinking about this for quite some time. Is function memoization really only for primitives?

I currently have this piece of code:

Public Shared Function Mize(Of TArg1 As Structure, TResult)(ByVal input_f As System.Func(Of TArg1, TResult)) As System.Func(Of TArg1, TResult)
    Dim map = New System.Collections.Generic.Dictionary(Of TArg1, TResult)
    Return Function(arg1 As TArg1)
               If map.ContainsKey(arg1) Then Return map.Item(arg1)
               Dim result = input_f(arg1)
               map.Add(arg1, result)
               Return result
           End Function
End Function

And I'm wondering should i upgrade TArg1 such that it could accept any arbitrary class?

Pacerier
  • 4,973
  • 7
  • 39
  • 58

4 Answers4

11

Is function memoization really only for primitives?

Nope. Who told you that?

I'm wondering should i upgrade TArg1 such that it could accept any arbitrary class?

Absolutely, yes. There's no reason whatsoever that your higher-order method needs to be restricted to functions that take value types, so long as the value you use as the argument is not going to be mutated such that it becomes lost in a hash table. You're not supposed to put objects in a hash table and then mutate them.

I use your technique all the time. Usually something like this in C#:

static Func<A, R> Memoize(this Func<A, R> f)
{
    var dict = new Dictionary<A, R>();
    return (A arg)=>
    {
        R result;
        if (!dict.TryGetValue(arg, out result))
        {
             result = f(arg);
             dict.Add(arg, result);
        }
        return result;
    };
}

And now you can say:

Func<int, int> fib = null;
fib = x=> x < 2 ? 1 : fib(x-1) + fib(x-2);
fib = fib.Memoize();

And hey presto, you've got a memoized implementation of fib.

Now here's a challenge: do the same for functions of two arguments.

Eric Lippert
  • 45,799
  • 22
  • 87
  • 126
  • heys thanks for the help. btw could you help me with my other question that is related to this question? http://stackoverflow.com/questions/6056060/i-need-a-way-to-modify-this-code-so-that-i-will-not-violate-dry – Pacerier May 19 '11 at 08:52
  • also is there any specific reason why you are using TryGetValue instead of ContainsKey in your example? (just curious) – Pacerier May 19 '11 at 08:52
  • @Pacerier: If you use ContainsKey then you do the lookup twice; once to see if the key is there, and then once again to fetch the value. TryGetValue does only one lookup. – Eric Lippert May 19 '11 at 13:54
  • cool i didn't know that – Pacerier May 19 '11 at 15:19
2

Your question is a bit vague, but my answer is: no.

Memoization is just a technique for invisible/encapsulated caching in function scope, and you can make it as complex as you like. Any object that, in whatever particular language/environment you're using, can be used as a key for the cache, and any object can be stored as a cached value for avoiding expensive re-computations.

I don't recognize the language in your example, but in for example Java, any object can be a key in a map/hashtable, so it's not limited to primitive types.

Rein Henrichs
  • 13,112
  • 42
  • 66
Magnus Wolffelt
  • 2,373
  • 2
  • 20
  • 23
  • Well, not in "function scope", certainly? Then the memoization would have no effect since it would fall out of scope every time the function is called... – Rein Henrichs May 18 '11 at 16:11
  • No well that's true - I was having a JavaScript implementation in mind where functions are objects that can have members, which can function as the memoization cache for the function. – Magnus Wolffelt May 18 '11 at 16:34
  • Sure, but then that's "object scope", and using object scope (for example, instance variables) is a common memoization strategy for OO languages, like `@foo ||= calculate_foo_expensively` in Ruby. :) – Rein Henrichs May 18 '11 at 16:54
  • Actually, I think you misinterpret.. I mean that in for example JavaScript, memoization need not pollute object scope, because the memoization results (or "cache") can be stored in a member of the function object, rather than the object the function belongs to. – Magnus Wolffelt Dec 05 '11 at 13:06
1

Memoization is a general optimization technique used to avoid repeated calculation of results for previously-processed inputs. It can certainly be used on any data type, not just for primitives. HTTP cacheing, for instance, can be seen as a form of (higher level) memoization.

I don't fully understand your question, but it seems as if you're trying to provide a general-purpose memoization function, "Mize"? That's not really how memoization is used. It's used on a case-by-case basis. Or is that some sort of example?

Rein Henrichs
  • 13,112
  • 42
  • 66
1

For memoization to be effective you really need your function to pure, that is the result only depends on its arguments and it causes no side effects. Provided your arguments have value object semantics (in .net this means making them immutable and overriding gethashcode and equality operators) then it's no problem to use them as keys for your lookaside cache.

It looks like you're trying to create some sort of generic memoization utility function - you might want to use aspect orientated programming to do this instead (e.g. using something like PostSharp, which already has a memoisation aspect you can use).

FinnNk
  • 5,799
  • 3
  • 28
  • 32