代码之家 › 专栏 › 技术社区 › Jivan

从哈希集中获取值最低的元素?

hashset rust

Jivan · 技术社区 · 8 年前

我试图用一个方法生成一个堆,该方法返回具有最小值的节点 f -值,同时将其从堆本身中移除。

堆在之后应该仍然可用,只有在没有删除值的情况下:

这个 Node struct及其实现:

use std::hash::{Hash, Hasher};

#[derive(Debug)]
struct Node {
    x: f64,
    y: f64,
    f: f64,
}

impl Node {
    fn to_bits(&self) -> u128 {
        let xb = self.x.to_bits() as u128;
        let yb = self.y.to_bits() as u128;
        (xb << 64) + yb
    }
}

impl PartialEq for Node {
    fn eq(&self, other: &Node) -> bool {
        self.x == other.x && self.y == other.y
    }
}

impl Eq for Node {}

impl Hash for Node {
    fn hash<H>(&self, state: &mut H) where H: Hasher {
        self.to_bits().hash(state)
    }
}

这个 Heap 结构:

use std::f64;
use std::collections::HashSet;

#[derive(Debug)]
struct Heap {
    pool: HashSet<Node>,
}

impl Heap {
    fn add(mut self, node: Node) -> Heap {
        self.pool.insert(node);
        self
    }

    fn consume(mut self) -> Node {
      // find the node with minimum f-value in self.pool
      // and "take" it, aka remove it from the pool
      // and then return it
      Node { x: 0.0, y: 0.0, f: 0.0 } // dummy node so that the code compiles
    }
}

还有 main 功能:

fn main() {
    let n1 = Node { x: 10.0, y: 11.0, f: 5.0 };
    let n2 = Node { x: 11.0, y: 12.0, f: 7.0 };
    let n3 = Node { x: 12.0, y: 13.0, f: 3.0 };
    let n4 = Node { x: 14.0, y: 14.0, f: 4.0 };

    let mut heap = Heap { pool: HashSet::new() };
    heap = heap.add(n1);
    heap = heap.add(n2);
    heap = heap.add(n3);
    heap = heap.add(n4);

    let minimal_n1 = heap.consume();
    println!("{:?}", minimal_n1);
    // should print
    // Node { x: 12.0, y: 13.0, f: 3.0 }

    let minimal_n2 = heap.consume();
    println!("{:?}", minimal_n2);
    // should print
    // Node { x: 14.0, y: 14.0, f: 4.0 }

    println!("Heap has {} nodes", heap.pool.len());
    // should print
    // Heap has 2 nodes
}

以下是我到目前为止尝试的关于 consume :

fn consume(mut self) -> Node {
    let mut min_f = f64::MAX;
    let mut min_node: Option<&Node> = None;

    for n in self.pool.iter() {
        if n.f < min_f {
            min_f = n.f;
            min_node = Some(n);
        }
    }

    self.pool.take(&min_node.unwrap()).unwrap()
}

问题是 self.pool 不可更改地被 iter() 方法,因此 self.pool.take() 不能在同一时刻易变地借用它。

最好的方法是什么 消费 方法获取并返回具有最小值的节点 F -价值观 pool ?

笔记:

需要一个集合(或映射),因为其他方法需要检索O(1)中的任何节点
我不使用有序集(这将很容易解决上述问题),因为添加/更新操作必须保持O(1)
这个 heap 需要在移除minimum-f节点后访问,如示例所示

1 回复 | 直到 8 年前

Shepmaster Tim Diekmann 8 年前

幸运的是,既然你要 self 从价值上来说,这是一个很容易解决的问题。扔掉所有不是最低限度的东西 Node :

fn consume(self) -> Node {
    self.pool
        .into_iter()
        .min_by(|a, b| a.f.partial_cmp(&b.f).expect("Found a NaN"))
        .expect("There was no minimum")
}

如果你需要保持 Heap 之后,需要在移除堆之前将找到的值与堆解除关联。克隆是最简单的解决方案:

fn consume(&mut self) -> Node {
    let min = self.pool
        .iter()
        .min_by(|a, b| a.f.partial_cmp(&b.f).expect("Found a NaN"))
        .cloned()
        .expect("There was no minimum");

    self.pool.remove(&min);

    min
}

这确实需要执行“额外”哈希查找。因为你要遍历整个 HashSet ,这似乎是一个相对较小的成本。

如果你不能很容易地克隆这个元素,那就系好安全带。使用来自 How to implement HashMap with two keys? ,我们可以构建一个 特质对象 可用于基于并行但等效的哈希/相等实现查找密钥:

use std::borrow::Borrow;

trait Key {
    fn as_bits(&self) -> u128;
}

impl Key for Node {
    fn as_bits(&self) -> u128 {
        let xb = self.x.to_bits() as u128;
        let yb = self.y.to_bits() as u128;
        (xb << 64) + yb
    }
}

impl Key for u128 {
    fn as_bits(&self) -> u128 { *self }
}

impl<'a> Hash for Key + 'a {
    fn hash<H: Hasher>(&self, h: &mut H) {
        self.as_bits().hash(h)
    }
}

impl<'a> PartialEq for Key + 'a {
    fn eq(&self, other: &Self) -> bool {
        self.as_bits() == other.as_bits()        
    }
}

impl<'a> Eq for Key + 'a {}

impl<'a> Borrow<Key + 'a> for Node {
    fn borrow(&self) -> &(Key + 'a) {
        self
    }
}

impl<'a> Borrow<Key + 'a> for u128 {
    fn borrow(&self) -> &(Key + 'a) {
        self
    }
}

有了这个支持,我们就可以将找到的元素转换成一个轻量级拥有的密钥,然后使用它再次查找:

fn consume(&mut self) -> Node {
    let min_key = self.pool
        .iter()
        .min_by(|a, b| a.f.partial_cmp(&b.f).expect("Found a NaN"))
        .map(Node::as_bits)
        .expect("There was no minimum");

    let min_key: &Key = min_key.borrow();
    self.pool.take(min_key).unwrap()
}