如何更改要遍历的结构？ [英] How do I mutate a structure I am looping over?
问题描述
此问题是由此CodinGame难题提出的。
我正在使用Dijkstra的方法实现基本的寻路算法。它使用边界 HashMap和完成 HashMap来保存与寻路相关的节点信息。在一个特定的循环中，我在边界中找到价值最高的节点，删除该节点，然后将该节点添加到完成 ，并在 boundary 中添加/更新节点的邻居信息。
I am implementing a basic pathfinding algorithm using Dijkstra's method. It uses a boundary HashMap and a finished HashMap to hold pathfinding-related node info. In a particular loop, I find the highest-valued node in boundary, remove the node, add the node to finished, and add/update the node's neighbors' info in boundary.
尝试变异边界在循环时使Rust的借阅检查器变得不容易，但是循环的逻辑对我来说似乎是合理的。如何重写它，以便编译器共享我的信心？ （或者解决我所缺少的错误，如果是问题所在的话。）
Attempting to mutate boundary while looping over it is making Rust's borrow checker queasy, but the logic of the loop seems sound to me. How do I rewrite it so that the compiler shares my confidence? (Or fix the errors I'm missing, if that's the issue.)
use std::io;
use std::collections::{HashSet, HashMap};
use std::cmp::Ordering;
use std::cell::RefCell;
struct NodeInfo {
nbrs: HashSet<i32>,
gwlinks: i32,
}
#[derive(PartialEq,PartialOrd)]
struct PFInfo {
avg: f32,
cum: i32,
dist: i32,
prev: Option<i32>,
}
impl Eq for PFInfo {}
impl Ord for PFInfo {
fn cmp(&self, other: &PFInfo) -> Ordering {
match self.partial_cmp(other) {
Some(ord) => ord,
None => Ordering::Equal
}
}
}
type Graph = HashMap<i32, RefCell<NodeInfo>>;
type PFGraph = HashMap<i32, PFInfo>;
// Find the path that passes the most gateway links per distance traveled,
// starting at a given node. This is meant to simulate the behavior of an
// "agent" which traverses the graph in the puzzle mentioned above.
fn generate_path(si: &i32, graph: &Graph) -> Vec<i32> {
let n = graph.len();
let mut boundary = PFGraph::with_capacity(n);
let mut finished = PFGraph::with_capacity(n);
boundary.insert( si.clone(),
PFInfo {
avg: 0.,
cum: graph.get(&si).unwrap().borrow().gwlinks,
dist: 0,
prev: None } );
// Keep grabbing the key corresponding the highest value until `boundary` is
// empty
while let Some( (currid, _) ) = boundary.iter().max_by_key(|x| x.1) {
// Move the node from `boundary` to `finished`
let val = boundary.remove(&currid).unwrap();
finished.insert(currid.clone(), val);
// Add or update all adjacent nodes that are not in `finished`
for nbrid in graph.get(&currid).unwrap()
.borrow()
.nbrs.iter()
.filter(|x| !finished.contains_key(x)) {
let currval = finished.get(&currid).unwrap();
let prev = Some(currid.clone());
let dist = currval.dist + 1;
let cum = currval.cum + graph.get(nbrid).unwrap().borrow().gwlinks;
let avg = cum as f32 / dist as f32;
boundary.insert(
nbrid.clone(),
PFInfo {
avg: avg,
cum: cum,
dist: dist,
prev: prev,
}
);
}
}
let mut path = Vec::new();
let mut currid = finished.iter().max_by_key(|x| x.1).unwrap().0.clone();
path.push(currid.clone());
while let Some(previd) = finished.get(&currid).unwrap().prev {
path.push(previd.clone());
currid = previd.clone();
}
path.reverse();
path
}
macro_rules! parse_input {
($x:expr, $t:ident) => ($x.trim().parse::<$t>().unwrap())
}
#[test]
fn test_generate_path() {
let mut inputs = "8 13 2
6 2
7 3
6 3
5 3
3 4
7 1
2 0
0 1
0 3
1 3
2 3
7 4
6 5
4
5".lines();
let header = inputs.next().unwrap().split_whitespace().collect::<Vec<_>>();
let n = parse_input!(header[0], i32); // the total number of nodes in the level, including the gateways
let l = parse_input!(header[1], i32); // the number of links
let e = parse_input!(header[2], i32); // the number of exit gateways
let mut graph = Graph::with_capacity(n as usize);
for node in 0..n {
graph.insert(node, RefCell::new(NodeInfo{ nbrs: HashSet::new(), gwlinks: 0 }));
}
let graph = graph;
for _ in 0..l as usize {
let link = inputs.next().unwrap();
let nodes = link.split(" ").collect::<Vec<_>>();
let n1 = parse_input!(nodes[0], i32); // N1 and N2 defines a link between these nodes
let n2 = parse_input!(nodes[1], i32);
graph.get(&n1).unwrap().borrow_mut().nbrs.insert(n2);
graph.get(&n2).unwrap().borrow_mut().nbrs.insert(n1);
}
let mut gateways = HashSet::new();
for _ in 0..e as usize {
let ei = parse_input!(inputs.next().unwrap(), i32); // the index of a gateway node
gateways.insert(ei);
}
let gateways = gateways;
for gwid in &gateways {
for gwnbr in &graph.get(gwid).unwrap().borrow().nbrs {
(&graph).get(&gwnbr).unwrap().borrow_mut().gwlinks += 1;
}
}
assert_eq!(generate_path(&0, &graph), vec![0, 3]);
}
错误：
Errors:
rustc 1.18.0 (03fc9d622 2017-06-06)
error[E0502]: cannot borrow `boundary` as mutable because it is also borrowed as immutable
--> <anon>:53:19
|
50 | while let Some( (currid, _) ) = boundary.iter().max_by_key(|x| x.1) {
| -------- immutable borrow occurs here
...
53 | let val = boundary.remove(&currid).unwrap();
| ^^^^^^^^ mutable borrow occurs here
...
76 | }
| - immutable borrow ends here
error[E0502]: cannot borrow `boundary` as mutable because it is also borrowed as immutable
--> <anon>:66:13
|
50 | while let Some( (currid, _) ) = boundary.iter().max_by_key(|x| x.1) {
| -------- immutable borrow occurs here
...
66 | boundary.insert(
| ^^^^^^^^ mutable borrow occurs here
...
76 | }
| - immutable borrow ends here
error: aborting due to 2 previous errors
推荐答案
我找到了解决这个问题的方法，并且它在某种程度上是可以推广的，这正是我所希望的。问题是，在 while 语句中创建的隐式引用一直存在循环的末尾，即使只需要在那一行上也是如此。借位从 .iter（）开始，并且一旦引用的值是<$ c，就不再需要$ c> clone d放在表达式的末尾。
I found a solution to my issue, and it's somewhat generalizable, which is what I was hoping for. The problem was that an implicit reference created in the while let statement was living to the end of the loop even though it was only needed on that one line. The borrow begins at .iter() and is no longer needed once the referenced value is cloned at the end of the expression.
while let Some( (currid, _) ) = boundary.iter().max_by_key(|x| x.1).clone() {
// ^---where borrow begins ^---where borrow could end
// Move the node from `boundary` to `finished`
let val = boundary.remove(&currid).unwrap();
finished.insert(currid.clone(), val);
...
} // <--- where borrow does end
诀窍是将 currid 的绑定移动到循环中。当在 while let 语句中借入该值时，借贷检查器显然认为借贷需要持续整个循环。相反，如果隐式借用是在常规 let 绑定中进行的，则借用检查器非常聪明，可以意识到可以在行尾安全地丢弃借用。 / p>
The trick was moving the binding of currid into the loop. When the value is borrowed in the while let statement, the borrow checker apparently thinks the borrow needs to last throughout the loop. If, instead, the implicit borrow is made in a regular let binding, the borrow checker is smart enough to realize the borrow can be safely discarded at the end of the line.
while !boundary.is_empty() {
let currid = boundary.iter().max_by_key(|x| x.1).unwrap().0.clone();
// ^---where borrow begins ^---where borrow ends
// Move the node from `boundary` to `finished`
let val = boundary.remove(&currid).unwrap();
finished.insert(currid.clone(), val);
...
}
I猜想这里的收获是，如果您需要在依赖于它的循环中对结构进行变异，则将结构的任何借用放入循环中，并使这些借用尽可能短—例如，使用克隆。
I guess the take away here is that if you need to mutate a structure in a loop that depends on it, put any borrows of the structure inside the loop and keep those borrows as short as possible – for example, by using clone.
这可能是提议的非词汇生存期。
这篇关于如何更改要遍历的结构？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
