Go语言 排序与搜索切片

Python027

Go语言 排序与搜索切片,第1张

Go语言标准库中提供了sort包对整型,浮点型,字符串型切片进行排序,检查一个切片是否排好序,使用二分法搜索函数在一个有序切片中搜索一个元素等功能。

关于sort包内的函数说明与使用,请查看 https://godoc.org/sort

在这里简单讲几个sort包中常用的函数

在Go语言中,对字符串的排序都是按照字节排序,也就是说在对字符串排序时是区分大小写的。

二分搜索算法

Go语言中提供了一个使用二分搜索算法的sort.Search(size,fn)方法:每次只需要比较㏒₂n个元素,其中n为切片中元素的总数。

sort.Search(size,fn)函数接受两个参数:所处理的切片的长度和一个将目标元素与有序切片的元素相比较的函数,该函数是一个闭包,如果该有序切片是升序排列,那么在判断时使用 有序切片的元素 >= 目标元素。该函数返回一个int值,表示与目标元素相同的切片元素的索引。

在切片中查找出某个与目标字符串相同的元素索引

因为char *strings[]不是指针而是指针数组,那么

temp = strings[top]

strings[top] = strings[seek]

strings[seek] = temp

这种交换交换的就是主调函数中的数组中的指针,把指向字符串的指针顺序改变了,当然按次序输出就达到排序目的了……

此篇文章流传甚广, 其实里面没啥干货, 而且里面很多观点是有问题的. 这个文章在 golang-china 很早就讨论过了.

最近因为 Rust 1.0 和 1.1 的发布, 导致这个文章又出来毒害读者.

所以写了这篇反驳文章, 指出其中的问题.

有好几次,当我想起来的时候,总是会问自己:我为什么要放弃Go语言?这个决定是正确的吗?是明智和理性的吗?其实我一直在认真思考这个问题。

开门见山地说,我当初放弃Go语言(golang),就是因为两个“不爽”:第一,对Go语言本身不爽;第二,对Go语言社区里的某些人不爽。毫无疑问,这是非常主观的结论。但是我有足够详实的客观的论据,用以支撑这个看似主观的结论。

文末附有本文更新日志。

确实是非常主观的结论, 因为里面有不少有问题的观点(用来忽悠Go小白还行).

第0节:我的Go语言经历

先说说我的经历吧,以避免被无缘无故地当作Go语言的低级黑。

2009年底,Go语言(golang)第一个公开版本发布,笼罩着“Google公司制造”的光环,吸引了许多慕名而来的尝鲜者,我(Liigo)也身居其中,笼统的看了一些Go语言的资料,学习了基础的教程,因对其语法中的分号和花括号不满,很快就遗忘掉了,没拿它当一回事。

在2009年Go刚发布时, 确实是因为“Google公司制造”的光环而吸引了(包括文章作者和诸多IT记者)很多低级的尝鲜者.

还好, 经过5年的发展, 这些纯粹因为光环来的投机者所剩已经不多了(Google趋势).

目前, 真正的Go用户早就将Go用于实际的生产了.

说到 其语法中的分号和花括号不满, 我想说这只是你的 个人主观感受, 还有很多人对Go的分号和花括号很满意,

包括水果公司的的 Swift 的语言设计者也很满意这种风格(Swift中的分号和花括号和Go基本相同).

如果只谈 个人主观感受, 我也可以说 Rust 的 fn 缩写也很蛋疼!

两年之后,2011年底,Go语言发布1.0的计划被提上日程,相关的报道又多起来,我再次关注它,重新评估之后决定深入参与Go语言。我订阅了其users、nuts、dev、commits等官方邮件组,坚持每天阅读其中的电子邮件,以及开发者提交的每一次源代码更新,给Go提交了许多改进意见,甚至包括修改Go语言编译器源代码直接参与开发任务。如此持续了数月时间。

这个到是事实, 在 golang-china 有不少吵架的帖子, 感兴趣的可以去挖下, 我就不展开说了.

