h8

计算机科学里的诡异

计算机科学里有几个经常让我觉得特别诡异的话题。诡异的本质在于这些话题常常技术性很强,却在道理上常常说不清楚。

第一个诡异的是优化。在UCSD听过George Varghese讲过一个学期的各种路由器算法优化。很多同学还挺喜欢那门课的,但是听得我尤其觉得诡异。网上也经常会贴出各种关于优化的段子,比如神奇的平方根倒数算法,比如神奇的矩阵cache align之类的。很多技术控津津乐道,转发不迭,但我看到之后也觉得特别诡异。

我自己的计算机科学可能还是优化起家的。当年在北京微软的时候也玩过各种各样类似的小把戏,从把数据直接存在mmx寄存器里而不是存在内存里,到用一个字节里的前7个bit存权值,最后一个bit存到上个节点的路径来实现Viterbi算法的动态规划,硬生生把802.11g的OFDM塞到了两个Intel core上。优化的问题各种各样,路数往往都挺像的。

但从学术上讲,优化这个问题常常就显得特别诡异。原因在于,首先,优化面对的问题往往都极为特殊,基本没有什么一般性,往往都是针对某个输入输出范围非常具体的问题,在一套非常具体的硬件上,给出非常具体的时间空间限制条件,做出的一个非常具体的实现设计。而这个设计的本质,往往只是把各种条件限制都搞清楚,然后想一个聪明的办法弄出一个解来,和解很多技巧性极强的奥数题一样:看到了解答之后顺着走一遍很容易证明这个解答是对的,但是却常常完全说不上来这个解是怎么想出来的,更没法证明出这个解是不是最优的。而且问题和限定的条件一但变一点点,原来的解法可能就完全不适用了。所以,这些优化的案例,解法聪明是聪明,却很难说有多少一般性的科学价值,没办法举一反三。

其实优化问题的本质可能很简单。简单地说,就是搜索呗。也就是给一堆限制条件,然后在一个高维、扭曲、非线性、甚至可能到处都是奇点和虫洞的空间里搜索一个足够优的解。这个搜索,需要对问题本质的分析和转化(对解的定义),需要对硬件实现有足够了解(对空间的定义),需要避免明显愚蠢的设计(剪枝),需要时间去迭代。剩下的基本看运气。

可能也不全看运气。MIT似乎就有个年轻教授在做相关的研究。就是你可以写一个没有优化的小程序片段,然后他的程序可以把它自动变成优化过的小程序片段,里面充斥着各种神奇的位操作。论优化的自动化可能,蛮有挑战的课题。这个在特殊硬件条件(比如手机芯片)下可能还挺有实际应用价值一点。

今天晚上太困了,想睡觉了。下篇再说其他的。