gpt4 book ai didi

rust - 是否可以仅通过一次查找就在HashMap上执行一个 `get`和两个 `insert`?

转载 作者:行者123 更新时间:2023-12-03 11:28:20 26 4
gpt4 key购买 nike

我有一个需要的应用程序:

  • 在哈希表中查找一个值,如果存在,则将其返回
  • 如果不存在,则存储一个临时值
  • 使用表
  • 中的其他值计算新值
  • 将新值存储到哈希表
  • 返回新值

  • 我只想通过1次哈希/查找来做到这一点。那可能吗?可以用2做吗?

    我正在计算斐波那契以表明目的。最好从3次查询优化为1次查询的函数是 index()函数:
    // Written by beefucurry

    use std::collections::HashMap;

    use std::cell::UnsafeCell;

    fn main() {
    let fib = SaveCall::<u32, u32>::new(|k, fib_| {
    if k < 2 {
    return k;
    } else {
    return fib_[k - 1] + fib_[k - 2];
    }
    });

    for k in (0..30).rev() {
    println!("fib[{}] = {}", k, fib[k]);
    }
    }

    pub struct SaveCall<'a, In: std::cmp::Eq + std::hash::Hash + Copy, Out> {
    cache: UnsafeCell<HashMap<In, Option<Out>>>,
    f: Box<dyn Fn(In, &SaveCall<'a, In, Out>) -> Out + 'a>,
    }
    impl<'a, In: std::cmp::Eq + std::hash::Hash + Copy, Out> SaveCall<'a, In, Out> {
    pub fn new(f: impl Fn(In, &Self) -> Out + 'a) -> Self {
    Self {
    cache: UnsafeCell::new(HashMap::new()),
    f: Box::new(f),
    }
    }
    }

    impl<'a, In: std::cmp::Eq + std::hash::Hash + Copy, Out> std::ops::Index<In>
    for SaveCall<'a, In, Out>
    {
    type Output = Out;
    fn index<'b>(&'b self, input: In) -> &'b Self::Output {
    unsafe {
    //println!("~~Looking up {:?}", input);
    let cache = self.cache.get();
    let saved = (*cache).get(&input);
    if saved.is_some() {
    //println!("~~Found {:?}", input);
    let z = saved.unwrap().as_ref();
    if z.is_some() {
    return z.unwrap();
    } else {
    panic!("Attempted to compute a value based on itself");
    }
    }
    (*cache).insert(input, None);
    //println!("~~Computing {:?}", input);
    let output: Out = (self.f)(input, self);
    //println!("~~Writing to cache {:?}", input);
    (*cache).insert(input, Some(output));
    let output_ref = (*cache).get(&input).unwrap().as_ref().unwrap();
    output_ref
    }
    }
    }

    playground

    最佳答案

    I'd like to do this with only 1 hash/lookup. Is that possible?



    单个哈希查找是不可能的,因为Rust无法知道计算本身是否可能尝试更改 SaveCall对象的结构。如果您的回调不接受 self作为参数,则有可能,但不能使用所需的API。

    Is it possible to do it with 2?



    使用 HashMap::entry ,可以使用2,它使您可以在 map 中搜索键,并修改位置并检查它是否具有值,而不必重新计算哈希。

    最初查询表并返回或插入 None时,可以使用此方法一次计算哈希,然后在获得最终结果时可以正常插入。

    这将我们带到您的代码本身。无法使用 std::ops::Index特性来执行您想要的操作。您的示例代码已尝试使用 UnsafeCell解决此问题,但您的不安全代码违反了不安全代码必须遵守的要求。

    简短的版本是 Index特性返回一个引用。您特别想通过在访问条目时插入条目来改变 map ,这意味着HashMap必须增加并为其值重新分配空间。如果必须重新分配,则意味着 index返回的引用无法保持有效,因为它们引用的是已重新分配的内存。

    那在哪里离开你?
  • 您需要停止使用Index特性,而是在SavedCall类型上实现一个不返回引用的方法。
  • 您需要决定要返回的内容。如果要直接返回Out,则Out需要明确为Copy类型。如果要支持非复制类型,则可能需要返回RcArc

  • 例如
    impl<'a, In: std::cmp::Eq + std::hash::Hash + Copy, Out> SaveCall<'a, In, Out> {
    fn get(&self, input: In) -> Rc<Out> {

    或者
    impl<'a, In: std::cmp::Eq + std::hash::Hash + Copy, Out: Copy> SaveCall<'a, In, Out> {
    fn get(&self, input: In) -> Out {

    这是在示例代码 on the Rust playground上构建的更完整的版本。这使用Rc最好地演示了该示例,但是如果 Out: Copy可以,则可以将其精简。

    关于rust - 是否可以仅通过一次查找就在HashMap上执行一个 `get`和两个 `insert`?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59148656/

    26 4 0
    Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
    广告合作:1813099741@qq.com 6ren.com