5 回答

TA貢獻1757條經驗 獲得超7個贊
值得注意的是: 的大小Vertex
是 2 個 float64 的大小,即 16 個字節。指向 Vertex 的指針的大小可能是 8 個字節。因此,如果存在大量重復頂點,則對頂點實例進行重復數據刪除至少有可能將大小減半。
如果您選擇這樣做,您確實需要類似于代碼的第二個版本的東西。但是,您可以像此處一樣使用每圖重復數據刪除器,也可以簡單地使用全局頂點重復數據刪除器。后者意味著當任何一個圖被丟棄時,重復數據刪除器都無法進行垃圾收集。
任一圖中有多少個頂點將處于活動狀態?隨著時間的推移,您將創建和銷毀多少圖表,以何種模式?這兩個問題的答案將決定重復數據刪除/駐留 Vertex 實例所節省的空間是否值得。

TA貢獻1772條經驗 獲得超6個贊
你真的需要這么多間接嗎?如果您更改頂點表示以保留其自己的邊緣,我認為表示會變得更加清晰,更容易使用,并且內存占用較小。
type Vertex struct {
Values [2]float64
Edges map[*Vertex]struct{}
}

TA貢獻1775條經驗 獲得超8個贊
由于這些只是由坐標組成的頂點,您真的需要內存訪問嗎?
這是您在不使用指針的情況下通過的測試用例:https://play.golang.org/p/RBV0NNf9F_m
這是一個帶有指針的版本,但請注意我如何在第二次調用中傳遞相同的v1
實例。v2
對于指針,即使相同(x,y)
也會產生新的內存地址。所以請注意這樣做的后果。
這是帶有指針的代碼:https ://play.golang.org/p/y9UCNUVIMVP

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)
}
}

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很少會調用檢查,并且空間是一個更重要的約束,因此這最適合我,盡管可能并不適合所有情況。
- 5 回答
- 0 關注
- 199 瀏覽
添加回答
舉報