佛系程序员 第四品

多年之前,我当时的BOSS的BOSS来上海,就坐在我边儿上。那几天憋了半天,憋出了一个我感觉挺重要的问题,看他不太忙的时候就问他:“你觉得我们项目上什么是最重要的,或者说,我们遇到了事儿,应该按什么标准、什么方向判断优先级呢?”那位祖师爷转过头来,盯着我看了两秒,就盯得我心里一阵毛,然后严肃地和我讲:“Hugo,没有任何一个原则,是能应对所有问题的。你明白我的意思么。”。然后聊天结束。

其实须菩提问佛祖也是一个手段问题:“云何应住?云何降服其心?”。佛祖的回答也是很简单,和我BOSS的BOSS说得其实是一个意思:

金刚经 第四品 妙行无住分

“复次,须菩提!菩萨于法,应无所住,行于布施,所谓不住色布施,不住声香味触法布施。须菩提!菩萨应如是布施,不住于相。何以故?若菩萨不住相布施,其福德不可思量。须菩提!于意云何?东方虚空可思量不?”“不也,世尊!”“须菩提!南西北方四维上下虚空可思量不?”“不也,世尊!”“须菩提!菩萨无住相布施,福德亦复如是不可思量。须菩提!菩萨但应如所教住。”

本品划重点,非“应无所住”莫属。本系列写到了这第四品,总算到正题了。这四个字就是我在本系列中想表达的重点。这个字面意思很容易懂,但是真用上就不那么简单了。

我说“真用上就不那么简单了”,有人可能体会不到是什么意思。我试举一例。我面试时常遇到这样一类候选人,你问他LinkedList和ArrayList的区别是什么,他能讲得很清楚。然后在这个问题的铺垫下,再让他写个简单的代码,遇到需要使用一个List的时候,他随手就用了ArrayList,然后和他一起现场Review一下,问,这个场景下,会不会有什么性能问题?提示到这种程度,还是想不到这里应该考虑用LinkedList,非得等我指着代码,一一说破,他才恍然大悟,信誓旦旦地表示刚才只是大意忘了这个点而已。

一个最基本的知识,一个自己能讲得清清楚楚的东西。真到应该用的时候,并不能用得上的。什么原因呢?因为他知道的是“知识”,应用“知识”的过程,是一个组合问题,你要把所有已知的相关知识和当前的问题一一对应过之后,才能全面地回答一个问题。这是一个至少是O(n)复杂度的问题,当解空间太大的时候,没人有这个脑力。一个“知识”,只有内化成“见识”、“智慧”之后,才能以O(1)的速度求解所有问题。那么怎么内化呢?

看过《倚天屠龙记》的人应该对张三丰教张无忌太极时的经过印象颇深:

  张三丰一路剑法使完,竟无一人喝采,各人尽皆诧异:“这等慢吞吞、软绵绵的剑法如何能用来对敌过招?”转念又想:“料来张真人有意放慢了招数,好让他瞧得明白。”

只听张三丰问道:“孩儿,你看清楚了没有?”张无忌道:“看清楚了。”张三丰道: “都记得了没有?”张无忌道:“已忘记了一小半。”张三丰道:“好,那也难为了你。你自己去想想罢。”张无忌低头默想。过了一会,张三丰问道:“现下怎样了?”张无忌道: “已忘记了一大半。”

周颠失声叫道:“糟糕!越来越忘记得多了。张真人,你这路剑法很是深奥,看一遍怎能记得?请你再使一遍给我们教主瞧瞧罢。”

张三丰微笑道:“好,我再使一遍。”提剑出招,演将起来。众人只看了数招,心下大奇,原来第二次所使,和第一次使的竟然没一招相同。周颠叫道:“糟糕,糟糕!这可更加叫人胡涂啦。”张三丰画剑成圈,问道:“孩儿,怎样啦?”张无忌道:“还有三招没忘记。”张三丰点点头,收剑归座。

张无忌在殿上缓缓踱了一个圈子,沉思半晌,又缓缓踱了半个圈子,抬起头来,满脸喜色,叫道:“这我可全忘了,忘得干干净净的了。”张三丰道:“不坏不坏!忘得真快,你这就请八臂神剑指教罢!”说着将手中木剑递了给他。张无忌躬身接过,转身向方东白道: “方前辈请。”周颠抓耳搔头,满心担忧。

傻子都看得出来,张三丰在传授剑道、剑意,而不是在传授剑招。我们推衍一下,这里的“道”是什么呢?学编程、写代码,做人、做事儿有没有“道”呢?

佛祖的道,就是无所住。不住‘色’,不住‘声’、‘香’、‘味’、‘触’、‘法’。有人可能想问:这些色啦、法啦都是什么意思呢?这不重要,因为这里只是举例、比喻,佛祖也没办法把所有你可能要住的东西都枚举出来不是?有人可能又想问:那就是什么原则、法则都不要啦,做个不讲原则的人啦?更不是。我只能诡辩说“不讲原则”也是一个原则。因为更深的意思,我也没办法讲出来了。我只能建议说,不要总想着分析具体什么应该做,什么不应该做。那就是“邪道”了。无论你分析出什么结果,都是有所住。

我几年前就常常感觉有点儿对不住我手下的小弟。因为他们有时来问我一些具体的问题,我没办法给到他们一些正面的、直接的、具体的回答。我的回复大都都是方向性的,原则性的。然后他们自己折腾半天。但是如果事情到我这里,他们又会看到我好像什么都能搞得定,而且还挺快。我起初是有些担心,他们会不会觉得我就是故意不告诉他们。后面大家共事久了,就不会有这种担心了。因为他们会发现,我这人向来是知无不言、言无不尽的。只是有些人终归还是不习惯我的风格,喜欢谈具体的东西,不喜欢谈抽象的。这也无可厚非。而我也其实并不总是对所有人都有足够的耐心。这时候就照章办事儿就好。

佛系程序员 第三品

《金刚经》的前面两品都是铺垫,佛祖开始说正事是第三品。正文如下:

金刚经 第三品 大乘正宗分

佛告须菩提:“诸菩萨摩诃萨应如是降伏其心!所有一切众生之类:若卵生、若胎生、若湿生、若化生;若有色、若无色;若有想、若无想、若非有想非无想,我皆令入无余涅盘而灭度之。如是灭度无量无数无边众生,实无众生得灭度者。何以故?须菩提!若菩萨有我相、人相、众生相、寿者相,即非菩萨。”

当年年少中二的时候,读到第一句“我皆令入无余涅盘而灭度之”,就去闭目参悟武功心法去了,后来什么都没悟出来,这经的后半句也没读下去。直到多年之后,再来读的时候才发现,原来佛祖根本不是这个意思。

我先来翻译一下大意:

佛跟须菩提说:“你们应该和他们讲:如果你说‘我把所有众生都度了’。其实就没人被度,因为你有众生相的话,你就连菩萨都不是。(菩萨都不是,你度个毛啊)”

先小科普一下“灭度”,即“度灭”,就是超脱生死的意思。只是一种得了无上智慧后的一种状态,不是指死。涅槃也不是死的意思。没死也可以涅槃。

佛祖这里说的‘度’、‘菩萨’,其实只是一种比喻。而不是单纯地说‘度’或教育‘菩萨’。而是在阐释一种理念。我想了很久,如何用一个比较现代化的比喻来解释这个理念。但是感觉比喻还是太间接,还是直接讲理念是什么比较直接,用比喻的形式来说话,对听众的“慧根”要求太高,可能听了还是听不懂,而一句话说了,听众没听懂,就是白说。

佛祖的这个理念可以有很多种讲法,比如“内容”和“形式”,“动机”和“手段”,“过程”和“结果”。其实都是同一个理念的不同表达形式。

“度众生”,是形式、是手段,是外在的结果。佛祖想说的是,心大于法。如果你动机不纯,过程不正,内容不善,做什么都是徒劳的,不会得正果。(佛祖在这里没说什么“纯”、“正”、“善”,我纯粹为了工整而硬加的。而且佛祖想说的其实也并不是这些,佛祖想说的就是心态。无我,无人,无众生,无寿者。度只是手段。没有一个合适的心态,度也是白度。)

所以做人做事儿,最重要的是你的本心。明朝大哲王守仁创立的心学也表达了类似的观点:

爱问:“至善只求诸心,恐于天下事理有不能尽。”

先生曰:“心即理也。天下又有心外之事、心外之理乎?”

——《传习录 卷一》

这里的心,指的是“道心”,而非“人心”,和佛教里的“阿耨多罗三藐三菩提心”大体是一个意思。至于两者的区别,王守仁自己的解释是:

“只说‘明明德’,而不谈‘亲民’,便似老、佛。”

意思是认为佛学只是让人开悟、明至理,但是普罗大众完全用不上。所以说王守仁的心学理论上是比佛学更接地气并有实用价值的。但是心学IPO才小几百年,没有佛教根基深厚。王守仁的名气也没释迦牟尼大,所以人们平时聊天放屁、插科打诨都是拿佛祖开涮,提王明阳也没人知道啊。

你看哈,很多宗教、理学的经典其基本理念都很类似,按初中政治、历史课本的话说,都是唯心的,都是错的。说到唯心,我就又想插一嘴。我一直就特别纳闷儿,你看哈,量子力学解释不了女人为什么老问男人诸如“我和你妈同时落水你先救谁”之类的问题,也没人说量子力学是错的,但是有些人总是用唯心主义解释不了这个世界运作的原理为由,认定所有的唯心主义学说都是荒谬的。

这个扯远了。

我们回到第三品的经文上,这个在说什么事儿呢。我先引用知乎上的一个问题,结果正义是不是就可以无视过程的正义性。我回答说不是,我说因为你的过程,可能就是别人的结果。而这段佛经更进一步,过程都不够,而且要考量初衷及动机。所以你看出家人总是一本正经、心无旁骛的,因为他心有邪念都不行。佛祖就看不上他。

这段经文还说了什么呢?我们想想之前的问题是什么?须菩提问的是,如何降服善男善女的心,让他们也像如来佛祖一样有大智慧,得以超脱(涅槃)。

那佛祖回答这些是什么意思?其实有两层额外的意思(佛祖从来不说狠话,所以没有直说):

  1. 须菩提,你这是想去度化众生么?你这想法就不对啊。你在分你、别人、众生。
  2. 众生其实是度不了的。如果能度,佛祖就直接说了。而且,众生是不需要度的。佛祖也从来没有想过去度化谁,甚至也不关心有没有人能度。

说白了就是在批评教育须菩提。

至于说原文里的我相、人相、众生相、寿者相都是啥意思,因为我并不是在讲经,这里就不展开了。

佛系程序员 第二品

如何最快地学到新东西呢?一般找对人,然后问对的问题,大概算是比较便捷的方式之一。但是问对的问题其实很不容易,因为想问对的问题,有两个前提:知道自己知道什么、不知道什么,还知道自己想要什么。面试的时候,如果真有人在提问环节什么都不问,我心里基本就把这个人放弃了。因为不提问的人,要么是什么都不知道,要么是对做事儿没兴趣,要么是对事儿没自己的想法,只会人云亦云,要么是对我这个人有成见,懒得和我说话;无论是哪种情况,都不是什么好现象。所以干脆直接拒掉好了。

《金刚经》这么平易近人的作品,写作手法上也是和小说有一拼,真就是师徒一问一答的形式。感觉比《XXX语录》还像是语录。第二品,和第一品一样,看上去又是一堆废话。我们来瞻仰一下原文:

金刚经 第二品 善现启请分

时,长老须菩提在大众中即从座起,偏袒右肩,右膝着地,合掌恭敬而白佛言:“希有!世尊!如来善护念诸菩萨,善付嘱诸菩萨。世尊!善男子、善女人,发阿耨(nuò)多罗三藐三菩提心,云何应住,云何降(xiáng)伏其心?”佛言:“善哉,善哉。须菩提!如汝所说,如来善护念诸菩萨,善付嘱诸菩萨。汝今谛听!当为汝说:善男子、善女人,发阿耨多罗三藐三菩提心,应如是住,如是降伏其心。”“唯然,世尊!愿乐(yào)欲闻。”

其实说白了,就是须菩提问佛祖如何收了世人的心。那么为说这么一堆废话呢?因为多出来的每句话,都是有意义的。我们一起来分析一下。你也可以说我的说法牵强附会。但是佛经这东西啊,比《哈姆雷特》还哈姆雷特,比《红楼》还红楼。照例先翻译一下。

