地圖在Golang

Question

設置如果我有一個像結構：

type Foo struct { 
    title string 
    Tags map[string]string 
} 

如何可能接近維持了一套獨特的這種結構的？據我所知，雖然結構平等是一件事情 - 地圖平等不是。這意味着我無法比較我的上述結構。因此我不能只實施map as set pattern。

我能想到的兩個選項是：將標籤轉換爲排序的[][]string或use reflect.Deepequal。任何人有更好的主意？

Answer 1

根據你在做什麼，一個選項可能是將結構存儲爲地圖中的值而不是鍵。爲此，您將需要創建一些方法來從每個結構值生成唯一鍵。

像這樣的東西可能會奏效：

// Doesn't have to be a string: just has to be suitable for use as a map key. 
func (foo *Foo) key() string { 
    return key_string 
} 

fooSet := make(map[string] *Foo) 

// Store a Foo 
fooSet[x.key()] = x 

// Check if x is in the set: 
if fooSet[x.key()] != nil { 
    println("x is in the set") 
} 

如何好這一工程將取決於你如何有效地得到您的結構的關鍵。

Answer 2

有幾種實現方法。 James Henstridge實際上有一個好主意，我試圖實現它。它表現得相當不好，只是使用地圖，沒有我自己的哈希算法。

我解決這個問題的方法只是保留你的結構數組，然後在插入它們時刪除任何重複項。

package structset 

type Foo struct { 
    title string 
    Tags map[string]string 
} 

func (f Foo) Equals(f2 Foo) bool { 
    if f.title != f2.title { 
    return false 
    } 

    if len(f.Tags) != len(f2.Tags) { 
    return false 
    } 

    for k, v := range f.Tags { 
    if w, ok := f2.Tags[k]; !ok || v != w { 
     return false 
    } 
    } 

    return true 
} 

type FooSet []Foo 

func (this FooSet) Add(value Foo) { 
    if !this.Contains(value) { 
    this = append(this, value) 
    } 
} 

func (this FooSet) Length() int { 
    return len(this) 
} 

func (this FooSet) Contains(f Foo) bool { 
    for _, v := range this { 
    if v.Equals(f) { 
     return true 
    } 
    } 
    return false 
} 

func NewSet() FooSet { 
    return FooSet(make([]Foo, 0, 100)) 
} 

我這個基準我i7-3770K Windows機器上，並得到：

BenchmarkSmallSetWithFewCollisions   50000    46615 ns/op 
BenchmarkSmallSetWithMoreCollisions  50000    46575 ns/op 
BenchmarkSmallSetWithManyCollisions  50000    46605 ns/op 
BenchmarkMediumSetWithFewCollisions   1000   2335296 ns/op 
BenchmarkMediumSetWithMoreCollisions  1000   2352298 ns/op 
BenchmarkMediumSetWithManyCollisions  1000   2336796 ns/op 
BenchmarkLargeSetWithFewCollisions   50   46805944 ns/op 
BenchmarkLargeSetWithMoreCollisions   50   47376016 ns/op 
BenchmarkLargeSetWithManyCollisions   50   46815946 ns/op 

要伊克出來的性能極少量的，您可以先插入所有數據到數組，然後刪除所有重複項後。

的刪除重複的代碼是：

func (this FooSet) RemoveDuplicates() { 
    length := len(this) - 1 
    for i := 0; i < length; i++ { 
    for j := i + 1; j <= length; j++ { 
     if this[i].Equals(this[j]) { 
     this[j] = this[length] 
     this = this[0:length] 
     length-- 
     j-- 
     } 
    } 
    } 
} 

的基準是這樣的：

BenchmarkSmallSetWithFewCollisions   50000    45245 ns/op 
BenchmarkSmallSetWithMoreCollisions  50000    45615 ns/op 
BenchmarkSmallSetWithManyCollisions  50000    45555 ns/op 
BenchmarkMediumSetWithFewCollisions   1000   2294791 ns/op 
BenchmarkMediumSetWithMoreCollisions  1000   2309293 ns/op 
BenchmarkMediumSetWithManyCollisions  1000   2286290 ns/op 
BenchmarkLargeSetWithFewCollisions   50   46235870 ns/op 
BenchmarkLargeSetWithMoreCollisions   50   46515906 ns/op 
BenchmarkLargeSetWithManyCollisions   50   45865824 ns/op 

這裏是剛剛分配的Foo到地圖[字符串]美孚的基準。

BenchmarkSmallSetWithFewCollisions   50000    65718 ns/op 
BenchmarkSmallSetWithMoreCollisions  50000    64238 ns/op 
BenchmarkSmallSetWithManyCollisions  50000    55016 ns/op 
BenchmarkMediumSetWithFewCollisions   500   3429435 ns/op 
BenchmarkMediumSetWithMoreCollisions   500   3117395 ns/op 
BenchmarkMediumSetWithManyCollisions  1000   2826858 ns/op 
BenchmarkLargeSetWithFewCollisions   20   82635495 ns/op 
BenchmarkLargeSetWithMoreCollisions   20   85285830 ns/op 
BenchmarkLargeSetWithManyCollisions   20   73659350 ns/op 

在我看來，即使地圖是可散的，它仍然不會表現的很好。

Answer 3

你確定你的例子有效嗎？ 我相信你必須傳遞一個指向Add（）方法的指針才能使你的代碼工作。無論如何，這裏是我的執行：

package math 

// types 

type IntPoint struct { 
    X, Y int 
} 

// set implementation for small number of items 
type IntPointSet struct { 
    slice []IntPoint 
} 

// functions 

func (p1 IntPoint) Equals(p2 IntPoint) bool { 
    return (p1.X == p2.X) && (p1.Y == p2.Y) 
} 

func (set *IntPointSet) Add(p IntPoint) { 
    if ! set.Contains(p) { 
     set.slice = append(set.slice, p) 
    } 
} 

func (set IntPointSet) Contains(p IntPoint) bool { 
    for _, v := range set.slice { 
    if v.Equals(p) { 
     return true 
    } 
    } 
    return false 
} 

func (set IntPointSet) NumElements() int { 
    return len(set.slice) 
} 

func NewIntPointSet() IntPointSet { 
    return IntPointSet{(make([]IntPoint, 0, 10))} 
}