061 | 如何有效地找到一个目标

这周介绍的内容相对深一点，通过对比计算机处理信息时和人处理信息在方法上的不同，让大家进一步了解机器的世界，然后从计算机做事的方法上，找到对我们自己平时提高小高和成功率的启发。今天的内容主要是铺垫，会比较简单，但是接下来的三天会比较深入，因此我们还是把基础打得扎实一些，特别是一些概念。

在Q&A2里，我介绍了我的同学，清华大学史春元教授对计算机思维的理解，他通过近30年的科研，体会到Addressing这件事情在计算机科学中特别重要，事实上美国大学的教授们也认为大部分计算机的从业者对这件事的重要性明显低估了，以至于很多计算机工程师还在用人的方式考虑计算机的问题。

今天要讲的第一个概念就是Addresssin。Addressing这个词没有很达意的中文翻译，单纯翻译成编址大家还是不明白（那英语里还应该有多很多不达意的中文翻译呀，所以要用英英翻译而不是英汉翻译。），会问什么叫做编址。其实，我倒觉得更简单的一种讲法是 ——把所有东西进行编号。这样更为准确，也容易懂。在计算机里所有的东西都被编了号，这包括一个个的内存格子，笔记本电脑上那些在机壳上看得见和看不见的借口，计算机通过有线或者无线所连接的各种设备，它们都被编了号。对于这些编号，我们广义地称之为地址。在这周的内容里，我有时也会用到编号这个更通俗点的词，大家记住它和地址是一回事就好了。另外，计算机所见的、处理了的信息，它所运行的指令，也都被编了号。为什么编号这件事情重要呢，它又导致了计算机做事情和我们人有什么不同的？咱们还是先从人的认知过程讲起。

人在早先识别的东西并不多，我们只知道某些动物或者植物能吃，有一个能挡风遮雨的地方睡觉，等等。具体是这只羊还是那只羊，是这个苹果还是那个苹果，是这个山洞还是那个山洞，都没有分别。当后来人类接触的人和东西数量多了以后，人会对它们的特点进行描述，以便于区别（有种感觉，还是当数变大后，人对其整理的办法开始改变，有10本书和1000本书，10000本书处理办法是不同的，blog里的文章也是呀。）。比如因纽特人（就是爱斯基摩人）是根据每个人区别于其他人的特质给人起名字的，比如某个脚大的人被称为“大脚”，歪嘴的人被称为“歪嘴”。《人类简史》也讲了一个类似的故事。仅仅在60年前，南美地区的土著人会对某个头上沾满了鸟屎的人称为“鸟屎头”。也就说明人类区别个体是通过人和物与其它东西明显不同的特质实现的。这种区别和查找目标的习惯，我们一直沿用至今。比如，丈夫会对妻子讲，“帮我拿一下客厅茶几上的那个白色的糖盒子”。妻子到了客厅，直接走到茶几跟前，看到那个白色的盒子，就直接给丈夫了。上面就是今天人典型的做事方法，简单直接。

但是，计算机做这件简单的事情方法却不同。假如在未来的家庭里，丈夫和妻子都是机器人，机器人丈夫向机器人妻子提出的最常见的请求会是这样的：“能否将第三个房间，第六个家具，第九个位置的东西拿给我？”。接下来，机器人妻子拿来的是糖还是一瓶墨水，她并不去管。在这个例子中，你可以看到计算机和人类的行为有两点不同之处。一个是编号代替了实际的对象，另一个则很有趣，如果机器人丈夫以为那个地方放的是糖，但是妻子拿来的是墨水，他可以也会直接倒进咖啡里（哇，对啊！），这其实就是我们遇到的系统宕机的情况。

机器人丈夫能否会像人一样说“帮我拿一下客厅茶几上的那个白色的糖盒子”呢？也是可以的，这时机器人妻子必须进行两步骤操作，第一步是查找，找到客厅对应的房间编号，也就是前面说的地址，茶几对应的家具地址，以及白色糖盒子对应的位置地址，然后把糖盒子拿过来。也就是说，计算机的操作怎么都绕不过编号（过去，我一直把这种设置叫做quantify everything），这也是史教授等人说编号的设计和实现方法特别重要的原因。

计算机为什么要多此一举（对呀，我之前没想到问这个问题）？我在前面讲过，电子计算机从一诞生开始就是要处理大量的数据的，因此它必须采用完全不同于人的方式区分每一个目标（当数据量的量级不断的变大后，那是否意味着计算机要新办法区分每一个目标？）。最早的计算机，无论是算盘，还是帕斯卡的计算器，都没有编号一说。编号这件事始于图灵，在图灵之前，大家用计算机（机械的或者继电器的）算完一件事就完了，很难让它做复杂的事情，因此并不需要编号。图灵超出前人的地方在于他不满足于让计算机只做一种特定的计算，而要让它通过计算来实现一些复杂的功能。大家可以细细体会这两者的差别，以前的人把计算当作目的，图灵是把计算当作手段，实现一些功能才是他的目的。

