又见

递归

097

少做事情的另一个案例——中值问题,兼谈沟通技巧

假如有一个巨大的数组(你可以理解成一串数字),如何用最有效的方法找到它的中值?

这道题里的第一个坑是要寻找中值,而不是平均值。

第二个坑是“巨大”这个字眼。

第三个坑是“最有效”这三个字。

在这个问题上,一些候选人会想出一个比排序更好一点的方法,那就是我们前面提到的“N个加油站中找到K个距离最近的加油站”的那个方法。这里,只要把K设置成N的一半即可。

上述方法为什么效率不高呢?其根本的原因是做了太多的无用功!

事实上今天讲的方法和快速排序的方法非常相似,都是用一个随机的数值对数组进行划分。

从这个例子中我们可以总结出如下三点经验:

1. 少做事是提高效率的关键。

2. 一流人才和二流、三流的差别在于,后者虽然也能完成任务,但是未必能把事情做到最好,而一流的人总是能找到在当下最好的方法。而一种方法的好和坏,可以差出几十、上百倍的效率。这就是我讲的工程师水平差一级,贡献可以差出一个数量级的原因。

3. 对所学内容掌握得好坏高低,通常不是靠直接考核那些内容能知道的,而是要看能否运用所学。只有会用了,才是真的学到手了。


098

你的计算机为什么死机了?

在计算机中,堆栈这种先进后出的数据结构和处理任务的策略也被称为FILO(First In Last Out)或者FILS(First In Last Serve)。你可以想象一堆东西,放的时候先放底下的,拿的时候先拿上面的。和它对应的先进先出的数据结构被称为队列(Queue),你可以想象出我们排队的场景,先来先服务,它也被称为FIFO(First In First Out)或者FIFS(First In First Serve)。

通常,计算机在同时需要执行几个程序时,会根据下面几种策略来决定先运行哪一个,后运行哪一个,这些策略大致如下:

第一种,先来的先服务。

第二种,执行起来最省时间的先服务。

第三种,最少占用资源的先服务。

第四种,释放资源最多的先服务。

第五种,优先级高的先服务。

当然上述每一种都有它的道理,也有它的缺点。

如果调度不合理,会有一大堆程序堆在队列中,在用户看来计算机似乎不动了,感觉上就像死机了一样。这是我们见到的死机的第一个原因。

如果程序A依赖于程序B,程序B依赖于程序C,程序C又反过来依赖于程序A,这就形成死循环了,计算机就真的“死翘翘”了,除了重启没有更好的解决方法。

再有第三种情况,计算机软件有一些Bug,各种程序进入队列或者堆栈,在离开时次序搞乱了,也会出现死机。

总之,计算机本身并不具有智能的特性,它表现的好坏,完全取决于管理和调度资源的操作系统。

计算机在资源管理上,很多原则和我们日常生活和工作的原则相似,比如什么时候才有先进先出,先来先服务,或是反过来。但是在两个方面,它的思维方式和我们人完全不同。

其一,它并不追求公平、平等这样道德层面的目标,而是追求运行的整体效率。

其二,由于它的资源调度和使用策略是事先规划好的,尽管计算机科学家事先总是要把各种情况考虑完整,但是总是有一些事先无法预知的情况无法处理,以至于出现拥堵和死锁,而计算机本身是无法解决这些问题的,于是就出现死机,一切必须重新开始。


099

递归——计算机思维和人的思维最大的不同

人有人的思维,计算机有计算机的思维,它们很不相同。如果你要问其中最大的不同是什么,那就是一种被称为递归的逆向思维,它在英语里被称为recursive。相比之下,人的正向思维被称为递推(iterative)。

递推是人本能的正向思维,我们小时候学习数数,从1,2,3一直数到100,就是典型的递推。类似地,我们在学习过程中循序渐进,出发点都是这样正向,由易到难,由小到大,由局部到整体。

从递归方法的过程,即从上向下层层展开,再从下到上一步步回溯,你是否看出了它和我们昨天介绍的堆栈这种数据结构的一致性,即先进后出,后进先出。

递归的本质有两条:其一是自顶而下,其二是自己不断重复。

当然“八皇后”问题只是一个游戏,没有太多的实际意义。接下来,我们就来看一个具有意义的例子——自然语言处理中的语法分析。所谓语法分析,就是把一句话一级一级地分析出语法结构。

人循序渐进地学习是有道理的,但久而久之我们也就将自己局限在自底向上的工作方式中了,天生不适应自顶向下的做事方式。而计算机的思维在这方面则给了我们一个新的启发。

1. 很多时候,计算机的思维方式是自顶向下的,即递归。相比之下,人的思维方式是自底向上的递推。

2. 递归的便利性来自于它本身是一个简单重复的过程。这样可以把一个复杂的问题分解成很多层简单的问题。

3. 递归这种方法和昨天讲到的堆栈那种先进后出、后进先出的数据结构是对应的。

4. 很多时候我们需要逆向思维。

思考题:能否找一个利用递归这种方法解决实际问题的例子?


100

递归算法、管理授权和系统论

首先讲讲递归和社会组织结构的关系。

在日本或者英国资产阶级革命之前,社会的结构便是这种递归式的,也被称为封建式的。

