有句話很有趣：Stay hungry, stay foolish. 個(gè)人根據(jù)對(duì)這句話的理解 以一個(gè)有強(qiáng)烈求知欲的小白的角度，用提問(wèn)解答的方式組織全文。以此發(fā)現(xiàn)自己知識(shí)的不足并學(xué)習(xí)新的知識(shí)。
問(wèn)題目錄
- 包方面
- sort包里包括哪些文件
- sort.go如何使用，有什么需要注意的地方
- example_*_test.go格式的文件是做什么用的
- slice.go如何使用，有什么需要注意的地方
- search.go如何使用，有什么需要注意的地方
- genzfunc.go是什么，如何使用
- 算法方面
- 涉及到哪些算法
- 算法的比較
- 算法的穩(wěn)定性以及穩(wěn)定性的重要性
- Go語(yǔ)言方面
genzfunc.go是什么，如何使用- Go通過(guò)嵌套實(shí)現(xiàn)繼承
解答
sort包里包括哪些文件
如下所示
├── example_interface_test.go
├── example_keys_test.go
├── example_multi_test.go
├── example_search_test.go
├── example_test.go
├── example_wrapper_test.go
├── export_test.go
├── genzfunc.go
├── search.go
├── search_test.go
├── slice.go
├── sort.go
├── sort_test.go
└── zfuncversion.go
sort.go如何使用，有什么需要注意的地方
在 sort.go文件中，排序算法有: 插入排序(insertionSort)、堆排序(heapSort)，快速排序(quickSort)、希爾排序(ShellSort)、歸并排序(SymMerge)。 這些函數(shù)都是以小寫(xiě)字母開(kāi)頭，意味著他們對(duì)外是不可見(jiàn)的(letter case set visibility)。其中，歸并排序用于 Stable函數(shù)，其余算法用于 Sort函數(shù)。
Sort是基于interface實(shí)現(xiàn)的，新建數(shù)據(jù)類(lèi)型只要實(shí)現(xiàn) sort.Interface中的三種方法，就能使用Sort方法。下面看下接口中的方法的功能。
type Interface interface {
// Len返回序列中的元素?cái)?shù)量
Len() int
// 若i < j,則Less返回true
Less(i, j int) bool
// Swap 交換下標(biāo)為i和j的元素
Swap(i, j int)
}
在sort中g(shù)o支持[]Int切片IntSlice、[]Float64切片Float64Slice和[]string切片StringSlice這三種類(lèi)型。以IntSlice為例，可供我們使用的方法主要有：
Sort() 對(duì)序列進(jìn)行排序
Reverse() 結(jié)合Sort對(duì)序列進(jìn)行逆序排序
IsSorted() 判斷序列是否有序
Stable() 對(duì)序列進(jìn)行排序，同時(shí)保證值相等的元素排序后和原始順序相同(即使用穩(wěn)定的算法)。使用Stable需實(shí)現(xiàn)
sort.Interface中的所有方法
下面來(lái)看一些具體的例子:
package main
import "fmt"
import "sort"
func main() {
strs := []string{"c", "a", "b"} // 未排序
sort.Strings(strs)
fmt.Println("Strings:", strs)
ints := []int{7, 2, 4} //未排序
sort.Ints(ints)
fmt.Println("Ints: ", ints)
s := sort.IntsAreSorted(ints)
fmt.Println("Sorted: ", s)
//Output: Strings: [a b c]
//Ints: [2 4 7]
//Sorted: true
}
example*test.go格式的文件是做什么用的
在sort包中，有很多 example_*_test.go格式的文件，這些文件中的以 Example開(kāi)頭的函數(shù)講解了Sort包各種方法的使用方法。這是官方提供的使用案例，強(qiáng)烈建議讀者看看這幾份代碼。下面簡(jiǎn)單說(shuō)明一下這些代碼的用途。
├── example_interface_test.go //基礎(chǔ)用法，對(duì)一個(gè)[]struct進(jìn)行排序
├── example_keys_test.go //這個(gè)例子蠻有趣的，對(duì)struct中的元素可進(jìn)行可編程化的排序(即通過(guò)struct中的不同元素進(jìn)行排序)
├── example_multi_test.go //這個(gè)例子蠻有趣的，演示了用struct中不同的元素進(jìn)行排序的方法。
├── example_search_test.go //升序和降序的序列如何使用Search()
├── example_test.go //sort.go和slice的使用方法，列舉了上述過(guò)的三種數(shù)據(jù)類(lèi)型的使用方法，Reverse()和Slice()的使用方法。
├── example_wrapper_test.go //通過(guò)srtuct嵌套[]struct達(dá)到利用struct中不同元素進(jìn)行排序的目的。
Go中的map是未經(jīng)排序的k-v對(duì)，如果需要一個(gè)排序后的map，可以開(kāi)一個(gè)key/value的序列，對(duì)序列進(jìn)行排序，再遍歷map。
m := map[string]int{"Alice": 2, "Cecil": 1, "Bob": 3}
keys := make([]string, 0, len(m))
for k := range m {
keys = append(keys, k)
}
sort.Strings(keys)
for _, k := range keys {
fmt.Println(k, m[k])
}
// Output:
// Alice 2
// Bob 3
// Cecil 1
注意
Float64Slice
在Float64Slice的Less方法中，為避免依賴math.IsNaN,在包中寫(xiě)了一個(gè)功能一樣的IsNaN
// isNaN is a copy of math.IsNaN to avoid a dependency on the math package.
func isNaN(f float64) bool {
return f != f
}
Reverse
實(shí)現(xiàn)Reverse比較有趣，來(lái)看下源碼
type reverse struct {
// 在reverse結(jié)構(gòu)體中內(nèi)嵌Interface接口，使Reverse能使用Interface接口實(shí)現(xiàn)的方法
Interface
}
//Less()把Interface接口的Less()的參數(shù)翻轉(zhuǎn)，從而達(dá)到反轉(zhuǎn)的目的
func (r reverse) Less(i, j int) bool {
return r.Interface.Less(j, i)
}
// Reverse返回data的反轉(zhuǎn)序列
func Reverse(data Interface) Interface {
return &reverse{data}
}
slice.go如何使用，有什么需要注意的地方
思考一下可以想到，在 sort.Interface這個(gè)接口中， Len()和 Swap()方法一般是不需要改動(dòng)的，只有 Less()方法需要指出具體的元素比較項(xiàng)。若每寫(xiě)一個(gè)新類(lèi)型就需要實(shí)現(xiàn)三種方法比較麻煩， slice.go解決了這個(gè)問(wèn)題，它里面的方法只需提供less函數(shù)即可。
type Interface interface {
Len() int
Less(i, j int) bool
Swap(i, j int)
}
你可能要問(wèn)了，不提供 Len()和 Swap()并沒(méi)有實(shí)現(xiàn) sort.Interface接口啊。帶著疑問(wèn)，來(lái)看下Slice()的源碼。
func Slice(slice interface{}, less func(i, j int) bool) {
rv := reflect.ValueOf(slice)
swap := reflect.Swapper(slice) //reflect.Swapper根據(jù)slice類(lèi)型返回具體的swap func。
length := rv.Len()
quickSort_func(lessSwap{less, swap}, 0, length, maxDepth(length))
}
可以看到，Slice通過(guò)反射獲得Len()和Swap()。函數(shù)中的lessSwap結(jié)構(gòu)如下
// lessSwap有Less和Swap方法，用于自動(dòng)生成且優(yōu)化后的的sort.go的變種zfuncversion.go
type lessSwap struct {
Less func(i, j int) bool
Swap func(i, j int)
}
注意
slice.go里面的方法提供的interface類(lèi)型必須是切片類(lèi)型，否則會(huì)panic。
search.go如何使用，有什么需要注意的地方
Go中的Search函數(shù)是用二分查找實(shí)現(xiàn)的，比較簡(jiǎn)單。example_search_test.go的的使用方法如下。
func ExampleSearch() {
a := []int{1, 3, 6, 10, 15, 21, 28, 36, 45, 55}
x := 6
i := sort.Search(len(a), func(i int) bool { return a[i] >= x })
if i < len(a) && a[i] == x {
fmt.Printf("found %d at index %d in %v\n", x, i, a)
} else {
fmt.Printf("%d not found in %v\n", x, a)
}
// Output:
// found 6 at index 2 in [1 3 6 10 15 21 28 36 45 55]
}
search.go中為上述三種數(shù)據(jù)類(lèi)型([]Int切片( IntSlice)、[]Float64切片( Float64Slice)和[]string切片(StringSlice))分別提供了函數(shù)。
func SearchInts(a []int, x int) int {
return Search(len(a), func(i int) bool { return a[i] >= x })
}
我們可以借鑒下源碼中求中點(diǎn)的方式
h := int(uint(i+j) >> 1) // avoid overflow when computing h
注意
Search()函數(shù)不能單獨(dú)使用，需要在其下方配合判斷條件組合使用。search.go函數(shù)中傳入序列需要是排序過(guò)的，否則會(huì)出現(xiàn)奇怪的現(xiàn)象(因?yàn)?code>Search函數(shù)是通過(guò)序列下標(biāo)進(jìn)行搜索的)。由于是通過(guò)序列下標(biāo)進(jìn)行搜索的，在搜索序列中不存在的元素時(shí)會(huì)出現(xiàn)下面的現(xiàn)象(筆者之前是寫(xiě)Python的，不太喜歡這種設(shè)計(jì):If there is no such index, Search returns n)。
func ExampleWrongSearch() {
a := []int{1, 2, 3, 4, 5, 6}
fmt.Println(sort.SearchInts(a, 78))
fmt.Println(sort.SearchInts(a, -1))
// Output:
// 6
// 0
}
// Search()不能單獨(dú)使用，正確的寫(xiě)法應(yīng)該是這樣。
func ExampleSearch() {
a := []int{1, 3, 6, 10, 15, 21, 28, 36, 45, 55}
x := 6
i := sort.Search(len(a), func(i int) bool { return a[i] >= x })
if i < len(a) && a[i] == x { // 需進(jìn)行判斷，看是否找到了元素
fmt.Printf("found %d at index %d in %v\n", x, i, a)
} else {
fmt.Printf("%d not found in %v\n", x, a)
}
// Output:
// found 6 at index 2 in [1 3 6 10 15 21 28 36 45 55]
}
genzfunc.go是什么，如何使用
genzfunc.go通過(guò)運(yùn)行go generate命令生成zfuncversion.go。簡(jiǎn)單來(lái)說(shuō)，就是生成代碼的。它主要是給開(kāi)發(fā)者在寫(xiě)Go包的時(shí)候用的。在生成的zfuncversion.go中，原sort.go中的若干內(nèi)部函數(shù)被改寫(xiě)，以insertionSort為例，以下是生成的代碼被改動(dòng)的情況。
// sort.go中的insertSort
func insertionSort(data Interface, a, b int) {
for i := a + 1; i < b; i++ {
for j := i; j > a && data.Less(j, j-1); j-- {
data.Swap(j, j-1)
}
}
}
//zfuncversion.go中的insertionSort_func,可以看到，其中函數(shù)名加了_func后綴，data類(lèi)型由Interface變?yōu)閘essSwap
func insertionSort_func(data lessSwap, a, b int) {
for i := a + 1; i < b; i++ {
for j := i; j > a && data.Less(j, j-1); j-- {
data.Swap(j, j-1)
}
}
}
sort庫(kù)涉及到哪些算法
排序算法用到插入排序(insertionSort)、堆排序(heapSort)、快速排序(quickSort)、希爾排序(ShellSort)和歸并排序(SymMerge)；搜索算法用到二分查找算法。
在Sort()函數(shù)中，選擇算法的判斷條件如圖所示。
Sort()函數(shù)不能保證穩(wěn)定性，Go用歸并排序提供了一個(gè)穩(wěn)定的排序函數(shù)Stable()。
排序算法的比較
快排、堆排序和歸并排序
| 算法 | 時(shí)間復(fù)雜度 | 穩(wěn)定性 | 原地排序 |
|---|---|---|---|
| 快排 | 平均O(nlogn) 最好O(nlogn) 最壞O(n*n) | 不穩(wěn)定 | 是 |
| 堆排序 | 平均O(nlogn) 最好O(nlogn) 最壞O(nlogn) | 不穩(wěn)定 | 是 |
| 歸并排序 | 平均O(nlogn) 最好O(nlogn) 最壞O(nlogn) | 穩(wěn)定 | 否 |
注意：這里列舉的都是基本的排序算法。對(duì)于排序算法而言，算法是否穩(wěn)定需要對(duì)算法進(jìn)行具體的分析，不能一概而論。
在sort源碼中，在切片數(shù)量大于12時(shí)，用到快排和堆排序這兩種排序算法，當(dāng)maxDepth為0時(shí)，會(huì)從快排轉(zhuǎn)換為使用堆排序。作者根據(jù)這篇論文寫(xiě)算法的。Engineering a Sort Function following Bentley and McIlroy SP&E November 1993。 其中maxDepth的計(jì)算函數(shù)如下：
func maxDepth(n int) int {
var depth int
for i := n; i > 0; i >>= 1 {
depth++
}
return depth * 2 //return 2*向上取整(lg(n+1))
}
sort源碼中主要使用快排進(jìn)行排序的。也許讀者有疑問(wèn)，歸并排序的時(shí)間復(fù)雜度穩(wěn)定，同時(shí)也是一種穩(wěn)定的排序的算法，為何不使用這種排序算法呢。原因是歸并排序不是原地排序算法，他需要借助額外空間進(jìn)行歸并，空間復(fù)雜度較高，為O(n)。而對(duì)于堆排序，要使用首先需要建堆然后排序。源碼中的堆排序首先對(duì)數(shù)組中(hi - 1) / 2個(gè)節(jié)點(diǎn)依次堆化，再依次pop堆頂元素，完成排序。相較于快排，堆排序需要建堆這個(gè)過(guò)程，這個(gè)過(guò)程會(huì)打亂原來(lái)的數(shù)據(jù)順序，可能會(huì)將數(shù)據(jù)的有序度降低，即經(jīng)過(guò)建堆之后，數(shù)據(jù)反而變得更無(wú)序了。
穩(wěn)定性的用途
首先需明確穩(wěn)定性的定義：穩(wěn)定性指待排序的序列中，值相等的元素排序后和原始序列順序相同。在大學(xué)教學(xué)過(guò)程中，課上老師用來(lái)舉例的例子一般是一個(gè)int序列，在這個(gè)情境中難以看出穩(wěn)定性的實(shí)際作用。但實(shí)際開(kāi)發(fā)過(guò)程中，當(dāng)對(duì)一個(gè)有多個(gè)有效元素的[]struct進(jìn)行排序時(shí)，穩(wěn)定性的作用就發(fā)揮出來(lái)了：先用struct中某個(gè)元素進(jìn)行排序，再對(duì)struct中的另一個(gè)元素進(jìn)行排序，第一個(gè)元素排序的結(jié)果可以作為第二個(gè)元素排序的輸入。
舉個(gè)例子，現(xiàn)在需要對(duì)學(xué)生的成績(jī)數(shù)據(jù)進(jìn)行排序。希望按照總分從大到小排序，總分相同的學(xué)生，按照英語(yǔ)成績(jī)從大到小排序。有了穩(wěn)定的排序算法，可以先按照英語(yǔ)成績(jī)從大到小排序，再按照總分進(jìn)行排序。
Go語(yǔ)言方面
Go通過(guò)嵌套實(shí)現(xiàn)繼承
在sort包中很多地方都通過(guò)struct和interface的嵌套去實(shí)現(xiàn)繼承。從而繼承內(nèi)部嵌套結(jié)構(gòu)的方法和屬性。建議讀者多看看嵌套的相關(guān)代碼。舉例:
Reverse()的實(shí)現(xiàn)
sort/example_wrapper_test.go的實(shí)現(xiàn)
