the call-able to memozie
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.
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);
* 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.