How do I write a function that returns the minimum value of a set in go? I am not just looking for a solution (I know I could just initialize the min value when iterating over the first element and then set a boolean variable that I initialized the min value) but rather an idiomatic solution. Since go doesn't have native sets, assume we have a map[Cell]bool.
Maps are the idiomatic way to implement sets in Go. Idiomatic code uses either bool or struct{} as the map's value type. The latter uses less storage, but requires a little more typing at the keyboard to use.
Assuming that the maximum value for a cell is maxCell, then this function will compute the min:
func min(m map[Cell]bool) Cell {
min := maxCell
for k := range m {
if k < min {
min = k
}
}
return min
}
If Cell is a numeric type, then maxCell can be set to one of the math constants.
Any solution using a map will require a loop over the keys.
You can keep a heap in addition to the map to find a minimum. This will require more storage and code, but can be more efficient depending on the size of the set and how often the minimum function is called.
A different approach and depending on how big your set is, using a self-sorting-slice can be more efficient:
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 // this is a test file, copy it to set_test.go and run 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