5

我正在尝试在 rust 中记忆递归 collat​​z 序列函数，但是我需要记忆值的哈希图来保持其内容跨单独的函数调用。是否有一种优雅的方式可以在 rust 中执行此操作，或者我是否必须在 main 中声明 hashmap 并每次将其传递给函数？我相信每次调用该函数时，hashmap 都会被重新声明为空映射。这是我的代码：

fn collatz(n: int) -> int {
    let mut map = HashMap::<int, int>::new();
    if map.contains_key(&n) {return *map.get(&n);}
    if n == 1 { return 0; }
    map.insert(n, 
        match n % 2 {
            0 => { 1 + collatz(n/2) }
            _ => { 1 + collatz(n*3+1) }
        }
    );
    return *map.get(&n);
}

附带说明一下，当我从 HashMap 中插入和拉出项目时，为什么需要添加所有的 & 和 *？我只是这样做是因为编译器抱怨并添加它们修复了它，但我不知道为什么。我不能只传递价值吗？谢谢。

4

3 回答 3

4

您可以将thread_local用于线程局部静态。

thread_local! (static COLLATZ_MEM: HashMap<i32, i32> = HashMap::new());
fn collatz(n: i32) -> i32 {
    COLLATZ_MEM.with (|collatz_mem| {
        0  // Your code here.
    })
}

PS 还有一个出色的惰性静态宏，可用于真正的全局静态缓存。这是一个例子。

于 2014-08-14T17:46:26.443 回答
3

Rust 中没有 C 中的“静态”局部变量，没有。也许制作一个对象，将哈希放入其中，然后制作collatz一个方法。

您不能按值传递，因为这会进行复制（这对于复杂的键可能很昂贵）或移动（这将使您无法再次使用该键）。在这种情况下，您的密钥只是整数，但 API 旨在适用于任意类型。

于 2014-03-31T02:39:53.523 回答
0

使用thread-local!（如另一个答案中所建议的）来解决这个问题并不是那么简单，所以我在这里提供了一个完整的解决方案：

use std::cell::RefCell;
use std::collections::HashMap;

fn main() {
    println!("thread-local demo for Collatz:");
    (2..20).for_each(|n| println!("{n}: {c}", n = n, c = collatz(n)));
}

thread_local! (static COLLATZ_CACHE: RefCell<HashMap<usize, usize>> = {
    let mut cache = HashMap::new();
    cache.insert(1, 0);
    RefCell::new(cache)
});

fn collatz(n: usize) -> usize {
    COLLATZ_CACHE.with(|cache| {
        let entry = cache.borrow().get(&n).copied();
        if let Some(v) = entry { v } else {
            let v = match n % 2 {
                0 => 1 + collatz(n / 2),
                1 => 1 + collatz(n * 3 + 1),
                _ => unreachable!(),
            };
            cache.borrow_mut().insert(n, v);
            *cache.borrow().get(&n).unwrap()
        }
    })
}

如果线程本地存储不够全局，那么您可以使用once_cell crate的功能——它也在进入 std（已经在 nightly 中）——初始化一个静态变量：

#![feature(once_cell)]
use std::collections::HashMap;
use std::lazy::SyncLazy;
use std::sync::Mutex;

fn main() {
    println!("once_cell demo for Collatz:");
    (2..20).for_each(|n| println!("{n}: {c}", n = n, c = collatz(n)));
}

static COLLATZ_CACHE: SyncLazy<Mutex<HashMap<usize, usize>>> = SyncLazy::new(|| {
    let mut cache = HashMap::new();
    cache.insert(1, 0);
    Mutex::new(cache)
});

fn collatz(n: usize) -> usize {
    let cache = &COLLATZ_CACHE;
    let entry = cache.lock().unwrap().get(&n).copied();
    if let Some(v) = entry {
        v
    } else {
        let v = match n % 2 {
            0 => 1 + collatz(n / 2),
            1 => 1 + collatz(n * 3 + 1),
            _ => unreachable!(),
        };
        cache.lock().unwrap().insert(n, v);
        *cache.lock().unwrap().get(&n).unwrap()
    }
}

操场

于 2021-12-09T13:46:47.990 回答