Over Engineering:使用引用(borrow?)论“锈”中的HashMap键

Question

我正在编写一个搜索算法(BFS/DFS)来搜索游戏状态树。我已经用C语言做了这个东西，但我想知道Rust是否会更快，因为我一直想学习Rust，所以我想我应该试一试。

我试图将这个东西优化到过度工程的程度(我喜欢它，让我这样做吧)，我用C语言做了一个我认为很酷的优化，但我不知道如何在Rust中(/if it is possible)。

我的算法概述如下：

Add the start state to a queue, and make a hashmap [State -> Previous State, Action]
// I use this hashmap to find the way back later, and to check if I have been in a state before.

Take a state S0 from the queue:
   for all possible actions, calculate next state S1:
      if S1 is already a key in the hashmap, continue
      and add [ S1 -> S0, action taken ] to the hashmap
      add S1 to the queue,
   ...
   // some other stuff here to check when to stop

我在C语言中做的一个优化是这样的:不是将状态结构数据复制到队列中，而是将指向哈希表中的相同数据的指针复制到队列中(因为我只是将其添加到哈希图中)，这样我就不必复制状态数据，但队列只包含指向哈希图中相同数据的指针。

这在C中很容易实现，因为我有自己的hashmap实现，所以很容易创建一个函数来返回指向hashmap中正确数据的指针。

在Rust中，我现在有了这个：

// Add all possible moves to be searched through later
for m in possible_moves.iter() {
    if let Some(new_state) = popped.do_move(m) { // popped is S0 from my algorithm outline
        if backmap.contains_key(&new_state) { continue; }
        queue.push_back(new_state);
        backmap.insert(new_state, Wayback {
        prev_state: popped, did_move: m });
    }
}

但这意味着new_state数据将被复制到队列和哈希图中。我想知道是否有一种方法可以不在Rust中复制这些数据，就像我的C版本(或其他方式)。

我喜欢这种优化，因为我只是喜欢它的优化感觉，但在Rust的情况下，也因为现在这个复制意味着我拥有#[derive(Clone, Copy)]高于我的所有结构，这是不好的，如果没有一种方法来做我的过度工程优化，但有一种方法，不必派生复制和克隆我仍然想知道的特征。

非常感谢您的帮助！

附注:我认识到这不是你的常规代码问题，从我的解释中可能会很不清楚，所以如果有任何关于我的意思的问题，我会尽快回答他们。

Answer 1

我喜欢这个优化，因为我只是喜欢它的优化感觉，但在Rust的例子中，也是因为现在这个拷贝意味着我有#derive(克隆，复制)高于我所有的结构，这是不好的

取决于结构…的大小这真的很重要吗？Copy只是一个memcpy。

这里的问题是，Rust希望为每个数据片段都有一个明确的静态所有者，但这在您的算法中并不存在:状态由map和队列“拥有”。“共享”不明确所有权的方法是使用Rc，但这会转换为堆分配(如果不是原子的，refcount流量实际上并不重要)，如果是state，这可能是悲观的