Golang中的地图集

我解决这个问题的方法就是保留一个结构数组,然后在插入它们时删除任何重复项.

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,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分配给地图[string] 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

在我看来,即使地图是可以清洗的,它仍然表现不佳.