View source code
Display the source code in std/functional.d from which this page was generated on github.
Report a bug
If you spot a problem with this page, click here to create a Bugzilla issue.
Improve this page
Quickly fork, edit online, and submit a pull request for this page. Requires a signed-in GitHub account. This works well for small changes. If you'd like to make larger changes you may want to consider using local clone.

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

NameDescription
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

Authors

Andrei Alexandrescu

License

Boost License 1.0.