Beautiful Code

<Beautiful Code>一书不算薄,里面的38位作者,也算得上个顶个的牛。但总的来说,信息量却不太大。

耐着性子看到最后一章:<Writing Programs for “The Book” by Brian Hayes>,却突然有眼前一亮的感觉。

我对Brian这个人不太熟悉,从书后的介绍中得知,Brian是<American Scientist>计算机专栏的作者。比起其他几篇文章,这篇在文字上,明显要自然流畅一些。

Brian在本书中讨论的问题,其实很简单—判断三点共线。

我们人在判断这个问题的时候,自然可以简单的进行目测。当目测不足以区分的时候,可以连接任意两点,接着看另外一点是否在那条直线上。

放到程序里,最自然的思路莫过于,过同一点计算并比较斜率。然而,诚如书中所言,计算斜率的方法有一个边界条件—平行于Y轴的直线斜率不存在。对于这些边界条件,不得不加上条件跳转去处理。更为糟糕的是,如果三个点中,有两个点都是原点,那么这三点肯定是共线的,但这两个原点的斜率,却可以为任意值。

我们注意到,很多边界条件是由坐标系带来的。因此,如果我们选择计算三个点两两之间的距离,并且比较短边长度之和与长边长度。我们可以绕过很多泥沼,代码也因此变得简洁。

然而,这样做依然存在一个固有的问题—有理数的点之间,可以有无理数的距离。这当然是计算距离时,开根号给闹的。无理数距离的问题在于,这种精度问题,并不是由问题的输入带来,而是由中间步骤产生的。

Brian最后给出Jonathan Shewchuk的方案是,计算三点所构成三角形的面积,并与0作比较。

计算面积比起计算边长的优势在于,面积可以通过同顶点两个矢量的叉乘来计算(如下图所示)从而避免了开根号。也由此把精度问题,限制于输入数据的精度。

|x1-x3 y1-y3|
|x2-x3 y2-y3|

最终代码如下(三个点分别为p, q, r):

(defun area-collinear (px py qx qy rx ry)
(= (* (- px rx) (- qy ry)) (* (- qx rx) (- py ry))))

这个例子虽然极其简单,但把它稍稍一般化,就能反映出很多问题:

大部分情况下,我们会写出类似于计算斜率的直觉算法。更糟糕的是,我们甚至可能漏掉斜率不存在,或者斜率为任意值的边界。
DEV CC之后,QA一测,发现了斜率不存在的问题,于是代码里加上一句if条件分支,注释上bug号。
Beta之后,用户complain如此明显的,原点斜率不存在的bug,大家开会聒噪一番,DEV和QA相互指责一番,于是乎又多了一句if。
ZB之后,大家怀着忐忑的心情RTM,指望CRT不要过来抱怨,用户报了一堆bug,又得加班。

于是在质量保障指引下,代码距离美丽的标准渐行渐远。直到某一天,performance真正成了问题。

牛人大笔一挥,升级算法为计算边长,更新产品名称为XXX 2009(Engine Updated)。
不久,挑剔而又无聊的客户开始抱怨精度问题,大家讨论一番,牛人决定By Design回去,并且在Readme里面的Known Issues里加上一句说明。
当时间沉淀了计算边长的代码,这段代码也就成了不朽的丰碑和牛人津津乐道的谈资。

这时候,偏有不喑世事的小屁孩说,为什么我们不计算面积呢?
牛人说,我呸…哪凉快哪待着去…

牛人就是牛人,小屁孩暂时还不明白一个道理。如果你写了计算面积的代码,你就作出了一个假定—人们都知道用叉乘来计算面积。
小屁孩以为自己的长篇注释,能够把问题说清楚。然而,忙碌的人们谁会想听你一个小屁孩的教导。
这时候,小屁孩不得不感叹思科电话设计的完美,即使你把听筒拿起来,依然能有人打爆小屁孩的电话,要他亲自,一遍又一遍的解释。

世界的完美,往往就体现在对于完美的求不得与不可求。