英文:
How to avoid re-implementing sort.Interface for similar golang structs
问题
在Golang中有一个问题困扰着我。假设我有两个结构体:
type Dog struct {
Name string
Breed string
Age int
}
type Cat struct {
Name string
FavoriteFood string
Age int
}
当我尝试按照Age
对[]*Dog
和[]*Cat
进行排序时,我不得不定义两个不同的排序结构体,如下所示:
type SortCat []*Cat
func (c SortCat) Len() int {//..}
func (c SortCat) Swap(i, j int) {//..}
func (c SortCat) Less(i, j int) bool {//..}
type SortDog []*Dog
func (c SortDog) Len() int {//..}
func (c SortDog) Swap(i, j int) {//..}
func (c SortDog) Less(i, j int) bool {//..}
一个自然的想法是实现一个SortableByAge
接口,并使用接口函数创建一个Less
函数,如下所示:
type SortableByAge interface {
AgeValue() int
}
type SortAnimal []SortableByAge
func (c SortDog) Less(i, j int) bool {
return c[i].AgeValue() < c[j].AgeValue()
}
然而,根据:http://golang.org/doc/faq#convert_slice_of_interface,上述方法是行不通的。
所以我想知道在这种情况下最佳实践是什么,是否有其他技术可以减少重复实现类似结构体的sort.Interface
的需求?
编辑:
我意识到我的示例很糟糕:(
在实际情况中,这两个结构体非常不同,它们之间唯一的共同点是我希望按照一个共同的数值进行排序。
一个更好的例子是:
type Laptop {//...}
type Pizza {//...}
这两个结构体唯一的共同点是我希望按照价格对它们的切片进行排序。
因此,将它们合并为一个共同的结构体对于很多情况来说并不适用。但是我会研究一下"go generate"。
英文:
There is one problem bothering me in Golang.
Say I have 2 structs:
type Dog struct {
Name string
Breed string
Age int
}
type Cat struct {
Name string
FavoriteFood string
Age int
}
And when I try to sort []*Dog
and []*Cat
by Age
, I have to define 2 different sort struct like:
type SortCat []*Cat
func (c SortCat) Len() int {//..}
func (c SortCat) Swap(i, j int) {//..}
func (c SortCat) Less(i, j int) bool {//..}
type SortDog []*Dog
func (c SortDog) Len() int {//..}
func (c SortDog) Swap(i, j int) {//..}
func (c SortDog) Less(i, j int) bool {//..}
A natural thought is to implement some SortableByAge
interface and create a Less
function using the interface function. Like:
type SortableByAge interface {
AgeValue() int
}
And then:
type SortAnimal []SortableByAge
func (c SortDog) Less(i, j int) bool {
return c[i].AgeValue() < c[j].AgeValue()
}
However, according to:
http://golang.org/doc/faq#convert_slice_of_interface
dogs := make([]*Dogs, 0 , 1)
//add dogs here
sort.Sort(SortAnimal(dogs))
Above is not possible.
So I wonder what is the best practice for this case and
Is there any other technique that can reduce the need for implementing the sort.Interface
for similar structs again and again that I have missed?
EDIT:
I realized that my examples are terrible
In real life case, these 2 structs are very different, the only thing in common between them is that I wish to sort them by a common numeric value.
A better example would be:
type Laptop {//...}
type Pizza {//...}
And the only thing these 2 structs share in common is that I wish to sort a slice(agh... should not have used Pizza
in example) of them by price.
So, combining them to a common struct is not really working for a lot of cases.
But will look into go generate.
答案1
得分: 11
这个特定案例
在这个特定案例中,你不应该使用两种不同的类型,因为它们是相同的,只需使用一个通用的Animal
类型:
type Animal struct {
Name string
Age int
}
func (a Animal) String() string { return fmt.Sprintf("%s(%d)", a.Name, a.Age) }
type SortAnim []*Animal
func (c SortAnim) Len() int { return len(c) }
func (c SortAnim) Swap(i, j int) { c[i], c[j] = c[j], c[i] }
func (c SortAnim) Less(i, j int) bool { return c[i].Age < c[j].Age }
func main() {
dogs := []*Animal{&Animal{"Max", 4}, &Animal{"Buddy", 3}}
cats := []*Animal{&Animal{"Bella", 4}, &Animal{"Kitty", 3}}
fmt.Println(dogs)
sort.Sort(SortAnim(dogs))
fmt.Println(dogs)
fmt.Println(cats)
sort.Sort(SortAnim(cats))
fmt.Println(cats)
}
输出结果(Go Playground):
[Max(4) Buddy(3)]
[Buddy(3) Max(4)]
[Bella(4) Kitty(3)]
[Kitty(3) Bella(4)]
一般情况
一般情况下,如果你愿意放弃具体类型并使用接口类型,你可以使用通用的排序实现。
创建你想要切片持有的接口类型:
type Animal interface {
Name() string
Age() int
}
你可以有一个通用的实现:
type animal struct {
name string
age int
}
func (a *animal) Name() string { return a.name }
func (a *animal) Age() int { return a.age }
func (a animal) String() string { return fmt.Sprintf("%s(%d)", a.name, a.age) }
你的具体动物类型:
type Dog struct {
animal // 嵌入animal(它的方法和字段)
}
type Cat struct {
animal // 嵌入animal(它的方法和字段)
}
在SortAnim
上实现sort.Interface
:
type SortAnim []Animal
func (c SortAnim) Len() int { return len(c) }
func (c SortAnim) Swap(i, j int) { c[i], c[j] = c[j], c[i] }
func (c SortAnim) Less(i, j int) bool { return c[i].Age() < c[j].Age() }
使用它:
dogs := SortAnim{&Dog{animal{"Max", 4}}, &Dog{animal{"Buddy", 3}}}
cats := SortAnim{&Cat{animal{"Bella", 4}}, &Cat{animal{"Kitty", 3}}}
fmt.Println(dogs)
sort.Sort(SortAnim(dogs))
fmt.Println(dogs)
fmt.Println(cats)
sort.Sort(SortAnim(cats))
fmt.Println(cats)
输出结果(Go Playground):
[Max(4) Buddy(3)]
[Buddy(3) Max(4)]
[Bella(4) Kitty(3)]
[Kitty(3) Bella(4)]
英文:
This Specific Case
In this specific case you shouldn't use 2 different types as they are identical, just use a common Animal
type:
type Animal struct {
Name string
Age int
}
func (a Animal) String() string { return fmt.Sprintf("%s(%d)", a.Name, a.Age) }
type SortAnim []*Animal
func (c SortAnim) Len() int { return len(c) }
func (c SortAnim) Swap(i, j int) { c[i], c[j] = c[j], c[i] }
func (c SortAnim) Less(i, j int) bool { return c[i].Age < c[j].Age }
func main() {
dogs := []*Animal{&Animal{"Max", 4}, &Animal{"Buddy", 3}}
cats := []*Animal{&Animal{"Bella", 4}, &Animal{"Kitty", 3}}
fmt.Println(dogs)
sort.Sort(SortAnim(dogs))
fmt.Println(dogs)
fmt.Println(cats)
sort.Sort(SortAnim(cats))
fmt.Println(cats)
}
Output (Go Playground):
[Max(4) Buddy(3)]
[Buddy(3) Max(4)]
[Bella(4) Kitty(3)]
[Kitty(3) Bella(4)]
General Case
In general you can only use a common sorting implementation if you're willing to give up concrete types and use interface types instead.
Create the interface type you want your slice to hold:
type Animal interface {
Name() string
Age() int
}
You can have a common implementation of this:
type animal struct {
name string
age int
}
func (a *animal) Name() string { return a.name }
func (a *animal) Age() int { return a.age }
func (a animal) String() string { return fmt.Sprintf("%s(%d)", a.name, a.age) }
Your specific animal types:
type Dog struct {
animal // Embed animal (its methods and fields)
}
type Cat struct {
animal // Embed animal (its methods and fields)
}
You implement sort.Interface
on SortAnim
:
type SortAnim []Animal
func (c SortAnim) Len() int { return len(c) }
func (c SortAnim) Swap(i, j int) { c[i], c[j] = c[j], c[i] }
func (c SortAnim) Less(i, j int) bool { return c[i].Age() < c[j].Age() }
Using it:
dogs := SortAnim{&Dog{animal{"Max", 4}}, &Dog{animal{"Buddy", 3}}}
cats := SortAnim{&Cat{animal{"Bella", 4}}, &Cat{animal{"Kitty", 3}}}
fmt.Println(dogs)
sort.Sort(SortAnim(dogs))
fmt.Println(dogs)
fmt.Println(cats)
sort.Sort(SortAnim(cats))
fmt.Println(cats)
Output (Go Playground):
[Max(4) Buddy(3)]
[Buddy(3) Max(4)]
[Bella(4) Kitty(3)]
[Kitty(3) Bella(4)]
答案2
得分: 10
注意:根据提交记录ad26bb5所示,在Go 1.8(2017年第一季度)中,你无需实现Len()
、Swap()
和Less()
,因为问题16721已得到解决。只需要实现Less()
,其余部分由反射完成。
问题是:
> 1. 绝大多数sort.Interface使用切片
> 2. 必须定义一个新的顶级类型
> 3. Len
和Swap
方法总是相同的
> 4. 希望通过最小的性能损失使常见情况更简单
请参阅新的sort.go
:
// Slice sorts the provided slice given the provided less function.
//
// The sort is not guaranteed to be stable. For a stable sort, use
// SliceStable.
//
// The function panics if the provided interface is not a slice.
func Slice(slice interface{}, less func(i, j int) bool) {
rv := reflect.ValueOf(slice)
swap := reflect.Swapper(slice)
length := rv.Len()
quickSort_func(lessSwap{less, swap}, 0, length, maxDepth(length))
}
只要你有一个Less()
函数来比较两个实例并遵守一个接口,你就可以对任意数量的结构体进行排序。
Go 1.18泛型将添加另一种选项,如nwillc/genfuncs/container/sort.go
所示。
// Sort sorts a slice by the LessThan order.
func (s GSlice[T]) Sort(lessThan genfuncs.BiFunction[T, T, bool]) {
n := len(s)
s.quickSort(0, n, maxDepth(n), lessThan)
}
使用BiFunction
:
// BiFunction accepts two arguments and produces a result.
type BiFunction[T, U, R any] func(T, U) R
这只是一个示例,说明了如何实现通用排序:它不是官方示例(因为泛型在撰写本文时,即2022年第一季度,仍然非常新颖)。
英文:
Note: as illustrated in commit ad26bb5, in Go 1.8 (Q1 2017), you won't have to implement Len()
and Swap()
and Less()
since issue 16721 was resolved. Only Less()
is needed, the rest is done by reflection.
The problem was:
> 1. Vast majority of sort.Interface uses a slice
>2. Have to define a new top level type
>3. Len
and Swap
methods are always the same
>4. Want to make common case simpler with least hit to performance
See the new sort.go
:
// Slice sorts the provided slice given the provided less function.
//
// The sort is not guaranteed to be stable. For a stable sort, use
// SliceStable.
//
// The function panics if the provided interface is not a slice.
func Slice(slice interface{}, less func(i, j int) bool) {
rv := reflect.ValueOf(slice)
swap := reflect.Swapper(slice)
length := rv.Len()
quickSort_func(lessSwap{less, swap}, 0, length, maxDepth(length))
}
So as long as you have a Less()
function comparing two instances respecting an interface, you can sort any number of struct respecting said common interface.
Go 1.18 generics will add another option, as illustrated in nwillc/genfuncs/container/sort.go
.
// Sort sorts a slice by the LessThan order.
func (s GSlice[T]) Sort(lessThan genfuncs.BiFunction[T, T, bool]) {
n := len(s)
s.quickSort(0, n, maxDepth(n), lessThan)
}
With BiFunction
:
// BiFunction accepts two arguments and produces a result.
type BiFunction[T, U, R any] func(T, U) R
This is just an example illustrating how a generic sort could be implemented: it is not an official one (since generics are, at the ime of writing, Q1 2022, still very new).
答案3
得分: 0
这种情况下的最佳实践是按照twotwotwo的建议定义一个类型为Animal的结构体:
type Animal struct{
Species,Name string
Age int
}
如果猫和狗足够相似以至于可以按照相同的方式进行排序,那么它们也足够相似以至于可以使用相同的结构体。如果它们在某些方面有所不同,那么你应该为每种类型重新实现接口。
另一种方法是将[]*Cat
切片中的所有指针复制到一个大小相同的[]SortableByAge
切片中。如果你要对切片进行排序,那么排序的时间复杂度为O(n*log(n)),所以额外的O(n)不会影响性能。
第三种选择是,在极少数情况下,如果你有许多类型由于某种原因必须是不同的,但仍然具有非常简单的排序函数,你可以考虑使用go generate来自动生成它们。
英文:
The best practice for this case would be to define
type Animal struct{
Species,Name string
Age int
}
as suggested by twotwotwo. If cat and dog are similar enough to be sorted in the same way, they are also similar enough to be the same struct. If they are different in some way, then you should reimplement the interface for each type.
An alternative could be to copy all pointers from your []*Cat
slice into a []SortableByAge
slice of the same size. If you are going to sort the slice, that will take O(n*log(n)) so an extra O(n) shouldn't be a performance issue.
A third alternative, in the rare event that you have many types that for some reason have to be distinct but still have very simple sorting functions, you can look at autogenerating them with go generate.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论