在 golang 的映射中使用指针

Question

我是 golang 新手，正在编写一些图形路由算法。我的图形表示看起来像这样

type Vertex [2]float64

type Edges map[Vertex]BagOfVertices

type BagOfVertices map[*Vertex]bool

我希望能够将特定顶点的边表示为对其他顶点的一组引用。我的记忆力非常有限。为了避免分配大量重复Vertex对象的内存成本，我想使用指向顶点对象的指针。

我有 1,335,262 个节点和 4,895,070 个边以及大约 800MB 的 RAM。

这是我的尝试

func (e *Edges) GetOrCreateVertex(vertex Vertex) *Vertex {

    edges := *e

    if _, ok := edges[vertex]; ok {

        fmt.Println("Found val")

        return &vertex

    }

    edges[vertex] = make(BagOfVertices)

    fmt.Println("Create val")

    return &vertex

}

func TestEdges(t *testing.T) {

    var edges Edges = make(map[Vertex]BagOfVertices)

    // Create edge from vertex 0 to vertex 1

    v0 := edges.GetOrCreateVertex(Vertex{0, 0})

    v1 := edges.GetOrCreateVertex(Vertex{1, 1})

    edges[*v0][v1] = true

    // Check edge exist from vertex 0 to vertex 1

    v0 = edges.GetOrCreateVertex(Vertex{0, 0})

    v1 = edges.GetOrCreateVertex(Vertex{1, 1})

    if _, ok := edges[*v0][v1]; !ok {

        t.Errorf("Edge from %v to %v does not exist", v0, v1)

    }

}

显然，返回的指针GetOrCreateVertex指向刚刚创建的值，而不是 的键Edges。如何将GetOrCreateVertex指针返回到地图中的键Edges？

Answer 1

值得注意的是： 的大小Vertex是 2 个 float64 的大小，即 16 个字节。指向 Vertex 的指针的大小可能是 8 个字节。因此，如果存在大量重复顶点，则对顶点实例进行重复数据删除至少有可能将大小减半。如果您选择这样做，您确实需要类似于代码的第二个版本的东西。但是，您可以像此处一样使用每图重复数据删除器，也可以简单地使用全局顶点重复数据删除器。后者意味着当任何一个图被丢弃时，重复数据删除器都无法进行垃圾收集。任一图中有多少个顶点将处于活动状态？随着时间的推移，您将创建和销毁多少图表，以何种模式？这两个问题的答案将决定重复数据删除/驻留 Vertex 实例所节省的空间是否值得。

Answer 2

你真的需要这么多间接吗？如果您更改顶点表示以保留其自己的边缘，我认为表示会变得更加清晰，更容易使用，并且内存占用较小。type Vertex struct {   Values [2]float64   Edges  map[*Vertex]struct{}}

Answer 3

由于这些只是由坐标组成的顶点，您真的需要内存访问吗？这是您在不使用指针的情况下通过的测试用例：https://play.golang.org/p/RBV0NNf9F_m这是一个带有指针的版本，但请注意我如何在第二次调用中传递相同的v1实例。v2对于指针，即使相同(x,y)也会产生新的内存地址。所以请注意这样做的后果。这是带有指针的代码：https ://play.golang.org/p/y9UCNUVIMVP

Answer 4

解决这个问题的一种方法是在其值中添加对 Vector 键的引用，如下所示https://play.golang.org/p/s4T8cV8uYm8type Vertex [2]float64type Edges map[Vertex]EdgeValtype EdgeVal struct {    Ref *Vertex    BagOfVertices BagOfVertices}type BagOfVertices map[*Vertex]boolfunc (e *Edges) GetOrCreateVertex(vertex Vertex) *Vertex {    edges := *e    if val, ok := edges[vertex]; ok {        fmt.Println("Found val")        return val.Ref    }    edges[vertex] = EdgeVal{&vertex, make(BagOfVertices)}    fmt.Println("Create val")    return &vertex}func TestEdges(t *testing.T) {    var edges Edges = make(map[Vertex]EdgeVal)    // Create edge from vertex 0 to vertex 1    v0 := edges.GetOrCreateVertex(Vertex{0, 0})    v1 := edges.GetOrCreateVertex(Vertex{1, 1})    edges[*v0].BagOfVertices[v1] = true    // Check edge exist from vertex 0 to vertex 1    v0 = edges.GetOrCreateVertex(Vertex{0, 0})    v1 = edges.GetOrCreateVertex(Vertex{1, 1})    if _, ok := edges[*v0].BagOfVertices[v1]; !ok {        t.Errorf("Edge from %v to %v does not exist", v0, v1)    }}

Answer 5

我设法找到一种方法来保持紧凑的表示，不幸的是，它确实需要付出代价degree(Vertex)来查看是否存在边缘。https://play.golang.org/p/xnw2p6Ut78ptype Vertex [2]float64type Edges map[Vertex]BagOfVerticestype BagOfVertices map[*Vertex]boolfunc (e *Edges) AddEdge(v1 Vertex, v2 *Vertex) {    edges := *e    if edges[v1] == nil {        edges[v1] = make(BagOfVertices)    }    if edges[*v2] == nil {        edges[*v2] = make(BagOfVertices)    }    edges[v1][v2] = true}func (e *Edges) HasEdge(v0 Vertex, v1 Vertex) bool {    edges := *e    found := false    for child := range edges[v0] {        if *child == v1 {            found = true        }    }    return found}func TestEdges(t *testing.T) {    var edges Edges = make(Edges)    // Create edge from vertex 0 to vertex 1    v0 := Vertex{0, 0}    v1 := Vertex{1, 1}    edges.AddEdge(v0, &v1)    // Check edge exist from vertex 0 to vertex 1    v0 = Vertex{0, 0}    v1 = Vertex{1, 1}    if !edges.HasEdge(v0, v1) {        t.Errorf("Edge from %v to %v does not exist", v0, v1)    }}就我而言，我正在遍历所有子项，因此HasEdge很少会调用检查，并且空间是一个更重要的约束，因此这最适合我，尽管可能并不适合所有情况。