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

gk7wooem  于 12个月前  发布在  Go
关注(0)|答案(4)|浏览(97)

在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

dogs := make([]*Dogs, 0 , 1)
//add dogs here
sort.Sort(SortAnimal(dogs))


上面是不可能的。
所以我想知道这种情况下的最佳做法是什么,
有没有其他技术可以减少我一次又一次错过的类似结构的sort.Interface实现的需要?
编辑:我意识到我的例子很糟糕:(
在真实的情况下,这两个结构是非常不同的,它们之间唯一的共同点是我希望通过一个共同的数值对它们进行排序。
一个更好的例子是:

type Laptop {//...}
type Pizza {//...}


这两个结构体唯一的共同点是我希望按价格对它们的一个切片进行排序(啊......在示例中不应该使用Pizza)。
因此,将它们组合到一个公共结构中并不适用于很多情况。但我们将研究go generate。

9rbhqvlz

9rbhqvlz1#

本案例

在这种情况下,你不应该使用两个不同的类型,因为它们是相同的,只需要使用一个公共的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  // Embed animal (its methods and fields)
}

type Cat struct {
    animal // Embed animal (its methods and fields)
}


您可以在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)]

dgsult0t

dgsult0t2#

注意事项:如commit ad26bb5所示,在Go 1.8(2017年第一季度)中,你不必实现Len()Swap()Less(),因为issue 16721已经解析。只需要Less(),其余的都是通过反射完成的。
问题是:
1.绝大多数排序。接口使用切片
1.必须定义一个新的顶级类型

  1. LenSwap方法始终相同
    1.希望简化常见情况,同时对性能的影响最小
    查看新的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年第一季度,仍然非常新)。

jckbn6z7

jckbn6z73#

这种情况下的最佳做法是定义

type Animal struct{
    Species,Name string
    Age int
}

字符串
正如twotwetwo所建议的那样。如果cat和dog足够相似,可以以相同的方式进行排序,那么它们也足够相似,可以成为同一个结构。如果它们在某些方面不同,那么您应该为每个类型重新实现接口。
另一种方法是将[]*Cat切片中的所有指针复制到相同大小的[]SortableByAge切片中。如果要对切片进行排序,则需要O(n*log(n)),因此额外的O(n)不应该是性能问题。
第三种选择是,在极少数情况下,您有许多类型,由于某种原因必须是不同的,但仍然具有非常简单的排序功能,您可以使用go generate自动生成它们。

kh212irz

kh212irz4#

在Go 1.21中,他们添加了一个新的包slices。它包含处理泛型类型切片的函数。
slices.SortFunc()可能会为你简化一些事情,它比sort.Sort()更快,官方推荐。

package main

import (
    "cmp"
    "fmt"
    "slices"
)

type Dog struct {
    Name  string
    Breed string
    Age   int
}

type Cat struct {
    Name         string
    FavoriteFood string
    Age          int
}

func CmpDog(a, b Dog) int {
    return cmp.Compare(a.Age, b.Age)
}

func CmpCat(a, b Cat) int {
    return cmp.Compare(a.Age, b.Age)
}

func main() {
    dogs := []Dog{
        {"Candice", "Poodle", 13},
        {"Alice", "Dalmation", 4},
        {"Bob", "Labrador", 8},
    }

    cats := []Cat{
        {"Betty", "Fish", 108},
        {"Brittany", "Fish", 99},
        {"Karen", "Fish", 81},
    }

    slices.SortFunc(dogs, CmpDog)
    slices.SortFunc(cats, CmpCat)
}

字符串
请注意,slices.SortFunc()并不稳定。为了稳定排序,可以使用slices.SortStableFunc(),它与slices.SortFunc()具有相同的签名。

相关问题