我刚接触计算机的时候,总是为它强大的计算能力所折服,又有些不服气:计算机不就是靠“傻算”取胜嘛——简单重复操作,人类无论怎么锻炼,速度都不可能提升太多,芯片的处理能力却可以按照摩尔定律持续增长。换句话说,计算机算得比人快,“无它,手快尔”。

可是后来,我逐渐发现,用计算机解决许多问题,依靠的并不是“傻算”加上生搬硬套生活中的直观方法,而是“别开天地、自成一体”。我曾经遇到过一个每日运营数据分析的程序,需要10小时才能计算出结果(在当时的业务环境下,这速度完全不可接受),其思维就是生活中的直观方法。我花了一天时间来改进算法,最后只需要5分钟。这个例子我记忆犹新,它充分说明:强大的计算能力,并不能直接带来充沛的解决问题的能力;用计算机解决复杂问题,必须懂得计算机的“玩法”,理解计算机的逻辑,然后才谈得上妥善运用计算能力。

怎样才算懂得计算机的“玩法”,理解计算机的逻辑呢?可以举个排序的例子来说明。

排序,这几乎是我们每时每刻要遇到的问题,对普通人来说,排序就是把一堆东西按大小顺序组织起来;对应的,许多变成语言提供了现成的sort函数,对某些程序员来说,排序就是查找语言文档,调用这种函数即可。但是,事情真的这么简单吗?

为进行排序,需要定义一种关系R用来比较任意两个元素,以常见的小于(<)关系为例,a < b 可以表示为 a R b;现在要做的是,对于排序结果中的任意两个元素Xi, Xj,如果i < j(也就是说Xi在Xj之前),必然存在关系Xi R Xj。

这段话看起来繁杂,意义却很重要。常见的数值类型”天然“就可以进行小于计算,所以对不少程序员来说,a < b中的 <,和返回true或者false的布尔运算符没有区别。这样“凑合”确实可以解决简单问题,却无法处理复杂对象的排序,把人按照身高排序,把货物按照发送的远近排序,把向量按照夹角排序;因为这些时候,排序的对象并不是身高、距离、夹角的度数,而是人、货物、向量。还有些人,大概了解关系的概念,但没有考虑“对排序结果中的任意两个元素,关系都成立”,所以排序结果经常出现“局部有序,全局无序”的情况。

用计算机解决排序问题,必须首先定义“关系”的概念,它在编程语言中存在对应物——常见的数值类型往往会提供默认的排序关系,也可以由用户指定排序关系,比如Java中的Comparator类,Python中的cmp函数,都对应着关系的概念。

以上两点都了解清楚之后,就可以开始选择排序算法。请注意,排序算法与排序关系是彼此独立的——不同的排序关系,可以采用同样的排序算法;同样的排序关系,可以应用到不同的排序算法(这里体现的,是计算机科学中的“责任分隔”、“低耦合”的原则)。

学过算法的人大都记得,常用的排序算法有几种:插入排序、快速排序、归并排序等等。编程语言一般会提供通用的sort函数,确保排序的结果是正确的,所以是不是就不需要了解排序算法了呢?

一般来讲,如果排序的规模比较小(小于千),插入排序是足够快的,也足够简单,同时只需要O(1)的额外空间;如果排序的规模较大,那么选择快速排序比较合适,只是它需要O(log n)的额外空间;如果排序的规模更大,内排序已经不合适,则应当选择归并排序之类的外部排序(External Sorting)算法。

对应到实际开发中,经常会遇到各种场景,比如资源非常有限(典型的就是移动开发),或者运算量非常大(海量数据的处理),这些时候需要程序员理解各种排序算法之后的原理,如果不分青红皂白,只管随意抓一个sort函数来用,结果很可能不只是计算缓慢,而是根本无法实行。所以说,要用计算机高效地解决真正的问题,必须懂得计算机的“玩法”,理解计算机的逻辑。

亨利·福特曾说:“人们需要的是汽车,而不是更快的马”。相应的,汽车时代有汽车时代的规矩和逻辑,同样是赶路,已经不可能再用骑马的规矩和逻辑进行。计算机也是如此,我的经验是,“基本上,计算机可以无限延伸人的能力,前提是懂得计算机的逻辑”,如果在高速增长的计算能力面前还只能延续手工时代的直观方法和简单逻辑,充其量,也只是骑高铁的马夫。