graph - 自己的竞技场数据结构

This question already has answers here:

Implement graph-like data structure in Rust

(3个答案)


3年前关闭。




我想对一个非常大的(节点数)图进行建模，该图由许多非常大的(内存方式)节点组成。由于节点是如此之大，所以我只想存储一次，然后将借用传递给它们，因此从概念上讲，是这样的:

struct Graph<'a> {
    nodes: Vec<Node<'a>>,
}

struct Node<'a> {
    edges: HashMap<String, &'a Node>,
    // ...lots of other data...
}

当然，没有办法像这样构造Graph，因为(a)借用元素时Vec不允许我添加新节点，并且(b)我不能告诉rustc nodes向量将用于终身'a。我也不能使用Rc之类的东西，因为该图具有循环。

我想表达的是各种各样的竞技场，这使我可以分配很多Node，只要竞技场存在，就向它们进行不可变的借用，并使用生命周期检查来确保没有剩余的Node引用竞技场被取消分配时退出。就像是:

struct Graph<'a> {
    nodes: Arena<'a, Node<'a>>,
}

struct Node<'a> {
    edges: HashMap<String, &'a Node>,
}

impl<'a, A> Arena<'a, A> {
    fn own(&self, a: A) -> &'a A {
        // magic
    }
}

impl<'a, A> Drop for Arena<'a, A> {
    fn drop(&'a mut self) {
        // magic
    }
}

在语义上可以在Rust中表达吗？

最佳答案

一个简单的解决方法是使用typed-arena条板箱。它包含带有Arena方法的fn alloc(&self, T) -> &mut T类型。

另一个简单的解决方案是使用索引而不是引用(并且永远不要从Vec中删除，因为这会使索引无效)。在64位平台上，使用32位索引可能会减少一些字节。

但是，两种解决方案都无法删除节点。您可能会停止引用它们，但它们仍将保留在内存中，因此，将它们用于动态图(节点来回移动)需要更多的工作。在这种情况下，我的建议是从新的竞技场定期创建图的新克隆(不复制未使用的节点)，这类似于使用移动垃圾收集器(如果自动化程度较低)。