首页 > 程序开发 > 综合编程 > 其他综合 >

白话算法(5) 魂斗罗大战变形金刚(兼做第一部分小结)

2011-04-19

 在若干年前——不对,应该是若干若干年前——要不是过了这么久我还真不好意把它拿出来讲——在那虽值得怀念却并不一定是无忧无虑的——小时候,有一天,老爸突然对我说,“我看到那个游戏机挺好玩的,给你买一台吧”。看官,我当时那个

 在若干年前——不对,应该是若干若干年前——要不是过了这么久我还真不好意把它拿出来讲——在那虽值得怀念却并不一定是无忧无虑的——小时候,有一天,老爸突然对我说,“我看到那个游戏机挺好玩的,给你买一台吧”。看官,我当时那个高兴劲儿你一定可以想见了吧!——我一向爱玩具胜过好吃的东西,可是还真没敢奢望能买那个东西——当时它还是个稀罕物呢,此前我也只是在电视上看到过而已。
  你猜的没错,老爸所说的游戏机就是经典的任天堂红白机。
  话说我站在卖游戏机的专柜前,看着满柜子满墙的游戏卡、宣传画、手柄、激光枪还有大大的电视机,眼睛都花了。老板娘推荐给我的游戏卡,是当时最最经典的《魂斗罗Ⅰ》。我手里捏着游戏卡那硬邦邦的黄色塑料外壳,盯着上面印着的两个拿着机枪的壮汉,脑袋里开始漫无边际地幻想这游戏该有多么好玩——就在这个时候,突然间,鬼使神差地,我问了一个这辈子最傻的问题——
  “呃,这个卡一般可以播放多长时间?”

  如今,这个傻小子已经变成了一个傻大叔(承蒙老天眷顾),并且做了7年程序员,可是,他仍然不敢说自己真的理解了计算机——因为在玩游戏的时候,他仍然会感觉“真神奇呀!”。每次进入游戏,都像是开始了一段新的故事。不像变形金刚,只能从汽车变成机器人,或者从机器人变成汽车。也不像橡皮泥,虽然理论上它是千变万化的,但是它是无结构的——也就是说,你输入什么,它就输出什么,没有交互的感觉。如果硬要作个比喻的话,我觉得游戏就像小河,虽然它有固定的河床,但是,每次都有不一样清凉的河水从你的腿间流过,不同的小鱼追逐嬉戏,跃出水面。

系统的结构

  如果有机会看到人类设计的或者自然界存在的那些自动装置,你常常可以发现它们的结构很大程度上受控于这些自动装置可能发生的故障以及对付故障所采取的相应的预防性测试办法(或多或少有些效果)。说它们能预防故障的产生有些夸张,好似采用了与这个主题不同的一种乐观的描述方法。它们不是预防故障的产生,而是被设计成当大部分故障发生时,系统不至于因此而失效。要消除所有的故障,或者消除故障所带来的影响是不可能的,我们能尝试采取的措施仅仅是设计一种自动装置,使得系统在发生大部分故障时仍能继续工作。这种装置减轻了故障产生的危害,并不是消除了故障本身。大部分人造的和自然的自动装置以及它们内在原理概莫如此。
——约翰·冯·诺依曼

  当年玩变形金刚的时候积攒了不少怨念。我总是盯着不知重复着变了多少次形的机器人发呆,幻想着一定还有某种奇妙的形态没有被我发现。
  如果把变形金刚和魂斗罗都看作一个系统——它具有一个内部状态并存在于一个外部环境中,外部环境也有一个状态,这两个状态总是唯一地决定了下一个内部状态——的话,我很想替小时候的自己问一句,“同是系统,差距怎么就这么大呢?”。与变形金刚的区区2个状态相比,魂斗罗可以接收的输入状态和内部状态几乎是无限多的。确实,许多计算机程序让人感到神奇很大程度上是因为它们可以接收无限多个(至少是数量极大的)输入状态。不过说起来,这个能耐倒也不是计算机独有的,生活中的许多系统也能做得到。
  先说线性系统,譬如切菜机,它的设计者可能预设了它能切黄瓜、切土豆、切苹果……不过如果我们把手指头或者小JJ伸进去它也能照切不误。当然没有哪个傻蛋会塞进去一根钢筋,这倒不是因为说明书上写了“不要放入硬物”(到底有多硬才算是“硬物”?),而是我们知道切菜机里面的刀片碰上钢筋要断掉。这就是悲哀的现实:系统设计者的初衷总是希望用户能把系统当作黑箱来使用,但是用户要想用好系统往往需要多了解一些系统的内部状态和实现原理。如果你硬不告诉他们原理,他们也会去猜测。电视机刚被发明出来的时候,人们猜测那个方盒子里有一个小人。如果人们一直这么不明真相的话,可以想见,在播放A片的时候,该有多少电视机被砸啊。

  在计算机世界里,和切菜机类似的是像AddOne()这样的方法。

view sourceprint?1 static int AddOne(int a)

2 {

3 return a + 1;

4 }

