fn_cache crate
This crate implements an easy way to cache values for a function. If you have a slow running function, this can be used to speed up successive runs dramatically. It is also quite useful for memoization of recursive functions, to prevent calculating the same function twice in different calls.
Of particular note, this caching is done without cloning or copying, allowing functions to return large objects, while the cache only returns a reference to them instead of copying them.
Allowed functions
This crate attempts to remain fairly flexible with the functions it accepts. All of the following should be allowed:
- fn types.
- Fn types that have no references.
- Fn + 'static types that take only static references.
- Fn + 'a types that take references of lifetime 'a.
For obvious reasons, FnMut and FnOnce are not allowed, as functions need to be rerunnable and pure.
Examples
The following example shows a recursive fibonacci implementation, which would be O(2ⁿ) without memoization (caching). With memoization, it becomes O(n), and can easily be calculated.
use HashCache;
let mut cache = new;
assert_eq!;
For even bigger results, the num crate might be employed.
In order to avoid copying the BigUint
s while accessing the
cache twice, you can to change the result to be stored in an
Rc.
use Rc;
use HashCache;
use BigUint;
let mut cache = new;
assert_eq!;