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.
ReturnType!fun memoize(alias fun)
(
Parameters!fun args
);
ReturnType!fun memoize(alias fun, uint maxSize)
(
Parameters!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);
}Parameters
| Name | Description |
|---|---|
| fun | the call-able to memozie |
| maxSize | The maximum size of the GC buffer to hold the return values |
Returns
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.
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) @safe nothrow
{
return n < 2 ? n : memoize!fib(n - 2) + memoize!fib(n - 1);
}
writeln(fib(10)); // 55
Example
To improve the speed of the factorial function,
ulong fact(ulong n) @safe
{
return n < 2 ? 1 : n * memoize!fact(n - 1);
}
writeln(fact(10)); // 3628800
Example
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;
writeln(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);
}
writeln(fact(8)); // 40320
// using more entries than maxSize will overwrite existing entries
writeln(fact(10)); // 3628800