Blog

知其所以然(三):为什么算法这么难?

广大码农同学们大多都有个共识,认为算法是个硬骨头,很难啃,悲剧的是啃完了还未必有用——除了面试的时候。实际工程中一般都是用现成的模块,一般只需了解算法的目的和时空复杂度即可。 不过话说回来,面试的时候面算法,包括面项目中几乎不大可能用到的算法,其实并不能说是毫无道理的。算法往往是对学习和理解能力的一块试金石,难的都能掌握,往往容易的事情不在话下。志于高者得于中。反之则不成立。另一方面,虽说教科书算法大多数都是那些即便用到也是直接拿模块用的,但不幸的是,我们这群搬砖头的有时候还非得做些发明家的事情:要么是得把算法当白盒加以改进以满足手头的特定需求;要么干脆就是要发明轮子。所以,虽说面试的算法本身未必用得到,但熟悉各种算法的人通常更可能熟悉算法的思想,从而更可能具备这里说的两种能力。 那么,为什么说算法很难呢?这个问题只有两种可能的原因: 算法本身就很难。也就是说,算法这个东西对于人类的大脑来说本身就是个困难的事儿。 讲得太烂。 下面会说明,算法之所以被绝大多数人认为很难,以上两个原因兼具。 我们说算法难的时候,有两种情况:一种是学算法难。第二种是设计算法难。对于前者,大多数人(至少我当年如此)学习算法几乎是在背算法,就跟背菜谱似的(“Cookbook”是深受广大码农喜爱的一类书),然而算法和菜谱的区别在于,算法包含的细节复杂度是菜谱的无数倍,算法的问题描述千变万化,逻辑过程百转千回,往往看得人愁肠百结,而相较之下任何菜谱涉及到的基本元素也就那么些(所以程序员肯定都具有成为好厨师的潜力:D)注意,即便你看了算法的证明,某种程度上还是“背”(为什么这么说,后面会详述)。我自己遇到新算法基本是会看证明的,但是发现没多久还是会忘掉,这是死记硬背的标准症状。如果你也啃过算法书,我相信很大可能性你会有同感:为什么当时明明懂了,但没多久就忘掉了呢?为什么当时明明非常理解其证明,但没过多久想要自己去证明时却发现怎么都没法补上证明中缺失的一环呢?

逃出你的肖申克(四):理智与情感

医学上,对于一些罹患严重癫痫症的病人,一种万不得已但颇为有效的方法是切断其大脑的胼胝体。胼胝体是两个脑半球之间的信息高速通道,含有2亿多条神经纤维,一旦切断之后,两脑半球之间的沟通也就相当于从信息时代回到了石器时代。经过这类手术的不幸的病人被称为“裂脑人”。对裂脑人的研究发现了关于人类大脑的一些非常重要的性质,例如《改变心理学的40项研究》第一章“一个脑还是两个脑”里面提到的研究揭示出左右脑在空间感,视觉触觉,语言方面的一些深刻而有趣的差异。 《How We Know What Isn't So》里面则提到另一则非常有趣的有关裂脑人的研究:我们知道,语言能力主要在左脑。对于裂脑人,我们将两幅不同的图画分别呈现给裂脑人的左脑和右脑,呈现给左脑的图画上面是一只鸡爪,而呈现给右脑的则是覆盖着皑皑白雪的牧场。这之后,让他从一堆图片中寻找能跟他看到的图片相匹配的图片。结果非常耐人寻味:裂脑人的左手(右脑控制)会去选择一把铁锹(铁锹铲除牧场上的白雪),而其右手(左脑控制)则会去选择一只小鸡(小鸡和鸡爪配对)。两个脑半球分别根据自己所掌握的信息选择了最匹配的图片。然而,最有趣的地方在于当实验者询问被试为什么选择这两幅图片的时候。裂脑人会说:“哦,很简单啊,小鸡有鸡爪,而铁锹用来铲鸡屎”。

知其所以然(续)

