跳至主要内容

环境驱动编程

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

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 三卷本也许对很多人来说是玩笑话,但转眼看看现在的大学本科教育,它也非常矛盾:踏踏实实从基础学起,四年时间不够了解冰山一角;讲究实用直接建造空中楼阁,又会缺乏理论基础,很难有突破。如果真有那么一天,花毕生精力也不能全面了解,那这个行业将如何发展?
  我猜测将来会提有一套新的体系来取代现有的图灵模型和冯式计算机。现在用计算机解决问题,都习惯将问题划分成小规模的子问题来解决,这意味着子问题的性质和问题本身相同,有点像化学中的“分子”,麻雀虽小五脏俱全。但现实就像薛定谔的那只猫一样,都是概率问题:个人的运动时无规则的,但组合成一个整体后是有规律的。就像一个人的形态是稳定的,而具体到每个原子的运动又是无规律的。如果未来的计算机也是如此,能够整个这些并发的无规则计算,由量变引起质变,产生有规则的计算结果,那世界又会如何呢?期待一下 ^_^。

总结

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


评论

此博客中的热门博文

AutoHotKey 新手入门教程

AutoHotKey 真是一个好玩的工具!短短几行代码就是先了“窗口置顶”、“窗口透明”等功能,之前我还特意为此装了好几个小工具,现在都可以卸掉了。闲来无事,就把 Quick Start 翻译了一下,我没有逐字逐句地翻译,有时候我嫌原文罗嗦就用自己的话概括地描述了一下。 原文地址:http://www.autohotkey.com/docs/Tutorial.htm 教程目录 创建脚本 启动程序 模拟鼠标键盘 操纵窗口 输入 变量与剪切板 循环 操纵文件 其他特性 创建脚本 每个脚本都是一个纯文本文件,由一些能被 AutoHotKey.exe 执行的命令组成。一个脚本可能还包含 热键 和 热字符串 。如果没有热键和热字符串,脚本在启动的时候就会从头依次执行到尾。 创建一个新的脚本: 下载 并安装 AutoHotkey。 右击鼠标,选择 新建 -> 文本文档 。 输入文件名并确保以 .ahk 结尾。例如:Test.ahk。 右击文件,选择 编辑脚本 。 输入以下内容:#space::Run www.google.com 上一行的第一个字符 "#" 代表键盘上的 Windows 键;所以 #space 表示在按住 Windows 键后再按空格键。"::" 后面的命令会在热键激活后执行,在本例中则会打开谷歌主页。继续按下面步骤操作,来执行这个脚本: 保存并关闭该文件。 双击该文件来启动它。在系统托盘里会出现一个新图标。 按下 Windows 和空格键,网页会在默认的浏览器里打开。 右击系统托盘里的绿色图标可以退出或编辑当前脚本。 注意: 可以同时启动多个脚本,并且在系统托盘里都会有一个相应的图标。 每个脚本都能定义多个 热键 和 热字符串 。 想让某个脚本开机即启动,可以将它的 快捷方式放到开始菜单的启动目录里 。 启动程序 命令 Run 可以运行程序、打开文档、网页链接或快捷键。请参看以下示例: Run Notepad Run C:\My Documents\Address List.doc Run C:\My Documents\My Shortcut.lnk Run www.yahoo.com Run mailto:someone@somedoma

sed单行脚本学习笔记

Sed单行脚本学习笔记 redraiment, 2009-12-31 回家真好   前段时间忙着找工作、项目结题、写报告……反正是总有做不完的事情,哈哈。好在暂时告一段落了,应老妈强烈要求回家休息几天。这次回家除了这身衣服,只带了一本《 sed与awk 》,我觉得这种小册子最适合茶余饭后休闲之用。如果你也有兴趣学 sed ,推荐你一起看《 sed与awk 》(可以在 谷歌图书 在线阅读英文版:D)。   花了两天时间,看完了前面 sed 的部分。要掌握一个工具就要熟悉它的规则,man 等参考手册向我们介绍这些规则,教程则演示如何使用这些规则,但要将这些规则运用自如,还需要去理解别人的代码并尝试自己解决问题。在 SourceForge 上有份经典的文档:《 SED单行脚本快速参考 》(单行脚本要求命令行长度小于65个字符),由 Eric Pement 整理, Joe Hong 翻译,通篇阅读后获益良多,故撰此文和大家分享。 精彩脚本摘录 # 在每一行后面增加一空行 sed G   在参考手册中,命令G的作用是“将换行符后的保持空间内容追加到模式空间”。就像前文提到的,看过教程后只是熟悉了规则,还不能将规则运用自如,我自己写的代码是:sed 's/$/\n/',就是因为我还不熟悉每个命令会对模式空间产生什么影响。所以看到这段参考代码时感觉眼前一亮:“原来还可以这样写!” # 显示文件中的最后10行 (模拟“tail”) sed -e :a -e '$q;N;11,$D;ba'   假设文件有 N 行(N 大于10),显示最后10行也就意味着删除前的 N-10 行。在多行模式中,命令“D”可以删除模式空间中第一行;命令“N”可以将下一行追加到模式空间中,建立多行模式。因此问题转化为:“1)将整个文件的内容放入一个模式空间中;2)删除前 N-10 行。”其中问题1)通过控制语句“b”来解决:sed ':a; N; ba';至于问题二,模式“1,$”代表文本中的所有行,因此紧跟着的命令被执行N次,同理,模式“11,$”匹配后面的 N-10 行,因此“11,$D”一个执行了 N-10 次。   其实,在 GNU sed 中,命令“$q”是可以删掉的,因为在最后一行执行命令“N”就会因出错而自动退出。   另外,在

DAO层测试

<dependency> <groupId>com.wix</groupId> <artifactId>wix-embedded-mysql</artifactId> <version>2.1.4</version> <scope>test</scope> </dependency> 利用 wix-embedded-mysql 把MySQL嵌入到进程中,作为内存型的MySQL来做单元测试。 脚本: resources/migrations/mysql/<database>/<timestamp>_<action>.sql 但多个项目需要共享数据库脚本,可能可以用 git submodule 共享。