因此,就有了“仆人的仆人不是自己仆人”的说法。这和递归算法不关心下面一层层计算的细节是一致的。

在管理上,不提倡越级管理。

这样递归式的社会结构的好处是明显的。一来每一级官员只要管理好自己的下属即可,至于自己的下属如何管理他们的下属,上级不需要操心。这种做法被称为授权。二来由于各级组织的同质化,当市长的人要学会当省长,照理说是一件比较容易的事情。

在管理上,最糟糕的是被称为“微观管理(Micro Management)”的方法,也就是说上级会规定下级做事的每一个细节。微观管理不仅存在于公司或者其他组织中,也常常存在于我们的家庭中,很多父母对孩子的管理就是微观管理。有这样习惯的人,不妨记住我们这两天谈到的“递归方法”。

递归方法还有一个特点就是下面一层的做法和上面一层的做法一模一样,这在管理上可以认为是共享同一种文化,或者榜样的力量。

类似地,家长对孩子的榜样的力量也是很大的。我们常说,有什么样的家风,就有什么样的孩子。我在《硅谷来信》中说过,每一个熊孩子的后面都有一对熊家长,就是这个道理。

从递归算法我想引申出来的第二个想法就是系统论的思想。递归思想是自顶向下的,先从整体上开始考虑,而不是从细节上开始考虑,这一点和系统论是一致的。

很多人问我,做一件事应该先从最顶层入手,还是先从最底层入手?坦率地讲,这个问题没有标准答案。但是对搞计算机科学的人来讲,需要先做顶层设计,这就如同盖房子先要有一个大致的外观草图,然后才能设计细节。类似地,写一本书也是如此,先要有顶层框架,明确写什么,然后才是补充细节。

递归算法的第三个启发是倒推式的工作方式。

采用递归的思维方式做事情是倒推。比如今年10月1日前要完成某件事情,它被分解成了5个步骤。我们先看看第五步需要多少时间,比如一个月,因此我们就知道第四步一定要在9月1日完成,并且逐步往前倒推。大部分时候你只要一倒推,就会发现事情根本不可能全部做完,这时候就必须舍弃。这样虽然不能保证想做的事情都做到,但是至少能保证交付的事情是令人满意的。

如果把做事情这种倒推的方式扩展到极限,那就是按照生命的长度倒推自己这辈子该做的事情。我在很多场合讲,如果我们是向死而生,我们就会懂得舍弃,懂得做减法的道理。


来信补充 | 计算机如何有效地进行学习?

机器学习,实际上是寻找一种数学模型,让这种模型符合它所要描述的对象。

无监督的学习很容易获得大量的数据,但是由于没有做人工标识,因此计算机相当于自己在找方向,这样机器学习出来的模型就可能不准确,比如把土星的运动轨迹和木星的相混淆。

有监督的学习则相反,一方面输入的数据比较精确,相当于利用了人类的智力,有了一个大致的方向。但是因为人工标识数据不仅成本高,而且很难得到足够量的数据。这种机器学习方法提高到一定程度,就再也提高不了了。

Alpha Go就采用了一个新的学习方法,就是所谓的“强化学习”( Reinforcement Learning)。它的方法其实也很简单,就是计算机在没有人为给定方向的条件下,自己试着走一个方向,然后由人设定的一些原则告诉它好不好,也就是说需要有一个判断价值的反馈信号送还给机器学习系统。

不过这时人会给它一个反馈信息:如果开得对,人就不干预,如果开错了,人会马上手动控制。这样虽然没有标识告诉它怎么开是对的,但是这种反馈接受多了,它将会朝着更好的方向进化。这就是强化学习。

最后为了方便理解,我把有监督的学习,无监督的学习和增强学习通过下面这个比方再总结一下。

有监督的学习就如同凡事你都学习你的上级之前的做事方法,但是水平也不会高出他们太多。无监督的学习就是没人管,自己做,到年底上级根据你的表现给你奖金,奖金就是你做事的目标函数。

强化学习就是没人管你怎么做,如果做得好,上级及时给你反馈;如果做坏了,对你进行批评。


答读者问25 | 用“递归”做事有哪些缺点? 

在具体实现时,很多情况是使用递归的原则设计,递推的原则实现。

1. 苹果手机的操作系统和芯片总的来讲是对单进程进行优化,它一次打开一个进程,而不是同时打开很多个,这样就有任务的切换成本,但是每次执行任务时较快。安卓是优化多进程,打开的应用可以不关,切换成本很低,但是进程太多了就极慢,简单的办法是人为关上进程。

2. 不知道你的三星的操作系统是原装的安卓,还是运营商替你优化的。由于安卓是开源的,很多厂家(小米等)做了不必要的、对手机厂家有利的修改,国内运营商通常给你装一堆没用的东西。

3. 苹果对应用软件开发商要求较严,国内很多App开发者相对规矩点。国内没有官方的安卓商店,什么百度、腾讯、360的,对App开发者要求很松,大部分国内的安卓App都被安卓官方认定为木马软件。你如果装了很多木马,结果我就不说了。另外,360的安全软件在美国本身就被认定为木马。

评论