当时,有个叫须菩提的长老,从人群中坐起来。光着右膀子,右腿跪着,作合十礼,毕恭毕敬地向佛祖问道:“好久不见啊,老大哥,觉悟者们喜欢跟菩萨们讲道理,事事叮嘱。老大哥,如果有些有志青年男女,也想成为觉悟者,得到无上的大智慧。那我们菩萨们,得跟他们讲什么作人作事儿的原则?怎么说才能让他们信服呢?”佛说:“没错,没错。须菩提啊!就像你说的,觉悟者们的确喜欢和菩萨们讲道理,叮嘱他们。这回大家都好好听着,我就跟你们掰扯掰扯:‘如果有些有志青年男女,也想成为觉悟者,得到无上的大智慧。那我们菩萨们,就可以这样讲作人作事儿的原则,从而让他们信服。’”。(大伙齐声说:)“就得这句话了,老大哥,我们想听想得高兴得屁颠屁颠的。”

第一句,“时,长老须菩提大众中即从座起”。须菩提是谁?佛祖座下十大弟子里排前三吧。大众呢,就是第一品提到的1250个僧人。“从大众中即从座起”,什么意思?不是从世尊附侧座起。明白了么。第二品,第一句,还是在说平等。

佛经的写法和《圣经》最大的不同点在于,佛经都是讲故事,聊闲天,你从中读出什么看客自便。所以我说佛经比《红楼》还红楼。而《圣经》基本就是上帝说要什么,就是什么。让天下雨天就下雨。上帝说什么你必须听,不听就死去吧,死了还要下地狱。所以我一直不是很理解,上帝心肠这么歹毒的人,还有这么多拥护者。看来人们还真都有点儿“斯德哥尔摩综合征”倾向。

佛就不一样,特别的亲民。然而须菩提在发问前还是把该做的礼节一个不落地都做了。为什么呢?他不注重礼节,佛祖也不会拿他如何——估计顶多也就不搭理他了呗。不过佛祖胸怀这么宽广的,会这么小心眼么?他不是衣食都自理的么?这其实是在描述第二个道理:一个人,如果知道什么是对的,什么是好的,那么照做就是了。不用在意对方或其他人如何看待。这其实不仅仅需要见识,还需要勇气。须菩提对佛的尊敬,并不是做给佛看的,也不是做给其他人看的,而且也不是因为自己觉得对而做的,因为为了对而做,也是错的,甚至不是做给自己的。

再来看须菩提问问题是如何问的。先说,“希有!世尊!”,这是打招呼,就像写信要写“致某某某”,后面要署名,不能只写正文,这些都是规矩。还是礼,还是尊敬。

后面又做了一个铺垫:“如来善护念诸菩萨,善付嘱诸菩萨。”,什么意思呢?问别人问题,如果不想显得唐突,就得写解释一下来龙去脉,说话也得有个起承转合。别人才好接话不是?这可以说是话术,也可以说是礼。

当然啦,佛经原文是梵文,这个版本的《金刚经》是姚秦(即后秦,公元4世纪的一个朝代)时翻译的,那个时代的人很重礼,至于这些繁文缛节是译本才有的特点还是梵文就有的意思?我就不清楚了。但是这重要吗?不重要的。

我们先回到问题上,问题的核心就一句话:“善男子、善女人,发阿耨多罗三藐三菩提心,云何应住,云何降伏其心?”。佛祖听了之后如何回答的呢?

佛祖先是肯定了他的想法和疑问,然后把这个冗长的问题复述了一遍。这简直和现在发布会或演讲中的问答环节别无二致啊。这套路原来已经传承千年了。当然我相信这肯定不是佛祖首创。公共场合讲话,总是要照顾多数人的。然而在佛祖的铺垫中,有几个字是套路之外的。这几个字才是佛祖想着重表达的:

汝今谛听!当为汝说

汝,就是你;今,这回,现在;谛听,好好听、仔细听。然后我才给你讲讲。意思是什么呢?一层意思是,你不好好听,可能根本就听不懂。其实后半句还有一层意思是,如果不是你要听,我也不会讲。你这问了,我便趁这个机会讲讲。

这里的“听”,不是listen的意思,也不是hear的意思,而是comprehend的意思。这三者有什么分别,我在知乎问题《为什么有很多学生在老师讲课的时候什么都懂,但是做题却不会做?》下面有相关的解释。这里就不展开了。

佛祖的行事风格是,听众们不想听,或是没想到去听,便不会非讲给你听。几乎所有的佛经,都是这种弟子问然后佛祖答的形式。你不问,我便不说。因为多数情况下,说了其实作用也不大。因为想法上的事儿,得自己有听的意愿,也有理解的意愿,才能理解并接纳新的想法。自己钻牛角尖,陷进去出不来的人,佛祖是连话都懒得讲的。通俗点儿讲,佛祖也是认同“狗改不了吃屎”及“烂泥糊不上墙”的。

须菩提是聪明人,一听就懂。立马表态:“愿乐欲闻。”,比“谛听”的程度还高。当然啦,这里应该是没有拍佛祖马屁的意思的。更多的还是礼节而已。

总结一下第二品,这一品主要讲人和要自己的想法、见识,不受旁人眼光、看法的影响;又要有开放的心态去了解别人的想法,并能接纳别人的想法。没有这个基础,读多少书都没有用。

佛系程序员 第一品

金刚经我读了有不下100遍,基本每一遍都有新的理解。有些感想总是想写下来,且不管有没有人会看。至少经年之后,自己有了更多的感悟,再回来看的时候,也好有个印证。金刚经共有三十二品,此为第一品感悟。

金刚经 第一品 法会因由分

如是我闻,一时,佛在舍卫国祗树给孤独园,与大比丘众千二百五十人俱。尔时,世尊食时,著衣持钵,入舍卫大城乞食。于其城中,次第乞已,还至本处。饭食讫,收衣钵,洗足已,敷座而坐。

我第一次读到这里的时候就停下来去Google “金刚经 原文”,“金刚经 正文”。因为一眼看上去就觉得不正经。就像是某个佛家弟子写的听经文后的自传,而不是释迦摩尼写的经文。但是找了半天,发现这真的就是正文原经的时候,我愣了半天,这和我想象中少林寺困住狮王谢逊的“金刚伏魔圈”的本源之经实在相去太远了。不过能让六祖慧能开悟的经文。我还是耐着性子读了下去。

我先翻译一下:

我是这么听说的,有一回,佛在“舍卫国祗树给孤独园”这边,和250位和尚在一块儿。正赶上佛祖他老人家要吃饭了,于是穿上衣服,拿着要饭的钵盂,到城里去要饭。大伙在城里挨着个地要完饭,回到园子时各自的位置上,把饭吃完,把衣服脱下来和钵盂一起收好,洗了个脚,铺了个地垫坐了下来。

咳,“衣”或许应该翻译成“袈裟”吧?不过这不重要。说重点。佛教的无上经典(我突然感觉应该也可以作为丐帮的),一开头把佛祖的日常起居介绍一下,有什么特别的地方么?没有吧。没有就对了。佛祖本来就没什么特别的。佛祖想表达的也是这个。佛祖也要吃饭,也要穿衣服,也要洗脚,站久了也会累,也没个像样的地方讲经,更没有什么神迹。就是个普通人。但是他也是特别的,因为他是佛祖,百千万亿劫(佛教时间单位,一劫大概等于268亿7680万年)才出一位的无上正觉者(得“阿耨多罗三藐三菩提心”者)。

这在告诉我们一个很简单的道理:所有人,其实都是一样的、平等的。好,这又是一句废话——直到你真正明白它的意思。

我不知道我是否明白了,但是我感觉这是在讲,其实作人呢,并不需要真正地畏惧、敬仰、羡慕、嫉妒、敌视、鄙夷任何人。因为人啊,都是一样一样一样的。所以和人讲话什么的,甭管谁,不用脸红,说错了他又不会打你。哪怕上手打架,泰森站对面也不用怵,反正他也不屑于打你的,对吧?

比如我见过一些人,知道自己在某些技术方面不是特别好,做东西就特没有信心,做得对不对都不敢讲,更不要问做得好不好了。其实在一方面就是没明白一个道理:别人能做到的事儿,你只要不是智力上或是态度上有什么问题,应该终归也是可以的,而且不需要别人的肯定,才能有自信说做得好了。你只要真明白在做什么,自己就会有标准。因为人和人都是一样的。

但是至于说,为什么有人住千亩大平层,有人住桥洞搭窝棚呢?

因为人和人其实是不一样的。而且人和人之间的差距和收入的差距一样,是能差几个数量级的。程序员更甚。

我不是说人是一样的么,怎么就又不一样了呢?我说话有没有逻辑?这不是我的逻辑,这是佛祖的逻辑。想得读懂《金刚经》,你得适应佛祖的逻辑。后面几品《金刚经》里,出现最多的句式就是:佛说XXX,即非XXX,是名XXX。所以我说读懂《金刚经》,就不是说真是读懂《金刚经》,而是称之为、当作读懂《金刚经》。我说“当作”,就不是“当作”,是当作“当作”……

这段还说什么了呢?佛这么NB的人,岁数也这么大了,他也没让人照顾自己吃喝拉撒睡分毫。都是自己做的,自己穿衣服,自己洗脚,而且井井有条。为什么这么讲呢?如果去看下其它上部座经文就知道了。基本上都是这样开头的。(下部座经文像《本愿经》、《法华经》什么的就算了,那里的佛就开始自带主角光环了。)

写这些又是什么意思呢?其实是在讲,吃喝拉撒睡也是经文,吃喝拉撒睡也是修行。好,这是什么意思呢?

这个可以有很多意思。我这里只想说一个,就是,你想修行(或想学习)是可以随时随地的。

有人时常说自己没有XX机会去做XX。比如,没时间看书,没时间学习,没时间做这儿,没时间做那。其实吧,不是真想做罢了。真想做的事儿,总是可以做,而且随时随地。

第一品的东西不多,我就先说这些。开头没别的,就是要把心态放正,建立信心,并切实地做下去。无论做什么事儿,这都是前提。放第一品。非常合适。

注:本文仅仅描述我对经文的理解,并不表示我完全赞同并实行。

佛系程序员

最近面试了大概上百位求职者,和有些人谈得开了,有人会让我给他点儿建议。我大都只是建议他们培养出一种把事儿做好的心态。有缘的,我会建议去读一读《金刚经》。听者基本都是一脸不知所以的表情。倒不是说我之前有从《金刚经》中悟出了什么,只是后来读《金刚经》发现其中有很多理念,与我对写代码的想法不某而合。当然,也可以说是我自己一厢情愿地想当然罢了。下面我简单地介绍一下这些理念。

首先,一说《金刚经》或任何一部佛学经典,人们常常会有的一个刻板的印象可能就是:和尚才要读那东西。我一开始读《金刚经》的动机就不太纯正,我就是想看看佛祖这么牛逼的人是怎么忽悠,啊不,感化人的。后面我读完了就发现自己脸就肿了。《金刚经》中有个四句偈,是这样说的:

“若以色见我,以音声求我,是人行邪道,不能见如来。”

说得很白,我就不解释了。如来为了被人误解,甚至还说:

若人言:如来有所说法,即为谤佛,不能解我所说故。

我十分想知道那些天天烧香拜佛的人听到佛祖这么讲会有什么样的心理活动。

好,如来说他什么都没说,那《金刚经》说了些什么呢?六祖慧能说,这句话可以说是《金刚经》的总旨:

应无所住,而生其心。

这句话能展开解释成很多东西。我这里就不展开了。回到前面说的给求职者的建议上,我给候选人推荐读《金经刚》的意思其实是:你不要依赖别人如何讲、如何做,你要有自己的见识,自己的作为。我说什么,说得再对,再好,也是我的,不是你的。然而,我又不是真的就是要让人按这个原则做。因为按任何原则做,其实都是“有所住”。但是呢,又不是说让人抛弃所有原则。《金刚经》还说:

汝若作是念:“发阿耨多罗三藐三菩提心者,说诸法断灭。”莫作是念!

这大概就是“不可说,说即是错。”的来源吧。

所以呢,只能你自己去看《金刚经》,至于能从中读懂多少,就要看个人的悟性和缘分了。这个在《金刚经》里也给读者打了招呼:

若善男子、善女人,于后末世,有受持读诵此经,所得功德,我若具说者,或有人闻,心即狂乱,狐疑不信。须菩提!当知是经义不可思议,果报亦不可思议。

