在 golang 的映射中使用指针

Question

我是 golang 新手，正在编写一些图形路由算法。我的图形表示看起来像这样type Vertex [2]float64type Edges map[Vertex]BagOfVerticestype 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/s4T8cV8uYm8

type Vertex [2]float64

type Edges map[Vertex]EdgeVal

type EdgeVal struct {

    Ref *Vertex

    BagOfVertices BagOfVertices

}

type BagOfVertices map[*Vertex]bool

func (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/xnw2p6Ut78p

type Vertex [2]float64

type Edges map[Vertex]BagOfVertices

type BagOfVertices map[*Vertex]bool

func (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很少会调用检查，并且空间是一个更重要的约束，因此这最适合我，尽管可能并不适合所有情况。