到2012年初,Go 1.0发布,语言和标准库都已经基本定型,不可能再有大幅改进,我对Go语言未能在1.0定型之前更上一个台阶、实现自我突破,甚至带着诸多明显缺陷走向1.0,感到非常失望,因而逐渐疏远了它(所以Go 1.0之后的事情我很少关心)。后来看到即将发布的Go 1.1的Release Note,发现语言层面没有太大改变,只是在库和工具层面有所修补和改进,感到它尚在幼年就失去成长的动力,越发失望。外加Go语言社区里的某些人,其中也包括Google公司负责开发Go语言的某些人,其态度、言行,让我极度厌恶,促使我决绝地离弃Go语言。

真的不清楚楼主说的可以在 Go1.0 之前短时间内能实现的 重大改进和诸多明显缺陷 是什么.

如果是楼主说前面的 其语法中的分号和花括号不满 之类的重大改进, 我只能说这只是你的 个人主观感受 而已,

你的很多想法只能说服你自己, 没办法说服其他绝大部分人(不要以为像C++或Rust那样什么特性都有就NB了, 各种NB特性加到一起只能是 要你命3000, 而绝对不会是什么 银弹).

Go 1.1的Release Note,发现语言层面没有太大改变. 语言层没有改变是是因为 Go1 作出的向后兼容的承诺. 对于工业级的语言来说, Go1 这个只能是优点. 如果连语言层在每个版本都会出现诸多大幅改进, 那谁还敢用Go语言来做生产开发呢(我承认Rust的改动很大胆, 但也说明了Rust还处于比较幼稚和任性的阶段)?

说 Go语言社区里的某些人固执 的观点我是同意的. 但是这些 固执 的人是可以讲道理的, 但是他们对很多东西的要求很高(特别是关于Go的设计哲学部分).

只要你给的建议有依据(语言的设计哲学是另外一回事情), 他们绝对不会盲目的拒绝(只是讨论的周期会比较长).

关于楼主提交的给Go文件添加BOM的文章, 需要补充说明下.

在Go1.0发布的时候, Go语言的源文件(.go)明确要求必须是UTF8编码的, 而且是无BOM的UTF8编码的.

注意: 这个 无BOM的UTF8编码 的限制仅仅是 针对 Go语言的源文件(.go).

这个限制并不是说不允许用户处理带BOM的UTF8的txt文件!

我觉得对于写Go程序来说, 这个限制是没有任何问题的, 到目前为止, 我还从来没有使用过带BOM的.go文件.

不仅是因为带BOM的.go文件没有太多的意义, 而且有很多的缺陷.

BOM的原意是用来表示编码是大端还是小端的, 主要用于UTF16和UTF32. 对于 UTF8 来说, BOM 没有任何存在的意义(正是Go的2个作者发明了UTF8, 彻底解决了全球的编码问题).

但是, 在现实中, 因为MS的txt记事本, 对于中文环境会将txt(甚至是C/C++源文件)当作GBK编码(GBK是个烂编码),

为了区别到底是GBK还是UTF8, MS的记事本在前面加了BOM这个垃圾(被GBK占了茅坑), 这里的bom已经不是表示字节序本意了. 不知道有没有人用ms的记事本写网页, 然后生成一个带bom的utf8网页肯定很有意思.

这是MS的记事本的BUG: 它不支持生成无BOM的UTF8编码的文本文件!

这些是现实存在的带BOM的UTF8编码的文本文件, 但是它们肯定都不是Go语言源文件!

所以说, Go语言的源文件即使强制限制了无BOM的UTF8编码要求, 也是没有任何问题的(而且我还希望有这个限制).

虽然后来Go源文件接受带BOM的UTF8了, 但是运行 go fmt 之后, 还是会删除掉BOM的(因为BOM就是然并卵). 也就是说 带 BOM 的 Go 源文件是不符合 Go语言的编码风格的, go fmt 会强制删除 BOM 头.

前面说了BOM是MS带来的垃圾, 但是BOM的UTF8除了然并卵之外还有很多问题, 因为BOM在string的开头嵌入了垃圾,

导致正则表达式, string的链接运算等操作都被会被BOM这个垃圾所污染. 对于.go语言, 即使代码完全一样, 有BOM和无BOM会导致文件的MD5之类的校验码不同.

所以, 我觉得Go用户不用纠结BOM这个无关紧要的东西.

在上一个10年,我(Liigo)在我所属的公司里,深度参与了两个编程语言项目的开发。我想,对于如何判断某个编程语言的优劣,或者说至少对于如何判断某个编程语言是否适合于我自己,我应该还是有一点发言权的。