《金刚经》,在我看来,是本破除愚昧的书。

从用缓存优化函数性能说说第三方框架的使用

导读

前面两篇文章分别从计算机及领域知识编程语言本身的角度聊了聊写代码要考虑的事儿。但是理解了计算机系统、领悟了领域知识、精通了某门编程语言就够了么?我在编程到底难在哪里的回答里说,软件开发是搭积木式的,如果你想搭得好又有价值,一个合理的办法是在已经搭好的基础上继续搭,而不是把所有东西自己重新搭一遍。JDK和.NET Framework都是这种已经搭好了的最基本的架子。想想软件发展了几十年,各式框架已经一应俱全,基本想做个任何事情都已经有现成的框架可用。当然,如果你觉得现在已经搭好的东西就是坨屎,当然可以也应该自己搭个更好的。但是现实的情况大都是:人家明明已经搭好那么多各式各样的建筑并欢迎你去添砖加瓦,结果只是因为自己不知道、不了解那些东西的存在,自己重头搭了个双层火柴盒还觉得不错。软件开发显然比在minecraft里搭积木要复杂且抽象些。随之而来的一个问题就是:可应用框架的地方并不显而易见,尤其是当你觉得自己写一个更快的时候。这也是本文将要讨论的重点。(在校生请不要误会,在校生请夯实基础并从基础搭起,能搭多少搭多少。)

引子

假设我们发现这个下面开平方函数很慢,比如要一秒,我们Profile之后发现函数慢在Math.sqrt这个第三方函数上,遗憾的是下层Math库的作者声称他那边儿没有进一步提速的空间了,而且他已经不再维护了。然而我们死活就是想要提高这个函数的性能,怎么办?

public double sqrt(final double n) {
    return Math.sqrt(n);
}

代码 1

解决方法倒是有不少的,比如升级硬件,比如换一个更快的库,比如开多线程,或者把Math的作者高薪挖过来。只是这些方案的成本都不低。考虑到这个函数是个纯函数,又考虑到内存并不是很贵,如果又能和用户确认一下他们的输入并不是随机的,有比较高的重复度和局域性的话。把这个函数的运算结果保存下来或许是最多快好省的方案了。实现起来也很简单(注:请无视代码2的拆装箱损耗,那不是问题重点)。

private final Map<Double, Double> rootMap = new ConcurrentHashMap<>();

public double sqrt(final double n) {
    return rootMap.computeIfAbsent(n, Math::sqrt);
}

代码 2

这个实现的一个问题就是它只加不删。如果用户真能保证他们的输入有比较高的重复性的话这个问题倒不大。但是保不齐存在一个2B用户没按约定使用,系统最后就OOM了,然后常见的后果是这个软件员会被拉出来背内存泄漏导致宕机的锅。所以保险起见应该给这个Map设定一个上限。到了就把老化的结果删除。(注:请无视代码中try..finally及iterator的用法,那也不是重点)

private final Map<Double, Double> rootMap = new LinkedHashMap<>();
private final int maximumSize = 1000;

public double sqrt(final double n) {
    try {
        return rootMap.computeIfAbsent(n, Math::sqrt);
    } finally {
        if (rootMap.size() > maximumSize) {
            rootMap.remove(rootMap.keySet().iterator().next());
        }
    }
}

代码 3

如果用户只要求精确到小数点后两位就够了。那么一个简单的提高命中率的改进就是把参数先进行舍入再执行运算。

private final Map<Double, Double> rootMap = new LinkedHashMap<>();
private final int maximumSize = 1000;

public double sqrt(final double n) {
    final double r = round(n, 2);
    try {
        return rootMap.computeIfAbsent(r, Math::sqrt);
    } finally {
        if (rootMap.size() > maximumSize) {
            rootMap.remove(rootMap.keySet().iterator().next());
        }
    }
}

public double round(final double n, final int scale) {
    return new BigDecimal(Double.toString(n))
              .setScale(scale, BigDecimal.ROUND_HALF_UP))
              .doubleValue();
}

代码 4

好了,到目前为止,在不考虑线程安全性的前提下,我对这个函数结果留存的实现方案算是比较满意了。然后才是本文的正题:代码4的问题是什么?如何解决?

问题在哪儿

业务逻辑不明确

想象一下,如果你第一次看到这个代码4,你能否一眼看出哪些代码是业务逻辑的需要,哪些不是?

这还仅仅是为保存一个方法的执行结果,就多出了十几行代码。这还没打Log呢,还没处理异常呢,还没加调用信息统计呢,还没做运行时Profiling呢,还没保证多线程安全呢。

请想象一下,你把上面的这些附加功能都按从代码1到代码4的实现方式加上去,这代码还能看么?

解决思路很简单:业务逻辑应该与非业务逻辑分离

代码冗余、维护成本高

软件开发的一个基本的原则就是写的代码要测试一下。你自己写了个round方法,你就得写相应的测试覆盖这个函数吧。你代码多,测试也会多。这都是实现上的成本。

另一方面,这回的情况是这样:你在实现这个功能的时候,发现需要这个round方法,于是自己写了一个。另一个程序员在界面显示的时候为了做截断可能也会自己写个round方法。大家在同一个Team、同一个代码库上工作,最好是不要出现这种很多人做重复性的工作。怎么解决呢?可以写个utils包,每个人想到什么感觉可能对别人也有用的东西就放在里面。

但是这其实是个悖论,如果一个程序员在实际项目上连类似这种round的方法都去自已写,有两种可能:一、公司什么库都不让用或是用之前要走半年流程什么的,这个可以通过跳槽来解决。二、意味他并没有事先查找可用utils的意识,没有这种意识的话,就算有别的成员放在项目内utils包里他大概也是不会找的。当然,这个情况可以这样解决:谁写了之后,大家开个会广告一下。最终结果大概会是:程序员们为了不开会,非常自觉地都不再写任何utils了。

更好的办法就是,只要有哪个著名的开源库里有的,大家就都不要自己写这种常见的功能。当然这个办法对于一小部分人来说也会有问题:谁知道我要的东西在哪个开源库里有?这个问题只有Google和Stackoverflow能回答。然后Google之后发现了一堆库可以用的,那么用哪个呢?

如果就是不乐意用别人的东西,非想要自己写,也行。在Team里找一两个最NB的人专门负责这些低层框架上的东西。并给所有人做好Training。

最要不得的就是想到什么就写什么。就像代码4那样。它看上去代码质量也挺高,Style也挺不错,目测也没Bug,但是成本高,没法维护、不好拓展。

可重用性差

考虑一下,如果你需要把Math类里的所有函数都做这样的处理呢?我猜会不会有人想用Map<String, Map<String, Object>>什么的?而且只改一个文件就行了呢!

再考虑一下,如果这个函数的调用会抛出异常呢?你是想把异常也保存一下呢?还是想下次重试呢?

上面的Map使用的是最简单的FIFO策略,如果你需要LRU呢?

还有,你这里把round之后的结果当Key,如果有的需要用toString()的结果当Key呢?

你每种情况具体分析分别实现还是为之写个通用框架呢?

在别人的肩膀上搭积木

善用第三方库

这个世界上的肩膀很多,如果想搭好自己的积木就要找到合适的肩膀,最重要的一步是找到那个重复出现的问题是什么,找到那个模式(不限于设计模式,也包括规范、代码模式等)。

限定大小的Map就是个会重复出现的问题。round一个double值也是个会重复出现的问题。显然这些问题Apache和Google都遇到过,并把他们的库公开了出来给大家用。用上之后代码就可以简化很多。(注:Guava也有类似的Map)

import org.apache.commons.math3.util.Precision;
import org.apache.commons.collections4.map.LRUMap;

private final Map<Double, Double> rootMap = new LRUMap<>(1000);

public double sqrt(final double n) {
    return rootMap.computeIfAbsent(Precision.round(n, 2), Math::sqrt);
}

代码 5

这个例子很容易,但是实现中的情况会比这个复杂得多。复杂的不是要实现的功能本身,最难是你能不能找到模式,找到可以重用的现成的东西,然后最重要的:用对。不要拿着锤子看什么都像钉子。比如,如果你觉得Java 8的Stream不错。但是把Stream这样用就不对了。(注:代码来自Stackoverflow的某问题的回答)

// BEING: Wrong usage example
public Double round(final Number src, final int scale) {
    return Optional.ofNullable(src)
                   .map(Number::doubleValue)
                   .map(BigDecimal::new)
                   .map(dbl -> dbl.setScale(scale))
                   .map(BigDecimal::doubleValue)
                   .orElse(null);
}
// END: Wrong usage example

代码 6

这个代码就是在风格或某一特性上走极端了。

剥离非业务逻辑

代码5仅仅是用上了些第三方的库,代码相对简洁了些。但是比代码1还是复杂了3倍。而且你一眼看去,很容易就产生误解,把rootMap当成了核心。而其实Math::sqrt才是。

现在我们目标很明确,就是要让我们的代码只做我们需要做的事情,让库和框架去解决别的和业务本身没关系的问题。代码5做到了一部分,但是不彻底,而且还有侵入性(你要用一个框架就要对现有代码大动干戈的性质)。有没有办法让代码回到代码1的程度呢?

有人可能想到了。AspectJ可以做到。只要在项目里放一个这样的Aspect,然后就直接用代码1就是了。(注:此为示意代码)

@Aspect
@Component
public class StoreMethodResult {
    private final Map<Double, Double> map = new LRUMap<>(10000);

    @Around("execution(* *.Calculator.*(..)) && args(value,..)")
    private Object round(ProceedingJoinPoint pjp, double value) 
        throws Throwable {
        return map.computeIfAbsent(Precision.round(value, 2), v -> {
            return (Double) pjp.proceed(new Object[]{v});
        });
    }
}

public class Calculator {
    public double sqrt(final double n) {
        return Math.Sqrt(n);
    }
}

代码 7

我们解决了代码4的问题,成功把它简化回到了代码1的程度。但是这样搞会引入两个新问题:

  1. StoreMethodResult和Calculator是两个类。单看Calculator你是无法知道Calcuator在执行的时候它的结果会被保存下来。所以你给代码1加一个能力、功能、机制的时候,还是最好在Calculator本身上留下点儿线索。一个代码是注释。更好的办法是用Annotation。按这个思路做下去,就会需要一个Annotation Driven的Aspect。
  2. 代码7本身也存在类似代码4的问题:它也是在重新造轮子。这个轮子叫缓存(Cache)。

通用化方案

这个函数调用结果保存下来的需求实在是太广泛了,肯定已经有现成的通用解决方案了啊。Spring Cache就是其中的一个方法。使用Spring Cache和Spring Boot的实现方式就是这样:

@SpringBootApplication(scanBasePackages = {"your.package.name.*"})
@EnableCaching
public class Application {
    @Bean
    public CacheManager getCachemanager() {
        final SimpleCacheManager simpleCache = new SimpleCacheManager();
        simpleCache.setCaches(Lists.newArrayList(
      new ConcurrentMapCache("math")));

        return simpleCache;
    }

    @Cacheable(value = "math", 
        key = "T(org.apache.commons.math3.util.Precision).round(#n, 2)")
    public double sqrt(final double n) {
        return Math.sqrt(n);
    }
}

代码 8

代码看着好多,但是前面的都是初始化Cache的部分。对于sqrt函数而言,只需要放个@Cachable就行了。

用Spring Cache不是目的,少写代码也不是重点。请注意在这个实现方案下,函数与其附加能力是放在一起的,而与主要业务逻辑又是分离的。这才是重点。库和框架的使用,应该是为了让你更高效地写出更可读、更少Bug的代码。如果你用一个框架之后,发现代码比之前更不好读,你可能得想想你有没有用对,或是你选择的这个框架本身的设计理念是不是合理。但是代码好不好读这个事儿有些主观,有人反而会觉得用了一堆他不会正确使用的框架的代码才是不好读的。我就呵呵了。相关讨论请参考本系列第一篇《从开平方说说写代码应该考虑的事儿》。

JSR-107 JCache

在程序中Cache结果的能力是如此基本,人们早在2001年就开始了把它放在Java框架里的讨论,即JSR-107。但是不知道是不是因为用的人太多,争论过于激烈,这个JSR在2012年才发布了早期预览草案。直到2014年3月才发布了最终版。

Spring Cache是在2011年引入到Spring 3.1 M1的。Spring Cache本身不是缓存框架,它是各种缓存框架与Spring的胶水(虽然它也自带了个实现,但是功能性要差很多)。Spring Cache的实现和JSR中推荐的做法非常相近,再从Spring Cache发布和JSR的时间线看来,或许Spring Cache在推动JSR-107的进程上也发挥了不小的作用。

