Mise en cache des résultats de fonctions autoréférentielles en Rust

Question

J'essaie de m'initier à la rouille avec les problèmes du projet Euler, en particulier https://projecteuler.net/problem=76 .

J'ai trouvé une solution à ce problème :

fn main() {
    println!("{}", solution(100, 99));
}

fn solution(sum_to: i32, max_size: i32) -> i32 {
    if sum_to == 0 || max_size == 1 {
        1
    } else if sum_to < 0 {
        0
    } else {
        (1..=max_size)
            .map(|i| solution(sum_to - i, min(i, sum_to - i)))
            .sum()
    }
}

Je sais que cela fonctionne, mais il faut une éternité pour l'exécuter parce qu'il finit par calculer le résultat pour la même entrée plusieurs fois.

J'ai essayé de mettre en place une solution de mise en cache, mais je rencontre des problèmes avec le vérificateur d'emprunts.

Code :

use std::cmp::min;
use std::collections::HashMap;

fn main() {
    println!("{}", solution_head(100))
}

fn solution_head(sum_to: i32) -> i32 {
    let mut cache = HashMap::new();
    (1..sum_to)
        .map(|i| solution(&mut cache, sum_to - i, min(i, sum_to - i)))
        .sum()
}

fn solution(
    cache: &mut HashMap<i32, HashMap<i32, i32>>,
    sum_to: i32,
    max_size: i32,
) -> i32 {
    if sum_to == 0 {
        1
    } else if sum_to < 0 {
        0
    } else {
        let cache_entry = cache.entry(sum_to);
        let map = cache_entry.or_insert(HashMap::new());
        let map_entry = map.entry(max_size);
        *map_entry.or_insert_with(|| {
            (1..=max_size)
                .map(|i| solution(cache, sum_to - i, min(i, sum_to - i)))
                .sum()
        })
    }
}

Erreur :

error[E0500]: closure requires unique access to `*cache` but it is already borrowed
  --> src/bin/problem_76.rs:27:35
   |
24 |         let cache_entry = cache.entry(sum_to);
   |                           ------------------- borrow occurs here
...
27 |         *map_entry.or_insert_with(|| {
   |                    -------------- ^^ closure construction occurs here
   |                    |
   |                    first borrow later used by call
28 |             (1..=max_size)
29 |                 .map(|i| solution(cache, sum_to - i, min(i, sum_to - i)))
   |                                   ----- second borrow occurs due to use of `*cache` in closure

Je ne suis pas du tout certain de la manière d'y parvenir, car le problème ultime que le vérificateur d'emprunts rencontre avec ce code est que je suis les deux :

• en utilisant une référence au cache dans la fonction pour vérifier si j'ai déjà calculé le résultat
• envoyer une référence au cache à l'appel récursif de la fonction afin de pouvoir vérifier si j'ai déjà calculé le résultat en aval.

Quelle est la manière idiomatique d'accomplir cela en Rust ?

Answer 1

Le problème est que cache_entry pointe vers une valeur à l'intérieur de cache ce qui signifie que vous ne pouvez pas modifier cache alors que l'entrée est dans le champ d'application. Je restructurerais le code pour utiliser .get() y .insert() . Je simplifierais également cache ser HashMap<(i32, i32), i32> .

Le code suivant fonctionne rapidement pour moi :

use std::collections::HashMap;

fn main() {
    let mut cache = HashMap::new();
    println!("{}", solution(&mut cache, 100, 99));
}

fn solution(cache: &mut HashMap<(i32, i32), i32>, sum_to: i32, max_size: i32) -> i32 {
    if sum_to == 0 || max_size == 1 {
        1
    } else if sum_to < 0 {
        0
    } else if let Some(x) = cache.get(&(sum_to, max_size)) {
        *x
    } else {
        let x = (1..=max_size)
            .map(|i| solution(cache, sum_to - i, std::cmp::min(i, sum_to - i)))
            .sum();
        cache.insert((sum_to, max_size), x);
        x
    }
}

Terrain de jeux