Я новичок в golang, и я пишу некоторые алгоритмы маршрутизации графа. Мое представление графа выглядит так:
type Vertex [2]float64
type Edges map[Vertex]BagOfVertices
type BagOfVertices map[*Vertex]bool
Я хочу иметь возможность представлять ребра из определенной вершины в виде набора ссылок на другие вершины. Я очень ограничен в памяти. Чтобы избежать затрат памяти на выделение множества дубликатов Vertex
объектов, я хочу использовать указатели для объектов вершин.
У меня 1335 262 узла, 4895070 ребер и около 800 МБ ОЗУ.
Здесьмоя попытка сделать это
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)
}
}