环境驱动编程

环境驱动编程——参加算法论坛后有感

redraiment, 2009-11-07

现场回顾

　　我很荣幸地作为特邀专家入京参加 CSDN 主办的 SD2.0 大会。大会以“移动+嵌入+云”为主题，举办了三天。白天有很多名家讲座，晚上还有5个主题沙龙，我参加的是算法论坛的沙龙。主持人是王尧（左轻侯），曾经先后工作于 Borland 中国公司和微软中国公司，现供职于 IBM 中国开发中心，从事 DB2 的研发工作。与会的还有五位嘉宾：

1. 王炜：北京南天软件有限公司总架构师；
2. 宋兴烈：起步软件公司总工程师；
3. 云风：网易公司技术研发经理；
4. 贾自艳：腾讯搜索技术研发中心研究员；
5. 顾森：北大在校学生（http://www.matrix67.com/）。

　　论坛围绕“在新一轮技术浪潮中，算法又重新站到了重要位置”这一话题展开讨论。本来有几个问题想和各位嘉宾讨论，但由于时间不足，加上我住处较远，只好忍痛在 21:20 出去赶班车，到家已经 23:40 了。不过收获还是不少，我结合大会上其他专家的一些观点，将其整理出来和大家分享。

算法重获重视

　　IT 行业经历了大型机时代、PC 时代、互联网时代，以及即将到来的移动终端+云计算时代。早期由于硬件的先天不足，需要靠软件后天来补；随着硬件的高速发展，一个普通的算法在十八个月以后性能就可以提升一倍，而且大部分经过高度优化的算法都被打包成类库，需要可以方便地调用；但随着互联网时代的到来，用户能够主动参与建设互联网，算法要处理的不再是几台 PC 中存储的数据，而是整个互联网中的信息。

　　引用李德毅院士的话：“集中统一的调度，顺序的、确定的输入，不能描述互联网的工作机理和交互机理，互联网突破了图灵机的描述范畴。”李院士将云计算定义为传统的“图灵计算”结合“大众计算”，“大众计算”意味着至少能处理这浩如烟海的互联网信息，因此算法也必须与时俱进。

环境驱动编程

　　在讨论中，王玮一直强调要灵活地运用算法，这个我以前提的“工具理论”不谋而合。他现场举了个例子：字符串匹配算法中，Rabin-Karp 算法理论上并非最优的，但在实际运用地比较好。这是由于硬盘的I/O效率远低于内存等高速存储器，并非理想的高效随机存储器。其他匹配算法都需要反复读取前面的数据，而 RK 算法只需按顺序从前往后以此处理，在处理大数据时避免了大量的读取操作，因此在实践中的表现反而比其他理论上更高效的算法要好。如果有一天，硬盘的随机存取速度达到了内存甚至寄存器的水平，那这些原本最优的算法可能又会变得没有优势。

　　我在上一篇文章中也提过，真的要深入研究算法，就不可能仅局限于理想状况，必须结合硬件等现实环境。这意味着编程时选用什么算法，受到程序所处环境的制约。比如现在主流操作系统选用“分时机制”而不是“批处理机制”，也是因为受到所处环境需要实时交互的制约，而“分时机制”在频繁调度作业时也需要开销，机器利用率反而比不上“批处理机制”。

　　我将这个思想称作“环境驱动编程”，它是“工具理论”在编程实践中的运用。但要真正能做到“环境驱动编程”并不简单，需要我们有很深厚的算法功底，就像在《做到忘记》一文中提到的，要做到无招胜有招，必须先把所有招数融会贯通。讨论中云风也提到：“在将来，把克努特的《计算机程序设计艺术》三卷本读完，可能只是作为程序员的基本素质！”

我的发言

　　那天云风在现场提问：对一个长度为 N 的数组实现洗牌算法。作为大学生的我初生牛犊不畏虎，也不怕丢人就举手回答了。当时我的原话是：“用一个 FOR 循环从 N 倒退回 1，每次都随机产生一个 0 到 i 之间的数，对应的元素与第 i 个元素交换。”翻译成 C++ 代码就是：

for ( int i = v.size() - 1; i > 0; i-- ) {

    swap ( v[i], v[rand() % i] );

}

　　但几位嘉宾似乎没听清楚，于是我重新组织语言重复了一遍，但好像还是没讲清楚，只好坐下让顾森自己来讲。以前我的队友反映我说话难懂我还不相信，看来真的要去学学口才基础了，呵呵。

我的遐想

　　据顾森自己介绍，他最近在研究中文分词技术。他觉得很多人将计算机“神话”了，认为它无所不能，还举了一个例子：想知道今天北京的天气，只需在搜索引擎中输入“北京”、“天气”这两个关键词即可，但很多“脑子不好使的人”（这是原话）就喜欢输入“今天北京气温多少度？”等计算机无法理解的话。他一说完，我随即也听到了一些反对的声音：“你那样才是脑子不好使，人家的做法才算正常。”

　　我当时脑海中想起 TAOCP 作者克努特在做 ACM 图灵奖演讲时举的例子：“电影制造厂家在1920年强烈地反对有声电影的引进，因为他们为能够不用声音也可以传递词语这样一种方式感到自豪。”因为较少的设施总能给人带来更多的快乐，我之前也大侃特侃《物尽其（奇）用》，以至于很难割舍那些很有美感的方法。我能理解巧妙运用关键词而快速获得信息的乐趣，因为这是一门艺术，并非所有人都能运用自如。但计算机终究需要是一台可以方便使用的工具。在对艺术有了深入了解后，艺术就慢慢地过渡到科学。关于科学与艺术的讨论可以参看克努特1974年获得图灵奖时的演讲。

　　在参加完为期三天的大会后，我一直在思索一个问题：IT 业不断地发展，累计下来的知识越来越丰富，今天进入了移动终端时代，也许明天就迎来量子计算的时代。云风说看完 TAOCP 三卷本也许对很多人来说是玩笑话，但转眼看看现在的大学本科教育，它也非常矛盾：踏踏实实从基础学起，四年时间不够了解冰山一角；讲究实用直接建造空中楼阁，又会缺乏理论基础，很难有突破。如果真有那么一天，花毕生精力也不能全面了解，那这个行业将如何发展？

　　我猜测将来会提有一套新的体系来取代现有的图灵模型和冯式计算机。现在用计算机解决问题，都习惯将问题划分成小规模的子问题来解决，这意味着子问题的性质和问题本身相同，有点像化学中的“分子”，麻雀虽小五脏俱全。但现实就像薛定谔的那只猫一样，都是概率问题：个人的运动时无规则的，但组合成一个整体后是有规律的。就像一个人的形态是稳定的，而具体到每个原子的运动又是无规律的。如果未来的计算机也是如此，能够整个这些并发的无规则计算，由量变引起质变，产生有规则的计算结果，那世界又会如何呢？期待一下 ^_^。

总结

　　整个大会都很精彩，让我这只一直窝在学校里的井底之蛙开阔了视野。这次是我第一回去北京，住处安排得太远，只好忍痛舍弃第二天的沙龙，非常可惜。希望以后还有机会参加！