Go语言圣经 - 第7章 接口 - 7.6 sort.Interface接口

第7章 接口

接口类型是对其它类型行为的抽象和概括.接口类型不会和特定的实现细节绑定在一起,这种抽象的方式能让我们的函数更加的灵活和更具有适应能力

Go语言的接口比较特殊,因为它是满足隐式实现的。也就是说,我们无需给具体类型定义所有满足足的接口类型,只需要让类型拥有一些简单必要的方法。这样我们新建一个接口类型,满足具体类型,并且我们不需要更改这些类型的定义。当我们使用的类型来自于不受我们控制的包时,这种机制比较有用

7.6 sort.Interface 接口

排序和字符串格式化是我们经常要使用的操作

Go语言中的sort包内置了一些函数能够实现对任何序列进行排序,它有点特别,因为sort.Sort函数不会对任何具体的序列和它的元素做任何假设,它使用了一个接口类型sort.Interface来指定了通用的排序算法和可能需要参与排序的序列类型之间的约定

上述接口的实现由序列的具体表示和它希望排序的元素决定,序列的表示通常是一个切片

一个内置的排序算法要知道三个要素:序列长度,两个元素比较结果,两个(元素的交换方式

package sort

type Interface interface {
	Len() int
	Less(i,j int)bool //i,j are indices of sequence elements
	Swap(i,j int)
}

为了对序列进行排序,我们还得定义实现了上述方法的具体类型。让我们那字符串切片作为例子

type StringSlice []string

func (p StringSlice) Len() int         {return len(p)}
func (p StringSlice) Less(i,j int)bool {return p[i]<p[j]}
func (p StringSlice) Swap(i,j int)     {p[i],p[j]= p[j],p[i]}

现在我们一个切片转换为一个StringSlice类型来进行排序:

func Sort(data Interface) {
    n := data.Len()
    quickSort(data, 0, n, maxDepth(n))
}

sort.Sort(StringSlice(names))

好的,现在排序代码已经构建好了,让我们实际使用一下。我们来对一个表格中的音乐播放列表进行排序,每个元素都不是它的本身而是指针,这样会更加快捷

type Track struct {
	Title  string
	Artist string
	Album  string
	Year   int
	Length time.Duration
}

var tracks = []*Track{
	{"Go", "Delilah", "From the Roots Up", 2012, length("3m38s")},
	{"Go", "Moby", "Moby", 1992, length("3m37s")},
	{"Go Ahead", "Alicia Keys", "As I Am", 2007, length("4m36s")},
	{"Read 2 Go", "Martin Solveig", "Smash", 2011, length("4m24s")},
}

func length(s string) time.Duration {
	d, err := time.ParseDuration(s)
	if err != nil {
		panic(s)
	}
	return d
}

我们使用printTracks函数将播放列表打印成一个表格。一个图形化的展示可能更好,我们使用text/tabwriter包来生成一个列整齐对齐和隔开的表格,如下:

func printTracks(tracks []*Track) {
	const format = "%v\t%v\t%v\t%v\t%v\t%v\t\n"
	tw := new(tabwriter.Writer).Init(os.Stdout, 0, 8, 2, ' ', 0)
	fmt.Fprintf(tw, format, "Title", "Artist", "Album", "Year", "Length")
	fmt.Fprintf(tw, format, "-----", "-----", "-----", "-----", "----", "------")
	for _, t := range tracks {
		fmt.Fprintf(tw, format, t.Title, t.Artist, t.Album, t.Year, t.Length)
	}
	tw.Flush() //calculate column widths and print table
}

注意:*tabwriter.Writer是满足io.Writer接口的,它会收集每一篇写向它的数据:它的flush方法会格式化整个表格并且将它写向os.Stdout(标准输出)

为了能按照Artist字段对播放列表进行排序尻,我们会像对StringSlice 那样定义一个新的带有必须的Len,Less和Swap方法的切片类型

type byArtist []*Track

func (x byArtist) Len() int           { return len(x) }
func (x byArtist) Less(i, j int) bool { return x[i].Artist < x[j].Artist }
func (x byArtist) Swap(i, j int)      { x[i], x[j] = x[j], x[i] }

为了调用排序程序,我们必须先将Tracks转换为新的byArtist类型,它定义了具体排序,并且我们可以继续调用排序函数

func main() {
	sort.Sort(byArtist(tracks))
	printTracks(tracks)
	sort.Sort(sort.Reverse(byArtist(tracks)))
	printTracks(tracks)
}
Title      Artist          Album              Year  Length  
-----      -----           -----              ----  ------  
Go Ahead   Alicia Keys     As I Am            2007  4m36s   
Go         Delilah         From the Roots Up  2012  3m38s   
Read 2 Go  Martin Solveig  Smash              2011  4m24s   
Go         Moby            Moby               1992  3m37s   
Title      Artist          Album              Year  Length  
-----      -----           -----              ----  ------  
Go         Moby            Moby               1992  3m37s   
Read 2 Go  Martin Solveig  Smash              2011  4m24s   
Go         Delilah         From the Roots Up  2012  3m38s   
Go Ahead   Alicia Keys     As I Am            2007  4m36s   

在上面使用了sort.Reverse函数,我们再来详细看一下

func Reverse(data Interface) Interface {
	return &reverse{data}
}	

func (r reverse) Less(i, j int) bool {
	return r.Interface.Less(j, i)
}

type reverse struct {
	// This embedded Interface permits Reverse to use the methods of
	// another Interface implementation.
	Interface
}

reverse的另外两个方法Len和Swap隐式的由原有内嵌的sort.Interface提供,因为reverse是一个不公开的类型,所以导出函数Reverse返回一个包含原有sort.Interface值的reverse实例

我们来重新定定义一个新的类型byYear

type byYear []*Track

func (x byYear) Len() int           { return len(x) }
func (x byYear) Less(i, j int) bool { return x[i].Year < x[j].Year }
func (x byYear) Swap(i, j int)      { x[i], x[j] = x[j], x[i] }
func main() {
	sort.Sort(byYear(tracks))
	printTracks(tracks)
}

打印出结果,非常完美啊

Title      Artist          Album              Year  Length  
-----      -----           -----              ----  ------  
Go         Moby            Moby               1992  3m37s   
Go Ahead   Alicia Keys     As I Am            2007  4m36s   
Read 2 Go  Martin Solveig  Smash              2011  4m24s   
Go         Delilah         From the Roots Up  2012  3m38s   

我们在来继续看一个嵌套排序(多条件),并打印结果

type customSort struct {
	t    []*Track
	less func(x, y *Track) bool
}

func (x customSort) Len() int           { return len(x.t) }
func (x customSort) Less(i, j int) bool { return x.less(x.t[i], x.t[j]) }
func (x customSort) Swap(i, j int)      { x.t[i], x.t[j] = x.t[j], x.t[i] }

func main() {
	sort.Sort(customSort{tracks, func(x, y *Track) bool {
		if x.Title != y.Title {
			return x.Title < y.Title
		}
		if x.Year != y.Year {
			return x.Year < y.Year
		}
		if x.Length != y.Length {
			return x.Length < y.Length
		}
		return false
	}})

	printTracks(tracks)
}
Title      Artist          Album              Year  Length  
-----      -----           -----              ----  ------  
Go         Moby            Moby               1992  3m37s   
Go         Delilah         From the Roots Up  2012  3m38s   
Go Ahead   Alicia Keys     As I Am            2007  4m36s   
Read 2 Go  Martin Solveig  Smash              2011  4m24s   

如我们所见,要实现这样的排序,那意味着时间复杂度是O(n logn),检查一个序列是否已经有序需要至少n-1次比较,sort包中的IsSort函数帮我们做了这样的检查。像sort.Sort一样,它也使用sort.Interface 对这个序列和它的排序函数进行抽象,但是它从不会调用Swap方法:如下是代码示范:

values := []int{3, 1, 4, 1}
	fmt.Println(sort.IntsAreSorted(values))
	sort.Ints(values)
	fmt.Println(values)
	fmt.Println(sort.IntsAreSorted(values))
	sort.Sort(sort.Reverse(sort.IntSlice(values)))
	fmt.Println(values)
	fmt.Println(sort.IntsAreSorted(values))
false
[1 1 3 4]
true
[4 3 1 1]
false

为了使用方便,sort包为[]int \ []string[]float64 的正常排序提供了特定的版本和函数类型,对于其他类型,例如[]int64\ 或者[]uint,尽管路径很简单,但是这是需要我们手动实现的

上一篇:Java中的注解到底是怎么一回事?,java基础入门题库


下一篇:Python----递归函数