我是 golang 新手，正在編寫一些圖形路由算法。我的圖形表示看起來(lái)像這樣type Vertex [2]float64type Edges map[Vertex]BagOfVerticestype BagOfVertices map[*Vertex]bool我希望能夠?qū)⑻囟旤c(diǎn)的邊表示為對(duì)其他頂點(diǎn)的一組引用。我的記憶力非常有限。為了避免分配大量重復(fù)Vertex對(duì)象的內(nèi)存成本，我想使用指向頂點(diǎn)對(duì)象的指針。我有 1,335,262 個(gè)節(jié)點(diǎn)和 4,895,070 個(gè)邊以及大約 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指向剛剛創(chuàng)建的值，而不是 的鍵Edges。如何將GetOrCreateVertex指針?lè)祷氐降貓D中的鍵Edges？
5 回答
長(zhǎng)風(fēng)秋雁
TA貢獻(xiàn)1757條經(jīng)驗(yàn) 獲得超7個(gè)贊
值得注意的是： 的大小Vertex是 2 個(gè) float64 的大小，即 16 個(gè)字節(jié)。指向 Vertex 的指針的大小可能是 8 個(gè)字節(jié)。因此，如果存在大量重復(fù)頂點(diǎn)，則對(duì)頂點(diǎn)實(shí)例進(jìn)行重復(fù)數(shù)據(jù)刪除至少有可能將大小減半。
如果您選擇這樣做，您確實(shí)需要類似于代碼的第二個(gè)版本的東西。但是，您可以像此處一樣使用每圖重復(fù)數(shù)據(jù)刪除器，也可以簡(jiǎn)單地使用全局頂點(diǎn)重復(fù)數(shù)據(jù)刪除器。后者意味著當(dāng)任何一個(gè)圖被丟棄時(shí)，重復(fù)數(shù)據(jù)刪除器都無(wú)法進(jìn)行垃圾收集。
任一圖中有多少個(gè)頂點(diǎn)將處于活動(dòng)狀態(tài)？隨著時(shí)間的推移，您將創(chuàng)建和銷毀多少圖表，以何種模式？這兩個(gè)問(wèn)題的答案將決定重復(fù)數(shù)據(jù)刪除/駐留 Vertex 實(shí)例所節(jié)省的空間是否值得。
夢(mèng)里花落0921
TA貢獻(xiàn)1772條經(jīng)驗(yàn) 獲得超6個(gè)贊
你真的需要這么多間接嗎？如果您更改頂點(diǎn)表示以保留其自己的邊緣，我認(rèn)為表示會(huì)變得更加清晰，更容易使用，并且內(nèi)存占用較小。
type Vertex struct {
Values [2]float64
Edges map[*Vertex]struct{}
}
www說(shuō)
TA貢獻(xiàn)1775條經(jīng)驗(yàn) 獲得超8個(gè)贊
由于這些只是由坐標(biāo)組成的頂點(diǎn)，您真的需要內(nèi)存訪問(wèn)嗎？
這是您在不使用指針的情況下通過(guò)的測(cè)試用例：https://play.golang.org/p/RBV0NNf9F_m
這是一個(gè)帶有指針的版本，但請(qǐng)注意我如何在第二次調(diào)用中傳遞相同的v1實(shí)例。v2對(duì)于指針，即使相同(x,y)也會(huì)產(chǎn)生新的內(nèi)存地址。所以請(qǐng)注意這樣做的后果。
這是帶有指針的代碼：https ://play.golang.org/p/y9UCNUVIMVP
慕慕森
TA貢獻(xiàn)1856條經(jīng)驗(yàn) 獲得超17個(gè)贊
解決這個(gè)問(wèn)題的一種方法是在其值中添加對(duì) 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)
}
}
慕妹3242003
TA貢獻(xiàn)1824條經(jīng)驗(yàn) 獲得超6個(gè)贊
我設(shè)法找到一種方法來(lái)保持緊湊的表示，不幸的是，它確實(shí)需要付出代價(jià)degree(Vertex)來(lái)查看是否存在邊緣。
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)
}
}
就我而言，我正在遍歷所有子項(xiàng)，因此HasEdge很少會(huì)調(diào)用檢查，并且空間是一個(gè)更重要的約束，因此這最適合我，盡管可能并不適合所有情況。
- 5 回答
- 0 關(guān)注
- 212 瀏覽
添加回答
舉報(bào)
0/150
提交
取消