亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全,請及時綁定郵箱和手機立即綁定
已解決430363個問題,去搜搜看,總會有你想問的

在 golang 的映射中使用指針

在 golang 的映射中使用指針

Go
撒科打諢 2023-07-26 19:38:17
我是 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?
查看完整描述

5 回答

?
長風秋雁

TA貢獻1757條經驗 獲得超7個贊

值得注意的是: 的大小Vertex是 2 個 float64 的大小,即 16 個字節。指向 Vertex 的指針的大小可能是 8 個字節。因此,如果存在大量重復頂點,則對頂點實例進行重復數據刪除至少有可能將大小減半。

如果您選擇這樣做,您確實需要類似于代碼的第二個版本的東西。但是,您可以像此處一樣使用每圖重復數據刪除器,也可以簡單地使用全局頂點重復數據刪除器。后者意味著當任何一個圖被丟棄時,重復數據刪除器都無法進行垃圾收集。

任一圖中有多少個頂點將處于活動狀態?隨著時間的推移,您將創建和銷毀多少圖表,以何種模式?這兩個問題的答案將決定重復數據刪除/駐留 Vertex 實例所節省的空間是否值得。


查看完整回答
反對 回復 2023-07-26
?
夢里花落0921

TA貢獻1772條經驗 獲得超6個贊

你真的需要這么多間接嗎?如果您更改頂點表示以保留其自己的邊緣,我認為表示會變得更加清晰,更容易使用,并且內存占用較小。


type Vertex struct {

   Values [2]float64

   Edges  map[*Vertex]struct{}

}


查看完整回答
反對 回復 2023-07-26
?
www說

TA貢獻1775條經驗 獲得超8個贊

由于這些只是由坐標組成的頂點,您真的需要內存訪問嗎?

這是您在不使用指針的情況下通過的測試用例:https://play.golang.org/p/RBV0NNf9F_m

這是一個帶有指針的版本,但請注意我如何在第二次調用中傳遞相同的v1實例。v2對于指針,即使相同(x,y)也會產生新的內存地址。所以請注意這樣做的后果。

這是帶有指針的代碼:https ://play.golang.org/p/y9UCNUVIMVP



查看完整回答
反對 回復 2023-07-26
?
慕慕森

TA貢獻1856條經驗 獲得超17個贊

解決這個問題的一種方法是在其值中添加對 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)

    }

}



查看完整回答
反對 回復 2023-07-26
?
慕妹3242003

TA貢獻1824條經驗 獲得超6個贊

我設法找到一種方法來保持緊湊的表示,不幸的是,它確實需要付出代價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很少會調用檢查,并且空間是一個更重要的約束,因此這最適合我,盡管可能并不適合所有情況。


查看完整回答
反對 回復 2023-07-26
  • 5 回答
  • 0 關注
  • 199 瀏覽
慕課專欄
更多

添加回答

舉報

0/150
提交
取消
微信客服

購課補貼
聯系客服咨詢優惠詳情

幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

公眾號

掃描二維碼
關注慕課網微信公眾號