在递归Fibonacci实现中,不能将不可变借用的HashMap缓存借用为可变

Question

我想实现Fibonacci系列以及缓存已经计算的结果.我不确定这种方法在Rust中是否可行,但它是我提出的最好的方法.这是代码:

use std::collections::HashMap;

pub fn fib_hash(n: u32) -> u64 {
    let mut map: HashMap<u32, u64> = HashMap::new();

    // This is the engine which recurses saving each value in the map
    fn f(map: &HashMap<u32, u64>, n: u32) -> u64 {
        let c = match map.get(&n) {
            Some(&number) => number,
            _ => 0,
        };
        if c != 0 {
            return c;
        }
        let m = match n {
            1 if n < 1 => 0,
            1...2 => 1,
            _ => f(&map, n - 1) + f(&map, n - 2),
        };
        map.insert(n, m);
        m
    }
    f(&map, n)
}

我们的想法是拥有一个HashMap可以重复使用的"全局" .但是,我猜这不可能,因为我们最终会为地图提供多个可变借款人.这是我得到的错误

error[E0596]: cannot borrow immutable borrowed content `*map` as mutable
  --> src/lib.rs:20:9
   |
7  |     fn f(map: &HashMap<u32, u64>, n: u32) -> u64 {
   |               ------------------ use `&mut HashMap<u32, u64>` here to make mutable
...
20 |         map.insert(n, m);
   |         ^^^ cannot borrow as mutable

我可以在Rust中使用这种方法吗？什么是这个问题的最佳解决方案？

Answer 1

您将map参数声明为fas &HashMap<u32, u64>,这是一个不可变引用,只允许您调用get和其他不修改的函数HashMap.使用&mut HashMap<u32, u64>的类型map需要一个参考,让突变.这也要求您使用&mut map而不是注释呼叫站点&map.

就个人而言,我会使用一种不同的方法来使用所有权转移而不是引用.但每个人都有自己的风格.

pub fn fib_hash(n: u32) -> u64 {
    // This is the engine which recurses saving each value in the map
    fn f(map: HashMap<u32, u64>, n: u32) -> (HashMap<u32, u64>, u64) {
        if let Some(&number) = map.get(&n) {
            return (map, number);
        }
        let (map, a) = f(map, n - 1);
        let (mut map, b) = f(map, n - 2);
        let res = a + b;
        map.insert(n, res);
        (map, res)
    }
    let mut map = HashMap::new();
    map.insert(0, 0);
    map.insert(1, 1);
    map.insert(2, 1);
    f(map, n).1
}

操场