Обновление изменяемого HashMap в цикле while

Question

Я пытаюсь реализовать алгоритм Каргера в Rust, и у меня возникла проблема при попытке обновить изменяемую хэш-карту в цикле 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;
    }
}

Когда я пытаюсь получить доступ к карте, я получаю сообщение об ошибке элемент не найден, но удаленные ключи не должны существовать в векторных значениях в этой точке.

Я убежден, что это то, чего я не понимаю в (Im) изменчивости в Rust.

Answer 1

Я не совсем уверен, чего вы пытаетесь достичь здесь, но исходя из того, что я вижу выше, то есть вы хотите изменить свое оригинальное graph (потому что вы передаете это как изменчивое заимствование к вашей функции) и что у вас нет возвращаемого значения, и что ваш вопрос касается изменения хэш-карты - я предполагаю, что вы хотели бы, чтобы изменения были отражены в вашем исходном 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]}