由于硬件工程师和编程语言设计者的努力,对于程序员来说,实现这样的功能就和按下切菜机的按钮一样简单直接。

  再稍微复杂一点的,是像Sign()这样的方法。

view sourceprint?1 static int Sign(int i)

2 {

3 if(i < 0) return -1;

4 else if(i > 0) return 1;

5 else return 0;

6 }

Sign()比AddOne()高级的地方在于,系统能够把输入先分类再处理。在现实世界中,与Sign()类似的系统是公共厕所。当然,犀利的你一定注意到了,公共厕所本身是没有能力把人分为男人、女人、中性人的,要做到这一点恐怕需要复杂的硬、软件设备。

  更复杂的,是像排序算法这种输入是一个集合的情况。它复杂的地方在于,往往不能把集合拆解成单个的元素分别处理,而是得把它作为一个整体来考虑。换句话说,得把输入当作一个系统。这样排序算法就成了“输入是一个系统的系统”,有点别扭。我们不如换一个视角,把输入作为一个系统看待,把排序算法看作是对这个系统的调节。也就是这种感觉:new int[]{3, 1, 2}.Sort()。
  我们在前面几篇曾经提到过无法把集合直接处理成有序的,但是我们忘了问一句“为什么呢?”。答案自然是“因为硬件不支持”。想象一下,如果有这样一个“排序存储器”,它就像一个水池一样能对存储单元产生“浮力”,且存储单元里的值越大受到的浮力越大,而且存储单元还能像潜水艇似的自由地根据受到的浮力浮起、沉下,那么当我们把数据放到这个“排序存储器”里面的时候自然就得到排好序的集合了。
  说到硬件,正所谓巧妇难为无米之炊,了解硬件能提供哪些功能是编程的起点。让我们简单回顾一下计算机系统的硬、软件的分工。计算机硬件本身是无结构的,它就像刚刚买来的乐高拼装玩具,只有一些尚未连接在一起的碎片。这些碎片——四则运算/比较大小的指令、寄存器和随机存储器以及寻址、数据传送、跳转等控制指令——就是硬件可以提供的“直接处理”的功能。当我们编写软件时,就是在把这些碎片拼装成具有某种结构的系统,这个系统接收到输入时,系统的内部状态也会发生改变。
  我这个说法,好像在暗示“代码是结构,变量(里面的数据)是状态”,但是请警惕这种说法。对于AddOne()和Sign()函数,可以认为系统的结构只是那几个if else语句,系统的状态就是返回值。但是,当系统状态由一个集合来表现时,就不那么容易分得清了。考虑第4篇介绍的堆,这个数据本身也具有结构(所谓数据结构),但是它到底是一个一维数组还是一个二叉树全靠解释它的代码来决定,而系统的行为(譬如运行时间),不单依赖于代码提供的结构,也依赖于数据的结构。另一个有趣的例子是第3篇介绍的使用了随机变量的快速排序。即使是同样的输入,每次调用随机化快速排序所耗费的时间(即系统的行为)都不同,这样从黑箱的角度,我们已经无法确定为我们排序的到底是同一个程序还是不同的程序。我们只能说代码和数据共同体现系统的状态。结构和行为,作为状态的一部分,也是由代码和数据共同体现的。换句话说,虽然程序的代码是程序员一早写好的,但是程序运行起来之后的结构却是动态的。正因为如此,我们可以期望有一天程序能够学习、推理、创新、解决问题、具有自我意识……
  为什么冯·诺依曼说“要消除所有的故障,或者消除故障所带来的影响是不可能的”呢?作为一个系统设计者,难道可以接受这么令人沮丧的结论吗?要消除所有故障,系统设计者必须做到:1)将系统的输入严格限制为预设的有限的范围之内;2)确保除了输入之外,系统的内部状态不会被任何其它的外部状态所影响。在局部上,人们的一些努力(如类型安全、DEP等)使我们向这两个条件迈进了一大步。但是如果我们把系统放到无限宽广、无限深远的外部环境中,就会发现,要想百分之百地满足这两个条件只是系统设计者的一厢情愿罢了。其一,往往很难限制输入的范围。像“被强行灌入毒药而变成小正太”这种事总是会发生。其二,很难预先穷举出所有可能导致系统故障的因素。放入太硬的东西会使切菜机的刀片断掉;放入软的但是韧性很强的东西刀片又割不断;放入太粘的也不行;酸性太强也不行……其三,你可以只允许测试过的输入,但是这样将大大减弱系统的功能。没有人会愿意买一个只能切黄瓜和土豆的切菜机(放入其它东西会导致机器立刻自爆);一个算法若只能排序10个元素也足以让人无语了;其四,虽然也有像变形金刚那样只有2个状态但仍然卖的很好的系统,但是我们仍然无法阻止变形金刚内部的螺丝钉被腐蚀、生锈,它的朔料外壳在过热或过冷的环境中变形(变形!!)或者碎裂。
  更别提还有Hack这种有趣的事情。系统总是适用

相关文章
最新文章
热点推荐