时间戳

首页 > 解决方案 > 在 golang 的地图中使用指针

go - 在 golang 的地图中使用指针

问题描述

我是 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地图中的键？

我的工作是创造

测试失败演示

我的解决方法是使用第二张地图来存储指向顶点的指针。

type Vertex [2]float64
type GraphType struct {
    vertices Vertices
    edges    Edges
}
type Vertices map[Vertex]*Vertex
type Edges map[*Vertex]BagOfVertices
type BagOfVertices map[*Vertex]bool

func (graph *GraphType) Init() {
    graph.vertices = make(Vertices)
    graph.edges = make(Edges)
}
func (graph *GraphType) GetOrCreateVertex(vertex Vertex) *Vertex {
    if val, ok := graph.vertices[vertex]; ok {
        fmt.Println("Found val")
        return val
    }
    graph.vertices[vertex] = &vertex
    graph.edges[&vertex] = make(BagOfVertices)
    fmt.Println("Create val")
    return &vertex
}

func TestEdges(t *testing.T) {
    var graph GraphType
    graph.Init()
    // Create vertex 0 and vertex 1
    graph.GetOrCreateVertex(Vertex{0, 0})
    graph.GetOrCreateVertex(Vertex{1, 1})

    // Create edge from vertex 0 to vertex 1
    v0 := graph.GetOrCreateVertex(Vertex{0, 0})
    v1 := graph.GetOrCreateVertex(Vertex{1, 1})
    graph.edges[v0][v1] = true

    // Check edge exist from vertex 0 to vertex 1
    v0 = graph.GetOrCreateVertex(Vertex{0, 0})
    v1 = graph.GetOrCreateVertex(Vertex{1, 1})
    if _, ok := graph.edges[v0][v1]; !ok {
        t.Errorf("Edge from %v to %v does not exist", v0, v1)
    }
}

标签： go

解决方案

你真的需要这么多间接吗？如果您更改顶点表示以保留其自己的边缘，我认为该表示会变得更清晰，更易于使用，并且内存占用少。

type Vertex struct {
   Values [2]float64
   Edges  map[*Vertex]struct{}
}

推荐阅读