6 releases
0.3.2 | Mar 8, 2020 |
---|---|
0.3.1 | Mar 8, 2020 |
0.2.0 | Feb 9, 2020 |
0.1.1 | Feb 1, 2020 |
#17 in #i64
341 downloads per month
Used in competitive-hpp
22KB
469 lines
memoise
Simple memoization library for rust
Documentation
Find it on docs.rs.
Usage
Add this to your Cargo.toml
:
[dependencies]
memoise = "0.3"
And then, just add memoise
attribute to functions you want to memoise:
use memoise::memoise;
#[memoise(n <= 100)]
fn fib(n: i64) -> i64 {
if n == 0 || n == 1 {
return n;
}
fib(n - 1) + fib(n - 2)
}
And you can call it normally:
fn main() {
println!("{}", fib(45));
}
And run it:
$ cargo build --release
$ time cargo run --release -q
1134903170
real 0m0.039s
user 0m0.000s
sys 0m0.016s
If comment out memoise
attribute, it will not be memoised.
// #[memoise(n <= 100)]
fn fib(n: i64) -> i64 {
if n == 0 || n == 1 {
return n;
}
fib(n - 1) + fib(n - 2)
}
$ cargo build --release
$ time cargo run --release -q
1134903170
real 0m5.019s
user 0m4.984s
sys 0m0.016s
When no bounds for keys given, the cache table Vec
will be allocated dynamically.
use memoise::memoise;
// the cache table for `n` is dynamically allocated
#[memoise(n)]
fn fib(n: i64) -> i64 {
if n == 0 || n == 1 {
return n;
}
fib(n - 1) + fib(n - 2)
}
_reset
function frees allocated Vec
.
fib(42); // This allocates cache table for `0..n+1`
fib_reset();
memoise_map
memoises a function by using BTreeMap
.
It is suitable for keys are sparse.
#[memoise_map(n)]
fn fib(n: i64) -> i64 {
if n == 0 || n == 1 {
return n;
}
fib(n - 1) + fib(n - 2)
}
_reset
function also releases all allocated memory.
For more information, you can find a document on docs.rs.
Dependencies
~1.5MB
~34K SLoC