Function std.functional.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.
Prototypes
Task.ReturnType!fun memoize(alias fun)( ParameterTypeTuple!fun args ); Task. ReturnType!fun memoize(alias fun, uint maxSize)( ParameterTypeTuple!fun args );
Example
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);
}
Technically the memoized function should be pure because memoizememoizenot
enforce that because sometimes it
is useful to memoize an impure function, too.
Example
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)
{
return n < 2 ? 1 : memoize!fib(n - 2) + memoize!fib(n - 1);
}
assert(fib(10) == 89);
Example
To improve the speed of the factorial function,
ulong fact(ulong n)
{
return n < 2 ? 1 : n * memoize!fact(n - 1);
}
assert(fact(10) == 3628800);
Example
This memoizes all values of fact up to the largest argument. To only cache the final
result, move memoize
ulong factImpl(ulong n)
{
return n < 2 ? 1 : n * factImpl(n - 1);
}
alias fact = memoize!factImpl;
assert(fact(10) == 3628800);
Example
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);