第1节:我为什么对Go语言不爽?

Go语言有很多让我不爽之处,这里列出我现在还能记起的其中一部分,排名基本上不分先后。读者们耐心地看完之后,还能淡定地说一句“我不在乎”吗?

1.1 不允许左花括号另起一行

关于对花括号的摆放,在C语言、C++、Java、C#等社区中,十余年来存在持续争议,从未形成一致意见。在我看来,这本来就是主观倾向很重的抉择,不违反原则不涉及是非的情况下,不应该搞一刀切,让程序员或团队自己选择就足够了。编程语言本身强行限制,把自己的喜好强加给别人,得不偿失。无论倾向于其中任意一种,必然得罪与其对立的一群人。虽然我现在已经习惯了把左花括号放在行尾,但一想到被禁止其他选择,就感到十分不爽。Go语言这这个问题上,没有做到“团结一切可以团结的力量”不说,还有意给自己树敌,太失败了。

我觉得Go最伟大的发明是 go fmt, 从此Go用户不会再有花括弧的位置这种无聊争论了(当然也少了不少灌水和上tiobe排名的机会).

是这优点, Swift 语言也使用和 Go 类似的风格(当然楼主也可能鄙视swift的作者).

1.2 编译器莫名其妙地给行尾加上分号

对Go语言本身而言,行尾的分号是可以省略的。但是在其编译器(gc)的实现中,为了方便编译器开发者,却在词法分析阶段强行添加了行尾的分号,反过来又影响到语言规范,对“怎样添加分号”做出特殊规定。这种变态做法前无古人。在左花括号被意外放到下一行行首的情况下,它自动在上一行行尾添加的分号,会导致莫名其妙的编译错误(Go 1.0之前),连它自己都解释不明白。如果实在处理不好分号,干脆不要省略分号得了;或者,Scala和JavaScript的编译器是开源的,跟它们学学怎么处理省略行尾分号可以吗?

又是楼主的 个人主观感受, 不过我很喜欢这个特性. Swift 语言也是类似.

1.3 极度强调编译速度,不惜放弃本应提供的功能

程序员是人不是神,编码过程中免不了因为大意或疏忽犯一些错。其中有一些,是大家集体性的很容易就中招的错误(Go语言里的例子我暂时想不起来,C++里的例子有“基类析构函数不是虚函数”)。这时候编译器应该站出来,多做一些检查、约束、核对性工作,尽量阻止常规错误的发生,尽量不让有潜在错误的代码编译通过,必要时给出一些警告或提示,让程序员留意。编译器不就是机器么,不就是应该多做脏活累活杂活、减少人的心智负担么?编译器多做一项检查,可能会避免数十万程序员今后多年内无数次犯同样的错误,节省的时间不计其数,这是功德无量的好事。但是Go编译器的作者们可不这么想,他们不愿意自己多花几个小时给编译器增加新功能,觉得那是亏本,反而减慢了编译速度。他们以影响编译速度为由,拒绝了很多对编译器改进的要求。典型的因噎废食。强调编译速度固然值得赞赏,但如果因此放弃应有的功能,我不赞成。

编译速度是很重要的, 如果编译速度够慢, 语言再好也不会有人使用的.

比如C/C++的增量编译/预编译头文件/并发编译都是为了提高编译速度.

Rust1.1 也号称 比 1.0 的编译时间减少了32% (注意: 不是运行速度).

当然, Go刚面世的时候, 编译速度是其中的一个设计目标.

不过我想楼主, 可能想说的是因为编译器自己添加分号而导致的编译错误的问题.

