fn_memo/
lib.rs

1//! A library for creating the memoization of a function
2//! that uses cache to improve the performance.
3//!
4//! You can create the memoization with `unsync::memoize` function.
5//! It uses a `HashMap` for caching.
6//!
7//! ```
8//! use fn_memo::{FnMemo, unsync, recur_fn::direct};
9//!
10//! let mul_2 = unsync::memoize(direct(|n| {
11//!     println!("Evaluating {}", n);
12//!     n * 2
13//! }));
14//!
15//! assert_eq!(0, mul_2.call(0)); // Output "Evaluating 0."
16//! assert_eq!(4, mul_2.call(2)); // Output "Evaluating 2."
17//! assert_eq!(10, mul_2.call(5)); // Output "Evaluating 5."
18//! assert_eq!(4, mul_2.call(2)); // No output. The result is cached.
19//! mul_2.clear_cache();
20//! assert_eq!(4, mul_2.call(2)); // Output "Evaluating 2."
21//! ```
22//!
23//! The `memoize` function takes a `RecurFn` argument,
24//! which allows you to memoize a recursive function and the result of
25//! each recursion will be cached. See
26//! [the API reference of `recur-fn`](https://docs.rs/recur-fn/)
27//! for details.
28//!
29//! ```
30//! use fn_memo::{FnMemo, unsync, recur_fn::recur_fn};
31//!
32//! let fib = unsync::memoize(recur_fn(|fib, n: usize| {
33//!     println!("Evaluating {}", n);
34//!     if n <= 1 {
35//!         n
36//!     } else {
37//!         fib(n - 1) + fib(n - 2)
38//!     }
39//! }));
40//!
41//! assert_eq!(55, fib.call(10));
42//! assert_eq!(5, fib.call(5));
43//! ```
44//!
45//! The code above will output the evaluation from 0 to 10.
46//! Each of them is outputed only once.
47//!
48//! For the sequence (i.e. the function that takes an `usize` argument),
49//! you can also use `unsync::memoize_seq`. It uses a `Vec` as a bucket
50//! to cache. It has a better performance and requires the memory
51//! proportional to the largest argument that have cached.
52//!
53//! You can costumize the data structure of the cache by implementing
54//! `unsync::Cache` trait and create memoization with `unsync::Memo::new` method.
55//!
56//! The APIs under `unsync` namespace are for single-thread.
57//! The result of `unsync::memoize` does not `Sync` even the cached function does.
58//!
59//! ```compile_fail
60//! use std::{sync::Arc, thread};
61//! use fn_memo::{FnMemo, unsync, recur_fn::direct};
62//!
63//! let f = Arc::new(unsync::memoize(direct(|n: i32| n)));
64//! thread::spawn(move || { f }); // Compile Error
65//! ```
66//!
67//! The synchronized memoization APIs are under `sync` namespace.
68//!
69//! ```
70//! use fn_memo::{FnMemo, sync::chashmap, recur_fn::direct};
71//! use std::thread;
72//! use std::sync::Arc;
73//!
74//! let mul_2 = Arc::new(chashmap::memoize(direct(|n| {
75//!     println!("Evaluating {}", n);
76//!     n * 2
77//! })));
78//!
79//! let mut threads = Vec::new();
80//! for _ in 0..4 {
81//!     threads.push(thread::spawn({
82//!         let mul_2 = Arc::clone(&mul_2);
83//!         move || {
84//!             for n in 0..10 {
85//!                 assert_eq!(n*2, mul_2.call(n));
86//!             }
87//!         }
88//!     }));
89//! }
90//! for thread in threads {
91//!     thread.join().unwrap();
92//! }
93//! ```
94//!
95//! The code above will output the evaluation from 0 to 9.
96//! Each of them is outputed only once.
97#[cfg(feature = "sync")]
98pub mod sync;
99pub mod unsync;
100
101pub use recur_fn;
102
103/// The memoized function.
104pub trait FnMemo<Arg, Output> {
105    /// Calls the function. If the result of `arg` is already cached,
106    /// it will return the cached result, otherwise, it calculates the result
107    /// and adds it to the cache.
108    fn call(&self, arg: Arg) -> Output;
109    /// Clears the cache.
110    fn clear_cache(&self);
111}
fn_memo/lib.rs

fn_memo/
lib.rs