我有一个习惯,看定理必看证明。一个你不明白其证明的定理在我看来比不知道这个定理还要糟糕,因它给你造成一种懂了的错觉。在没有明白背后的证明之前,任何一个定理对你来说都是等价的——等价于背乘法口诀(只不过有的长一点有的短一点)。一个原本美妙的定理,把其证明扔掉就是真正的买椟还珠,暴殄天物。 从现实意义来说,去理解一个定理的证明会带来巨大的好处,首当其冲的好处就是你很难再忘掉它。这一点其实很容易解释——在理解一个定理的证明之前,定理对你而言是一堆没有内在联系的词句,而在理解了证明之后,定理就归约为证明它所需的条件加上逻辑...这是一个树状的知识结构,越往上层走,需要记忆的节点就越少。

逃出你的肖申克(三):遇见20万年前的自己

《Synaptic Self》中曾提出一个发人深省的观点:由于人的大脑是经过漫长的进化年代“堆积”起来的,也就是说,从爬行动物到哺乳动物到高级灵长类这些进化阶段,我们的大脑从只有原始的反射模块,到拥有初步的情感区域,一直到神奇的具有6层结构的“新皮质”所支撑的高级认知能力,一步步走来。这个过程并非上帝预先编程架构好的,而更像是在既有结构上“叠床架屋”,比如,大脑从内到外基本上是按照进化年代来排序的,比如啮齿类等一些小型哺乳动物的新皮质是光滑的,这是新皮质在进化出高级灵长类之前的样子,后来为了解决大脑中空间不够的问题,进化之手发明了大脑皮层沟回,通过这些褶皱,在不增加太多占用体积的前提下使得大脑皮层表面积暴涨,正是这些褶皱使得灵长类进化出独特的高级认知活动,如工作记忆,语言。这种“堆砌式”的进化有它节省和复用的好处(《Kludge》),然而另一方面也带来了奇特的“进化时滞”效应——进化年代较近的大脑模块和较久远的模块之间要达成完美沟通需要一定的时间,在这之前便会造成多个模块之间面对同一个问题决策不一致的问题。 我们的高级认知模块明明知道有些事情很重要,必须提前准备并持之以恒,然而我们内心的另一个小声音却在万般阻挠我们把屁股从床上挪开或者把眼睛从网页上挪开;我们明明知道赌博,烟酒,犯罪是不对的,然而内心的一个小声音却在喋喋不休地催我们动手去做。我们明明知道高糖高脂肪的食物不宜多吃,但内心的一个小声音却总是怂恿着再吃最后一勺(不禁让人想起《傀儡人生》)。令人感到遗憾的是,很多时候在这个争端中败下阵来的却是代表更先进生产力的高级认知模块,更令人感到遗憾的是,在大多数时候我们的高级认知模块似乎根本就没有启用,而是凭借着本能或直觉“自动驾驶”自己的身体(《Gut Feelings》)。

暗时间

如果你有做总结的习惯,你在度过一段时间之后总结自己在某某领域投入了多少时间,建议千万不要粗略地去计算有多少天下班后拿起书来翻看过,因为这样你也许会发现书倒是常翻,但领悟却不见得多深,表面上花的时间不少,收益却不见得那么大。因为看书并记住书中的东西只是记忆,并没有涉及推理,只有靠推理才能深入理解一个事物,看到别人看不到的地方,这部分推理的过程就是你的思维时间,也是人一生中占据一个显著比例的“暗时间”,你走路、买菜、洗脸洗手、坐公车、逛街、出游、吃饭、睡觉,所有这些时间都可以成为“暗时间”,你可以充分利用这些时间进行思考,反刍和消化平时看和读的东西,让你的认识能够脱离照本宣科的层面。这段时间看起来微不足道,但日积月累将会产生庞大的效应。能够充分利用暗时间的人将无形中多出一大块生命。你也许会发现这样的人似乎玩得不比你少,看得不比你多,但不知怎么的就是比你走得更远。比如我就经常发现一些国外的牛人们为什么不仅学习牛逼,连“业余”玩儿的东东也都搞得特牛逼,一点都不业余(上次在《How We Decide》上看到斯坦福的一个牛人,理论物理学博士,同时是世界扑克大赛的前六名保持者,迄今累计奖金拿了六百多万刀),你会奇怪,这些家伙到底哪来的时间,居然可以在不止一个领域做到卓越?

不是书评 :《我是一只IT小小鸟》

