5

私はさびで再帰的なコラッツシーケンス関数をメモ化しようとしていますが、メモ化された値のハッシュマップが別の関数呼び出し間でその内容を保持する必要があります。さびでこれを行うエレガントな方法はありますか、それともメインでハッシュマップを宣言して毎回関数に渡す必要がありますか? 関数を呼び出すたびに、ハッシュマップが空のマップとして再宣言されていると思います。これが私のコードです：

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そのメソッドを作成します。

値で渡すことはできません。これは、コピー (複雑なキーではコストがかかる可能性があります) または移動 (キーを再度使用できなくなる可能性があります) のいずれかを行うためです。この場合、キーは単なる int ですが、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 クレートの機能を使用できます。これは 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 に答える