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排序例子

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

2.2 go排序源码解析

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

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

但是在example的ByAge定义中,只看到了对三个方法的定义,没有对这个接口实现的声明。难道实现了这三个方法方法就自然而然的实现了这个Interface!这也也忒高级了吧!只要定义了这三个方法ByAge对象就满足了sort定义可排序的的集合要求,可以被作为sort.Sort方法的参数被使用的, sort.Sort(ByAge(people))这样被排序了。
那看下一个对象具备一个定义了上面有三种能力,如何进行排序。也就是sort(Interface)方法中,如何使用Interface的这三个方法来完成排序的功能。
首先看sort?方法的实现。

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

先找好中心点,然后两边递归调用分别作快排,熟悉的思路(熟悉的配方,熟悉的味道!JDB)。但显然这个quickSort是一个改良的快排,在每次执行快排时,如果发现depth已经递减为0,而元素还很多,说明待排序的数据分布不均衡,则使用堆排序,如果子集元素少于7个,则直接进行插入排序。
这个所谓的quickSort并不是我们数据结构中熟悉的经典快排?,看上去只是一个递归的代码框架,找了中间点,然后两边递归调。并没有涉及的具体的元素操作,没有我们期待中的两边元素比较,交换位置,检查点移动这样的操作。当然也就看不到我们期望的元素比较Less方法,也没有看到元素位置调整的Swap。为了了解下实际排序的操作怎么做的,需要再往下看一点。
堆排序方法heapSort 和插入排序方法insertionSort才是真正执行元素排序的方法,选择考察其中比较简单的insertionSort方法。

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

至此,结合这个例子,和一点源码理解了go中排序的使用方法。写自己的代码让待排序的集合实现以上三个方法Len、Less、Swap,调用sort.go的Sort方法,完成排序功能,顺利完成手里的feature开发。
故事到这里本该结束了,非常不受控制的,脑子里半秒钟就闪过这个例子在java中的样子,于是就有了后面的故事。。。

原创文章。为了维护文章的版本一致、最新、可追溯,转载请注明: 转载自idouba

本文链接地址: Sort源码实现比较Go&Java语言风格(1)


, , , ,

Trackbacks/Pingbacks

  1. Sort源码实现比较Go&Java语言风格(3) | idouba - 2017年1月10日

    […] 前面两部分分别描述了Go和java两种语言对sort的使用方式和源码实现。作为go初学者,最想做的是通过例子和源码来对新的语言有个理解。这部分就结合自己的理解整理下,可以看到,是非常主观。 4 语言语法比较 可以看到,两种语言的思路基本上是一样的,用户必须定义比较规则。在排序过程中都要考察集合长度,使用用户定义的比较规则,然后调整元素位置来达到排序的效果,对应go的interface要求的三个方法。但是还是有挺多不同。 首先从使用方式上看,go的规则(通过方法来体现)定义在集合上,并且定义了三个方法,分别获取集合的状况,元素比较的规则,元素位置操作的方法;而java的规则定义在元素上,用户只用一个元素比较的规则compareTo?就够了。看起来java要求用户定义少,因为其封装的多,这也是其一贯的风格。对用户要似乎更友好一点。比较而言go更直接,简单。留给程序员能干预的更多一点。但还是觉得Len和Swap方法留给用户定义的意义不是很大,就像源码中自带的好几个例子,Len除了返回集合长度, Swap(i,j)除了{ a[i], a[j] = a[j], a[i] },真想不好我们还能赋予它其他的使用方法。 […]

发表评论