惯用的 Go 中 set 的最小值

Question

如何编写一个函数来返回 go 中集合的最小值？我不只是在寻找解决方案（我知道我可以在迭代第一个元素时初始化最小值，然后设置一个布尔变量来初始化最小值），而是一个惯用的解决方案。由于 go 没有本地集，假设我们有一个map[Cell]bool.

Answer 1

Maps 是在 Go 中实现集合的惯用方式。惯用代码使用 bool 或 struct{} 作为映射的值类型。后者使用较少的存储空间，但需要在键盘上打字多一点才能使用。

假设一个单元格的最大值是maxCell，那么这个函数将计算最小值：

func min(m map[Cell]bool) Cell {

    min := maxCell

    for k := range m {

        if k < min {

            min = k

        }

    }

    return min

}

如果 Cell 是数字类型，则 maxCell 可以设置为数学常量之一。

任何使用地图的解决方案都需要对键进行循环。

除了地图之外，您还可以保留一个堆以找到最小值。这将需要更多的存储和代码，但取决于集合的大小和调用最小函数的频率，效率会更高。

Answer 2

一种不同的方法，根据你的集合有多大，使用自排序切片可以更有效：

type Cell uint64

type CellSet struct {

    cells []Cell

}

func (cs *CellSet) Len() int {

    return len(cs.cells)

}

func (cs *CellSet) Swap(i, j int) {

    cs.cells[i], cs.cells[j] = cs.cells[j], cs.cells[i]

}

func (cs *CellSet) Less(i, j int) bool {

    return cs.cells[i] < cs.cells[j]

}

func (cs *CellSet) Add(c Cell) {

    for _, v := range cs.cells {

        if v == c {

            return

        }

    }

    cs.cells = append(cs.cells, c)

    sort.Sort(cs)

}

func (cs *CellSet) Min() Cell {

    if cs.Len() > 0 {

        return cs.cells[0]

    }

    return 0

}

func (cs *CellSet) Max() Cell {

    if l := cs.Len(); l > 0 {

        return cs.cells[l-1]

    }

    return ^Cell(0)

}

playground // 这是一个测试文件，将其复制到 set_test.go 并运行 go test -bench=. -benchmem -v

BenchmarkSlice                20          75385089 ns/op             104 B/op          0 allocs/op

BenchmarkMap                  20          77541424 ns/op             158 B/op          0 allocs/op

BenchmarkSliceAndMin          20          77155563 ns/op             104 B/op          0 allocs/op

BenchmarkMapAndMin             1        1827782378 ns/op            2976 B/op          8 allocs/op