如何避免为类似的 Golang 结构体重新实现 sort.Interface 接口?

huangapple go评论88阅读模式
英文:

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() &lt; 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 如何避免为类似的 Golang 结构体重新实现 sort.Interface 接口?

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(&quot;%s(%d)&quot;, 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 &lt; c[j].Age }

func main() {
	dogs := []*Animal{&amp;Animal{&quot;Max&quot;, 4}, &amp;Animal{&quot;Buddy&quot;, 3}}
	cats := []*Animal{&amp;Animal{&quot;Bella&quot;, 4}, &amp;Animal{&quot;Kitty&quot;, 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(&quot;%s(%d)&quot;, 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() &lt; c[j].Age() }

Using it:

dogs := SortAnim{&amp;Dog{animal{&quot;Max&quot;, 4}}, &amp;Dog{animal{&quot;Buddy&quot;, 3}}}
cats := SortAnim{&amp;Cat{animal{&quot;Bella&quot;, 4}}, &amp;Cat{animal{&quot;Kitty&quot;, 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. LenSwap方法总是相同的
> 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.

huangapple
  • 本文由 发表于 2015年5月20日 05:39:03
  • 转载请务必保留本文链接:https://go.coder-hub.com/30336616.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定