英文:
Minimum value of set in idiomatic Go
问题
你好！以下是你要翻译的内容：
如何编写一个在 Go 语言中返回集合最小值的函数？我不仅仅是在寻找一个解决方案（我知道可以在迭代第一个元素时初始化最小值，并设置一个布尔变量来表示是否已经初始化了最小值），而是要找一个符合惯用写法的解决方案。由于 Go 语言没有原生的集合类型，我们可以假设有一个 map[Cell]bool。
英文:
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.
答案1
得分: 2
地图是在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可以设置为math常量之一。
使用地图的任何解决方案都需要循环遍历键。
除了地图之外，您还可以保留一个堆，以找到最小值。这将需要更多的存储空间和代码，但根据集合的大小和最小函数的调用频率，可能更高效。
英文:
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.
答案2
得分: 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
英文:
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)
}
<kbd>playground</kbd> // 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
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论