为了实现复杂的功能，对机器来讲，最简单的方法就是把所有要计算的对象，比如数据，都编上号。在图灵机模型中，所用的数字都放在了一个个编了号（地址）的格子里。计算机对于数据的操作，都是先找到盒子的地址，然后把那个盒子中的数据拿出来处理，处理完内容后，再放回到某个地址中。图灵的这种做法有什么好处呢？主要有两点，首先，他可以用一个数学模型把计算机这个机器描述清楚，这就如同我么可以用变量（variables）x、y、z把一个数学公式描述清楚一样。我们计算简单的数学题和物理题时，直接使用数字，但是计算复杂的问题时，就要先写数学公式，再代入数字，分两步走。这和计算机工作的道理是一样的，因为面对的问题复杂了。当计算机直接操作的是那些编了号的格子时，如何用最少的信息，将所有的东西编号就成了计算机科学里的艺术了（这个data science有联系吗？），以后我们会陆续讲到这点。

另外，计算机科学中也从此有了一个大的课题 —— “查找”（Search），也就是说，在计算机里根据一个东西的特征把它的地址找到。

查找时我们今天要讲的第二个概念。得到了具体的地址后，计算机才好访问（Access）（爬虫？）里面的具体内容。这就好比一个藏书千册的国学大师，要读一本书前，先要用某种方法在几十个书架上找到它的位置，然后才能取出来一样。后一个动作及时计算机里面的访问，这就是今天的第三个概念。事实上，只要我们的藏书超过几百本，找书的时候，就要遵循一些方法了，否则找东西的效率非常低下。接下来，我们就来看看在“查找一个东西”这个具体问题上，人和计算机的思维有何相同和不同之处，今天只讲相同之处，明个天会讲差异之处。

• 第一种是一次按顺序扫一眼，这种方法不仅能够用于找书，其实在街上找某个地址也是如此。这种方法看似慢，其实是人能够最快做到的，因为如果随机乱找，会来回来去找好几次也不得要领。找东西有经验的人都知道要按照顺序找，找过的地方就要争取不看第二遍。这个也是上帝喜欢本人的一个很好的例子。这个笨方法在计算机软件中还会时不时地用到，我们称之为顺序查找。这是我们今天讲的第四个概念，等一会儿我们说说它的应用场景。

• 第二种是字典查找法。查字典的人从来都不用一页页地翻找，而是大约估摸着索要查的字所在的位置，直接打开那一页，如果发现要找的字在这一页的前面，就往前翻，否则就往后翻，总之几次之后，就能找到该找的字。而且爱动脑筋的人在使用一本字典时间长了以后，查字典的速度回提高，翻几次就能找到他想找的字。大家记住这个情况，因为它比绝大多数学计算机的人所了解的二分查找法更快。

那么计算机采用什么方法呢？上述两种方法都用，第一种方法显然是笨办法，但是在一些场景下依然在使用，比如你编辑一篇文章时，要把“北京”这个词跳出来，全部替换成“上海”，除了顺序查找别无他法。第二种字典查找法在计算机中用得也很多，但是由于计算机中的字典只有两个字母与，0和1，因此它有了一个新变种，就是计算机从业者常说的二分查找(Binary Search)这是几天介绍的第五个概念。

关于二分查找的游戏很多人都做过。比如游戏者让大家在心中像一个1~1000个数字，然后你问他问题，对方回答“yes”或者“no”，你用10次一定能够猜出他心中想的数字（哎，怎么算出10次的呀？）。这个花招其实很简单，你第一次只要问他是否小于500，如果yes，说明数字在1~499里面，第二次折半问他这个问题即可。类似地，如果他的回答是否定的，说明对方心目中的数字是在500~1000之间，第二次往大了折半问即可。然后你不断缩小范围，每次减少一半，这样问10次即可，因为2的十次方等于1024，大于1000（这样想的啊！）。这就是二分查找。如果你用这个办法查找某个身份证号的位置（以及相应的个人信息），大约需要31次，不需要把13亿中国人的身份证扫一遍，31次和13次，这个差距还是巨大的。

但是，二分法查找有一个问题，就是所有的数据要实现排序，而排序是有成本的。相比查找，排序的速度要慢得多。因此，是否应该对数据先花点时间进行一次排序，则要看具体应用的情况而定。如果数据进行一次查找，为此事进行排序显然就不合算了，只有当查找的次数足够多，通过次抵消它的边际成本（哇，懂点技术对商业模式的理解大大加深，不懂了，赔死你），为此花一些时间排序才合算。当然，这个场景有一个前提，就是数据是静态的，比如大学的数据库在进行学籍管理时，每一个年级新生入校后，人员是稳定的，对他们按照学号进行一次排序就有意义。但遗憾的是，在大部分现实生活的应用中，数据总是在变化的，比如一个公司的员工，每个有新的进来，老的离开。再比如一个人开车时，位置是不断变动的，周围加油站离他的距离也是变化的。在这种情况下，找一个目标是否要对所有的目标先排序，就值得商榷了。当然在这种情况下，我们还是有办法利用原来数据有序的特点，动态调数据的，然个每次排序所做的工作不要太多，这在我们后面介绍完计算机中“堆”这个概念时，大家就会明白是怎么做到的了。

今天我们介绍了五个概念，此外，通过今年天的内容我们可以看到：

• 第一，当一个问题的规模大到一定程度之后，它就不再是同类小问题的放大， 就变成了另一个问题，需要的解决方法则完全不同。计算机需要对所有的东西进行编号就是这个原因。
• 第二，凡事都有成本，一种方法好不好，是有前提条件的的。
• 第三，世界上大部分事情不是一成不变的，很难处理一次就能一劳永逸享受成果。

除了顺序查找和二分查找两种和人的直觉类似地方法，计算机在寻找目标的方法上，还有优于人的地方，明天讲。


























​