在2014年4月,JSR-107最终发布的一个月之后,Spring就在4.1版中提供了对JSR-107的支持

然而JCache毕竟和Spring Cache还不是完全一致的。所以使用JCache实现的版本看上去会有些不一样。(注:CacheManager的创建还是需要的,只是略去了。)

@CacheResult(
        cacheName = "math", 
        cachedExceptions = { IllegalArgumentException.class })
public double sqrt4(@CacheKey final double n) {
    return Math.sqrt(n);
}

public double roundedSqrt(final double n) {
    return sqrt3(Precision.round(n, 2));
}

代码 9

不难发现JCache的Annotation和Spring Cache的用法略有不同。于是产生了下面几个不同:

  1. 由于自定义key表达示的缺失不得不引入一个新的函数来实现Round的行为。
  2. cachedExceptions的出现又让我们相对比较容易地处理异常。
  3. 独立的@CacheKey的用法相对直观,但是灵活度不足。

各有各的优劣。没有哪一个是完美的。在实际使用中应该根据实际需要选择最合适的框架。需要注意的是,这种使用方式上的不同,对于框架的选择一般是次要性因素。其使用方式上的不同,往往是其设计理念与目标的不同的外在体现而已。而设计理念与目标,才是选择框架的主要指标与标准。

 综述

像本文这样举一个例子,说明正确使用库与框架带来的诸多好处,是件很容易的事儿。然而实际这样做起来绝不会像说起来这么简单。因为你不仅仅要完成需求,还要识别出其中的模式与通用部分,查找可用的库或框架,然后再学习这些库的正确使用方式并集成到你的项目中。从代码4到代码8,代码没多,但是其实是比自己写一个更难,所花的时间也更多。(尤其是你还并不知道也还不会用那些框架的时候)。然而这些多出来的步骤都不是障碍,最大的障碍是心魔。

当你千辛万苦调了几天Bug把代码跑通大功告成之后,是觉得这是结束?还是刚刚开始?愿意不愿意想一想有没有别的方法做同样的事儿?愿意不愿意去把各个方案比较一下?愿意不愿意承认自己一开始拍脑袋想到的办法可能不是最合适的?如果是项目工期十分紧张的情况下呢?如果你的同事、你的领导甚至整个公司都并不赏识你的做法,只求一个个的项目能按时上线呢?如果你现在已经处于天天加班,天天调试老代码又不敢大改的窘境了呢?

那些都不是真的困境,那些都是自己的心魔。

从一个小函数说说编程语言的学习

PHP是世界上最好的语言[1]。

——有人说

编程语言层面上的东西根本不是重点,把基本功打好,学一门新的语言就是信手拈来。

——又有人说

这俩梗好老。

——我说

引言

上一篇文章《从开平方说说写代码应该考虑的事儿》讨论了如何熟悉并利用领域知识和计算机知识编写更高质量代码。这一篇也是从一个非常简单的编程问题开始,通过分析针对这个问题的不同实现方式,阐释学习一门语言都要学些什么以及怎么样才算熟悉了一门语言。

注:本文无意嘲讽《21天精通XXXX》系列,毕竟或许还是有人可以做到的,尤其是在现在这种有人只要用过就敢妄称精通的大环境下。本文只是想说明一些显而易见却又被人熟视无睹的事实。

一个简单的问题

不少人可能毕业之后就从来没写过哪怕排序之类的基本算法,这很正常,但是没人用不到各类Containers(Collections)。而且,但凡是代码写得足够多又不勤于复制粘贴的懒人,就少不得写些工具类把一些常用操作独立出来。比如这样一个函数:

public static <T> List<T> except(List<T> list, List<Integer> indexes) {
}

我常常拿这个简单的函数当面试题,基本没有人猜不出来这个函数是要干什么,倒是会有个别人表示不知道前面的<T>是干什么用的。有性子急的可能很迅速地就构思出了如下实现,然后下一秒就发现坑在哪儿了。(简洁起见,本文所有代码略去参数为null之类的边界检查):

public static <T> List<T> except(List<T> list, List<Integer> indexes) {
    for (int index : indexes) {
        if (index < list.size())
            list.remove(index);
    }

    return list;
}

代码 1

显然上面的代码结果是不正确的。我们下面就来一步步地分析,看这个函数在Java里应该如何实现,都有哪些坑。主要意图是在这个过程体会,怎样才是充分地并合理地利用一个语言本身的理念与机制去解决问题。我也建议各位看官也先想一想自己心中的答案是什么再往下看。

先说需求到底是什么?

一说到“正确”,一说到“方案”,不少有经验的程序员的标准回答就是“看情况(It depends)”。看什么情况?看到底是要解决什么问题。我曾经也很喜欢这样回答问题,听上去多特么严谨。但是有时候这么说就不合适了,比如面试的时候这么回答就是犯傻,把到手的按自己能力方向展开并引导面试节奏的机会拱手还给了面试官。知道什么情况就说什么。没有具体上下文,要么自己假设一个;要么说自己的实现方式为了通用起见,所以牺牲了这些、这些、这些。即使不是面试,也不要说“看情况”,除非你真打算把情况一一列举出来并分情况讨论,你乐意说可能听的人也没耐心听,因为问问题的人一般只需要其中一个情况,你不嫌累,听者也会嫌烦。

回到问题上来。所以这个函数的需求是什么?需求就是函数签名所描述的那些。就像Array.Sort,它需要知道具体被使用的环境吗?它只要做到最好就是了。

函数签名能告诉你的,并不仅仅是行为,而且可以有实现细节。比如:

  1. 它是一个泛型函数:这大概是一个Util方法。
  2. 它返回一List<T>:所以它应该生成一个新的List<T>,意思应该是不要动参数List。
  3. 下标集合也是List:所以可能有重复,要处理。

等等。

正确性

代码1的问题是,它没有意识到删除了一个元素之后,后面的元素的下标就都变了,而且没有处理参数下标重复的问题。(还有别的问题后面再讨论)

于是一个简单的改进就可以同时解决上面的两个问题。

public static <T> List<T> except(List<T> list, List<Integer> indexes) {
    Collections.sort(indexes);
    for (int i = indexes.size() - 1; i >= 0; i++) {
        final int index = indexes.get(i);
        if (index < list.size())
            list.remove(index);
    }

    return list;
}

代码 2

这个没什么难的,所有人都可以做到这一步。遗憾的是不少人走到这一步就不再走了。因为它已经是正确的了(如果先不考虑对参数的改动)。我不知道是不是因为喝了Bert Lance那句“If it ain’t broke, don’t fix it.”毒鸡汤,并成功解释成了“如果它没坏,就不要改进它,不要重构它,不要动它!而且我也只能做到这里了!

正常情况下,如果并不需要复杂设计与编码就可以做到O(n)的函数,还是不要一开始就写成O($$n^2$$)的好吧?代码写成这样,好意思在文件头上留下自己的名字么?(要不要加是另一回事儿。)

线性时间复杂度

在上面的代码基上,一个可以提高性能的改进是这样的:把要排除的元素标记成null。然后找出不是null的元素。

public static <T> List<T> except(List<T> list, List<Integer> indexes) {
    for (final int index : indexes) {
        list.set(index, null);
    }
    final List<T> result = new ArrayList<>();
    for (final T value  : list) {
        if (value != null)
            result.add(value);
    }

    return result;
}

代码 3

这个代码有两个问题:

  1. 性能还不是O(n)。
  2. 显然如果参数list里本来就有null就不行了。

问题1后面会展开讨论。对于问题2,理论上,可以用一个自己私有的对象实例代替null。

public static <T> List<T> except(List<T> list, List<Integer> indexes) {
    final T DELETE_MARKER = new T();    // Compile Error
    for (final int index : indexes) {
        list.set(index, DELETE_MARKER);
    }
    final List<T> result = new ArrayList<>(list.size());
    for (final T value  : list) {
        if (value != DELETE_MARKER)
            result.add(value);
    }

    return result;
}

代码 4

但是很可惜的是,由于Java的类型擦除机制,类似上面的方式在Java里是不可行的,因为T在运行时不存在。想知道T是什么?在Java里你得多传一个Class参数进来。而C#里上面的代码是可行的(当然需要额外泛型约束才能编译通过,但那不是重点,重点是C#可以知道T具体是什么)。

既然这种方式遇到了些障碍。我们就换一个思路:这个函数一共就俩参数,不for这个就只能for那个。(如果你解决问题真是这么个思路还是不要当程序员了。)

public static <T> List<T> except(List<T> list, List<Integer> indexes) {
    final List <T> result = new LinkedList<>();
    for (int i = 0; i < list.size(); i++) {
        if (!indexes.contains(i)) {
            result.add(list.get(i));
        }
    }

    return result;
}

代码 5

代码5的结果正确,但是性能又退化成O(log(n))或O($$n^2$$)了。想想,为什么是有“或”?为什么有两种情况?

通用性(独立于参数实现)

请思考如下几个问题:

  1. list.contains的复杂度是多少?
  2. list.get的复杂度是多少?

List的某些操作的时间复杂度取决于其实现方式,甚至还会依赖于调用者的使用模式。对于JDK中常见的几个List实现,在本文的使用方式下,他们的理论上的时间复杂度会是这个样子的(有没有哪个跟算法书上说的不一样?请想想为什么):

ListOperations

图1

也就是说,代码5的时间复杂度会依赖于传入参数的类型。这显然不够理想。有没有办法让这个函数的运行效率无关参数类型呢?

问题1出在List的contains方法上,无论在哪种实现方式下,它都是O(n)复杂度的。好像无解啊?那有没有什么Container的contains方法是O(1)的?当然有啊:

public static <T> List<T> except(List<T> list, List<Integer> indexes) {
    final List <T> result = new LinkedList<>();
    final Set<Integer> indexesSet = new HashSet<>(indexes);
    for (int i = 0; i < list.size(); i++) {
        if (!indexesSet.contains(i)) {
            result.add(list.get(i));
        }
    }

    return result;
}

代码 6

问题2出在get操作上,LinkedList的get慢,但是ArrayList的get是O(1)的啊。所以心够宽的话,大不了可以先把整个list复制到一个新的ArrayList里不就结了?没错,但是那代码太美我不敢贴上来。那有没有别的方法呢?想一想现在的情形:我们无论如何是要遍历整个list,而且应该只需要遍历一遍。

这明明就是Iterator的地盘啊。所以用iterator就好了啊。

public static <T> List<T> except(List<T> list, List<Integer> indexes) {
    int index = -1;
    final Iterator<T> iterator = list.iterator();
    final Set<Integer> indexesSet = new HashSet<>(indexes);
    final List<T> result = new LinkedList<>();
    while (iterator.hasNext()) {
        final T item = iterator.next();
        index++;
        if (!indexesSet.contains(index))
            result.add(item);
    }

    return result;
}

代码 7

有经验的程序员其实一开始想的就是这个方法。这就是有经验的程序员和菜鸟的差距。到这一步,这个函数在功能上性能上都达到了预期的要求,而且做到了不依赖具体参数类型。面试的时候,如果有人能在15分钟内做到这一步,我就已经很高兴了。

但是,本文的重点要讲的,还没有开始。上面只是热身:熟悉问题本身。

正题才刚刚开始:那都是Java代码吗?

上面的确都是Java代码,因为它们都符合Java 8语言规范啊,能编译,能运行。但是不觉得有什么问题么?就这么简单的一个问题,怎么需要这么多代码呢?感觉什么地方不太对啊。

感觉不对是因为,这种代码,也不是Java,这是几乎所有OO编程语言及其框架的公共子集。它没有充分利用Java Collections Framework所提供的各类机制,上面的那些代码,放在C#里,放在Python里,放在C++里,仅仅需要修改一下语法和类名就可以同样地正确工作起来。如果学一种语言只是学到这门语言的这样的公共语言部分,其实就可以解决所有编程问题,不再学习任何新的语言点也能写出所有需要写的代码来,只是写起来就像上面一样——繁复。学一门语言,如果只是学到这种“公共子集”程度,的确是可以“一通百通”,信手拈来,几个小时学完。但是这离学会那门语言,还差得很远。