设计你自己的进度条 进度条的设计是一个很多人都知道的故事:同样的耗时,如果不给任何进度提示,只是在完成之后才弹出一个完成消息,中间没有任何动态变化,那么整个过程就会让人等得非常焦急,导致一些人干脆把程序关了了事。如果有进度不断更新,那么对整个过程耗时的心理感受就会远低于实际值,用户也不会郁闷到把程序关了。(你有多少次在银行处理手续的时候,看着工作人员把一堆材料不停地倒腾来去,心里多希望他们可以在柜台小窗口上投影一个进度条?) 这里的原因在于,没有进度提示的话,我们无法判断这个等待什么时候才是个尽头。如果有不断增长的进度条,那么我们对于什么时候会达到100%就会有一个粗略的估计,这个估计是一剂定心丸,让我们知道这事情总会并且会在不久的将来完成。 做事情也是同样的道理,善于规划的人,会将目标分割成一个个的里程碑,再将里程碑分割成TODO列表。前阵子流行的GTD方法学,核心的理念就在于,如果你把任务分割了,你就有了进度条,你就知道,事情在不断的进展,你总会完成任务或到达你的目标,你会有一个时间估计。反之如果没有这个分割,整个的任务或目标对你来说就只有两种状态——“完成”和“未完成”,如果不幸是一个比较漫长的目标,那么你会发现你的进度条总是“未完成”,一次又一次的等待未果会耗尽你的耐心,让你下意识的产生“这事什么时候才能完呢?”的疑惑,没有分而治之,你就不知道未来还需要付出多少努力才能达到目的,这就会让你心生怯意,不敢进一步投入时间,免得血本无归。在这样的心理下,不少人就会选择保守策略——退出,以免到头来花了时间还一事无成。

[BetterExplained]遇到问题为什么应该自己动手

我们在生活中总是在不停地试图做最优经济决策,只不过很多时候我们为适应远古社会而进化的大脑未必适用于现代工业社会(《Mean Genes》,《进化心理学》,《How We Decide》),所以很多时候我们可以在超市为选择哪一卷卫生纸斟酌半天(《Predictably Irrational》),却在面对生活中重大抉择的时候轻易就随波逐流(《Paradox Of Choice》)。 我们的很多决策依赖于情绪系统的输出(从进化时间上比较“旧”的大脑部分)(《How We Decide》,《Synaptic Self》),这部分大脑属于典型的经过了漫长进化时间所雕琢过的,决策机制严重适应远古社会的模块(《Mean Genes》),比如在物质贫乏的远古时期,不管什么时候遇到富含热量的食物是必吃无误的,所以我们的情绪大脑只要闻到美食是绝对不去克制诱惑的,长出脂肪又如何?有的是饥寒交迫的时候去燃烧这些脂肪。然而这条规则到了现代这个物质充裕的社会却成了灾难(去查一下美国的肥胖比例?),可谓成也萧何败萧何。这样的例子在《Mean Genes》中还有不少。 我们在学习新东西,遇到困难的时候,为什么会放弃?因为我们下意识中会对所面临的困难以及成功后所得的收益作一个评估(经典的cost/return分析),这里特别重要的是对面临的困难的评估:我们都知道学习任何一门技能,一开始可能还兴趣浓厚,捋袖子上阵,过了一阵子便会遇到一个典型的分水岭,你会发现未知的东西比你想象得要多,困难重重,似乎一眼看过去没法确信什么时候才能掌握,甚至觉得有点Mission Impossible,当觉知到的困难到一定程度之后,我们的大脑便会想:既然很大可能最终失败,甚至看不到成功的可能,为什么要白费力气去学一通呢?还不如省省呢。这是一个聪明的经济决策,去权衡性价比应该是每个经济个体的原则。然而,这个决策笨就笨在,它把困难评估得过高了,因此决策的前提就弄错了。为什么这么说呢?

我在南大的七年

