The OpenD Programming Language

memoize

* Memoizes a function so as * to avoid repeated computation. The memoization structure is a hash table keyed by a * tuple of the function's arguments. There is a speed gain if the * function is repeatedly called with the same arguments and is more * expensive than a hash table lookup. For more information on memoization, refer to this book chapter.

template memoize(alias fun)
memoize

Parameters

fun

the call-able to memozie

Return Value

A new function which calls fun and caches its return values.

Note: Technically the memoized function should be pure because memoize assumes it will always return the same result for a given tuple of arguments. However, memoize does not enforce that because sometimes it is useful to memoize an impure function, too.

Examples

double transmogrify(int a, string b)
{
   ... expensive computation ...
}
alias fastTransmogrify = memoize!transmogrify;
unittest
{
    auto slow = transmogrify(2, "hello");
    auto fast = fastTransmogrify(2, "hello");
    assert(slow == fast);
}

To memoize a recursive function, simply insert the memoized call in lieu of the plain recursive call. For example, to transform the exponential-time Fibonacci implementation into a linear-time computation:

ulong fib(ulong n) @safe nothrow
{
    return n < 2 ? n : memoize!fib(n - 2) + memoize!fib(n - 1);
}
assert(fib(10) == 55);

To improve the speed of the factorial function,

ulong fact(ulong n) @safe
{
    return n < 2 ? 1 : n * memoize!fact(n - 1);
}
assert(fact(10) == 3628800);

This memoizes all values of fact up to the largest argument. To only cache the final result, move memoize outside the function as shown below.

ulong factImpl(ulong n) @safe
{
    return n < 2 ? 1 : n * factImpl(n - 1);
}
alias fact = memoize!factImpl;
assert(fact(10) == 3628800);

When the maxSize parameter is specified, memoize will used a fixed size hash table to limit the number of cached entries.

ulong fact(ulong n)
{
    // Memoize no more than 8 values
    return n < 2 ? 1 : n * memoize!(fact, 8)(n - 1);
}
assert(fact(8) == 40320);
// using more entries than maxSize will overwrite existing entries
assert(fact(10) == 3628800);

Meta