本文要实现的这个函数,大概算是最普通的编程问题了,它所涉及的,是几乎每个Java程序员天天都要使用到的东西。也就是JCF的那些接口,那些类。我说上面的代码没有充分利用Java,所以我们看看JCF的三个主要接口里都有些什么?请仔细看一遍下面两张图,有没有哪个函数名让你眼前一亮或是一头雾水的感觉呢?各位看官看这些方法的时候请思考下面几个问题:

  1. 了解这些API的用法,是否需要依赖工作上的项目提供特别的机会?
  2. 你觉得需要几年的工作经验才能让一个人知道并能在合适的时候正确地使用这些函数?
  3. 知道这些函数的使用,算熟悉Java?精通Java?还是没有直接关系?

JCFInterfaces

图 2

图中,绿色高亮的是Java 8新引入的接口。黄色高亮部分是辅助性函数,就是那种你完全不知道、不使用,也能无障碍地写出Java代码的函数。没高亮的函数,是必须要有的,也必然会用到的,也是那种每个人都不得不知道的,所谓的语言公共子集部分。当然,如果有人说他连remove方法都用不着,或是说从来只用iterator,我也并不觉得奇怪。

充分利用Java

我们看到List接口里有个比较特别的ListIterator或许不是所有人都知道。我们也来看看这个ListIterator和Iterator比有什么特别的地方。注意:ListIterator继承Iterator。

ListIterator

图3

所以稍微对Java多熟悉一些,就可以知道,从ListIterator是可以在遍历一个List的过程中知道当前index而不需要自己维护一个index变量的。于是我们的代码可以简化成:

public static <T> List<T> except(List<T> list, List<Integer> indexes) {
    final ListIterator<T> iterator = list.listIterator();
    final Set<Integer> indexesSet = new HashSet<>(indexes);
    final List<T> result = new LinkedList<>();
    while(iterator.hasNext()) {
        if (!indexesSet.contains(iterator.nextIndex())) {
            result.add(iterator.next());
        }
    }

    return result;
}

代码 8

如果用Java 8,那也可以通过新的removeIf来实现(想想这个函数线程安全吗?):

private static int index = -1;
public static <T> List<T> except(List<T> list, List<Integer> indexes) {
    index = 0;
    final Set<Integer> indexesSet = new HashSet<>(indexes);
    final List<T> result = new LinkedList<>(list);
    result.removeIf(t -> !indexesSet.contains(index++));

    return result;
}

代码 9

如果喜欢用Stream呢,还可以写成这样:

public static <T> List<T> except(List<T> list, List<Integer> indexes) {
    final Set<Integer> indexesSet = new HashSet<>(indexes);

    return range(0, list.size())
            .filter(i -> !indexesSet.contains(i))
            .mapToObj(list::get)
            .collect(toList());
}

代码 10

然而不幸的是,这个代码又出性能问题了。因为它依赖了输入参数list的get方法。在前面的代码中,我们说过,总是可以把list先Copy到一个新的ArrayList中。但是如果传入参数本来就是ArrayList就是多余的了。所以要么就先检查一下参数类型是instanceof ArrayList不就结了?但是如果参数是个自定义的List呢?要不要先给参数做个Quick Perf测试来侦测其get方法是不是O(1)的再来决定要不要先Copy到ArrayList中呢?

在一个成熟的框架里写代码的一个好处是:你可以先假设你遇到的一切General的问题都已经有人遇到过了,而且很可能已经在框架层解决了。你只是得:

  1. 先意识到这个是General的问题。
  2. 形式化规范化这个问题。
  3. 然后用正确的姿势Google一下看看有没有人已经解决了。

比如代码10中的特定方法的性能问题,JDK已经意识到这个问题并且帮你解决了,有个专门的无方法接口叫RandomAccess用来标识一个List的get方法的时间复杂度是不是O(1)或比随机多次get快(详参文档)。那么代码中就可以用这个接口做为判断标准:

public static <T> List<T> except(List<T> list, List<Integer> indexes) {
    final Set<Integer> indexesSet = new HashSet<>(indexes);
    final IntStream indexesToSelect = range(0, list.size())
            .filter(i -> !indexesSet.contains(i));

    if (list instanceof RandomAccess) {
        return indexesToSelect.mapToObj(list::get)
                              .collect(toList());
    } else {
        final List<T> accessList = new ArrayList<>(list);
        return indexesToSelect.mapToObj(accessList::get)
                              .collect(toList());
    }
}

代码 11

当然,这个代码正确工作的前提是,那个自己实现了一个List接口的人,也知道正确地使用RandomAccess接口。

好了,代码8到代码11展示了如何充分使用Java框架来解决这个问题。但是不幸的是,有些代码变得更恶心了(脸好疼)。每种方式都有自己的优劣,应当在使用的时候根据实际需要选择合适的方案。

LinkedList vs ArrayList

以上我们分析过参数的具体类型会对函数性能产生的影响。但是还没有具体讨论过以上代码3至代码9中所创建的临时List对象的选择问题。有心的人可能已经发现,有的用的是ArrayList有的用的是LinkedList。那么用得对吗?更进一步,什么叫用对?

Java自带了这两个主要的List的实现。从图1中可以看出他们在性能上的差别。理论上,我们可以根据自己的使用方式,根据是get操作多还是add/remove操作多来决定是用LinkedList还是用ArrayList。这是我们以上分析的主要依据,如果你Google网上的类似问题,这也是大家的建议。

但是问题是,这个依据对吗?add/remove多的时候,用LinkedList就一定好吗?还有什么其它会影响性能的因素呢?

CPU缓存命中率

CPU缓存命中率主要取决于:所需要访问的数据的大小,在内存中的分布及最重要的访问模式。那么具体到这个函数的CPU缓存命中率,主要受List本身(不包括各个List项T本身)在内存中的分布的影响。请试着想象一下他们两者在内存中的分布情况。大体会如下两图所示。

ArrayList内存分配示意图:

ArrayListMemory

图 4

LinkedList内存分配示意图:

LinkedListMemory

图 5

所以最糟糕的情况会是什么样的呢?你每次访问的LinkedList中的一个Node都Miss CPU的所有一、二、三级缓存。当然实际一般不会这么糟糕,但是绝对比ArrayList要糟糕。缓存不命中的后果就是从内存中读取数据。从内存读又怎么了呢?我们得先看看CPU缓存的访问速度与内存访问速度的差距才能回答这个问题。

从下图可以看出各级缓存结构的访问延迟(Core i7):

AccessLatency

图 6

不难看出,根据问题规模的不同,内存访问会比CPU缓存慢3至50倍。那么这会对LinkedList的性能产生多大的影响呢?看访问延迟,估计有最大50倍性能差吧。不过性能上的事儿,必须要测试一下才知道。

在当前所实现的except函数的环境中,使用List的方式是创建一个默认大小的List,然后只增加不删除。我们就来模拟这个使用方式的下,不同List实现随着问题规模增长时性能的变化。结果如下图所示:

AppendBenchmark

图 7

从图中不难看出,在问题规模比较小(小于一两百万数据)的时候,LinkedList有些许优势,而当问题规模大于五百万数据之后,由于数据局部性不足及CPU缓存容量的限制,LinkedList的性能下降得非常快。(据图可以估计出测试平台的CPU L3缓存大小,不是Core i7)

所以简单起见,你可以在所有的情况下都使用ArrayList,而不用太担心其插入、删除的理论性能比较低的事儿,其数据的局部性可以把大O的系数拉到很低。如果你的所预见的使用情况都只有不到几万数据量的话,用LinkedList也是不错的。当然其实这么少的数据,随便你用什么都可以。

上面这个结论对所有语言都是成立的。如果想深入了解,可以参考《Number crunching: Why you should never, ever, EVER use linked-list in your code again》。Bjarne Stroustrup也在其讲座中表达过同样的观点

有人可能会问,那根据输入的大小选择合适的List实现不就结了吗?也行,就是代码会变得貌似一坨屎,而且还得根据CPU型号选取临界值。如果不想自己的母亲时不时被后来看代码的人问候,还得写注释解释清为什么这么做。另外,调用的人也会很不爽,他会面临这么个问题:这个函数有时候返回LinkedList有时候返回ArrayList。我想多数人会希望API的行为是下面几者之一:
  1. 一直返回一种实现。
  2. 参数是什么类型,也返回什么类型。
  3. 不依赖任何List实现,让调用者根据结果自行构建List。

这样这个API的行为才是可控的。

Java有两个List实现!太漂亮了!

这里想说些题外话,我们如果退一步想想,上面代码复杂度问题的根源,其实是Java本身造成的。它自带了两个List的实现,于是有心的Java程序员们在写代码的时候,无时无刻不在想着:我这回应该用哪个实现呢?但是写C#、写Python什么的,你完全不用考虑这个问题。因为它们都只自带了一种List。因为LinkedList实在是没什么存在的必要。大概唯一的好处就是强迫一部分过于懒惰Java程序员们动动脑子。在某人不小心用了LinkedList,搞出个大大的性能问题,经过简单的分析就可以知道他写的那个List处理函数是多么的糟糕:一个不小心就把一个O(n)的函数用出了O($$n^2$$)的效果。自此LinkedList臭名昭著:性能杀手,效果拔群。于是JDK又引入了RandomAccess接口给这俩List擦屁股。说你们应该在写函数时候多多考虑一下非RandomAccess的List的感受嘛,你看我连接口都设计给你了,你不用?怪我喽?

如果对此有话题有兴趣,可以参看这个知乎问题下面的前五个回答。为什么那么多公司不用 .NET,而选择 PHP、JSP,是 .NET 有什么缺点吗?(这个问题虽然都没问Java,下面一群回Java的,呵呵)有个回答说的好:“.NET的问题就在于不能有效提高使用者的智商。”。Java不仅能,而且擅长。

想我写了快十年C#代码,其间几乎没有细想过List的实现是用数组更好还是用链表更好这个问题(毕竟也很少直接用List)。然而写Java的第一天我就意识到了。这个问题在Stackoverflow上很火。其中有一个排名不高的的回答有些碍眼。他说,LinkedList的作者Joshua Bloch(此人也是Effective JavaJava Concurrency in Practice两本书的作者),发过这样一条Twitter

Does anyone actually use LinkedList? I wrote it, and I never use it.

看这语气,说像是在说:“我写了个用于IQ测试的Java类,你们通过了吗?”

通过以上二节的分析,主要并不是想解释如何在LinkedList和ArrayList之间做取舍,而是想说明一个事实:这些分析里有计算机本身的约束,也有不少是Java语言本身的一些细节,而不同的语言里,针对同一个问题会有不同的设计,不同的细节。如果不了解这些细节,并不能用合理的方式使用这门语言。而这些才是学习语言的难点。(PHP充斥着各种细节,所以成了最好的语言。)

掌握一门语言的法门,只能靠深学活用。能通过一个下午熟悉的,只有语法而已。而语法本身,常常并不是一门语言最重要的部分。甚至连重要都算不上。

接口隔离原则

前面讨论了Java里两个List的现实之间的取舍问题。一个终级解决办法就是不做取舍,让调用方自己去从结果集构建List,如果他需要一个List的话。意思就是说,我们不要求参数是List,也不返回一个List。而只使用完成这个函数所必须的操作(同时不损失性能)。这就是最小接口依赖原则的含义。哪么哪些接口是我们为了实现这个函数所必须要使用的呢?其实就一个:遍历。于是我们的except函数可以被简化成这样。

public Iterable<T> except(Collection<T> list, Set<Integer> indexes) {
}

indexes的参数变成了Set,也更符合这个操作本身的要求。直接返回一个Iterable,可以让使用者按自己的要求和具体环境选择下一步所需要的具体数据类型。我们来考虑如何实现这个函数,虽然从语法上,直接返回一个List是合法的,但是显然已经不符合我们的目标。所以,在这个版本的实现中,真的需要返回一个纯粹的Iterable才能达到效果。(思考题:如果有个子类重写了这个函数并返回一个具体的List,是否算违反了里氏代换原则?)

public static <T> Iterable<T> except(Collection<T> list, Set<Integer> indexes) {
	final Iterator<T> iterator = list.iterator();
	final Set<Integer> validIndexes = indexes.stream().filter(i -> i < list.size() && i >= 0).collect(toSet());

	return () -> new Iterator<T>() {
		private int cursor = 0;

		@Override
		public boolean hasNext() {
			return cursor < list.size() - validIndexes.size();
		}

		@Override
		public T next() {
			while (validIndexes.remove(cursor))
				move();

			return move();
		}

		private T move() {
			cursor++;
			return iterator.next();
		}
	};
}

代码12

