爱豆吧!

idouba@beta.

Sort源码实现比较Go&Java语言风格(1)

1 前言

刚开始拥抱go,非常新鲜!才使用没多久,属于没有经验,有一点感受的那种。具体也说不了特别清楚,就是觉得:简单,直接,灵活,方便。作为一个 java 重度中毒(ZHANGDU*2)用户,过程中还是习惯对照着思考,至少在这个阶段。也好,发现对照着想,似乎更容易融会贯通。 对资深的go程序员来说,应该都是非常基础基本的问题,但也挡不住咱这个小白要发表下感想。

第一篇文章首先结合最近做一个小feature时用到go中元素排序的功能,顺便了解下两种语言中排序功能的使用方式,各自源码中对排序功能的实现。当然最主要的是在这个过程中,作为go初学者对语言的体会和理解。

2 Go排序源码解析

现在一般不太会自己写排序算法的实现了,就去搜go的package, 如愿找到了package sort?,和猜想的接口差不多,有一个func Sort(data Interface) 。只要把待排序的对象传到一个sort方法中就可以了。

只是对这个Interface?对象还有点疑惑,这个Interface是个啥东西呀?带着这个疑问,瞄见了package前面这个这个example(裁剪了部分非关键代码)。

2.1 go排序例子

type Person struct {
Name string
Age int
}
// ByAge implements sort.Interface for []Person based on the Age field.
type ByAge []Person
func (a ByAge) Len() int { return len(a) }
func (a ByAge) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
func (a ByAge) Less(i, j int) bool { return a[i].Age < a[j].Age }
func main() {
sort.Sort(ByAge(people))
}type Person struct {
Name string
Age int
}
// ByAge implements sort.Interface for []Person based on the Age field.
type ByAge []Person
func (a ByAge) Len() int { return len(a) }
func (a ByAge) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
func (a ByAge) Less(i, j int) bool { return a[i].Age < a[j].Age }
func main() {
sort.Sort(ByAge(people))
}

这个例子看上去挺简单,对一个Person的对象数组ByAge,调用sort.Sort(ByAge(people))按照Age属性进行排序。在关注sort方法之前,首先留意到集合上定义了三个方法:Len、Swap、Less。为什么要在数组上要定义这三个方法,字面意思有一点点暗示我们这三个子操作是与排序有关,尤其是Less方法,与java中熟知的compareTo(T)从字面上理解是何其相似。

2.2 go排序源码解析

Interface是何物,和这三个方法之间有什么关系,带着疑问去看下sort.go的源码。果然在文件的顶头就定义了这样一个interface(只是interface的名字叫做Interface着实刚才有点误导人了):

/ A type, typically a collection, that satisfies sort.Interface can be
// sorted by the routines in this package. The methods require that the
// elements of the collection be enumerated by an integer index.
type Interface interface {
// Len is the number of elements in the collection.
Len() int
// Less reports whether the element with
// index i should sort before the element with index j.
Less(i, j int) bool
// Swap swaps the elements with indexes i and j.
Swap(i, j int)
}

注释也明确的告诉我们,只有实现了这个interface的集合才可以被排序。哦,说错了,人家注释中说的不是implements,而是satisfy。似乎感觉到了的go的Interface和java的Interface的一丝丝淡淡的不同。

但是在example的ByAge定义中,只看到了对三个方法的定义,没有对这个接口实现的声明。难道实现了这三个方法方法就自然而然的实现了这个Interface!这也也忒高级了吧!只要定义了这三个方法ByAge对象就满足了sort定义可排序的的集合要求,可以被作为sort.Sort方法的参数被使用的, sort.Sort(ByAge(people))这样被排序了。

那看下一个对象具备一个定义了上面有三种能力,如何进行排序。也就是sort(Interface)方法中,如何使用Interface的这三个方法来完成排序的功能。

首先看sort方法的实现。

// Sort sorts data.
// It makes one call to data.Len to determine n, and O(n*log(n)) calls to
// data.Less and data.Swap. The sort is not guaranteed to be stable.
func Sort(data Interface) {
// Switch to heapsort if depth of 2*ceil(lg(n+1)) is reached.
n := data.Len()
maxDepth := 0
for i := n; i > 0; i >>= 1 {
maxDepth++
}
maxDepth *= 2
quickSort(data, 0, n, maxDepth)
}

这个方法里,只是用到了取接口定义的Len的方法,来获取集合元素个数,根据元素个数估算下如果是被平衡分布的树的深度。该深度作为一个参数传给quikSort方法用,进行真正的排序。看到到这里知道go的sort用的是快排!然后看下这个快排到底是怎么做的,虽然大致都知道快排的算法是怎么回事,还是非常想知道go里面是怎么实现的。

func quickSort(data Interface, a, b, maxDepth int) {
for b-a > 7 {
if maxDepth == 0 {
heapSort(data, a, b)
return
}
maxDepth--
mlo, mhi := doPivot(data, a, b)
// Avoiding recursion on the larger subproblem guarantees
// a stack depth of at most lg(b-a).
if mlo-a < b-mhi {
quickSort(data, a, mlo, maxDepth)
a = mhi // i.e., quickSort(data, mhi, b)
} else {
quickSort(data, mhi, b, maxDepth)
b = mlo // i.e., quickSort(data, a, mlo)
}
}
if b-a > 1 {
insertionSort(data, a, b)
}
}

先找好中心点,然后两边递归调用分别作快排,熟悉的思路(熟悉的配方,熟悉的味道!JDB)。但显然这个quickSort是一个改良的快排,在每次执行快排时,如果发现depth已经递减为0,而元素还很多,说明待排序的数据分布不均衡,则使用堆排序,如果子集元素少于7个,则直接进行插入排序。

这个所谓的quickSort并不是我们数据结构中熟悉的经典快排,看上去只是一个递归的代码框架,找了中间点,然后两边递归调。并没有涉及的具体的元素操作,没有我们期待中的两边元素比较,交换位置,检查点移动这样的操作。当然也就看不到我们期望的元素比较Less方法,也没有看到元素位置调整的Swap。为了了解下实际排序的操作怎么做的,需要再往下看一点。

堆排序方法heapSort 和插入排序方法insertionSort才是真正执行元素排序的方法,选择考察其中比较简单的insertionSort方法。

// Insertion sort
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)
}
}
}

终于,我们期待的三个重要方法都看到了。Len方法负责获取集合状态(除了常规的集合长度外,这里还有根据集合长度算出的一个深度),这个集合即可以是我们原始传给Sort方法的那个集合,其实也是中间每次递归的那个小集合。Less()是负责比较元素大小的规则。而Swap方法负责实现元素位置的置换,即执行排序的动作。

至此,结合这个例子,和一点源码理解了go中排序的使用方法。写自己的代码让待排序的集合实现以上三个方法Len、Less、Swap,调用sort.go的Sort方法,完成排序功能,顺利完成手里的feature开发。

故事到这里本该结束了,非常不受控制的,脑子里半秒钟就闪过这个例子在java中的样子,于是就有了后面的故事。。。