在 while 循环中更新可变 HashMap

Question

我正在尝试在 Rust 中实现 Karger 算法，但在尝试在 while 循环中更新可变哈希映射时遇到了运行问题。

地图更新成功，但在下一次克隆时，更新的值似乎没有改变。但是，从地图中删除元素会反映在以后的迭代中。

我已经尝试调试和打印地图的值，但事件的顺序对我来说没有意义。

use itertools::Itertools;  // 0.8.0
use rand::seq::{IteratorRandom, SliceRandom}; // 0.6.5
use std::collections::HashMap;

fn contract_edge(graph: &mut HashMap<i32, Vec<i32>>, num_trials: i32) {
    let mut count = 0;

    while graph.len() > 2 && count < num_trials {
        // clone graph so I can mutate graph later
        let imut_graph = graph.clone();

        // choose random node
        let from_value = imut_graph
            .keys()
            .choose(&mut rand::thread_rng())
            .unwrap()
            .clone();
        let values = imut_graph.get(&from_value);
        let to_value = values
            .unwrap()
            .choose(&mut rand::thread_rng())
            .unwrap()
            .clone();

        let from_edges = imut_graph[&from_value].iter().clone();

        // accessing to_value in imut_graph gives error here later
        let to_edges = imut_graph[&to_value]
            .iter()
            .clone()
            .filter(|&x| *x != from_value && *x != to_value);

        let new_edges = from_edges.chain(to_edges);

        // since I am mutating the graph I thought the next time is is clone it would be updated?
        graph.insert(from_value, new_edges.map(|v| v.clone()).collect());
        graph.remove(&to_value);
        for (_key, val) in graph.iter_mut() {
            *val = val
                .iter()
                .map(|v| if v == &to_value { &from_value } else { v })
                .unique()
                .cloned()
                .collect();
        }
        count += 1;
    }
}

当我尝试访问地图时，出现找不到元素的错误，但此时矢量值中不应存在已删除的键。

我确信这是我对 Rust 中的（Im）可变性不了解的地方。

Answer 1

我不太确定你想在这里实现什么，但根据我在上面看到的，也就是说，你想改变你原来的 graph （因为你正在传递那个作为对您的函数的可变借用）并且您没有 return 值，并且您的问题是关于改变哈希图 - 我假设您希望更改反映在您的原始 HashMap。那你为什么要首先克隆它呢？

另一方面，如果您不想改变原始对象，则不要将其作为可变借用传入，而是作为不可变借用传入。然后在开始循环之前创建它的克隆，并在整个算法中使用该克隆版本。

您遇到的问题正在发生，因为在每次迭代中您都克隆原始 graph 而不是克隆的 imut_graph，即在每次迭代中您创建一个新的 HashMap ，然后你正在变异，然后你开始一个新的循环，你仍然在检查原来的长度，然后你再次克隆原来的。

所以你有两个选择：

use std::collections::HashMap;

fn mutated(map: &mut HashMap<i32, Vec<i32>>) {
    map.insert(1, vec![4, 5, 6]);
}

fn cloned(map: &HashMap<i32, Vec<i32>>) -> HashMap<i32, Vec<i32>> {
    let mut map = map.clone();
    map.insert(2, vec![7, 8, 9]);
    map
}

fn main() {
    let mut map = HashMap::new();
    map.insert(0, vec![1, 2, 3]);

    println!("{:?}", cloned(&map));

    mutated(&mut map);
    println!("{:?}", map);
}

哪个会给你：

{0: [1, 2, 3], 2: [7, 8, 9]}
{0: [1, 2, 3], 1: [4, 5, 6]}

在 while 循环中更新可变 HashMap

Updating mutable HashMap in a while loop

immutability

rust

borrow-checker