我想实现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
。但是,我猜这不可能,因为我们最终会为地图提供多个可变借款人。这是我得到的错误
锈2015年
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 2018
error[E0596]: cannot borrow `*map` as mutable, as it is behind a `&` reference
--> src/lib.rs:20:9
|
7 | fn f(map: &HashMap<u32, u64>, n: u32) -> u64 {
| ------------------ help: consider changing this to be a mutable reference: `&mut std::collections::HashMap<u32, u64>`
...
20 | map.insert(n, m);
| ^^^ `map` is a `&` reference, so the data it refers to cannot be borrowed as mutable
我可以在Rust中使用这种方法吗?什么是这个问题的最佳解决方案?
你将map
的f
参数声明为&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
}
诀窍是使map
成为参数列表中的可变引用(并明确使用生命周期):
use std::collections::HashMap;
fn fib<'a>(n: u32, memo: &'a mut HashMap<u32, u32>) -> u32 {
if n <= 2 {
return 1;
}
return match memo.get(&n) {
Some(&sum) => sum,
None => {
let new_fib_sum = fib(n - 1, memo) + fib(n - 2, memo);
memo.insert(n, new_fib_sum);
new_fib_sum
}
};
}
fn main() {
let mut memo: HashMap<u32, u32> = HashMap::new();
let n = 10; //or user input...or whatever
print!("{}", fib(n, &mut memo));
}