我觉得Go中 { 不能另起一行是语言特性, 如果修复这个就是引入了新的错误.

其他的我真想不起来还有哪些 调编译速度,不惜放弃本应提供的功能 (不要提泛型, 那是因为还没有好的设计).

1.4 错误处理机制太原始

在Go语言中处理错误的基本模式是:函数通常返回多个值,其中最后一个值是error类型,用于表示错误类型极其描述;调用者每次调用完一个函数,都需要检查这个error并进行相应的错误处理:if err != nil { /*这种代码写多了不想吐么*/ }。此模式跟C语言那种很原始的错误处理相比如出一辙,并无实质性改进。实际应用中很容易形成多层嵌套的if else语句,可以想一想这个编码场景:先判断文件是否存在,如果存在则打开文件,如果打开成功则读取文件,如果读取成功再写入一段数据,最后关闭文件,别忘了还要处理每一步骤中出现错误的情况,这代码写出来得有多变态、多丑陋?实践中普遍的做法是,判断操作出错后提前return,以避免多层花括号嵌套,但这么做的后果是,许多错误处理代码被放在前面突出的位置,常规的处理逻辑反而被掩埋到后面去了,代码可读性极差。而且,error对象的标准接口只能返回一个错误文本,有时候调用者为了区分不同的错误类型,甚至需要解析该文本。除此之外,你只能手工强制转换error类型到特定子类型(静态类型的优势没了)。至于panic - recover机制,致命的缺陷是不能跨越库的边界使用,注定是一个半成品,最多只能在自己的pkg里面玩一玩。Java的异常处理虽然也有自身的问题(比如Checked Exceptions),但总体上还是比Go的错误处理高明很多。

话说, 软件开发都发展了半个世纪, 还是无实质性改进. 不要以为弄一个异常的语法糖就是革命了.

我只能说错误和异常是2个不同的东西, 将所有错误当作异常那是SB行为.

正因为有异常这个所谓的银弹, 导致很多等着别人帮忙擦屁股的行为(注意 shit 函数抛出的绝对不会是一种类型的 shit, 而被其间接调用的各种 xxx_shit 也可能抛出各种类型的异常, 这就导致 catch 失控了):

int main() {

try {

shit()

} catch( /* 到底有几千种 shit ? */) {

...

}

}

Go的建议是 panic - recover 不跨越边界, 也就是要求正常的错误要由pkg的处理掉.

这是负责任的行为.

再说Go是面向并发的编程语言, 在海量的 goroutine 中使用 try/catch 是不是有一种不伦不类的感觉呢?

1.5 垃圾回收器(GC)不完善、有重大缺陷

在Go 1.0前夕,其垃圾回收器在32位环境下有内存泄漏,一直拖着不肯改进,这且不说。Go语言垃圾回收器真正致命的缺陷是,会导致整个进程不可预知的间歇性停顿。像某些大型后台服务程序,如游戏服务器、APP容器等,由于占用内存巨大,其内存对象数量极多,GC完成一次回收周期,可能需要数秒甚至更长时间,这段时间内,整个服务进程是阻塞的、停顿的,在外界看来就是服务中断、无响应,再牛逼的并发机制到了这里统统失效。垃圾回收器定期启动,每次启动就导致短暂的服务中断,这样下去,还有人敢用吗?这可是后台服务器进程,是Go语言的重点应用领域。以上现象可不是我假设出来的,而是事实存在的现实问题,受其严重困扰的也不是一家两家了(2013年底ECUG Con 2013,京东的刘奇提到了Go语言的GC、defer、标准库实现是性能杀手,最大的痛苦是GC;美团的沈锋也提到Go语言的GC导致后台服务间隔性停顿是最大的问题。更早的网络游戏仙侠道开发团队也曾受Go垃圾回收的沉重打击)。在实践中,你必须努力减少进程中的对象数量,以便把GC导致的间歇性停顿控制在可接受范围内。除此之外你别无选择(难道你还想自己更换GC算法、甚至砍掉GC?那还是Go语言吗?)。跳出圈外,我近期一直在思考,一定需要垃圾回收器吗?没有垃圾回收器就一定是历史的倒退吗?(可能会新写一篇博客文章专题探讨。)

这是说的是32位系统, 这绝对不是Go语言的重点应用领域!! 我可以说Go出生就是面向64位系统和多核心CPU环境设计的. (再说 Rust 目前好像还不支持 XP 吧, 这可不可以算是影响巨大?)

32位当时是有问题, 但是对实际生产影响并不大(请问楼主还是在用32位系统吗, 还只安装4GB的内存吗). 如果是8位单片机环境, 建议就不要用Go语言了, 直接C语言好了.

而且这个问题早就不存在了(大家可以去看Go的发布日志).

Go的出生也就5年时间, GC的完善和改进是一个持续的工作, 2015年8月将发布的 Go1.5将采用并行GC.

关于GC的被人诟病的地方是会导致卡顿, 但是我以为这个主要是因为GC的实现还不够完美而导致的.

如果是完美的并发和增量的GC, 那应该不会出现大的卡顿问题的.

当然, 如果非要实时性, 那用C好了(实时并不表示性能高, 只是响应时间可控).

对于Rust之类没有GC的语言来说, 想很方便的开发并发的后台程序那几乎是不可能的.

不要总是吹Rust能代替底层/中层/上层的开发, 我们要看有谁用Rust真的做了什么.

1.6 禁止未使用变量和多余import

Go编译器不允许存在被未被使用的变量和多余的import,如果存在,必然导致编译错误。但是现实情况是,在代码编写、重构、调试过程中,例如,临时性的注释掉一行代码,很容易就会导致同时出现未使用的变量和多余的import,直接编译错误了,你必须相应的把变量定义注释掉,再翻页回到文件首部把多余的import也注释掉,……等事情办完了,想把刚才注释的代码找回来,又要好几个麻烦的步骤。还有一个让人蛋疼的问题,编写数据库相关的代码时,如果你import某数据库驱动的pkg,它编译给你报错,说不需要import这个未被使用的pkg;但如果你听信编译器的话删掉该import,编译是通过了,运行时必然报错,说找不到数据库驱动;你看看程序员被折腾的两边不是人,最后不得不请出大神:import _。对待这种问题,一个比较好的解决方案是,视其为编译警告而非编译错误。但是Go语言开发者很固执,不容许这种折中方案。

这个问题我只能说楼主的吐槽真的是没水平.

为何不使用的是错误而不是警告? 这是为了将低级的bug消灭在编译阶段(大家可以想下C/C++的那么多警告有什么卵用).

而且, import 即使没有使用的话, 也是用副作用的, 因为 import 会导致 init 和全局变量的初始化.

如果某些代码没有使用, 为何要执行 init 这些初始化呢?

如果是因为调试而添加的变量, 那么调试完删除不是很正常的要求吗?

如果是因为调试而要导入fmt或log之类的包, 删除调试代码后又导致 import 错误的花,

楼主难道不知道在一个独立的文件包装下类似的辅助调试的函数吗?

import (

"fmt"

"log"

)

func logf(format string, a ...interface{}) {

file, line := callerFileLine()

fmt.Fprintf(os.Stderr, "%s:%d: ", file, line)

fmt.Fprintf(os.Stderr, format, a...)

}

func fatalf(format string, a ...interface{}) {

file, line := callerFileLine()

fmt.Fprintf(os.Stderr, "%s:%d: ", file, line)

fmt.Fprintf(os.Stderr, format, a...)

os.Exit(1)

}

import _ 是有明确行为的用法, 就是为了执行包中的 init 等函数(可以做某些注册操作).

将警告当作错误是Go的一个哲学, 当然在楼主看来这是白痴做法.

1.7 创建对象的方式太多令人纠结

创建对象的方式,调用new函数、调用make函数、调用New方法、使用花括号语法直接初始化结构体,你选哪一种?不好选择,因为没有一个固定的模式。从实践中看,如果要创建一个语言内置类型(如channel、map)的对象,通常用make函数创建;如果要创建标准库或第三方库定义的类型的对象,首先要去文档里找一下有没有New方法,如果有就最好调用New方法创建对象,如果没有New方法,则退而求其次,用初始化结构体的方式创建其对象。这个过程颇为周折,不像C++、Java、C#那样直接new就行了。

C++的new是狗屎. new导致的问题是构造函数和普通函数的行为不一致, 这个补丁特性真的没啥优越的.

我还是喜欢C语言的 fopen 和 malloc 之类构造函数, 构造函数就是普通函数, Go语言中也是这样.

C++中, 除了构造不兼容普通函数, 析构函数也是不兼容普通函数. 这个而引入的坑有很多吧.

1.8 对象没有构造函数和析构函数

没有构造函数还好说,毕竟还有自定义的New方法,大致也算是构造函数了。没有析构函数就比较难受了,没法实现RAII。额外的人工处理资源清理工作,无疑加重了程序员的心智负担。没人性啊,还嫌我们程序员加班还少吗?C++里有析构函数,Java里虽然没有析构函数但是有人家finally语句啊,Go呢,什么都没有。没错,你有个defer,可是那个defer问题更大,详见下文吧。

defer 可以覆盖析构函数的行为, 当然 defer 还有其他的任务. Swift2.0 也引入了一个简化版的 defer 特性.

1.9 defer语句的语义设定不甚合理

Go语言设计defer语句的出发点是好的,把释放资源的“代码”放在靠近创建资源的地方,但把释放资源的“动作”推迟(defer)到函数返回前执行。遗憾的是其执行时机的设置似乎有些不甚合理。设想有一个需要长期运行的函数,其中有无限循环语句,在循环体内不断的创建资源(或分配内存),并用defer语句确保释放。由于函数一直运行没有返回,所有defer语句都得不到执行,循环过程中创建的大量短暂性资源一直积累着,得不到回收。而且,系统为了存储defer列表还要额外占用资源,也是持续增加的。这样下去,过不了多久,整个系统就要因为资源耗尽而崩溃。像这类长期运行的函数,http.ListenAndServe()就是典型的例子。在Go语言重点应用领域,可以说几乎每一个后台服务程序都必然有这么一类函数,往往还都是程序的核心部分。如果程序员不小心在这些函数中使用了defer语句,可以说后患无穷。如果语言设计者把defer的语义设定为在所属代码块结束时(而非函数返回时)执行,是不是更好一点呢?可是Go 1.0早已发布定型,为了保持向后兼容性,已经不可能改变了。小心使用defer语句!一不小心就中招。

前面说到 defer 还有其他的任务, 也就是 defer 中执行的 recover 可以捕获 panic 抛出的异常.

还有 defer 可以在 return 之后修改命名的返回值.

上面2个工作要求 defer 只能在函数退出时来执行.

楼主说的 defer 是类似 Swift2.0 中 defer 的行为, 但是 Swift2.0 中 defer 是没有前面2个特性的.

Go中的defer是以函数作用域作为触发的条件的, 是会导致楼主说的在 for 中执行的错误用法(哪个语言没有坑呢?).

不过 for 中 局部 defer 也是有办法的 (Go中的defer是以函数作用域):

for {

func(){

f, err := os.Open(...)

defer f.Close()

}()

}

在 for 中做一个闭包函数就可以了. 自己不会用不要怪别人没告诉你.

1.10 许多语言内置设施不支持用户定义的类型

for in、make、range、channel、map等都仅支持语言内置类型,不支持用户定义的类型(?)。用户定义的类型没法支持for in循环,用户不能编写像make、range那样“参数类型和个数”甚至“返回值类型和个数”都可变的函数,不能编写像channel、map那样类似泛型的数据类型。语言内置的那些东西,处处充斥着斧凿的痕迹。这体现了语言设计的局限性、封闭性、不完善,可扩展性差,像是新手作品——且不论其设计者和实现者如何权威。延伸阅读:Go语言是30年前的陈旧设计思想,用户定义的东西几乎都是二等公民(Tikhon Jelvis)。

说到底, 这个是因为对泛型支持的不完备导致的.

Go语言是没啥NB的特性, 但是Go的特性和工具组合在一起就是好用.

这就是Go语言NB的地方.

1.11 没有泛型支持,常见数据类型接口丑陋

没有泛型的话,List、Set、Tree这些常见的基础性数据类型的接口就只能很丑陋:放进去的对象是一个具体的类型,取出来之后成了无类型的interface{}(可以视为所有类型的基础类型),还得强制类型转换之后才能继续使用,令人无语。Go语言缺少min、max这类函数,求数值绝对值的函数abs只接收/返回双精度小数类型,排序接口只能借助sort.Interface无奈的回避了被比较对象的类型,等等等等,都是没有泛型导致的结果。没有泛型,接口很难优雅起来。Go开发者没有明确拒绝泛型,只是说还没有找到很好的方法实现泛型(能不能学学已经开源的语言呀)。现实是,Go 1.0已经定型,泛型还没有,那些丑陋的接口为了保持向后兼容必须长期存在着。

Go有自己的哲学, 如果能有和目前哲学不冲突的泛型实现, 他们是不会反对的.

如果只是简单学学(或者叫抄袭)已经开源的语言的语法, 那是C++的设计风格(或者说C++从来都是这样设计的, 有什么特性就抄什么), 导致了各种脑裂的编程风格.

编译时泛型和运行时泛型可能是无法完全兼容的, 看这个例子:

type Adder<T>interface {

Add(a, b T) T

}