—— 跨进南大校门的第一天,我知道,我自由了。 父亲是个对新事物有强烈兴趣的人,村里第一台电视机是他自己组装的,当时全村人都跑过去看,电视机只能收到一个台,CCTV。座机电话是第一个装的。大哥大刚出现的时候,他也是第一个买来用的,那个时候的移动电话真是贵得离谱。 父亲告诉我的第二件最重要的事情是:遇到任何问题,找书去就行。他在自己的专业中完全是自学的。在不属于自己的专业中(后来买了电脑之后需要学习如何架设公司网站,如何网上营销,如何进行电子财务管理,如何使用各种作图软件制图等等)也全都是靠买书自学。 为什么说到这两件事情,因为这是对我一生影响最重大的两个习惯。第一个习惯给了我学习新东西的强烈动机,有了热忱和兴趣,做事情就不觉得累,就自得其乐。第二个习惯则给了我学习任何新东西的方法——不会么?查书去。(当然,学习一门专业并不完全通过看书就行,但这毫无疑问是至关重要的一个途径。) 高三的时候,父亲买了电脑,我立时对这个神奇的事物产生了强烈的兴趣,每期的《电脑爱好者》和《电脑报》都会买来细细看,有时看到各种小工具、技巧还会摘抄下来,回去在自己家里的机器上捣鼓。那个时候我并不知道这样单纯的兴趣会把我引向一条专业的程序员道路。

[BetterExplained]如何有效地记忆与学习

你所拥有的知识并不取决于你记得多少,而在于它们能否在恰当的时候被回忆起来。 让我稍微说得更详细一点:学习新知识并将其存放于大脑中,最终的目的是要在恰当的时候能够想得起来去使用。因此,学习的有效性显然应该这样来衡量:当遇到需要用到学过的知识的时候,相关的知识是否会自动从你脑海中“蹦”出来,最起码——能否通过有意识的搜索将它们提取出来。 这可不像它听上去那么简单,否则就不会有“掉书袋”、“读死书”这种修辞手法了。 为了更深入地说明这一点,以下是几个著名的关于学习与记忆机制的实验: 《找寻逝去的自我》上提到这样一个例子: 假设这样一个任务:给你一个单词(如brain),要你寻找它的押韵单词(如train)。一段时间之后问你记不记得当时给你的单词是什么了。你可能会不大记得了。现在,如果当时不是要你寻找押韵单词,而是要你联想该单词的含义或功能(如brain的功能),那么你事后回忆起来当时是什么单词的可能性就大大增加了。 对此一个靠谱的解释是:后一种记忆编码方式(称为精细编码)提供了更多的提取线索。所谓条条大路通罗马,任何一个线索被触发都可能顺藤摸瓜地拎出整条鱼记忆来。 一个非常类似的实验是这样进行的(忘了出处了,顺便请教知道的同学:)): 给出同样一组单词,让一组被试数一数每个单词有多少个音节,让另一组被试阅读单词的含义(或者设想单词可以被使用在哪些场景中),之后让两组被试回忆列表上的单词,猜哪一组能够回忆出更多? 这是一个被广为认可的记忆机制,即:我们在记忆的时候将许多线索(例如当时的场景、问题的背景,甚至所处的语言环境、空间位置)一并编码进了记忆,事后能否提取出这段记忆严重取决于提取线索是否丰富、以及在回忆的时候是否重现了记忆时的线索。

逃出你的肖申克(二):仁者见仁智者见智?从视觉错觉到偏见

《Making Up the Mind》上讲了这么一个简单但深刻的实验: 我们看到这张图片的第一反应是:5个凸的按钮,1个凹的按钮。 现在仅仅将图片上下颠倒一下: 在我们眼中立即就变成了:1个凸的按钮,5个凹的按钮。 为什么同一副图片,仅仅是上下颠倒一下,我们就对其作出了完全不同的解释呢? 我们知道,视觉图像要到达大脑,首先要在视网膜上成像(视网膜上密密麻麻地排布着感光细胞),刺激感光细胞形成的神经电冲动然后经过一系列复杂的神经通路到达视觉皮层。但后续的繁杂步骤其实都是对视网膜上成的像的处理。这里,对我们的讨论而言视网膜不妨可以看作一张感光胶片,重点在于视网膜上的像完全是一张二维图片。大脑从图像中提取出来的任何信息都以这张二维图片为原始素材。 那么,究竟大脑是怎么从二维图片中看出(推导出)三维的?