这还是用Java 8写的,都写了这么长,如果用老Java,代码将更长。解决长代码的方式也很简单,就是看看这个代码是不是承担了太多的责任。但是这么简单的操作,你说它承担了太多的责任,这不是搞笑么?但是它的确是的。它做的事情,至少可以分成这两步:

  1. 求indexes的补集。
  2. 按indexes选取元素。

于是这个操作可以被分解成这样:

public static <T> Iterable<T> except(Collection<T> list, Set<Integer> indexes) {
    return select(list.iterator(), 
              range(0, list.size()).filter(i ->
                      !indexes.contains(i)).iterator());
}

public static <T> Iterable<T> select(Iterator<T> list, Iterator<Integer> orderedIndexes) {
    return () -> new Iterator<T>() {
        private int cursor = 0;

        @Override
        public boolean hasNext() {
            assert list.hasNext();
            return orderedIndexes.hasNext();
        }

        @Override
        public T next() {
            while (cursor < orderedIndexes.next()) {
                cursor++;
                list.next();
            }

            return list.next();
        }
    };
}

代码 13

情况看上去更糟糕了-_-,但是这个新的select函数在通用性上显然比except要高得多,它也可以被except之外的其它的集合操作函数所使用。其它的集合操作函数,只是需要先通过纯粹的数学运算计算出要提取的元素的位置,然后最后调用select函数。

但是,即使这样,这个3行的except,跟它所需要解决的问题相比,也还是没必要地复杂了。

Iterable vs List

使用Iterable相比使用List,除了缩小了接口依赖之外,其实还有几个的不小的好处。

  1. 延迟求值。意思是这个函数本身运行时间变成了O(1)。
  2. 内存占用从O(n)减小到了O(1)。因为只返回了一个Iterable,而没有返回任何数据。

但是这些好处不是没有代价的。使用Iterable也会带来几个不小的问题。

  1. 隐式依赖参数列表。
  2. 不可重复使用。
  3. 非线程安全。
  4. 由于3,所以不可并行化。

第一点很明显,就当成思考题吧。第二点给个使用环境当引子。

private static <T> void printTwice(Iterable<T> items) {
    items.forEach(s -> System.out.println(s));
    items.forEach(s -> System.out.println(s));
}

