fn_cache crate

此 crate 实现了一种简单的方式来缓存函数的值。如果您有一个运行缓慢的函数，这可以用来显著提高后续运行的效率。这对于递归函数的记忆化也非常有用，可以防止在多次调用中重复计算相同的函数。

特别值得注意的是，这种缓存没有进行克隆或复制，允许函数返回大型对象，而缓存只返回它们的引用而不是复制它们。

允许的函数

此 crate 尽可能地保持对接受的函数的灵活性。以下所有类型都应该被允许

• fn 类型。
• Fn 类型，没有引用。
• Fn + 'static 类型，只接受静态引用。
• Fn + 'a 类型，接受生命周期为 'a 的引用。

出于明显的原因，FnMut 和 FnOnce 不被允许，因为函数需要可重跑且纯净。

示例

缓存可以处理递归函数，并提供一个使用非递归函数定义的快捷方式。每个缓存都有一个 recursive 函数来创建一个能够进行递归的缓存，但要求函数接受缓存作为第一个参数。每个 new 函数都接受一个不需要缓存的函数。

非递归

以下是一个计算时间较长的函数的示例。您不必每次都运行计算，只需计算一次并记住值。结果存储在用于随机访问的 HashCache 中。

use fn_cache::{FnCache, HashCache};
use std::{thread, time};

let sleep_time = time::Duration::from_secs(3);

let mut cache = HashCache::new(|&x| {
    thread::sleep(sleep_time);
    x
});

let start = time::Instant::now();
assert_eq!(cache.get(100), &100);
assert_eq!(cache.get(100), &100);

// time elapsed is only slightly longer than the sleep time
// far less than twice.
assert!(time::Instant::now() - start < sleep_time.mul_f32(1.1));

递归

以下示例展示了使用记忆化（缓存）的斐波那契数列递归实现，如果没有记忆化（缓存），则其复杂度为 O(2ⁿ)。使用记忆化后，其复杂度变为 O(n)，并且可以轻松计算。

use fn_cache::{FnCache, HashCache};

let mut cache = HashCache::<u8,u128>::recursive(|cache, x|
    match x {
        0 => 0,
        1 => 1,
        _ => *cache.get(x - 1) + *cache.get(x - 2),
    }
);

assert_eq!(
    *cache.get(186),
    332_825_110_087_067_562_321_196_029_789_634_457_848
);

对于更大的结果，可以使用 num 包。为了避免在访问缓存两次时复制 BigUint，可以使用 FnCacheMany::get_many 来一次性获取多个值，以避免尝试获取引用然后再进行修改。另外，由于输入从 0 开始，并且每个值必须在计算下一个值之前填充，因此您可以使用 VecCache 进行优化。

use fn_cache::{FnCache, FnCacheMany, VecCache};
use num_bigint::BigUint;

let mut cache = VecCache::recursive(|cache, x|
    match x {
        0 => BigUint::new(vec![0]),
        1 => BigUint::new(vec![1]),
        _ => cache.get_many([x - 1, x - 2]).into_iter().sum(),
    }
);

assert_eq!(
    cache.get(999),
    &BigUint::parse_bytes(b"26863810024485359386146727202142923967616609318986952340123175997617981700247881689338369654483356564191827856161443356312976673642210350324634850410377680367334151172899169723197082763985615764450078474174626", 10).unwrap()
);