惯用的 Go 中 set 的最小值

Question

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

Answer 1

Maps 是在 Go 中实现集合的惯用方式。惯用代码使用 bool 或 struct{} 作为映射的值类型。后者使用较少的存储空间，但需要在键盘上打字多一点才能使用。假设一个单元格的最大值是maxCell，那么这个函数将计算最小值：func min(m map[Cell]bool) Cell {&nbsp; &nbsp; min := maxCell&nbsp; &nbsp; for k := range m {&nbsp; &nbsp; &nbsp; &nbsp; if k < min {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; min = k&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return min}如果 Cell 是数字类型，则 maxCell 可以设置为数学常量之一。任何使用地图的解决方案都需要对键进行循环。除了地图之外，您还可以保留一个堆以找到最小值。这将需要更多的存储和代码，但取决于集合的大小和调用最小函数的频率，效率会更高。

Answer 2

一种不同的方法，根据你的集合有多大，使用自排序切片可以更有效：type Cell uint64type CellSet struct {&nbsp; &nbsp; cells []Cell}func (cs *CellSet) Len() int {&nbsp; &nbsp; return len(cs.cells)}func (cs *CellSet) Swap(i, j int) {&nbsp; &nbsp; cs.cells[i], cs.cells[j] = cs.cells[j], cs.cells[i]}func (cs *CellSet) Less(i, j int) bool {&nbsp; &nbsp; return cs.cells[i] < cs.cells[j]}func (cs *CellSet) Add(c Cell) {&nbsp; &nbsp; for _, v := range cs.cells {&nbsp; &nbsp; &nbsp; &nbsp; if v == c {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; cs.cells = append(cs.cells, c)&nbsp; &nbsp; sort.Sort(cs)}func (cs *CellSet) Min() Cell {&nbsp; &nbsp; if cs.Len() > 0 {&nbsp; &nbsp; &nbsp; &nbsp; return cs.cells[0]&nbsp; &nbsp; }&nbsp; &nbsp; return 0}func (cs *CellSet) Max() Cell {&nbsp; &nbsp; if l := cs.Len(); l > 0 {&nbsp; &nbsp; &nbsp; &nbsp; return cs.cells[l-1]&nbsp; &nbsp; }&nbsp; &nbsp; return ^Cell(0)}playground // 这是一个测试文件，将其复制到 set_test.go 并运行 go test -bench=. -benchmem -vBenchmarkSlice&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 20&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 75385089 ns/op&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;104 B/op&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 0 allocs/opBenchmarkMap&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 20&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 77541424 ns/op&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;158 B/op&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 0 allocs/opBenchmarkSliceAndMin&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 20&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 77155563 ns/op&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;104 B/op&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 0 allocs/opBenchmarkMapAndMin&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;1&nbsp; &nbsp; &nbsp; &nbsp; 1827782378 ns/op&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 2976 B/op&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 8 allocs/op