Использование указателей на карте в Голанге

Question

Я новичок в 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)
    }
}

Answer 1

Стоит отметить: размер Vertex - это размер 2 float64s, или 16 байт. Размер указателя на Vertex, вероятно, составляет 8 байт. Таким образом, дедупликация экземпляров Vertex может, по крайней мере, потенциально сократить размер пополам, , если есть много повторяющихся вершин.

Если вы решите сделать это, вам нужно что-то вродеваша вторая версия вашего кода. Однако вы можете либо использовать дедупликатор на граф , как вы делаете здесь, либо вы можете просто использовать глобальный дедупликатор вершин. Последнее означает, что дедупликатор не может быть собран мусором, когда отбрасывается какой-либо один граф.

Сколько вершин будет активным в любом одном графе? Сколько графиков вы будете создавать и разрушать со временем, по какой схеме? Ответы на эти два вопроса определят, стоит ли экономить пространство от дедупликации / интернирования экземпляров Vertex.

Answer 2

Тебе действительно нужно так много косвенных указаний? Если вы измените представление вершин, чтобы сохранить его собственные ребра, я думаю, что представление станет намного чище, с ним легче работать и с небольшим объемом памяти.

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

Answer 3

Поскольку это только вершины, состоящие из координат, вам действительно нужен доступ к памяти?

Передача теста без использования указателейвторой звонокС указателями даже тот же самый (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 вызывается редко, и пробел является более важным ограничением, поэтому для меня это лучше всего работает,хотя может не подходить для всех случаев.