代码12和代码13与之前的代码相比,在上面的使用方式下会具有不同的结果。而这个结果是编码者不想看到的。(C#里近似的接口IEnumerable,由于合理的接口设计,没有这个问题。)

可并行性

对于性能要求比较高的环境,可代码本身的并行性也会一个重要的代码可用性及质量的考量。如果用Java 8的流实现,并且实现成纯函数,好处之一就是可以比较简单地支持多线程并行计算。基于代码10,可以通过一个函数完成并行化。如代码14所示:

public static <T> Collection<T> except(List<T> list, Set<Integer> indexes) {
    return range(0, list.size())
                .parallel()
                .filter(i -> !indexes.contains(i))
                .mapToObj(list::get)
                .collect(toList());
}

代码 14

然而如果想把使用Iterator的代码并行化就没有那么轻松写意了。如果你有兴趣的话,可以写一个可并行化的Iterator试试。

Java vs .NET

写了12个版本的Java代码了,断断续续地花了好几天。代码越来越长,却始终找不到一个简洁、高效、灵活、可扩展的实现方式。想想就觉得火大。C#程序员可能早就憋不住了,这个问题的C#版实现方式不要太简洁。

public static IEnumerable<T> except<T>(IEnumerable<T> items, ISet<int> indexes)
{
    return items.Where((t, i) => !indexes.Contains(i));
}

看着这代码,顿时觉得写代码还是那么的美好,而且它具有一切好处:线性时间、延迟求值、参数无关、最小依赖等。写法也简单到我都不屑于提取出来一个函数。想想真心疼Java程序员们。不过或许这就是Java提高使用者智商的方式呢!再说了,我们都知道语言层面的东西都是不重要的。对吧?(这么想心里会舒服些,毕竟我也在写Java。)

如果你在写C#,可能不自觉地就免费地获得了不少的好处,这是一种幸福。但是这并不表示应该在写代码的时候可以无视上述的那些潜在问题。否则就成了Java程序员所鄙视的那种只会拖拖控件的码农界食物链末端生物。

.NET自动地为程序员们做了很多事情,而且做得很出色。但是做得太好,好到程序员代码写烂了它都能工作得还不错,结果不小心把不少.NET程序员都给惯傻了,傻到出点儿问题都不知道怎么下手处理,然后还反过来骂.NET是垃圾。而Java程序员从一上手写代码开始,就要开始解决这样那样的问题,水平慢慢地就被迫堆高了。其后果就是.NET始终被Java压制,这大概是微软始料未及的吧。

那些事儿

在引言里说过,这篇文章只是想说说那些显而易见的事儿。然而一千个人眼中有一千个哈姆雷特。所以我担心不说得清楚些,还是会有人不知道我在说在什么。本文的目的不是解释这个except函数在Java里怎么写也不是为了展示Java里多样的写法。本文要说的那些事是:

  1. 编程没有简单问题,再简单的问题都有多种解法适用于不同的环境。
  2. 学习一门语言从来不是一个简单的事儿。但是学习到这个语言的公共部分是个很简单的事儿(就像大牛们宣扬的,你基本功扎实的话,一两天的事儿)。
  3. 学习一门语言到公共部分就可以解决你工作上的所有问题,而且在这个层次,的确可以说用什么语言写代码都是无所谓的。(因为你总是可以自己搞定剩下的语言特定部分——大凡都通过重新造轮子的方式。)
  4. 深入学习一个语言,从来不是一个简单的事儿。(那怕简单如Java都是这样,我也没有深入学习过Java,我只是简单了解了一下JCF,然后看了点Best Practice而已。)
  5. 在你把一个语言学到一定深度之前,你可能会看到一些代码看不太懂。这个时候正确的积极的心态是承认自己的水平不够,而不是抱怨这个代码的可读性太差、搞得别人都看不懂。
  6. 最好等真精通了一门或几门语言之后再谈论什么一通百通,否则对于个人成长而言遗患无穷。(以Java为类,感觉对java.lang,java.util,java.io包里的所有最新的类的所有方法都了解并能合理使用才能算熟悉级别的吧。)
  7. 选择一门表达力强并且适用你个人理解力极限的编程语言,可以提高效率、节省时间、延长生命、早下班、赚更多的钱。(没最后两点大概没有人关心吧。)
  8. 公司不幸用了Java你也得适应。

参考书目

Cay S. Horstmann, Gary Cornell. Core Java 2, Volume II – Advanced Features (《Java2核心技术 卷II:高级特性》)

Richard Warburton. Java 8 Lambdas: Functional Programming for the Masses (《Java 8 函数式编程》)

Joshua Bloch. Effective Java Second Edition (《Effective Java中文版》)

Randal E. Bryant, David R. O’Hallaron. Computer Systems – A Programmer’s Perspective Third Edition (《深入理解计算机系统》)

Thomas H. Cormen, Charles E.Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms Second Edition(《算法导论》)

Donald E. Knuth. The Art of Computer Programming Vol 1: Fundamental Algorithms Third Edition (《计算机程序设计艺术 卷1:基本算法》)

从开平方说说写代码应该考虑的事儿

引言

很少有程序员需要自己写开平方函数,因为基本所有的语言都自带开平方的函数。更不用说1999年发布的SSE指令集,从CPU指令的级别上支持了开平方运算。当然这依然阻挡不住程序员们探索各种开平方方法的热情。其中最著名的当属John Carmack在开发Quake III时写的那段用精度换速度的Magic Code。如果你更关心如何提高开方函数的速度,你可以参考这篇比较各种方法速度文章,其中有些比单纯地使用CPU指令sqrtss开平方更快。

本文的关注点并不是速度,你甚至可以在本文中看到或许是业界最慢的一些方法。本文专注从软件工程领域的各各视角考量几种风格迥异的开平方函数,通过它们展示如何让代码的可重用度更高、使用上的灵活性更强、复杂度更低,以便于理解及维护。你总是可以在需要的时候,比较容易地提高一个具有高可维护性、设计良好的系统的性能。而一个系统一但由于代码质量上的问题,进入了一种难于理解、难于维护、难以变动、不可重用、无法预测运行结果的状态,如果再想提高其性能什么的,基本上就只能重写了。

导读

本文代码使用的语言是F#。但是你不必担心自己是否学过这个语言,当英语起来应该不会有什么问题。 本文中的示例与求解思路主要来自《Structure and Interpretation of Computer Programs 2nd Edition》,书中使用的是Scheme语言;类似地,那本书是某大学的计算机专门的入门教材,甚至不要求读者有编程经验。但是会需要微积分的基本知识,否则你应该只能搞懂第一个函数。

如果你很熟悉F#,那太好了,本文中的代码都是我一边看F#编程参考一边写的。如果有什么更好的实现方式,也希望你能指出来。

如果你根本不是计算机专业的,本文也值得一读,它或许能解释为什么你的那些计算机专业的同学们既不会修电脑修手机,也无法帮你找回被你遗忘的某网站的密码。因为下面这些才是他们所能解决的问题。

问题引出

求平方根运算的方法有很多,我们初中的时候就学习过手算开平方,还发过一个小册子,上面有各种数据表,用来直接查询一些数的平方根等。但是那些方面都不能方便才用于计算机:手算开平方规则较多,数据结构也复杂,代码量会很多;查表法需要过多的数据存储空间,也不切实际。

非计算机专业的人,很容易错估计算机领域问题的复杂度,一方面是因为人们总是喜欢这样做:先把问题在自己熟悉的领域重新定义,然后用自己在这个领域所熟悉的知识解决这个新问题,并声称原来的那个问题应该也具有同等的复杂度,并可以类似地解决掉。逻辑不好的人会很吃这套。

事实上,很多计算机专业人士在这方面也不惶多让。通常而言,在计算机领域,针对一个问题,找到一个可行的方案通常都是很简单的,并不需要什么高深的知识和精巧的构思。比如,如果你并没有高等数学的知识,仅仅用初、高中数学知识,你或许可以自己想出折半查找法求x的根,在[0,x)区间内以二分法搜索解,并得出像下面这样的代码:

open LanguagePrimitives

let inline abs x = if x > GenericZero then x else -x
let sqrt_v0 x = 
  let rec search f a b = 
    let close_enough target tolerance value =
      (abs (target - value)) < tolerance
    let avg = (a + b) / 2.0
    if a - b |> abs |> close_enough 0.0 0.001 then
      avg
    else
      match f avg with
      | v when v > 0.0 -> search f a avg
      | v when v < 0.0 -> search f avg b
      | v -> avg
  let half_interval_method f a b =
    let valueA = f a
    let valueB = f b
    match (valueA, valueB) with
    | (x, y) when x < 0.0 && y > 0.0 -> search f a b
    | (x, y) when x > 0.0 && y < 0.0 -> search f b a
    | (x, y) ->
      invalidArg "a" "f a must be of different sign with f b."
  half_interval_method (fun v -> v * v - x) 0.0 x

代码1

这个代码可行,结果也正确,只是有些小问题,比如:代码量多、速度慢、精度低。通常人们不把代码量当问题,因为它不能当作任何标准的度量;如果同时又对性能也没有什么过高要求的话,那么这段代码堪称完美。只是如果哪天需要改进其精度,会发现性能会随精度要求的提高而急剧下降。如果又想同时改进其性能,基本就只能整个重写一遍。这种半调子代码,几乎是所有软件项目的潘多拉魔盒,一但被打开,就会变得无法收拾。

问题的根源

写出高质量的代码,是每个软件工程师的职责,一个软件工程师的水平也可以通过其代码质量而得到体现。所以其实没有人会刻意地去写出像上面那样的半调子代码。出现这样的代码的原因,更多是非主观因素。比如相关知识储备不足、比如项目本身风格约束、比如工程进度的压迫等等。他们专注于问题本身,并尽自己所能写出了自己最满意的代码,却可能意识不到它其实是有多糟糕。这也是软件工程和土木工程的最显著不同:土木危楼,一目了然;软件危机,至死方现。

除了对计算机本身和软件工程本身的研究,多数软件工程项目都不仅仅需要软件方面的知识,更需要把软件工程知识与相关领域知识结合起来才能发挥其价值,这也是软件开发工作相比其它工作最特殊的地方之一。所以人们常说搞软件的要一直学习,这是没错的,因为在软件业,任何已经解决过的问题都不是问题,一方面是要学习如何解决这些问题,另一方面,如果想创造出些新的价值出来的话,势必要做一些别人没有想过、没有做过的事情。这些是题外话。

问题分析

求平方根函数,就是这种跨领域问题,解决起来总有两方面的基本工作要做:

  1. 熟悉领域知识。
  2. 找到这个问题在计算机领域的合适的解决方式。

开平方是一个数学问题,在着手设计并编写代码之前,从数学分析的角度深入而全面地了解一下这个问题是必不可少的。在这方面的工作都没有做充分的情况下,就会产生出类似上面的代码。

问题的解决大体如是:对问题本身有一个大局观,才能从中找到更合适的解决方案,同时也可以避免陷入自己的先入为主的知识体系的牛角尖而无法自拔。在这个阶段,有这样几个核心问题要回答:

  1. 问题所在领域的知识有哪些?
  2. 哪些知识可以更好地解决这个问题?
  3. 问题的环境(上下文)是怎么样的(问题没有普适的解法,所以需要针对具体环境)?

这些问题或许有些抽象而空洞,我们下面就开始一步步地求解开平方问题。最后这个函数写成什么样都不重要,重要的是我们如何走到那一步的,以及为什么要走那一步。

问题的求解

基本需求

回到问题上来。我们的目标是希望有一个函数,可以用来计算一个数的平方根,并需要满足以下的要求:

  • 时间复杂度在特定精度下为常量并稳定。
  • 可以灵活地调整所需要的精度。
  • 其他程序员能看得懂。

折半查找法并不符合前两个基本要求。所以它不是一个好的方法。

古巴比伦算法

我们只要简单地搜索一下就可以知道常见的开平方解法有哪些。而且不难发现有些方法在计算机系统上实现起来比折半法还要简单。比如公元前2000年,美索不达米亚人所使用的古巴比伦算法。而且不需要什么高深的数学知识,只是我们初高中没有学习过,不广为人知而已。

其计算过程很简单,如果我们猜g是x的一个根,那么$$\frac{g+\frac{x}{g}}{2}$$会是一个更好的根。用代码实现起来也很简单:

let square x = x * x
let sqrt_v1 x = 
  let rec sqrt_it guess =
    if (abs (square guess - x) / x) < 0.001 then
      guess
    else
      sqrt_it ((guess + x / guess) / 2.0)
  sqrt_it 1.0

代码2

代码2中我们把1.0当作所有数的平方根的初始猜测,然后迭代上面的算法直到误差小于0.001。这个函数基本满足前两个需求。只是没有背景知识的话,有些不太好看懂。对于一些对代码质量没有要求的环境,这个函数也已经完美了。

但是我们希望代码好读一些。而有心的人也会问,巴比伦人的算法的原理是什么。这些问题都还没有解决。

函数抽象

一个非常简单的提高代码可读性的手段是给你读不懂的部分起一个名字。

open LanguagePrimitives

let average x y = (x + y) / (GenericOne + GenericOne)
let close_enough target tolerance root = 
    (abs (target - root) / target) < tolerance 
let avg_damping f = fun x -> average x (f x) 
let sqrt_v2 x = 
  let getNext = avg_damping (fun v -> x / v)
  let rec sqrt_it guess =
    if square guess |> close_enough x 0.001 then
      guess
    else
      sqrt_it (getNext guess)
  sqrt_it 1.0

代码3

与前一个版本相比,这个函数其像仅仅是提取出了几个独立的小函数,给他们起了更明白的名字而已。有没有独立的函数,有没有名字都不是重点。每个语句都可以被提取成一个单独的函数,但是那样做一点意义都没有。重点是:哪些需要被提取出来,哪些不需要。引导你做出那些决定的策略才是重点。很多人不屑于做这种小函数的提取,尤其是在这些函数只有自己用的时候。但是有些有价值的东西,只有你这样做了之后才会发现。

比如上面的代码,经过整理之后,你就会发整个代码段中,与开平方运行有关的只有加粗的那个函数。这是一个非常强的信号,这个sqrt_v2函数的求解过程应该有着某种通用性。这个感觉没有错,那通用的部分就是求解方程的不动点。合理的函数提取就是过程抽象的手段,而提取之后又可以发现新的模式可以进一步抽象。过程抽象本身可以推进过程抽象。

于是那个通用的部分就又可以被提取出来了。于是开平方的代码本身就只剩一行了。它的含义就是:函数$$y=\frac{y+\frac{x}{y}}{2}$$的不动点,就是x的根。

let rec find_fix_point f guess = 
  let next = f guess
  if close_enough next guess 0.001 then
    next
  else
    find_fix_point f next

let sqrt_v3 x = 
  find_fix_point (fun v -> average v  (x / v)) 1.0

代码4

比较代码2、3、4,这三个版本的代码都源自古巴比伦算法。只是代码4具有更高的:

  • 可重用性:find_fix_point, avg_damping, close_enough都是通用方法。
  • 稳定性:基本可以在3次迭代内得到的一个很近似的解。
  • 可读性:代码量少,含义明确。

剩下的两个问题

根据我们之前提出的需求,代码4还存在两个主要的问题。

  • 可维护性比代码1低:因为依赖更多的领域知识,如果不知道古巴比伦算法,基本看不懂这个代码是怎么写出来的。
  • 其精度不可灵活控制:其内部使用了0.001来判断一个解是不是够好。但是显然对于计算$$\sqrt{0.0001}$$就不能正常工作了。

这两个问题是在我们选择古巴比伦法之前没有遇见到的。在软件开发的过程时常会出现类似这种状况:有些问题只有做出来甚至上线之后才会出现

这两个问题不是数学问题,而是纯粹编程实现上的问题。这也正是我们在分析领域问题时所需要注意的,如何把领域问题与计算机系统结合起来,并找到可能存在的问题及适合的解决方案的地方。

类似的,常见的计算机系统在数学领域的约束还有:

  1. 数值表示的精度。
  2. 数值表示的范围。
  3. 数值运算的截断误差。
  4. 不同数值运算间的速度差异。
  5. 数值求值策略对数学公式的敏感性。(等价的数学公示可能会有不同的运算结果。有些是数学本身的问题,有些有计算机系统约束的问题。)

我们下面继续分别解决这两个问题。但是不要忘了基于上面的话,它告诉我们:我们为解决这个两问题而引入的技术,很可能会带来新的问题。这是不可控的。只有做了才能发现。这是软件工程复杂性的另一个体现。《Principles of Computer System Design》一书对此进行了更详尽透彻的讨论。在此就不展开了。

牛顿法

当把一个函数化简到代码4的样子,我们不难又可以发现:如果我们不是要开平方,是要开立方。唯一需要改的地方很可能就是那个不动点方程。但是古巴比伦人没有给出开立方的迭代求解方法。即使有立方的,那任意次方的呢?更进一步地,有没有一个不动点方程可以求解任意一元多项式方程呢?牛顿说有:

假设a是对方程 f(x)=0的一个估算解,且f(x)可导,令:

$$b=a-\frac{f(a)}{f'(a)}$$

那么b是个比a更好的近似解,其中f'(a)是 f(x) 的导函数 f'(x)在a点的值。

很少有编程语言能在语言层面支持求导运算。但是任何语言都可以根据导数的如下定义:

$$Dg(x)=\frac{g(x + dx) – g(x)}{dx}$$

实现出一个求取函数f导数值的函数:

let deriv f dx = fun x -> (f (x + dx) - f x) / dx

并得到一个使用牛顿法的开平方函数:

let newton_method f = 
  let Df = deriv f 0.001
  find_fix_point (fun x -> x - f x / Df x) 1.0

let sqrt_v4 x =
  newton_method (fun y -> y * y - x)

代码5

我们看到这个版本书使用的函数$$y=y * y – x$$就是解为x的方程本身。那么即使你不明白牛顿法的工作方式是什么,你大概也可以猜到求立方根的方法可以写成这样:

let cube_root x =
  newton_method (fun y -> y * y * y - x)

代码6

看上去,基本所有的可导函数的解都可以用牛顿法解。但是事情其实不会这么简单。但是对牛顿法的深入讨论不在本文的讨论范围内。如果有兴趣可以自行参看微积分相关书籍。

另外需要注意的是,在代码5中的Df函数中,又引入了一个新的精度假设值0.001。我们提高了代码的可读性和可扩展性,但是进一步损害了其精度(4次迭代之后在小数点第9位会体现出来)。之后会介绍可以解决这个问题的一个方案。

无限延迟求值流

对于精度问题,有一个看似十分简单且可行但是实际没有太大价值的解决方案:把精度当参数之一。它只是把同样的问题抛给了调用者而已。而对调用者而言,我相信他们更希望拿到一个解之后才能真正确定这个解够不够好,他们也无法预知对所有定义域都合理的精度是什么。当然,他们可以简单地选择一个绝对足够好的精度,比如7位。但是这样做的后果就在是一些并不需要这么好的精度的情况下产生了额外的无用运算。

考虑到开平方运算是迭代进行的,一个思路就是把迭代过程中的每个值都返回给调用者,并在调用者需要下一个更好的解的时候才进行下一步的计算,直到调用者满意为至。

当一个思路产生之后,无论你脑子里是否能立马闪现出具体实现方案,一个好的习惯就是在先计算机领域看看,有没有合适的技术与理念可以用来实现这个思路的,并和你自己的方案进行比较、甄选。然后再着手实现。思路的寻找往往是最难也是最有价值的部分。如果你总是想到什么就做什么,可能所有问题倒是也都可以解决,但是在这个过程中很难会有思路上、水平上的提升。把一年的工作经验用十年,就是这个意思。

了解到计算机系统中可以用来实现上面所述思路的概念至少有:

  1. 流(Stream – a view of system structure):具有的延时求值特性。
  2. 按名调用(Call by name – an evaluation strategy)
  3. 协程(Coroutine – a language feature)

Stream会更适合实现我们所需要的功能。它不依赖于语言,而且应用广泛。LINQ, Reactive Extensions都是基于Stream View设计的。

参考《SICP》上的流实现,不难构建出如下的Stream类和用之实现的Stream化的Sqrt函数:

type Stream<'a>(empty:bool, head:'a, tail:unit -> Stream<'a>) = 
  new(head:'a, tail:unit -> Stream<'a>) = Stream(false, head, tail)
  member this.Head = match empty with 
                      | false -> head
                      | true -> invalidOp "An empty stream has no head."
  member this.Tail = tail()
  member this.IsEmpty = empty
  member this.iterate action = 
    if not empty then 
      action this.Head; this.Tail.iterate action
  member this.iterateWhen action condition = 
    if not empty then
      action this.Head;
      if condition this.Head then
        this.Tail.iterateWhen action condition
  static member Empty = 
    Stream<'a>(true, Unchecked.defaultof<'a>, 
               fun unit -> invalidOp "An empty stream has no tail.")
  static member Map func (s:Stream<'a>) = 
    if not s.IsEmpty then 
      Stream(func(s.Head), fun () -> Stream.Map func s.Tail)
    else
      Stream.Empty
  static member Infinit producer head = 
    let rec stream = 
      fun () -> Stream(head, fun () -> stream() |> Stream.Map producer)
    stream()

let sqrt_stream x =
  let inline avg_damping f = fun x -> average x (f x)
  let getNext = avg_damping (fun v -> x * 1.0 / v)
  Stream.Infinit getNext 1.0

代码7

在这个版本的开平方函数中,没有任何精度设定,也就没有实现上的精确度损失。但是限于我目前的F#水平,我相信这个Stream的实现并不简洁,欢迎大家给出改进建议。(这遍文章里的F#代码大概占我写过的全部F#的50%,选F#只是因为我觉得照搬书上的Scheme代码和用我熟悉的语言解决这么简单的问题都很无聊。)

符号求导

在上面的牛顿法一节中,我们为了求解函数的导数而引入了一个新的精度假设值并导致了一定的精度损失。其根本原因是我们其实根本没有求解出导函数,而是利用了计算机强大的运算能力直接计算出指定点的导数值而已。

如果我们能把导函数方程先求解出来,并用这个导函数计算导数,就不会再有那个精度误差了。也就是说。我们希望能把方程$$f(x)=ax^2+bx+c$$当参数,并求解出$$f(x)=2ax+b$$这个导函数。

高级编程语言基本都自带表达式解析库。F#也不例外。所以符号化求导实现起来也并不复杂,至少不用自己写词法分析器。你当然可以自己写一个彰显实力,只是不太好读的代码多了也就不好管理了。但是需要避免的状况是:你自己写的一个,仅仅是因为你不知道语言里自带了个库,或是不屑于用。这种情况很常见,比如一个例子是:

let abs a = if a > 0 then a else -a

你看不出来问题在哪?那说的就是你。

在F#中实现符号求导,我们只需要把所需要用的如下求导法则

  • $$\frac{dc}{dx}=0$$
  • $$\frac{dx}{dx}=1$$
  • $$\frac{d(u+v)}{dx}=\frac{du}{dx}+\frac{dv}{dx}$$
  • $$\frac{d(uv)}{dx}=u(\frac{dv}{dx})+v(\frac{du}{dx})$$

代码化成一组模式匹配:

let inline sum     e1 e2 = <@@ (%%e1: float) + (%%e2: float) @@>
let inline sub     e1 e2 = <@@ (%%e1: float) - (%%e2: float) @@>
let inline product e1 e2 = <@@ (%%e1: float) * (%%e2: float) @@>

let rec deriv (body:Expr) (p:Var) =
    match body with 
    | Var(x) ->
        if x = p then <@@ 1.0 @@> else <@@ 0.0 @@>
    | ValueWithName(x) ->
        <@@ 0.0 @@>
    | SpecificCall <@ (+) @> (_, _, [lArg;rArg]) ->
        sum (deriv lArg p) (deriv rArg p)
    | SpecificCall <@ (-) @> (_, _, [lArg;rArg]) ->
        sub (deriv lArg p) (deriv rArg p)
    | SpecificCall <@ (*) @> (_, _, [lArg;rArg]) -> 
        let pl = product lArg (deriv rArg p)
        let pr = product rArg (deriv lArg p)
        sum pl pr
    | _ -> invalidArg "body" ("Invalid body: " + body.ToString())

let derivE (exp:Expr) = 
    let (var, body) =
        match exp with 
        | Lambda(var, body) -> (var, body)
        | _ -> invalidArg "exp" ("Invalid exp: " + exp.ToString())
    let derivBody = deriv body var
    Expr.Lambda(var, derivBody)

let sqrt_v5 (y: float) = 
 let exp = <@ fun x -> x * x - y @>
 let f  = exp |>           EvaluateQuotation :?> ( float -> float )
 let Df = exp |> derivE |> EvaluateQuotation :?> ( float -> float )
 find_fix_point (fun x -> x - f x / Df x) 1.0

代码8

现实的项目中没有人会用符号求导技术来写个开平方函数。因为它比前面的版本要慢上1000倍。但是符号求导所带来的灵活性使得这个框架可以用来解决比开平方复杂得多的问题。

这个版本的代码没有使用流,如果需要,可以把它也实现成一个流。在软件工程领域,不同技术方案基本都可以合并而生成一个新的方式。而在非软件工程领域,这种合并常常会由于物理法则的约束而无法达成。这是软件工程复杂性的又一个体现。

综述

本文的主要意图是阐释,充实自身业务领域知识与计算机领域知识对于编写高质量代码的必要性,使用合适的方案解决一个问题能带来多方面的好处。这似乎是一句废话,但是其实这只是一个认识陷阱:人们,尤其是经验越丰富的人,一但认为自己理解了什么,或是利用起了他们的既往经验,他们就常常停止了探索,停止了学习,停止了思考。这对于软件开发是非常有害的。

但是另一方面,如上的发现问题、解决问题、发现新问题的循环是没有尽头的。具有钻研精神的程序员们总能在代码中发现问题并用各种方式尝试解决它,同时引入新的问题。专业的软件工程师能够根据最终目标和环境的不同知道应该往哪个方向走,并且到站了也知道停下来。在一个仅仅需要开平方的地方引入符号求导机制同样有害。

本文中的例子和解决问题的过程纯粹为阐释上述意图而刻意设定,请勿作编程指导,如果你能从中发现自己坠入的认识陷阱就再好不过了。

参考书目

Jerome H.Saltzer, M. Frans Kaashoek. Priciples of Computer System Design (《计算机系统设计原理》)

Harold Abelson, Gerald Jay Sussman, Julie Sussman. Structure and Interpretation of Computer Programs 2nd Edition (《计算机程序的构造和解释》)

Tomas Petricek, Jon Skeet. Real-world Functional Programming – With Examples in F# and C# (《C#与F#编程实践》)

Adrian Banner. The Calculus Lifesaver – All the tools you need to excel at Calculus (普林斯顿微积分读本)

Gerald M.Weinberg. The Psychology of Computer Programming (《程序开发心理学》)

谷强强 版权所有

《那人、那山、那狗》

之前看到片名的时候,以为和《篱笆、女人和狗》有什么亲缘关系,就一直没有看过。于是这部99年的好电影就这样被我错过了十多年。

这部影片所讲述的故事非常平凡,甚至平淡。就是邮递员老爸把工作交给儿子,陪儿子走最后一次邮路的过程。但是也正因为这种平凡而让人感觉真实而亲切,也正是因为这种平凡而更能体现出演员的实力。

然而情节和表演并不是本片最打动我的地方。平心而论这部电影的部分情节转承稍显突兀,刘烨的表演也有些生涩。论艺术品质算不得上乘。但是在这父子感情这件主线背后,还有关于对人生、社会、责任的思考。面上是在讲述这个发生在深山里的小故事,却影射着外面大社会的一些变化和冲突。

我不想赘述拙见,毕竟仁者见仁,智者见智。只是好电影值得更多人去品鉴。

咽炎

本来自己一直也没感觉嗓子有什么不舒服,但是自从上周六体检的时候医生跟我说有慢性咽炎开始,就觉得嗓子的确不舒服了。不疼不痒,就是毛毛的,想咳又没什么东西好咳的感觉。忘了从哪年开始,好像每年都这样,有时严重些,会咳个几个月才会好转。不过用屁股分析一下也能知道这大概是从我大中国冬天的大面积烧煤供暧开始的。虽然我一点热乎气儿都没沾着,这烟霾倒是没少吸。人们把由于工作需要而沾染的疾病叫职业病,不知道咽炎算不算得雾都生活病。我想,大概这就是生活在这样一片蒸蒸日上的沃土上所需要付出的代价。可谁都不想拿健康当代价,所以有了病,无论责任在谁,去医院看病的都得是本人。

上海的三甲医院不少,可也架不住全上海人得个头痛脑热的都去三甲医院看。所以本着不给三甲医院添乱,不让小医院的医生闲得蛋痛,也不纵容自己以排队为由无所事事地看一两个小时手机的原则,我还是去了某医院。我已经去过几次了,也看得出来这医院又贵又没水平,但是我相信看个咽炎应该还是足够了的。

早晨送了老婆到公司,花十分钟绕过罗山高架过来就是这家医院。把车在楼门口停下,拿着医保病例本就进去了。门口问询台没人,我就径直走向了总服务台。

“请问是在这儿挂号吗?”

“你什么不舒服?”

“我嗓子疼。”

“前边左转上二楼找护士。”

“哦,好。”

我正要转身,看见她瞥见了我手上的社保病例本,叫住我说:

“哎,我们这儿社保卡不好刷的,只能用现金或是刷卡,挂号费480。”

“哦,我知道的,中间带的卡可以用吧?”

“保险卡是吧?你上楼问护士吧。”

看来她也不知道。我就按她说的上了楼。记得我上次来的时候还是有人带我去的二楼护士台,现在连门口司仪都省掉了。不知道是不是入不敷出了。

到了护士台,有个看着像是医生的人走过来问我。

“你是什么不好啊?”

“啊,我就是嗓子痛。”

“啊,感冒了吧。”

她转过去又跟护士台的人说。

“我跟你们说过的吧?咱们人可以匀一匀。”

她又转过来打量了我一番,说。

“穿太少啦,感冒了应该多穿一些的。”

“啊,我就是咽炎,应该没有感冒。”

护士问我之前来过没有,又问了出生年月。然后问医生挂哪个科。我始终没说什么话,之前去公立医院看感冒也有把我安排在耳鼻喉科的。人比呼吸科少很多,医生看起来也更有耐心一些。

“就挂王主任的吧。”

“呼吸科好像也没有人啊。”

“不是吧,刚才不是来了一个吗?这个就挂王主任吧。”

然后护士就拿出来了个单子让我签字。

“我来带他过去吧。”

我签好了单子,她跟护士们说。

我就跟着她走了十几步来到一间诊室坐了下来。

然后她笑着跟我说,“这是我们从瑞金医院请来的专家,一个星期才来一次呢。”好像这是莫大的荣幸。

我没说什么,她就走了。

这个老大夫梳了个大背头,看上去很体面。

我说嗓子发毛,他就拿出舌板和手电叫我张嘴,看了一下说。

“是咽炎,扁桃体也有些肿。”

“扁桃体也发炎了?”

“有些红肿,你有扁桃体的是吧?”

“咽炎是急性的还是慢性的?上次体检的时候,他们说我是慢性的。”

“这次是急性的,我给你开些药……”

我有些诧异他这么快就要给我开药。于是问他。

“但是扁桃体发炎不是应该发烧的吗?可我不发烧啊。”

“有些人是不发烧的。”

“那是发烧好还是不发烧好呢?”

“这个看个人体质的。这个细菌和你的人体啊,就像两边对抗。比如如果你白血球高,但是不发烧,说明你体质好的。那,如果白血球不高,也不发烧,也可能说明你免疫系统太弱了。”

他看我好像意犹未尽,便说:

“我给你开个单子看下血项吧。”

然后递给我一个单子,指着旁边的房间说:

“就在隔壁。”

我前面就两个人,我就在门口等着,等的时候我看见我出来的诊室的门口的牌子上写的是“内分泌科”,这还是比较出乎我意料的。看来这个科真是人太少了,都开始出来拉客了。想想别的医院所有的科都人满为患的时候,这边儿一个主任医师在里头无所事事地坐一天。

没想几分钟就到我了,到我的时候换了个老一些的护士,我还挺庆幸。

我坐下,把单子放在桌子上,拉了一下衣袖没有拉上去,正准备把毛衣脱掉。护士说话了。

“要不扎手背吧。”

“手背好扎吗?”

“你这拉不上去我也没有什么办法啦。”

“那就扎手背吧。”

我觉得她有信心那就好。反而扎什么地方我是无所谓的。

她扎的时候我一直看着,刚扎进去的时候我就觉得没有扎正。果然她顿了一下。

“哎呀,血管滑掉了。”

我想着之前抽血没扎好之后的一大片淤青,心里就一群草泥马奔腾。

看着她挪动着针头,一阵阵疼痛从手背传来,我还得保持手一动不动,以防针头在里头把血管撕开个口子。

她调整了一会儿,血才慢慢地流了出来,接上真空试管血出的速度还是很慢。看来扎得真是很不好。本来只要几秒的采血,用了二十几秒才采到一小管底的量。

“血管太细了,又滑。”她解释到。

“应该够了吧。”她自己嘀咕着。然后把针头抽了出来。

“按压两分钟。”

她把一团棉花按在我手背上说。

“血管又细,还滑了,可能有些疼啊。”

“嗯。”

我使劲按着手背,找到个沙发上坐着等结果,想她说的是“滑”还是“划”。

旁边也有一个人在等结果,他旁边有一个女医生在等他讲一些手术上的事情,我没刻意去听,只是听见她在说在这里也可以做,就是费用会贵一些,医保卡也可以用什么的。恍惚间我有一种看见安利的感觉。

等了没十分钟,那个老医生就跑过来叫我。

看了一下血项没有任何有意义的异常。他就接着给我开药。

“我给你多开几种药,有喷的,有冲的,还有消炎的。”

他们医生一说消炎我就就敏感,我瞥了一眼屏幕,看见有头孢二字,我就问

“没有细菌感染也要吃抗生素吗?”

“你的扁桃体有些发炎,而且细菌感染也不一定血项高的。所以还是吃一些的好。”

我没有说什么。

“你看着感觉好了就可以了。慢性的药我也给你开了一些,那些可以接着吃。你听懂我的意思了吗?”

“嗯。”

我想反正我也是看得懂说明书的。

致谢之后我就下楼取药了,看着满满一包计四种共十二盒的各式中西药,我觉得真吃完没病也得吃出点什么病来。仔细看了一下药名,其中有一个是盐酸头孢他美酯,是三代头孢广谱抗生素。我觉得还是不要吃的好。

出门的时候嗓子毛毛的。

手背上还不时还会传来一阵阵的疼痛。