码农第1期

pdddy

贡献于2013-09-20

字数:0 关键词:

第 期碼農 codeMaker() 2012/07/05 1 • 本期专题:算法 • 对话归隐的大师: 高德纳 • 海量用户积分排名算法探讨 • Matrix67的Aha!Moment • 终身Coder,可以吗? • 工程的本质问题是组织 码农 i 卷首语 1 所谓码农 本期专题:算法 3 对话归隐的大师——Donald E. Knuth(高德纳) 11 关于TAOCP中用集合论对算法进行严格数学定义的理解 24 海量用户积分排名算法探讨 33 图说归并排序 图灵访谈 41 终身Coder,可以吗? 47 Matrix67的Aha!Moment 59 柳泽大辅谈如何想出好创意 iTran乐译 63 移动为什么重要? 70 Android 应用该是个啥样子? 87 为什么Pinterest是最让人失望的社交网络? 91 JavaScript并行运算新机遇——Web Workers的神奇魔法 118 别把自己当个超人——给初级程序员的⼀点小小建议 出版的未来 127 创意帮创意——⼀个关于图书、出版和筹款的故事 目录 码农 ii 当红书榜 153 看看大家都在看什么? 好书妙评 154 《七周七语言》 155 《算法(英文版 第4版)》 157 《罗素的故事》 158 《黑客与画家》 159 《重构:改善既有代码的设计》 TEAP早期试读 160 为什么选择MongoDB? 168 工程的本质问题是组织 编辑手记 177 檐头滴水话求职 社区动态 182 乐译7期 183 专家审读第3期 184 7月听课去 对于码农这个称呼,有些人喜爱有加,有些人不以为然。区别在 于对待“农”这个字的感觉。农当然是指农民,这个词寓义很丰 富,既可以说它伟大,也可以说它渺小。说它伟大,是因为我们 的生存离不开农民,而且中国⼀直是个农业为本的国家,曾经说 是百分之八十的人是农民,这意味着往前翻⼀两代,你我众人皆 是农民出身。以此观之,农可谓大哉。说它渺小,则是因为大家 的观念里,农民意味着有很多缺点,冠冕堂皇的说法是劣根性, 比如目光短浅、思维陈旧、自私小气,等等,总之是为我们受过 教育的人群所看不惯的种种毛病——这些毛病虽然我们自己也 有,但是我们看不见——于是乎“农民”成为了骂人时常用的字 眼。 其实,把自己的编程生涯与田间地头的锄禾日当午对应起来,确 是有那么些相似之处的。你能想象得到,田间整齐栽种的秧苗, 与屏幕上显示的错落有致的代码行有几分神似。各种庄稼的种植 是有讲究的,正如你要注意编程风格。施肥灌溉,犹如你对代码 进行的编译链接。除草除虫,自然是在做着debug。你挑水来我 浇园,大概是在小菜园中进行的结对编程。因为靠天吃饭,农民 们也要学点云计算,去五道口职业技术学校进修的人也多起来 了。收割的季节,活多人少,也常常是要搞外包的,因为 deadline很重要,time to market不容错过。 码农 1 卷首语 @武卫东 湖南怀化人氏。1991年清 华大学毕业后,⼀直从事计 算机图书出版行业。先后在 电子工业出版社、西蒙与舒 斯特公司、机械工业出版社 华章公司、人民邮电出版社 图灵公司工作。现任图灵公 司总经理兼总编辑。 图灵社区ID:豆他爹 ,有子 名豆,故有此号。 所谓码农 不过坦率地说,码农这个叫法让人体会更多的是滑稽、搞怪、无 厘头。毕竟⼀个是简单的体力劳动,⼀个是高智商的脑力劳动, 不可同日而语。而程序员却偏爱这样的时空错乱的感觉,自嘲 (我就是个农民!)的同时却又自命不凡(我是码农我怕 谁?!),特立独行极了。 码农的草帽底下,是⼀颗充满创造力的自由不羁的头脑。他们遵 从最佳实践而痛恨陈规教条,他们欣赏天才而不迷信权威,他们 喜欢思考而不轻易苟同。他们是技术人,却追求人文理想;他们 敢于呐喊,说出自己的观点和主张,也更善于脚踏实地,用自己 的点滴工作去改变现状。码农们是勤奋的,加班加点的工作是常 有的事情,城市夜间的灯火,有多少是在码农们的办公室和居所 点燃?周末四处举办的技术交流和讲座,又活跃着多少码农的身 影?线下读书,线上讨论,冥思苦想,动手实践,新技术驱动着 码农们的脚步,码农们在改变着我们的生活。 生存离不开农民,生活离不开码农。 ▉ 码农 2 图灵社区:很多中国程序员都将您视为计算机科学领域的 神祗。而这样的情况,又恰恰出现在盛行无神论的中国, 很有意思。我们已经清楚您写作《计算机程序设计艺术》 (以下简称TAOCP )的初衷和经历,也知道您关于“ 信仰 与科学的关系” 的系列讲座曾大受欢迎,因此对您的写作 和信仰之间的关系很感兴趣。能否谈⼀下,信仰和上帝在 TAOCP的创作过程中,给您带来的是哪些帮助呢? 高德纳:计算机科学是既壮观又幽美的,我 尝试尽自己所能,以最恰当的方式来解释我 所了解的某些片断。很显然,我自己并没有 任何超自然能力,但的确很喜欢讲述那些似 乎静静地等待着人们去讲出来的故事。写书 跟讲故事十分类似。 此外,虽然计算机科学非常美妙,但它也不 可能包办⼀切!我相信,总有⼀些神秘的东 西是超越人类的理解而存在的。 信仰是很私人的东西,它涵盖了⼀些永远无法证明的概 念。因此,本人在信仰问题上的看法,我并不指望每个人 都能同意。我认为,上帝希望我能创造某些成果,而这些 本期专题 算法 © Listal.com 计算机科学泰斗Donald E. Knuth(高德纳)归隐 已近20载,不问世事,潜心修订并继续创作煌煌 巨著《计算机程序设计艺术》(The Art of Computer Programming)多卷本。 图灵社区藉卷4A影印版出版之机,有幸邀得大师 接受关于此书的访谈,并在多位社区成员留言提 问 的帮助下,完成了这次珍贵的访谈。 对话归隐的大师 ——Donald E. Knuth(高德纳) 码农 3 ALGORITHM 东西能够启发其他人去创造其他成果。这就是我的宗教生活和科 学生活之间的主要关系。 图灵社区:对您耗费几十年的时间创作的 TAOCP,我们代表所 有已经和即将从中获益的中国读者,向您致以诚挚的感谢。到现 在为止,这部著作已经创作了半个世纪。这样的成书过程,让我 们想起歌德的《浮士德》。令人惊讶的是,目前这部作品仍可沿 用您最初确立的内容架构。请问这种基础是如何构筑的?在目前 的创作过程中,您用了哪些方法来保证自己的进度呢? 高德纳:是啊,我确实是几乎不间断地写计算机程序超过 50年 了,平均每周完成多于⼀个程序。譬如,我刚刚查了电脑,统计 出我在今年的持续学习和探索中,到目前为止已经写了 74个程 序。当然,其中某些程序是短小和简单的,但另外那些可都够让 我忙上⼀阵子的。这样的编程过程,很自然地启发了 TAOCP的 内容架构,我们能依此建立整个计算机科学的知识体系。1967 年,我跟Peter Naur第⼀次见面时,我们发现各自都独立地对这 ⼀领域提出了完全⼀致的基本框架。 都过了50年啦,照理说我早该写完TAOCP 才对。不过,我还有 很多累积下来的材料,需要20年甚至更多的时间,才可以转化成 恰当的文字。因此,当看到你问我怎样保持进度时,我都直想发 笑。 要说我还是能有那么⼀点点进度的话,那最主要归功于采用 了 “批处理” 而非“ 换入换出” 的机制:在⼀个时间段内,我通常只 全神贯注地做⼀件事情。每年我会暂停手上的工作两次,每次用 两三周的时间阅读邮寄过来的期刊。我每周都会收到 8份左右的 期刊,我的秘书会把它们放到盒子里。浏览完它们并了解到技术 码农 4 动向后,我会在自己的文件中加入备注,提醒自己在将来专注于 另外的主题时,应该阅读哪些内容。 目前,我正聚精会神在“可满足性求解器”(SAT solvers)这个令 人着迷的领域,最近编写的20个程序都是在这个主题做相关探索 的。藉由自己去钻研资料的手段,我可以更好地将核心思想传达 给非专家的读者,并将这些思想跟其他应用紧密结合,就仿佛我 的⼀生都在专职研究可满足性的求解问题那么自然。幸运的是, 我现在跟顶级的专家们保持着联系,他们自告奋勇帮我检查写作 中的错误。 图灵社区:我们听说,您目前还是先写出手稿,再在计算机中编 辑。然而,您的TeX 实际上颠覆了整个出版行业。那么,请问您 不全用计算机写作的原因是什么?Dr. Dobb’s在评价TAOCP 4A 的时候这样说道:“ 正如前几卷TAOCP 那样,最新的这⼀卷也是 浓缩了⼀个主题的精华内容。基于其高密度的内容和描述,本书 是近年来屈指可数的必须在印刷版格式下阅读的计算机图书之 ⼀。书中为数庞大的数学注释,将使所有电子格式束手无策, PDF版就像⼀批处处写满文字的 JPEG,难以卒读。” 您是否考虑 过,未来的电子写作和阅读应该是怎样的呢? 高德纳:我书写的速度跟我思维的速度是匹配的,这么⼀来,就 完全不存在任何“ 瓶颈” 。而我打字的速度就比我思考的速度更 快,这样当我试图用键盘创作重要内容时,就会产生同步问题。 (事实上,我也是先用笔写下你这10个问题的答案的。此刻,我 正在Mac上输入草稿,并在过程中尽可能修润行文。) 码农 5 速度通常不会是最重要的标准。科学⼀般都难以迅速解释或迅速 领会。我知道我的书是不容易读的,不过要知道的是,如果不是 我精雕细琢地写的话,它们会比现在难读⼀百倍。 图灵社区:在 《编程人生》 中,您讨论到黑盒的问题时,评论 道:“ 程序里有黑盒是不坏,但通常来说,如果可以看到盒子里 的东西,弄清楚黑盒内部的机理,那就可以改进它。” 我们觉得 这里似乎蕴含着黑客的精神。如果是的话,您是否可以具体描述 ⼀下您心目中的黑客精神? 高德纳:关于黑客精神,Steven Levy那本了不起的《黑客》中 描述得最好。那本书会同时地从众多层面来审视⼀个问题,并寻 找新的形式来组合基本的概念。 图灵社区:您从来都以极客(geek)自诩,并曾在访谈中提 到,论文集第8卷《娱乐和游戏论文集》(Selected Papers on Fun and Games)中有⼀章是“极客艺术品”(geek art)。大部 分中国读者都还无缘读到这本书,是否可以简单介绍⼀下,“ 极 客艺术品”所包含的内容呢? 高德纳:你们应该翻译那本书啊,我说真的! 简单说,能称得上“ 极客艺术品” 的应该是这样的艺术作品:它不 仅仅能因其美丽的颜色、质感和形式而打动我,同时也因能其对 技术的呈现方式而愉悦我的另⼀半大脑。 例如,我最珍爱的极客艺术藏品中的⼀件,正是 Bob Sedgewick(即Robert Sedgewick,《算法》 的作者——译注) 送给我的,那是1975年他刚完成关于快速排序的博士论文的时 码农 6 候。那是⼀件瑰丽的双层编织的纺织品,图案正是他在研究中发 现的其中⼀个数学模型。这个作品是他亲自在提花织机上手工织 造的。类似的作品还有我妻子做给我的⼀张巧夺天工的被子,上 面的图案是以爱因斯坦质数的迷人模型为基础的。去年,我自己 也利用零碎时间做了⼀些作品,那是用色彩斑斓的线、樱桃木和 黄铜钉交错而成的“凯尔特骑士之旅”。 我的很多朋友都已经培养出对极客艺术品的品味。 我听说,Nathan Myrvold 已经搜罗了几百件这样的 作品,其中大部分都是为他的居室专门制作的。 图灵社区:您的TeX 系统是开源的,您本人也被认 为是开源的重要实践者。在曾经的访谈中,您说“ 过 去的几十年间,开放源代码的成功可能是计算机领 域中唯⼀没使我觉得惊讶的事情” 。那么,在后面的 几十年,您预想开源运动将会有怎样的发展呢? 高德纳:请别让我预测未来,也不要相信别人在这 个问题上的说三道四。 回到开源,怎么说呢,有⼀件事是我希望发生的(我很奇怪为什 么尚未发生)。换言之,我希望人们可以找到⼀种比较简单的途 径,让用户能够定制他们的开源发行版。这么⼀来,所有人都可 以使得系统根据他们自己的计算机进行优化的调适,因为用户是 通过编译自己拿到的源代码,而不是仅仅安装(已经编译好的、 未根据系统做好编译优化的)二进制包。开源系统有⼀种尚未开 发的潜力,会使它大大好于任何闭源的系统,因为专有的、事先 打包的二进制成品必须在可用硬件限制的条件下照顾到最差情 况。举例来说,emacs对于我来说已经是又好又快,但我觉得如 很多人都认为高德纳是⼀名非常有趣的人 物。他会奖励每⼀个找出他的著作中任何 错误的人2.56美元,因为“256美分刚好是 十六进制的⼀美元” 。高德纳可以算是⼀ 名标准的黑客,他最喜欢的软件是 Emacs,并甚至还向作者理查· 史托曼提 交修补补丁。 - Wikipedia 码农 7 果能毫无顾忌地在自己的机器上编译它的话,它运行起来还会快 得多。我没空去学习Ubuntu这个发行版的所有底层复杂细节。 (我还真的重新编译过Linux内核——但只有在向导手把手的指 引下才得以完成。) 图灵社区:虽然,TAOCP 代表着您的主要成就,连您目前的头 衔都是“ 计算机程序设计艺术荣休教授” ,但也有很多人认为,您 花十年时间开发的TeX 对世界的影响更大。您对此有何看法?是 否可以总结⼀下算法研究和实际编程之间的联系和各自作用呢? 高德纳:我对于把⼀项有益的活动排在另⼀项之前这种事,不十 分感冒。例如,生物学家不应该把所有时间都花在攻克癌症和其 他重症的疗法上。如果他们中的⼀些人仅在较轻微的问题上取得 了重大进展——比如,消灭了头皮屑——他们也许实际上会带给 更多人更持久的快乐。 TeX使得文学编程成为了可能,这件事长远来看也许最终会给更 多人的生活带来积极的影响,这⼀点强过我所做的任何其他工 作,因为文学化的程序给它的用户带来的改进是巨大的。 但我们还是别拿苹果去和橘子比较了。我认为生活中的每⼀个方 面都是值得改进的,而我也很高兴能在自己生活的场所和时代中 以多种不同的方式做出贡献。 图灵社区:《具体数学:计算机科学基础(第2 版)》 ( Concrete Mathematics: A Foundation for Computer Science, 2E)的中文版同样会由图灵出版。是否可以谈谈它的 写作初衷,以及它跟TAOCP的关系? 码农 8 高德纳:《具体数学》是⼀份“ 纲领” ,它的内容是我对于数学诸 多方面应该如何教与学的思考。熟练掌握代数公式的基础技能, 对我来说始终都是关键所在。这些内容在 TAOCP里都有讨论, 但只能是蜻蜓点水;在斯坦福大学的课程中,我得以深入更多的 细节,而那些内容都被囊括在这本书中了。 图灵社区:“ 高德纳” 似乎是您仅有的⼀个外文姓名,这个名字让 中国读者很有亲切感。我们只知道这个名字是储枫教授(香港城 市大学计算机科学系主任,图灵奖得主姚期智的夫人——译注) 在您1977年访华前夕为您取的。给我们谈谈这个名字背后的故 事吧。 高德纳:储枫告诉我,之所以选择“ 高 ”作为我的中国姓,是因为 我个子高,还因为辅音G 和 K读起来差不多。“ 德纳” 两个字,显而 易见,是“Donald” 不错的谐音,并且有着体面的意义。她还给我 的爱人Jill起了“高精兰”这个名字。 我的两个孩子John 和 Jen也和我们⼀起来到了中国,他们当时分 别是12和11 岁——他们和中国孩子们在城市公园里玩了⼀些不需 要语言交流的游戏。储枫给他们也分别起了“ 高小强” 和 “高小 珍”的名字(见卷2索引)。 图灵社区:我们已经翻译了关于您的管风琴的⼀篇介绍 ,也读到 您在访谈中曾经把写作比喻成演奏管风琴。可以谈谈音乐对您生 活和研究的影响吗? 高德纳:音乐是我的主要副业,也是《娱乐和游戏论文集》⼀书 其中四个章节的主要内容。最近闲下来的时间,在我在 TAOCP 上连续工作几天并需要休息⼀下时,我开始(尽管只是试验性 码农 9 地)着手谱写新的管风琴乐曲,也算是终于兑现了⼀些我在上世 纪 60年代就拟订了的计划。尽管我知道别人来做这些事的话,可 以比我高明得多,但内心却有⼀个声音在催我歌唱! 图灵社区:最后,送上所有中国读者的最诚挚问候,祝您保持健 康,如期完成TAOCP的下⼀卷! 高德纳:再次感谢你们富有启发的问题。▉ 码农 10 记者 / @何逸勤 译者 / @何逸勤 (图灵社区特约编辑) 译者 / @高博 欢迎阅读访谈英文版 高德纳(Donald E. Knuth)在其名作The Art Of Computer Programming的第⼀卷Fundamental Algorithms 中,用集合论对 算法进行了严格的数学定义,仅仅用了⼀页,言简意赅,但是就 这⼀页足以体现出他深厚的数学功底,和驾驭数学的高超能力, 把数学语言的简洁与精确体现得淋漓尽致。我在读这⼀页时想到 了很多,受到的启发远不止纸上的这些,现在把这些理解写在这 里,希望对大家有所帮助。 在介绍算法的数学定义之前,我们要明确算 法的五个基本特征: •有限性:描述了⼀个算法在执行有限步之后 必须会终止。 •确定性:描述了⼀个算法的每个步骤都必须 精确地定义,可以严格地、无歧义地执行。 •输入:描述了⼀个算法在运行之前赋给它的 量,或在运行过程中动态地赋给它的量。 •输出:描述了⼀个算法运行结束时的结果。 •有效性:描述了⼀个算法在运行过程中的所 码农 11 本期专题 算法 作者 / 陆超超 @陆超超_lucc 南京大学软件工程专业的学生,大四即将毕业, 研究方向为computer vision 和 machine learning。喜欢理论也喜欢实践:时而研究数学 与算法,时而写写code。闲暇时喜欢书法与绘 画,无聊时喜欢登山旅游摄影。热爱生活,执着 于梦想! 关于TAOCP 中用集合论对算法进行 严格数学定义的理解 有运算必须是充分基本的,是可行的,原则上人们可以用 笔和纸在有限的时间内精确地完成这些运算。 高教授在用集合论定义算法时是严格按照这五个基本特征来做 的,下面我就用常用的集合论术语隆重地介绍算法的定义: 我们定义⼀个计算方法为⼀个四元组( Q, I, Ω, f ),每个字母的 意义为: Q: 表示计算状态的集合 I: 表示输入的集合 Ω: 表示输出的集合 f: 表示计算规则的集合 满足如下约束: I ⊂ Q,Ω ⊂ Q, f :Q → Q ∀q ∈Ω, f (q) = q 对集合I中的每⼀个输入x定义⼀个序列:x 0, x1, x2, ...,满足如下 规则: x0 = x, xk+1 = f (xk ),k ≥ 0 如果 k 是使 x k 在 Ω 中为最小的整数,那么就说这个计算序列在 k 步中终止,而且在此种情况下说x产生了输出 x k 。可能有些序列 永远不会终止,这只能称为⼀个计算方法,而不能称之为算法。 算法是⼀种对 I 中所有的 x 在有限步中终止的计算方法。 到目前为止,该定义虽然是用集合论描述的,但是丝毫没有难以 理解的地方,就相当于⼀个有限状态机,每⼀节点既是上⼀个节 点的输出节点,又是下⼀个节点的输入节点,最后 f 在输出集合 Ω 中保持逐点不动,很通俗易懂。然而,这个定义还不是很全 码农 12 面,只包含了算法五个基本特征的前四个,并没有包含第五个有 效性特征。在为该定义补充第五个基本特征之前,让我们先来用 上述定义描述⼀个具体的算法,用⼀个大家都很熟悉的欧几里得 算法。 欧几里得算法E:m和n是两个正整数,求它们最大的公因子。 E1[求余数]:m除以n并且令r为所得的余数。(0≤ r<n) E2[判断余数是否为零]:如果r=0,算法结束,n就是输出答案。 E3[减少]:置m←n,n←r,并返回步骤E1。 这个算法可以说是众人皆知,最平民化的算法。如何用上述算法 定义中的术语来描述这个算法呢?首先在欧几里得算法中,我们 涉及到单点(n),表示输出;有序数对(m,n),表示输入。 除此之外,还涉及三个不同的步骤,每⼀步基本都与m,n,r这 三个数有关,为了方便区别这三个不同的步骤,我们还要引入⼀ 个步骤的序列号,这样我们就可以用三个有序四元组分别表示每 ⼀个步骤了。所以欧几里得算法严格的数学描述如下: 欧几里得算法是⼀个四元组( Q, I, Ω, f ),每个字母的意义为: • Q: 所有单点(n),所有有序数对(m,n)和所有有序四 元组(m,n,r,1),(m, n,r,2)以及(m,n, p,3)的集合,其中m,n,p是正整数,r是⼀个非负整 数。 • I: 所有有序数对(m,n)的子集。 • Ω: 所有单点(n)的子集。 • f 的定义如下: 1. f((m,n))=(m,n,0, 1) 码农 13 2. f((m,n,r,1))=(m,n,m%n,2) 3. 如果r=0, f((m,n,r,2))=(n);否则 f((m,n,r, 2))=(m,n,r,3) 4. f((m,n,p,3))=(n,p,p,1) 5. f((n))=(n) 在这里有必要说明⼀下,上面的 f 定义了5条规则,第1条规则是 得到输入数对之后初始化为四元组,才能参与后面的步骤;第2 条对应于E1;第3条对应于E2;第4条对应于E3;第5条是算法 结束的终止条件。显而易见,欧几里得算法这样的数学定义与先 前的步骤是⼀⼀对应的,但是更加严格准确了。 现在,大家应该对算法的集合论定义有了比较清晰的了解。前面 已经说过,该集合论的数学定义不尽如人意,还不包括前面的有 效性基本特征。例如,当 Q 是仅用纸和笔而无法计算的无穷序 列,或者f是仅靠人脑也无法实现的计算,那么这时不满足有效 性的特征,也就不能称之为算法。所以为了使算法的数学定义更 加完善,我们应该给 Q 和 f 加⼀些约束,使运算的每⼀步都是可 行的、有效的,或更加具体⼀点说,就是使每⼀运算都只涉及初 等运算。在计算机中,什么样的初等运算最具有代表性呢?当然 是字符串的删除、添加、替换等操作啊,这些操作是绝对可行 的,而且表示的含义也很广泛,当然你也可以使用其他的初等运 算。接下来我们就在 Q 和 f 上加⼀些约束了: 首先,令A是字母的有限集合,并且令A°是A上所有串的集合, 我们用A°的串来对计算的状态进行编码,即不同的串代表不同的 计算状态。于是我们有: • Q:是所有 (σ, j) 的集合,其中σ ∈A°,0 ≤ j ≤ N,N为非负 整数 • I:是所有j=0时 Q 的子集,即是所有(σ, 0)的集合 码农 14 • Ω:是所有 j =N 时 Q 的子集,即是所有(σ, N)的集合 为了方便描述,我们还要给出⼀个定义:对于θ,σ,α,ω∈A°, 如果σ =αθω,则称 θ 出现在 σ 中。 现在我们可以给出f的约束了,如下: 0 ≤ j < N,θ j ,φ j ,α,ω ∈A,aj ,bj ∈ F1式:如果 θ j 不出现在 σ 中,那么: f σ, j( )( ) = σ,aj( ) F2式:如果 α是满足 σ =αθ jω 的最短的字符串,那么: f σ, j( )( ) = αφ j ,ω,bj( ) F3式: f σ,N( )( ) = σ,N( ) [注]: 1. F1式通俗地说就是:如果在⼀个字符串 σ 中如果找不到另 ⼀个字符串 θ j,就跳转第 a j 步。 2. F2式通俗地说就是:如果在⼀个字符串 σ 中找到了另⼀个 字符串 θ j,就用字符串 f j 替换字符串 θ j,然后跳转到第 b j 步。 3. F3式是终止条件。 上面对于f的约束显然能确保算法的有效性基本特征,因为上述 定义的每⼀步都对字符串进行了简单的操作。事实上,F1式、 F2式和F3式这三个式子足够可以描述我们手头的所有事情,更 具体⼀点就是,足够可以描述所有的计算机程序。为什么这样说 呢?我们知道,所有的计算机算法程序都是用某种编程语言写 的,而所有的编程语言无外乎三种结构:顺序,选择和循环。上 面的三个式子正好可以描述这三种结构,下面⼀⼀进行解释: 码农 15 • 顺序结构 这个最简单,这三个式子任意执行就可以了,而且只要指 定j,下⼀步就会进行你指定的第j个运算,所以不再赘述 了。 • 选择结构 F1式和F2式结合起来使用便是选择结构:如果 θ j 不出现 在 σ 中,就执行F1式,如果 θ j 出现在 σ 中,就执行F2 式。这里字符串中的出现与不出现就分别表示了相反的两 种计算状态。 • 循环结构 在F2式中,令b j=j,便会进行循环运算,然后用F1式判断 是否跳出循环,非常容易。 而F3式是描述算法执行结束的状态。所以用上面的F1式、F2式 和F3式三个式子可以描述所有的算法,而且每⼀步都是有效 的,到这里算法的集合论数学定义才算完备,囊括了算法所有的 五个基本特征。 除此之外,编程语言中最基本的数据类型——整型,可以用某个 字符的个数来表示,而编程语言中最基本的初等运算——加减 法,可以用字符串的替换来表示。所以现在,我可以说基于字符 串集合A°的F1式、F2式和F3式三个式子就构成了⼀门编程语 言,通过它们可以编写任何你想要的合法程序,和那些高级语言 (如C语言等)效果⼀样。但是这是⼀门有严格数学定义的编程 语言,为了以后叙述的方便,我将其命名为M语言(是Math语言 的简称,后面均用此简称)。 M语言中仅仅涉及 θ j, fj, aj, bj 这四个变量(变量的定义和前面⼀ 致),所以这四个变量的取值就决定了M语言中语句的每⼀步执 码农 16 行。换句话说,在M语言中每⼀条语句就是这四个变量的取值, 因此每⼀条语句就可以用这个四元组表示。以后,我们如果说用 M语言来编写程序,就是说用这四元组来编写程序,程序的每⼀ 条语句都是四元组,整个程序就是由这些四元组构成的。 为了熟练使用这种由集合论进行了严格数学定义的算法语言—— M语言,最后,我将M语言应用于⼀个具体的例子,用来说明其 强大的描述能力。当然,我们还是以欧几里得算法为例,考虑到 用字符串来描述初等运算,我们使用欧几里得辗转相减法,而不 是原先的辗转相除法。 题目表述如下: 通过描述上面的F1式、F2式和F3式三个式子中的 θ j, fj, aj, bj,给 出计算正整数m和n的最大公因子的⼀个“有效性”算法,令输入 为字符串 aaa m bbb n ,输出结果是 bbb gcd(m,n)  ,当然你完全可以输出 除b以外的其他字母,这里只是为了方便而已。希望你尽可能给 出简单的解。 我用自己的话重述⼀下这个题目:就是用M语言编写求最大公因 子的欧氏辗转相减法。根据前面所述,就是求⼀系列四元组。首 先还是按照前面介绍欧氏辗转相除法的方式来介绍辗转相减法, 如下: 欧氏辗转相减法ERM:m和n是两个正整数,求它们最大的公因 子。 ERM1[求差]:m减n并且令r为所得的差的绝对值。(0≤ r<n) ERM2[判断差是否为零]:如果r=0,算法结束,n就是输出答 码农 17 案。 ERM3[减少]:置m←min(m,n),n←r,并返回步骤ERM1。 这个算法ERM和前面的算法E的正确性很容易证明,限于篇幅, 这里就略去了。下面主要讲解⼀下我解决这道题目的思路: 题中两个正整数m和n分别是用a和b的个数表示的,所以要求m 和n的差,只要每次分别去掉⼀个“a”和⼀个“b”,为了便于字符串 的操作,每次直接去掉“ab”,⼀直到只剩下“a┄”序列或“b┄”序 列为止,这时剩下的“a”或“b”的个数就是m和n差的绝对值r,这 就完成了步骤ERM1。 为了方便步骤ERM3的赋值操作,我们需要知道min(m,n)到 底是哪⼀个,显然min(m,n)就是去掉的“ab”的个数,因此我 们需要换⼀种简单的方式保留“ab”的个数,就用另外⼀个字 母“c”替换“ab”,这就是F2式中的操作。但是“c”会把字符串中 的“a”序列和“b”序列分开,无法进行继续去掉“ab”的操作,因此 我们要把“c”移到字符串的最左边或最右边(这就导致了两种解 法,下文我都会给出)。这种移到最左边或最右边的操作⼀般会 是连续重复的,这就会使用到上文所说的F2式中的循环操作。 然后继续替换“ab”也会使用该循环操作。等替换完所有 的“ab”后,这时可以执行步骤ERM3,“c”的个数就是min(m, n),余下的“a”或“b”的个数就是r。 接下来要分两种情况,如果把“c”移到了最左端,由于跳到步骤 ERM1后要继续替换“ab”,所以这时要将所有的“c”变成“a”,将所 有的“b”或“a”都变成“b”;如果把“c”移到了最右端,这时要将所有 的“c”变成“b”,将所有的“b”或“a”都变成“a”,这些就是执行步骤 ERM3,当然这些过程都会用到F1式中的跳转操作和F2式中的循 环操作。执行完步骤ERM3后就会重复执行步骤ERM1,以此循 码农 18 环直到执行步骤ERM2,即r=0,也就是说字符串中只剩下“c”的 序列,这时“c”的个数就是m和n的最大公因子(gcd(m, n))。当 然不⼀定最后以“c”的表示输出,可以输出任意其他字符,那么 就可以用F2式中的循环替换操作。 下面我就给出该题目的⼀种解答(将“c”移到最左边),并将详 细解释该M语言编写的程序的每⼀步,该程序如下: 012 110 223 334 405 555 jjjjjab ab c ac ca ab ca bb ab θφ 【上述M语言版的辗转相减法程序注解】:j表示程序的步骤号, 每个步骤的具体含义为: • 第0步:如果找到“ab”就用“c”替换,然后跳转到第1步;如 果找不到“ab”,就直接跳转到第2步。(这⼀步就是 用“c”替换“ab”) • 第1步:如果找到“ac”就用“ca”替换,然后循环执行这⼀ 步;否则直接跳转到第0步。(这⼀步就是将“c”移到最左 边) • 第2步:如果找到“a”就用“b”替换,然后循环执行这⼀步; 否则直接跳转到第3步。(这⼀步就是执行ERM3中的n←r 操作) 码农 19 • 第3步:如果找到“c”就用“a”替换,然后循环执行这⼀步; 否则直接跳转到第4步。(这⼀步就是执行ERM3中的 m←min(m,n)操作) • 第4步:如果找到“b”就用“b”替换,然后跳转到第0步;否 则直接跳转到第5步。(这⼀步就是相当于执行ERM2的判 断) • 第5步:如果找到“a”就用“b”替换,然后循环执行这⼀步 (这⼀步就是为了满足题目的要求最终以“b”序列的形式 输出来结果) 为了使该M语言版算法的步骤更加清晰,我给出⼀个实例: m=6,n=4,此时的输入为σ=aaaaaabbbb,执行过程图如下: 执行结果输出结果σ=bb,即gcd(6, 4)=2。 码农 20 aaaaaabbbb→aaaaacbbb→aaaacabbb→aaacaabbb→aacaaabbb →acaaaabbb→caaaaabbb→caaaacbb→caaacabb→caacaabb→cacaaabb →ccaaaabb→ccaaacb→ccaacab→ccacaab→cccaaab→cccaac→cccaca →ccccaa→ccccba→ccccbb→acccbb→aaccbb→aaacbb→aaaabb→aaacb →aacab→acaab→caaab→caac→caca→ccaa→ccba→ccbb→acbb→aabb →acb→cab→cc→ac→aa→ba→bb 同理,我再给出该题目的另外⼀个解(将“c”移到最右边),该 程序如下: 012 110 223 334 405 555 jjjjjab ab c cb bc ba cb bb ab θφ 分析同上面的将“c”移到最左边的解。 最后为了完整性,同时考虑通用性,我将用伪代码的形式实现由 F1式、F2式和F3式所严格定义的算法通用程序,如下: while(!terminate condition){ find the first Theta_j in the input_string; if(No Found){ j=a_j; }else{ input_string=the sub_string in front of Theta_j + Phi_j + the sub_string behind Theta_j; j=b_j; } } 上面伪代码中选择语句if···else···的第⼀部分相当于F1式,第二 部分相当于F2式,而terminate condition相当于F3式,所以具有 码农 21 1 2 3 4 5 6 7 8 9 10 11 通用性,很容易将上述伪代码用高级语言编程实现,例如依照该 伪代码,可以轻松地将上面讲的辗转相减法的M语言版用高级语 言实现。下面就是我用C++实现的辗转相减法的第⼀种解(第二 种解几乎⼀样,只要改⼀下状态表中的变量值即可): #include #include using namespace std; int main (){ int j=0; string theta[]={"ab","ac","a","c","b","a"}; string phi[]={"c","ca","b","a","b","b"}; int b[]={1,1,2,3,0,5}; int a[]={2,0,3,4,5,5}; string input; cout<<"Input:"; cin>>input; cout<<"Output:"< t1.score 对于4号用户我们可以得到下面的结果: 算法特点 优点:简单,利用了SQL的功能,不需要复杂的查询逻辑,也不 引入额外的存储结构,对小规模或性能要求不高的应用不失为⼀ 种良好的解决方案。 缺点:需要对user_score表进行全表扫描,还需要考虑到查询的 同时若有积分更新会对表造成锁定,在海量数据规模和高并发的 应用中,这样做性能是无法接受的。 码农 26 1 2 3 算法2:均匀分区设计 在许多应用中缓存是解决性能问题的重要途径,我们自然会想: 能不能把用户排名用Memcached缓存下来呢?不过再⼀想发现 缓存似乎帮不上什么忙,因为用户排名是⼀个全局性的统计指 标,而并非用户的私有属性,其他用户的积分变化可能会马上影 响到本用户的排名。然而,真实的应用中积分的变化其实也是有 ⼀定规律的,通常⼀个用户的积分不会突然暴增暴减,⼀般用户 总是要在低分区混迹很长⼀段时间才会慢慢升入高分区,也就是 说用户积分的分布总体说来是有区段的,我们进⼀步注意到高分 区用户积分的细微变化其实对低分段用户的排名影响不大。于 是,我们可以想到按积分区段进行统计的方法,引入⼀张分区积 分表score_range: 表结构: 数据示例: 码农 27 表示[from_score, to_score)区间有count个用户。若我们按每 1000分划分⼀个区间则有[0, 1000), [1000, 2000), …, [999 000, 1 000 000)这1000个区间,以后对用户积分的更新要相应地更新 score_range表的区间值。在分区积分表的辅助下查询积分为s的 用户的排名,可以首先确定其所属区间,把高于s的积分区间的 count值累加,然后再查询出该用户在本区间内的排名,二者相 加即可获得用户的排名。 乍⼀看,这个方法貌似通过区间聚合减少了查询计算量,实则不 然。最大的问题在于:如何查询用户在本区间内的排名呢?如果 是在算法1中的SQL中加上积分条件: select 1 + count(t2.uid) as rank from user_score t1, user_score t2 where t1.uid = @uid and t2.score > t1.score and t2.score < @to_score 在理想情况下,由于把t2.score的范围限制在了1000以内,如果 对score字段建立索引,我们期望本条SQL语句将通过索引大大 减少扫描的user_score表的行数。不过真实情况并非如此, t2.score的范围在1000以内并不意味着该区间内的用户数也是 1000,因为这里有积分相同的情况存在!二八定律告诉我们, 前20%的低分区往往集中了80%的用户,这就是说对于大量低分 区用户进行区间内排名查询的性能远不及对少数高分区用户进行 排名查询,所以在⼀般情况下这种分区方法不会带来实质性的性 能提升。 码农 28 1 2 3 算法特点 优点:注意到了积分区间的存在,并通过预先聚合消除查询的全 表扫描。 缺点:积分非均匀分布的特点使得性能提升并不理想。 算法3:树形分区设计 均匀分区查询算法的失败是由于积分分布的非均匀性,那么我们 自然就会想,能不能按二八定律,把score_range表设计为非均 匀区间呢?比如,把低分区划密集⼀点,10分⼀个区间,然后逐 渐变成100分,1000分,10 000 分 …… 当然,这不失为⼀种方 法,不过这种分法有⼀定的随意性,不容易把握好,而且整个系 统的积分分布会随着使用而逐渐发生变化,最初的较好的分区方 法可能会变得不适应未来的情况了。我们希望找到⼀种分区方 法,既可以适应积分非均匀性,又可以适应系统积分分布的变 化,这就是树形分区。 我们可以把[0, 1 000 000) 作为⼀级区间;再把⼀级区间分为两 个2级区间[0, 500 000), [500 000, 1 000 000) ,然后把二级区间 二分为4个3级区间[0, 250 000), [250 000, 500 000), [500 000, 750 000), [750 000, 1 000 000),依此类推,最终我们会得到1 000 000个21级区间[0,1), [1,2) … [999 999, 1 000 000)。这实际 上是把区间组织成了⼀种平衡二叉树结构,根结点代表⼀级区 间,每个非叶子结点有两个子结点,左子结点代表低分区间,右 子结点代表高分区间。树形分区结构需要在更新时保持⼀种不变 量(Invariant):非叶子结点的count值总是等于其左右子结点的 count值之和。 码农 29 以后,每次用户积分有变化所需要更新的区间数量和积分变化量 有关系,积分变化越小更新的区间层次越低。总体上,每次需要 更新的区间数量是用户积分变量的log n级别的,也就是说如果 用户积分⼀次变化在百万级,更新区间的数量在二十这个级别。 在这种树形分区积分表的辅助下查询积分为s的用户排名,实际 上是⼀个在区间树上由上至下、由粗到细⼀步步明确s所在位置 的过程。比如,对于积分499 000 ,我们用⼀个初值为0的排名 变量来做累加;首先,它属于1级区间的左子树[0, 500 000) ,那 么该用户排名应该在右子树[500 000, 1 000 000) 的用户数count 之后,我们把该count值累加到该用户排名变量,进入下⼀级区 间;其次,它属于3级区间的[250 000, 500 000) ,这是2级区间 的右子树,所以不用累加count到排名变量,直接进入下⼀级区 间;再次,它属于4级区间的……如此往复,直到最后我们把用 户积分精确定位在21级区间[499 000, 499 001) ,整个累加过程 完成,得出排名! 码农 30 虽然,本算法的更新和查询都涉及若干个操作,但如果我们为区 间的from_score和to_score建立索引,这些操作都是基于键的查 询和更新,不会产生表扫描,因此效率更高。另外,本算法并不 依赖于关系数据模型和SQL运算,可以轻易地改造为NoSQL等 其他存储方式,而基于键的操作也很容易引入缓存机制进⼀步优 化性能。进⼀步,我们可以估算⼀下树形区间的数目大约为200 000 000,考虑每个结点的大小,整个结构只占用几十M空间。 所以,我们完全可以在内存建立区间树结构,并通过user_score 表在O(n)的时间内初始化区间树,然后排名的查询和更新操作都 可以在内存进行。⼀般来讲,同样的算法,从数据库到内存算法 的性能提升常常可以达到10 5以上;因此,本算法可以具有非常 高的性能。 算法特点 优点:结构稳定,不受积分分布影响;每次查询或更新的复杂度 为积分最大值的O(log n)级别,且与用户规模无关,可以应对海 量规模;不依赖于SQL,容易改造为NoSQL或内存数据结构。 缺点:算法相对更复杂。 算法4:积分排名数组 算法3虽然性能较高,达到了积分变化的O(log n)的复杂度,但 是实现上比较复杂。另外,O(log n)的复杂度只在n特别大的时 候才显出它的优势,而实际应用中积分的变化情况往往不会太 大,这时和O(n)的算法相比往往没有明显的优势,甚至可能更 慢。 码农 31 考虑到这⼀情况,仔细观察⼀下积分变化对排名的具体影响,可 以发现某用户的积分从s变为s+n,积分小于s或者大于等于s+n 的其他用户排名实际上并不会受到影响,只有积分在[s, s+n)区 间内的用户排名会下降1位。我们可以用⼀个大小为100 000 000 的数组表示积分和排名的对应关系,其中rank[s]表示积分s所对 应的排名。初始化时,rank数组可以由user_score表在O(n)的复 杂度内计算而来。用户排名的查询和更新基于这个数组来进行。 查询积分s所对应的排名直接返回rank[s]即可,复杂度为O(1); 当用户积分从s变为s+n,只需要把rank[s]到rank[s+n-1]这n个元 素的值增加1即可,复杂度为O(n)。 算法特点 优点:积分排名数组比区间树更简单,易于实现;排名查询复杂 度为O(1);排名更新复杂度O(n),在积分变化不大的情况下非常 高效。 缺点:当n比较大时,需要更新大量元素,效率不如算法3。 总结 上面介绍了用户积分排名的几种算法,算法1简单,易于理解和 实现,适用于小规模和低并发应用;算法3引入了较复杂的树形 分区结构,但是O(log n)的复杂度性能优越,可以应用于海量规 模和高并发;算法4采用简单的排名数组,易于实现,在积分变 化不大的情况下性能不亚于算法3。本问题是⼀个开放性的问 题,相信⼀定还有其他优秀的算法和解决方案,欢迎探讨! ▉ 码农 32 简介 ⼀般来说,排序算法主要被分为两类,即基于比较的算法和基于 非比较的算法。我已经发了⼀些关于前⼀类算法的帖子。插入排 序,冒泡排序和希尔排序是基于比较模型的。这三个算法的问题 是它们的复杂度都是O(n^2),所以它们非常慢。 那么有没有比O(n^2)更快的排序列表的方法呢?答案是有的,下 面就让我们看看这么⼀个算法。 之前提到的三个算法(插入、冒泡和希尔)的共同特点是,我们 是从原始列表里把元素两两取出,然后进行比较的。 码农 33 本期专题 算法 图说归并排序 作者 / Stoimen @stoimenpopov 插入排序和冒泡排序使用了太多的比较,这也是归并排序需要克 服的地方 在原始列表里进行比较不是最好的方式,而且我们也不需要那么 做。作为替代做法,我们可以尝试将列表分成更小的子列表然后 排序它们。在排序完更小的子列表以后(这么做比直接排序整个 原始列表要简单),我们可以尝试将小的子列表合并成⼀个有序 列表。这个技术就是典型的“分治”法(分而治之)。 ⼀般来说,如果⼀个问题太难以至于无从下手,我们可以尝试将 它分成较小的子问题,然后尝试解决这些子问题。然后我们可以 将子问题的结果合并起来(从而解决原始问题)。 如果排序大列表太困难,我们可以将它分割成更小的子列表,然 后排序它们 码农 34 综述 归并排序是⼀个基于分治法的比较排序算法。目前看来还不错, 当我们有⼀个非常大的列表需要排序,显然,如果将列表分成两 个子列表,然后再排序会更好些。如果等分以后还是太大,我们 就继续分割,直到可以很简单地排序为止(参见下图)。 合并排序过的子列表 码农 35 上图描述了在算法的某些步骤中,我们已经得到两个排序的列 表,而巧妙的地方是合并它们。然而,这也不是特别难。我们可 以比较两个列表的第⼀个元素,将其中较小的元素取出放在⼀个 新的列表中(这样得到的列表⼀定是有序的列表)。 实现 好在这个算法不但快速而且实现起来也不难,站⼀个开发者角度 上,这实在是太美妙了。下面是PHP版的实现。注意:每⼀个遵 从分治法的算法都可以使用递归方案轻易实现。然而,因为递归 的性能很糟,所以你可能需要找到⼀个迭代的方式。⼀般地,递 归可以被花费额外内存空间的迭代方式取代。下面是⼀个递归版 的归并排序。 $input = array(6, 5, 3, 1, 8, 7, 2, 4); function merge_sort($arr) { if (count($arr) <= 1) { return $arr; } $left = array_slice($arr, 0, (int)(count($arr)/ 2)); $right = array_slice($arr, (int)(count($arr)/2)); $left = merge_sort($left); $right = merge_sort($right); $output = merge($left, $right); return $output; 码农 36 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 } function merge($left, $right) { $result = array(); while (count($left) > 0 && count($right) > 0) { if ($left[0] <= $right[0]) { array_push($result, array_shift($left)); } else { array_push($result, array_shift($right)); } } array_splice($result, count($result), 0, $left); array_splice($result, count($result), 0, $right); return $result; } // 1, 2, 3, 4, 5, 6, 7, 8 $output = merge_sort($input); 码农 37 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 复杂度 归并排序的复杂度不是那么高,这⼀点是非常棒的,即使在最差 情况下它的复杂也只是O(n log n)。值得注意的是:即便是快速 排序的复杂度也可能在最差情况下达到O(n^2)。所以我们可以确 定,归并排序无论在什么情况下都非常稳定。 码农 38 为什么归并排序如此有用? 1. 快捷和稳定 归并排序成为⼀个非常棒的排序算法主要是因为它的快捷和稳 定。它的复杂度即使在最差情况下都是O(n log n)。而快速排序 在最差情况下的复杂度是O(n^2),当n=20的时候,它比归并要 慢4.6 倍。 2. 容易实现 另⼀个理由是归并排序很容易实现。诚然,大多数开发者认为速 度快的算法总是难以实现,但是这条守则并不适用于归并排序的 情况。 码农 39 归并排序不那么实用的三个理由 1. 比非比较排序算法慢 归并算法是基于比较模型的,因此它要比在线性时间里排序数据 的非比较算法要慢。当然,这也与输入数据有关,所以我们要仔 细对待输入。 2. 对于初学者来说比较难实现 尽管我不认为这是⼀个不用归并排序的主要理由,但仍有⼀些人 说它对于初学者来说太难实现了,尤其是合并部分的算法。 3. 在数据基本有序的情况下,它比冒泡和插入排序要慢 再⼀次提醒,要了解输入数据的重要性。如果输入数据基本已经 有序,那么插入和冒泡排序会更快。插入和冒泡排序在最好的情 况下复杂度是O(n),然而归并排序的最好情况是O(n log n)。 作为总结,我想说在实践中,归并排序是最好的排序算法毋庸质 疑,因为它易于实现而且快捷,所以每个开发者都应该牢记它。 ▉ 码农 40 查看英文原文: Computer Algorithms: Merge Sort 译者 / 于利霞 从事领域:java web开 发、OSGI开发,个人兴 趣:编程、上网、看电 视、看书,这就是生活。 《码农》电子刊迎来了第⼀位受访Coder——梁斌同学。今年3 月梁斌同学心血来潮,创建了10年老码农群,意外引起各路大牛 关注,很多重量级的Coder纷纷加入,仅仅10天后码农群就开始 了第⼀次Social活动。此外,梁斌也在探索如何延长码农的技术 生命,让我们⼀起来看看他对码农的看法。 图灵社区:为什么您会想建这样⼀个10年老码农群呢? 梁斌:很多人说,编码这活干到35岁就到头了,继续编码,不从 事管理岗,职业的不安全感越来越高。我就思考中国能不能有10 年以上的老码农,老码农怎么延长自己的技术生命。建这个群的 想法就自然出来了——10年老码农聚在⼀起,意在抱团取暖。 10年老码农群里有各种各样身份的人,创业的、当老大的、编程 的。码农有需要的时候,可以在群里寻求帮助,大家八仙过海, 各显神通。举个例子,比如说我,现在从清华毕业,年纪也大 了,不好找工作,做的软件也没人买,但群里有人知道你的价 值,知道梁斌还能当个仓库保管员(笑),这样机会就来了。也 有很多公司,特别是初创公司程序员都是新人,非常需要有经验 的老码农来凝聚开发团队。有这种需求的时候,他们会直接来这 个群找。类似的信息都会在群里流动,我们算是把肉都揽到自己 锅里了…… 图灵访谈 梁斌 @梁斌penny 清华大学计算机系在读博 士,THUIRDB 和微博寻人 的 Coder,《走进搜索引 擎》、《深入搜索引擎》 作者,10年老码农群群 主。 终身Coder ,可以吗? ——老码农如何延续技术生命 码农 41 而且如果有天美帝问,为什么中国没有10年、20年以上编码的 人?这个群也算是⼀个回应,总不能答曰中国人思维活跃、性情 奔放,不爱长期做⼀件事情吧。 图灵社区:为什么很多人毕业选择工作时,对编码还很有热情, 但经过多年工作,却不爱这行了? 梁斌:我觉得有很多原因,而且想明白这些原因都很难。 第⼀,也是最重要的⼀点,就是虽然你的年纪大了,但公司或者 团队对你的期望还是跟年轻人⼀样——输出大量的代码,但你的 精力已经无法匹敌年轻的时候,不能直接跟新码农拼了。但老码 农在其他方面是有优势的,经验很丰富、很值钱,就会转而考虑 从事别的工作。 第二,这个社会的诱惑特别多,无论是创业的诱惑,还是做管理 层赚大钱的诱惑。面对这些诱惑的时候,你还能安心地编程吗? 许多跟你⼀样的人选择其他机会后,价值发挥得比你大得多。你 虽然还很热爱编码,但是当老婆揪着耳朵说“你看某某编码水平 还没你高,车子买了,游艇买了,国外都去了好几次”,或者在 同学聚会看到旧同学各有发展的时候,就会感受到压力,毕竟人 不可能永远穷下去。 图灵社区:国外的程序员有这种问题吗? 梁斌:国外多少也有⼀些,但国外10年以上靠纯编程为生的人, 比国内要多得多。因为作为Coder,他们的价值是被社会认可 的。管理层和编码人员待遇差距没有那么大。编码的人买得起 房,买得起车,可能买不起游艇,但他热爱编码,不在乎这个。 码农 42 但如果管理层房车都有了,编码的人还要租房子,内心就很难平 衡了。就算自己安得其乐,家里人也会有意见。如果社会认可我 们的价值,如果编码这件事能带来足够的荣耀,还会有这么多人 转行吗? 说远⼀点,为什么中国互联网界加班这么多,干活那么快?⼀个 原因是中国互联网的钱都是美国人出的。在中国,创业公司想要 融资,走银行这条路基本走不通,90%以上都是从美国融资,那 么投资方就会对你有很高的要求,比如⼀年内用户数要增长到多 少。中国互联网业界有个共识,代码不用写很好,因为万⼀企业 黄了,代码写得再好都没有用。而请⼀个老码农的钱可以请好几 个新手,在这种情况下,初创阶段的公司为了快,就会请⼀些⼀ 般的人,等公司火起来之后,才会去招牛人。这种浮躁的心理让 整个行业认为程序员的价值只在干活“快糙猛”。 图灵社区:作为这个群的群主,你现在是想去做管理还是想去编 程,想去大公司还是小公司? 梁斌:我自己摸索出⼀条路——“个体户技术输出模式”,就是我 自己或者带小团队做⼀份技术,输出给多个客户。可能从每个公 司取得的收入不是特别多,但足够养活我和团队,这样我们可以 专心做我们想做的技术,让自己的技术生命继续往下走。为了保 持独立性,我可能终身都不会去某⼀家公司,而且我觉得我有责 任摸索⼀条能够延续技术生命的路,让码农们看到,继续编码是 有路走的。 图灵社区:这个模式的可行性在哪里? 码农 43 梁斌:这个模式通过做别人做不到的事来争取客户。因为在中 国,通过高质量代码来赚钱是非常难的。举个例子,同样是⼀千 万行乘⼀百亿列的矩阵运算,如果你我都在两个小时内运算完, 那么在客户眼里,我们就是⼀样的,虽然请个行家来看,可能我 的代码质量优于你10倍,但我绝对没可能拿到十倍的钱。只有当 你能做⼀百行乘⼀千维的小矩阵,而我却能完成更大的矩阵运算 时,才会有人买我的帐。 图灵社区:图灵即将发行⼀些电子书,对此您有什么看法? 梁斌:据我所知,现在很多人看不进书,原因在于书太难。我认 识的人中,还没有⼀位能看完Knuth的《计算机程序设计艺 术》,当然这套书很深,但其他书能看懂的人也不多。所以仅仅 开放电子书是不够的,这⼀步只是从0走到了1,你们应该找到更 多的方法,帮助读者真正学会。 图灵社区:码农群有⼀个主题,是“让码农Social起来”,这个想 法是怎么来的呢? 梁斌:我认识的很多码农都比较“宅”,跟机器待时间长了,有些 人当众发言都很困难,社交能力非常差。想想看,10年码农,社 交能力还差,长得又不怎样,怎么办啊!⼀个方法就是社交起 来,让更多人知道你的价值。群里的人都是老码农了,彼此间进 行沟通是很容易的,Social起来之后,不同背景的人彼此了解, 就能够迸发出更多火花。 码农需要Social,说到底也是出于安全感。我们面临人生、家 庭、职业、社会各种困惑,不Social就容易变得愤青、偏激、爱 码农 44 吵架。这个群里的人有着非常多的共同点,Social起来更容易感 受到编码的快乐和荣誉感。 图灵社区:确实,社交起来彼此都能有所收获。《码农》电子刊 的部分灵感也是来源于此,好多人说这个名字是自毁长城,您怎 么看? 梁斌:为什么我们不愿意管自己叫“程序员”?这个听起来光彩多 了,但是社会不认可。他们不觉得程序员有多大的价值,索性我 们就自贬⼀分,叫自己“码农”。如果我们像国外程序员那样被尊 重,又何苦这么无聊?现在很多公司要么是产品经理驱动,要么 是销售驱动。程序员如果永远出于被驱动的状态,就会逐渐丧失 主动性。 其实程序员并不要求多大的权利,只要有正常的发言渠道,能够 表达自己的意见就行了。我觉得你们做好⼀件事就行——就是给 那些默默无闻的码农⼀个发声的渠道,让他们有荣誉感。我们这 些人,不是什么经理,也非各种总监,更没有身负××长的光 环,不能忽悠广告,也输出不了什么趋势,顶多是个高级程序 员,就是在第⼀线干活的人,在你什么都不能给他的时候,荣誉 感非常重要。 图灵社区:老码农自身是否也存在⼀些问题,比如排斥新技术, 不开放,创新力不足等,使得职业上的不安全感越来越高? 梁斌:确实是,现在让我学⼀门新技术,我也不太愿意,也因此 放弃了很多的机会。因为白纸⼀张的时候你可以随便选择,但厚 厚的油画就再难涂抹。现在技术淘汰速度特别快,有时不懂新技 术都不好意思跟人打招呼,所以⼀些必备的东西还是要学习的。 码农 45 但老码农们肯定会走到这么⼀天——无法再学习新东西,所以我 现在想尝试类似“学徒”这样的制度,老码农虽然学习能力不足, 但眼界在,可以让年轻人去学习,我们给予⼀些指导,通过这种 方式把人员架构起来。 图灵社区:谢谢梁斌接受我们的采访,希望有⼀天,我们能够消 灭“码农”这个称号,大家都为自己的职业感到自豪,那时《码 农》也可以改名叫《编程人生》,那就再好不过了。 ▉ 码农 46 记者 / @谢工 @杨帆 应用语言学是什么? 图灵社区:我们先从你的博客 开始谈吧,现在 很多人都在看你的博客。 顾森:这个博客是从2005年7月开始写的,其 实本来完全是写给自己看的。我把它当做自己 的学习笔记,学了新东西,就放在上面,方便 以后查找。后来发现有人开始看我的博客,就 多了⼀份与别人分享的心,开始尝试着尽可能 地把东西讲明白,而不是只给自己看了。 博客读者多了,偶尔会遇到⼀些很神奇的事。 记得大⼀的时候要上《数据结构与算法》,我 算法很好,所以完全没有去听过课。最后期末 考试时,就两手空空地只拿⼀支笔去,结果发 现所有人都带着书呢,然后才知道原来这门课 的期末考试是开卷考试。最神奇的是,老师⼀ 进来,我才发现我俩其实本来就认识——他居 然是我的网友……于是那个课我得了⼀百分。 图灵访谈 Matrix67何许人也?如果说⼀个人 写数学博客写了七年不能让你吃 惊,再告诉你他是中文系的,不知 道你会不会觉得诡异?这位年轻的 数学爱好者即将在图灵出版《思考 的乐趣》⼀书,图灵社区借此机会 采访了他,他真是⼀个特别“ 好 ”玩 的人,“ 好 ”字的两种读法说的都是 他。 而且跟他接触之后,你会觉得 祖国的未来特别有希望。为什么 呢?请看下文。 Matrix67的Aha!Moment 码农 47 图灵社区:你读中文系是吧,怎么要修这个课呢? IT圈里很多 人都知道你,但大家又把你定义成⼀个北大就读的文科生,像你 这么喜欢数学的人怎么会学中文? 顾森:准确地说,其实我学的是应用语言学,是专门做中文信息 自动处理的。这是⼀个理科专业,而且跟数学关系特别大,是语 言学、数学、计算机的结合。我们跟着数学学院去学数理逻辑, 跟着计算机专业去学数据库、算法,感觉上很不像中文系。但我 们又要跟中文系的人去学语言学、古代文学史之类的,后者尤其 让我头疼。《古代文学史》是我唯⼀知道的在北大要学两年的 课,四个学期里我的分基本上是逐年下降的。⼀直到《古代文学 史(四)》,我实在不想学了,那个课就⼀次没去,最后背了两 天,考了60分,及格拉倒。我希望把时间花在我真正想学的东西 上。 图灵社区:其实这个专业本来就不算是中文系吧。 顾森:对。在中国,中文系的设置⼀直是有问题的。中文系的学 生⼀方面在学文学,另⼀方面在学语言学,但在国外,这完全是 两回事。我们现在学的就是偏语言学的。 事实上,我还挺喜欢语言学的,我最喜欢举的例子是汉语语言学 家陆俭明先生提出来的,他说“看报纸”可以说“把报纸看看”,但 是“借报纸”不能说“把报纸借借”;“洗衣服”可以说“把衣服洗洗”, 但是“买衣服”不能说“把衣服买买”。这就提出了问题,“看报 纸”、“洗衣服”和“借报纸”、“买衣服”这两组动作到底差别在哪 儿,以至于⼀个能换着说,⼀个不能换着说?⼀个更诡异的例子 则是,“收作业”可以说“把作业收收”,“交作业”却不能说“把作业 交交”。这个问题其实现在还没有⼀个完美的解释。语言学里的 码农 48 很多内容就是去找规律、建模型、提反例,整个就是⼀个理科的 氛围。我的书里有⼀节是讲中文分词的,就是从学校里的相关课 程中学到的。 现在我在人人网实习,主要做汉语文本分析,也接触算法,还挺 对我胃口的。因为我本来也是信息学竞赛保送的北大,对算法特 别熟悉。《思考的乐趣》这本书里也写了很多跟计算机相关的东 西,比如有⼀节就是专门讲协议的。这个是最早跟云风聊到的, 他先跟我讲了⼀个关于协议的问题,然后推荐了《应用密码学》 那本书,我买了之后疯狂地看,收获特别大。我把从《应用密码 学》和从他那儿了解到的东西,加上我自己想到的,整理成⼀篇 文章放进了《思考的乐趣》里,特别好玩。 我常常用我自己的专业知识做⼀些有趣的事情。上个月,我找来 了⼀份双字词表,然后从中找到了⼀些两个声母颠倒过来正好也 能说的词,然后用它们留空造句,出成⼀系列题让大家去填,比 如: 虽然公司位于⼀块( ),但是最后还是( )了。 答案:虽然公司位于⼀块宝地,但是最后还是倒闭了。 宝地和倒闭 魔术师熟练地从( )里变出来⼀只( )。 答案:魔术师熟练地从台布里变出来⼀只白兔。 台布和白兔 他知道好几种( )翻新机的( )方法。 码农 49 答案:他知道好几种鉴别翻新机的便捷方法。 鉴别和便捷 为了磨炼意志,他常常赤身睡在( )铁钉的( )上。 答案:为了磨炼意志,他常常赤身睡在布满铁钉的木板上。 布满和木板。 我特别喜欢干这样的事,这就是所谓的交叉学科吧。 图灵社区:这个学科有哪些实际应用呢?听起来应该有很多机 会。 顾森:我在《思考的乐趣》第⼀章里写到了分词,那其实就是⼀ 个最基本的应用。当然,分词之后还有对句法的结构分析、语义 的识别,以及用统计的手段去挖掘⼀些东西,例如从大规模的真 实语料里面统计出大家喜欢说什么,不喜欢说什么之类的。 Facebook之前就做过⼀些很有意思的东西,他们从语言文本中 抽出了表示心情好的积极的词,和表示心情不好的消极的词,然 后通过两类词出现的比例来看整个美国人口大致的幸福程度,结 果表明人们的幸福程度整体呈现上升趋势。这些东西都挺好玩 的。 图灵社区:你让我们想起《编程大师访谈录》里面的⼀个人—— Scott Kim,他就是专门在美国的各种杂志或者游戏中设置圈套 和谜题的人。 顾森:对啊,我以后挺想做那种工作的,类似游戏关卡设计师。 我特别喜欢给人家出题。 码农 50 好老师是什么样的? 图灵社区:听说你读书期间还休学了⼀年,为什么? 顾森:不想读书了。虽然我很喜欢这个专业,但有些课真的不喜 欢,会浪费我很多时间。比如《古代汉语》,老师规定考试答题 写繁体字可以加分,那时候就有很多人练繁体字。但最后发现, 这些人最后考试分数都特别低,因为繁体字要想写对是很难的, 老师把他们写错的字都当错字扣分了。 虽然很多中文系的必修课我们不用修,比如《古代典籍概要》等 背诵内容特别多的课程,但是最经典的文学史课程还是必须要学 的。本来我觉得能混过去就混过去,后来实在不想混了,就想出 去混了。另外,大三上学期结束后,我确实非常忙,不但在数学 培训机构专职工作,还接下了好多约稿,于是就休学了。休学之 后没多久,有幸结识了果壳网的⼀帮人,就在那里工作了大概半 年到⼀年。 我觉得,休学那⼀年收获特别大。 图灵社区:你在果壳网做了哪些事? 顾森:当时我是做数学分站的编辑。数学分站名字取得挺好, 叫“死理性派”。我把竞赛时认识的⼀群好友都拉过来,跟我⼀起 写文章、发文章,为数学科普做了很多工作。 图灵社区:现在忙什么呢? 顾森:简直像精神分裂⼀样,周⼀到周三在北大继续念书,周四 周五在人人网实习,周六周日还要去外地讲课,做中学数学培 码农 51 训。因为北京这边升学压力特别大,进度比课本赶早⼀年,而且 如果家长发现老师讲到课本之外去了,没有老老实实讲题,老师 会面临被投诉的危险。所以当我知道外地有分校的时候,就想到 外地去看⼀看。在外地讲课特别累,每天上午、下午、晚上各讲 3个小时的课。如果是寒暑假,可能会连续⼀个多月都是每天9小 时的课。 图灵社区:你现在教的学生是什么样的? 顾森:主要是初中生和高中生。这个课的定位是普通的数学培 训,帮助学生应对中考、高考或者竞赛。但我走得比这个更远⼀ 些。我希望能够把数学之美、思考的乐趣,甚至把生活中有趣的 点点滴滴都教给学生。这些对他们可能没有即刻的用途,但对将 来是很有帮助的。以后学生可能会发现,这个顾老师讲过,那个 顾老师讲过。 图灵社区:学生也能接受这样的教育方法吗? 顾森:对。而且我觉得作为⼀个教师,⼀方面是要把学生的思维 带活,让他们不要陷到应试教育里面,另⼀方面最好也能改变学 生的性格。他们的压力都比较大,我希望他们至少能在我的课堂 上轻松⼀些,活跃⼀些。比如,我绝对禁止课前走“同学们 好”、“老师好”的形式;也绝对禁止学生举手发言,要发言直接说 就行了;当然也绝对禁止站起来跟老师讲话,直接在座位上说就 可以了。他们可以喝水,可以吃东西,只要吃的东西味道别太 大,别嚼得嘎嘣嘎嘣的,别馋到其他同学就行了。我的课堂就是 完全开放的,觉得怎样舒适就怎样学,唯⼀的要求就是跟着老师 的思路走,让思维⼀直转,保证每⼀节课里,至少能够体会到⼀ 码农 52 两次思考的乐趣。后来,这些班里的孩子们思维比较开阔了,性 格也比较好了。 我教课教了三年,初⼀到初三都讲过,所以今后基本不用备课 了。但每年我自己都会学到⼀些新的东西,加进我的教学计划 里。而且,我也在不停地积累⼀些初中教育的方法。我教过⼀些 小孩,初⼀刚进来的时候,特别不爱思考或者不喜欢数学,性格 也不太好,不愿意跟老师、同学交流;初三之后,整个变了。其 他老师说我那个班简直就是“流氓班”。但家长没有投诉,家长挺 喜欢我的。 图灵社区:你的学生应该也很喜欢你。 顾森:对。上课时经常扯淡,学生们爱听。家长也挺高兴,因为 扯淡也扯得跟数学相关。老师讲正课,学生没有几个愿意听的, 最好的方法就是扯淡,扯⼀些表面上和课本没有关系的东西,大 家都愿意听,然后把数学的知识放到里面去。学生能够听到好玩 的故事,还能把该学的东西学下来,自己比较感兴趣的,还能跟 别人去讲,这就最好了。我常讲的,要么是《思考的乐趣》第⼀ 章那种比较好玩的故事和应用,要么是后面那些好玩的证明,用 我的话来说,就是“可以骗小女生用”。真有⼀些同学⼀拍大腿 说:“这个题太妙了,骗小女生太管用了。”把小孩教活,我觉得 非常重要。 要做周游全国的Geek 图灵社区:讲了这么久的课,收获如何?你明年就毕业了,有什 么职业规划吗? 码农 53 顾森:虽然累,但是收获挺大。再讲个三年,把⼀届初⼀学生带 到初中毕业,到时候,攒的东西又够写⼀本书了。 而且工作的时间集中在周六周日两天的话,其他的时间就多了。 等明年毕业之后,从周⼀到周五我都闲下来了。我想到处去实 习。在人人网玩⼀圈之后,我可能会去豆瓣、百度等等,每⼀个 单位可能都去实习⼀下,甚至到我不熟悉的行业去实习,这种感 觉挺好的。 图灵社区:有什么长远打算吗? 顾森:没有长远打算,我实习的目的就是想去接触各种各样的东 西,可能IT这个圈子混完了之后,会混其他的⼀些圈子。我有⼀ 些特别远的理想,也可以说是不靠谱的理想吧。从北京出发,去 全国各个地方,二线城市、三线城市都跑⼀圈,用⼀个理科生的 眼光,或者说⼀个Geek 的眼光去看,去寻找,去发现。大概花 个几年、十几年,把整个中国游⼀圈,然后再把沿途所见所闻所 想汇总起来,如果能够写成⼀本书,就太棒了。 我的双休日,就是别人的工作日。每周⼀、二、三休息,这样到 哪儿去都没有人跟我抢,可以到处去玩。 图灵社区:那你跟别人不是没有交集了?以后跟家人在⼀起,时 间都岔开了。 顾森:如果说另⼀半,我希望能够找⼀个跟我⼀样的人。我特别 讨厌有个固定的工作,我更希望每⼀个地方都去混⼀下。可能在 每个地方都是做最初级的工作,但却能够体会⼀下公司文化,体 会⼀下这个行业的新鲜事,目的也就达到了。 码农 54 图灵社区:你想过创业吗? 顾森:没有想过创业,因为创业其实事儿也挺多的,还不如看看 东西,写写东西。 图灵社区:在科普方面还有什么打算? 顾森:首先是要提高自己。我觉得我读的书太少了,尤其是考虑 到我不算是⼀个真正学数学的人。所以毕业之后,我最想做的就 是用自己的方法重新去学⼀次数学,然后用自己的方法再讲⼀次 数学。 图灵社区:面对什么样的对象去讲呢? 顾森:现在可能是面对⼀些数学爱好者,甚至是⼀些本来不喜欢 数学的人。但是以后,当我能够系统地去讲⼀些真正的数学思 维、数学方法的时候,有可能是针对⼀些数学专业的学生。因为 我很想改变中国的数学教育现状。 举个例子,现在的课本也好,教辅也好,考试也好,从来就是让 你证明⼀个命题,但从来没有让你推翻⼀个命题,也没有⼀道题 是让你先猜猜命题是对的还是错的,然后给你认为正确的结论找 到⼀个证明方法,给你认为错误的结论找出⼀个能推翻它的反 例。在数学研究中,你首先要有⼀个直觉,能够去判断⼀个问题 值得不值得研究,⼀个命题到底是对还是错,然后才是去证明或 者去找反例。如果有⼀天我能够改变数学教育,我肯定会培养学 生做这类问题。现在的数学教育就纯粹是让学生做题,很少有学 生能够领会到数学研究的乐趣。 码农 55 Aha! Moment 图灵社区:写这本书的想法是怎么产生的呢? 顾森:我曾经在网上看到热心的网友,把我的博客整个扒下来, 按时间从前到后整理起来。⼀方面我觉得很高兴,另⼀方面又觉 得这样帮助其实不是特别大。因为博客上的文章很零散,尤其是 最早2006年、2007年写的东西,其实非常不成熟。偶尔看原来 写的文章的时候,我就觉得,原来写的东西还可以再总结、提高 ⼀下。 我还曾收到很多网友的来信,他们真的把所有的文章全部看了⼀ 遍。当时我就想,应该给更多新看到这个博客的人提供⼀个途 径,让他们可以⼀下子读完这个博客中所有值得看的东西。认识 你们之后,想到可以写成⼀本书。我就想,⼀定要找到⼀条线 索,把这几年学到的东西有机地串起来,像说话⼀样,能够很自 然地从⼀个话题跳到另外⼀个话题,前后都是相关的,⼀气呵 成。 图灵社区:这本书跟你的博客有什么不⼀样? 顾森:书里添加了好多东西。在写这个博客之前,我就对很多数 学话题感兴趣。虽然后来有些文章可能会提到,但并没有专门把 它们写下来。比如关于“无穷集合的势”的话题,博客里面很多文 章就是建立在这个话题之上的。我⼀直在想,既然经常提到这 些,就应该找⼀个时间把它们系统地写下来。这次借写书的机 会,我把最想写的几个比较大的话题都写出来了。 码农 56 另外,这本书里我最喜欢的部分是几个“小合集”。它们其实是几 年来分散在各个时间、各个地方的内容,现在用统⼀的语言把它 们串在了⼀起。它们真的都是最好玩的东西。 回顾目录,我觉得特别满意,因为我真的把这几年来最想和大家 分享的东西,写在这⼀本书里了。 图灵社区:所以短时间内也没有第二本书可以出来了? 顾森:要看我能不能找到其他的话题。这本书面太广了。如果⼀ 个人想来看我的博客,这本书就是我最想让他看的文章,并且以 最想让他看的方式来呈现,里面还包括我个人的⼀些经历,比如 我是在什么情况下学到这些的。 有⼀些话题确实太大了,⼀两篇文章是讲不完的。要是有机会, 我想专注在其中的⼀两个点展开来讲,就像数学花园的⼀角。我 挺喜欢你们那本《图灵的秘密》 ,那本书就是这样做的。它从图 灵的角度,把很大的⼀个话题从头到尾串起来。我之前就对图灵 特别感兴趣,这本书里的内容正好属于我不知道,但稍微⼀看就 能看明白的那种。这本书真的特别好,它应该是我这段时间看过 的最好的科普书。 图灵社区:为什么你这本书不叫《数学的乐趣》,而叫《思考的 乐趣》? 顾森:数学的话,我觉得还挺大的,会不会有人感觉比较畏惧? 而“思考的乐趣”就比较浅了。而且这本书里很多内容也不算是和 数字相关的,而是和思维相关的。比如说第⼀章里讲到统计,很 多时候统计数据上显示两个东西相关,但不⼀定有因果关系。我 码农 57 常举的例子就是:去救火的消防员越多,火灾损失越严重。大家 估计会想,这怎么可能?其实这里的因果关系是颠倒的。正因为 损失越严重的,所以去救火的人才越多。这些其实和数学没有什 么关系,而是⼀种思维方式。看到这个,你能恍然大悟,然后会 心⼀笑,这就算是体会到思考的乐趣了。 图灵社区:你觉得什么样的人会喜欢《思考的乐趣》? 顾森:我觉得对数学感兴趣的人,不管是学数学的,还是普通的 数学爱好者,都会喜欢。这本书里会有⼀些比较冷门的东西,可 能数学专业的人也很难接触到。本来我以为像我这样纯粹因为兴 趣而去学习数学的人很少,后来发现其实挺多的。从很多网友给 我写的邮件里,我都发现他们是真的喜欢数学。我觉得特别感 动。我应该给这些读者送上⼀份这样的礼物。我希望读者朋友们 在每天晚上睡觉之前,或是在其他空闲的时候,不带任何功利的 目的来看这本书,如果真的能有“啊哈,灵机⼀动”的感觉,目的 就达到了。 ▉ 码农 58 顾森,重庆人,数学狂, 喜欢教学生数学魔术骗小 女生,喜欢混各种圈子, 讨厌固定工作。 记者 / @杨海玲 @杨帆 @何健辉 图灵社区:《创意不是想出来的》 这本书里面 有许多观点相当有趣,我第⼀次看的时候总是 忍不住频频点头。比如说“其实只要站在人类历 史的角度俯瞰下来,就会发现搞砸工作丝毫算 不上什么大事”、“愉快工作的人,其实要比‘听 话’的人更具有工作上的主动性”。请问⼀下您当 时为什么会想写这样⼀本书? 柳泽大辅:15年前,我与大学同学共同创立了 KAYAC公司。虽然我们共事多年,但难免有意 见相左的时候。这个时候我们都遵循⼀个原 则:不采用任何⼀方的意见,双方重新考虑方 案,直到互相认可。这种工作方式使我们都形 成了⼀个好习惯:与其去批判对方,不如想出 更精彩的点子去获得大家的认可。 图灵社区:您在本书中提到,出点子其实很简 单,有量的积累才能有质的飞跃。热爱工作、 保持积极乐观的生活态度也不难。但这和我们 实际的感受却不太⼀样,比如有些人并不喜欢 图灵访谈 柳泽大辅 DAISUKE YANASAWA 1974年出生于香港。毕业于庆应义 塾大学信息学院,后就职于索尼音 乐公司。1998年与3 位朋友共同创 立了KAYAC 公司,24岁就任总裁。 该公司是⼀家极具创新能力的网络 互动公司,每年推出100多种新服 务,销售规模连年增长,在日本受 到了广泛关注。著有《飞翔思考 法》、《创意不是想出来的》、 《 Web百发百中》、《这样的公司 制度很有用》。 柳泽大辅谈如何想出好创意 码农 59 自己的工作,或者有些人即使刚开始喜欢自己的工作,也无法⼀ 直保持对工作的热情。对此您是怎么看的? 柳泽大辅:我个人认为工作是⼀件有趣的事,但肯定也会有人认 为“工作是⼀种煎熬”。在这里我给大家出个主意。你可以这么 想:“如果不工作靠什么生存呢?”从这个角度去考虑,你就会发 现你会有许多意想不到的选择。 图灵社区:您有⼀个观点:无论是谁只要掌握了方法就能提出大 量的创意(暂且不论创意的好坏)。这里的方法有比如结果逆推 法、曼陀罗思考法、创意公式法,还有贵公司独创的Lonely Idea等等。但从我个人的观察来看,似乎出点子还跟个人的性格 有⼀定关系。比如有些性格外向的人,在头脑风暴的时候可能就 会比较活跃。对此您怎么看? 柳泽大辅:有研究表明,如果脑部的某处受损,原本开朗的人会 变得忧郁。⼀个人的创造力也许是与生俱来的。不过如果说“出 点子完全是由性格决定的”,那就有点太悲观了。我个人相信, 无论是谁都能想出许多创意来。 图灵社区:贵公司有⼀项“闪光弹”服务,替别人出点子,比如起 名字、如何进行演讲、生意怎么做等等,1个点子100日元。当 时为什么会想到开展这项业务? 柳泽大辅:我想通过这项服务向大家传达这样的理念:点子多了 世界就会变得充满活力。同时,这项业务也是为了我们自己进行 思维锻炼之用,并不是正经生意。1个点子100日元只能是倒贴 钱…… 码农 60 图灵社区:在这项业务中,所有问题都能得到解决吗?如果客户 觉得不满意,贵公司有什么措施吗? 柳泽大辅:对于这项业务,我们本着⼀个原则:全力以赴。至于 是否真的能想出好点子来,我们自己也不太清楚。不过对于每个 单子,我们最少提供11 个点子。只要能够以此拓宽客户的视野, 我们的努力就没有白费。 图灵社区:在进行头脑风暴时,除了做好分工(推动者、丢人 者、积极乐观的点子王)以及遵循三项基本原则(保证创意数 量、不要否定别人、听取别人意见)以外,在开始之前还应该做 ⼀些准备工作,比如说查阅资料等等。那么是不是需要看很多资 料呀?如果是24小时之内就需要的点子,怎么来得及看资料呢? 柳泽大辅:在进行头脑风暴前,并不需要看很多资料。在头脑风 暴中迸发出的点子,是比较原始的,或者可以说是⼀些“种子”。 这些“种子”能否生根发芽(即在现实生活中是否可行)?是否有 重复?是否有需求?这些问题都是需要在事后进行详细调查的。 不过在进行头脑风暴时可以带PC,对于不断迸发的想法,可以 实时地用搜索引擎查询相关资料。 图灵社区:那些负责“闪光弹”服务的员工(目前是11 名吧),每 天给别人出点子,会不会很累呀?个人觉得头脑风暴是⼀件非常 消耗体力的事情,而且客户提出的要求也都不太⼀样。 柳泽大辅:正如刚才所说的,这项业务是为锻炼思维之用,并不 是正经生意。虽然如此,这项工作也是很辛苦的。有的时候1个 单子需要100多个点子,让你连哭的时间都没有。不过,经过这 样的锻炼,你的创造力就增强不少。 码农 61 图灵社区:这样的创意产业的前景应该非常乐观。对于此项服 务,您未来有什么规划吗?比如说如何让它的销售额或者利润高 速增长。 柳泽大辅:目前我们的模式是:客户提出要求,由公司来回应。 将来我想让⼀般的用户也参与进来,让更多人感受到这种创新能 力的力量。 图灵社区:我看到贵公司每年都面向中国大学生进行招聘。25日 还要召开⼀个5国语言的企业招聘宣讲会。很少有公司会这么做 的。请问贵公司是出于什么考虑?将来是否考虑进军中国市场? 柳泽大辅:近几年,考虑到公司的全球化发展,我们公司开始面 向日本国外进行招聘。我个人认为,企业应该是超越国界的⼀种 全球化集团。我希望能将我们公司的理念推广到全世界。在我们 公司,有不少员工曾在中国受过教育,而且我们每年都会面向中 国进行招聘。这些员工对进军中国市场特别有兴趣,希望能够共 同努力。 ▉ 码农 62 欢迎阅读日文版 记者 / @乐馨 移动设备的数量 每天,全世界有371,124 名婴儿降生。 码农 63 iTran乐译 移动为什么重要? 三年之前,我第⼀次提 出 “移动优先” ( Mobile First)的思想,引来了⼀ 堆怀疑者。如今,现实情 形已经让更多的人相信, 认真对待移动互联网是多 么重要。不过,考虑到仍 会有人不太相信,下面我 就用⼀种非常生动的方式 来解释⼀下现时的情形。 每天,全世界有377,900 台iPhone售出。 每天,全世界有700,000 台Android设备激活。 码农 64 如果看iOS 设备的总量(iPhone加iPad和iPod Touch),每天售 出的Apple移动设备总数就有562,000 台。再加上Android设备, 那就是每天售出或激活127万台移动设备,比比看,每天出生的 宝宝才371,124 名。 码农 65 然而还不止这些。Nokia每天售出200,000 多台智能手机 。到 2011年底,RIM 每天售出143,000 台黑莓手机 。如此算来,每天 进入这个世界的智能手机总数就是145万台了,再比比看,每天 出生的宝宝是371,124 (原文错为317,124 )名。 码农 66 个性化计算市场的份额 显然,大量移动设备不断来到这个世界。这正给个性化计算市场 带来巨大的影响。看⼀看来自Asymco的数据 ,个性化计算最开 始的15年里,只有少数生产商(Amiga、Atari、Apple)在探 路。 接下来的15年完全被微软的WinTel 平台主宰了,除了Apple勉强 坚持。 码农 67 很快到了之前这三年,你可以看到市场完全重新洗牌,至今仍未 结束。Apple和Android大量蚕食着个性化计算市场。这是因为今 天的移动设备已不只是电话,它是我们所拥有的最具个性化的电 脑:随时陪伴我们,⼀直保持连接,且具备高性能。 天赐良机 码农 68 作者 / Luke Wroblewski @lukew Bagcheck联合创始人及 CPO。Bagcheck在公开 成立九个月后就被Twitter 收购。此前,曾是 Benchmark Capital 的驻 创家(EIR),及Yahoo 首席设计师(Chief Design Architect (VP))。 移动设备接管了个性化计算,同时为软件公司和软件服务造就了 大量机会。想想PayPal的移动支付业务。2009年,移动支付总 额为1.41 亿美元,到2011年底,这⼀数字已增涨至40亿美元 。 你没有看错,就是在三年时间里从1.41 亿涨到40亿。 eBay的趋势差不多。2011年eBay的成交总量(GMV)达到了50 亿 ,比2010年20亿的GMV翻了⼀倍还多。2009年只有6亿 。 码农 69 希望这组数据能帮助⼀些移动怀疑论者看到我们正面临的机遇。如果你还需 要更多信心方肯释疑,可以看看我正在推出的数据海报(data post)系列,从 而更深入地了解移动市场,以及其它内容。 ▉ 查看英文原文:Why Mobile Matters 译者 / 晨星 @steedhorse 单车歌手,浴室票友;红 酒葫芦,绿茶水泵;有限 版主,无量书虫;职业码 农,业余译工(Java语言 精粹,软件开发者路线 图,敏捷开发的艺术, C#3.0设计模式,代码之 美)。 对于应用该是个啥样子以及如何运作,Android 平台并没有硬性 的准则。谷歌⼀开始就很明确,他们没有规定什么是可接受的, 什么不是。这里有⼀系列《UI准则》 ,但多数只是关注像图标 (icons)、部件(widget )和菜单(menu)这样的小玩艺。 Android 平台面世以来,曾出现过成千上万套不同应用 UI 方案, 应用的观感非常不统⼀。现在,随着平台的成熟和应用数量的激 增,Android UI 的交汇点正在出现 。某些 UI 特性已经成为通用 标准,其中的⼀些甚至已经通过某种方式成为了 SDK 库的⼀部 分。不久,用户可以期待应用以更加统⼀的方式运作。某些控制 和交互模型将成为 Android 整体体验的⼀部分。 在本文中,我想从某个较高的层次来总结 Android UI 的常见功 能。之前我曾写过⼀些关于 UI 模式的文章,但从未从宏观的角 图灵访谈 作者 / Juhani Lehtimaeki @lehtimaeki Snapp TV公司(⼀家位于 英国的创业公司)Google TV和Andorid开发主管。 码农 70 iTran乐译 Android 应用该是 个啥样子? 度来看待过这个问题。现在,我想将它们归拢起来,以展现我对 Android 应用看起来应该是啥样子的观点。 冰淇凌三明治 就在不久之前,最新的 Android 版本(4.0)发布了。该版本中 出现了有“史”以来数量最多的用户体验改进。很自然,这些改进 将会影响将来 Android 应用的外观。⼀些改进可以向前移植到旧 版本,但是并不是所有的都可以。本文主要讨论当下 Android 应 用的外观。我们可以期待很快就看到 ICS UI 的变革,但事实 是:市场上有差不多 200,000,000 部 Android 设备运行从 2.1 到 2.3 之间的版本。 应用登录画面 很多应用都使用了仪表盘(Dashboard) UI 模式。如果应用的 主功能超过⼀项,此界面将会是个非常不错的起点。仪表盘展现 了应用最重要的功能,并提供了简便的快捷访问方式。 码农 71 Android 用户都非常熟悉仪表盘。如果运用得当,该方法能够让 用户在第⼀眼看到应用时产生“宾至如归”的感觉。 码农 72 通用应用程序画面 实际的窗体画面总是以多种形式出现,但只有少数特性变得非常 通用,并被用户学习、掌握和期待。屏幕顶端的操作条(Action Bar)非常通用而且易于把握概念。 • 左上角扮演应用图标或者Home图标的角色。点击操作即 可把用户带到应用的首页。新的操作条将用户带到上⼀级 画面,而不是首页,这种做法是毫无意义的。 • 操作条的中间将会扮演提供画面标题的角色,同时显示应 用的品牌颜色,或当前应用子功能的颜色。 • 屏幕的右上角会放置代表当前画面的最重要的、可执行功 能的图标。这部分应当只有与当前画面内容相关的动作。 但搜索功能已成为⼀个常见的例外。 码农 73 请查阅 Jake Wharton 的 ActionBarSherlock 库项目 了解操作条 的实现。 码农 74 列表画面 列表是 Android UI 中最常见的部件之⼀。在展示数据时,如果 不知道数据量将会有多大,它将会很有用。 当然,列表也有自己的弊端。为较好地展示列表内容的全貌,每 个条目应相对较小。但另⼀方面,如果把大量信息塞到狭小的区 域内,可能会导致用户难以使用列表及查阅要交互的条目。 关于如何使用列表,如果有些准则将会是件好事。用户已经习惯 于某些特定的元素和功能,如果列表遵循了某个类似的方法,用 户的学习曲线将会更为平缓。 列表画面的操作条 列表画面可使用操作条来展示整个列表所指向的目标操作。请注 意,列表画面的操作条不应当是用户对某个(或多个但不是全 部)列表条目执行操作的位置。 列表项和勾选框 通常,列表项自身仅包含很少的文本和图片元素。常见的情况 是,每个列表项都有⼀个勾选框,用于选择⼀个或多个列表项来 执行操作。 将勾选框放在列表项的最左端有以下几个好处: 1. 我们习惯于在所选项目的左边看到勾选框。无论网页、桌 面程序用户界面,还是在移动设备的某个地方,都是这 样。 码农 75 2. 在列表项的边上放置⼀个勾选项,允许我们给勾选框建立 更大的点击区域,由此能让用户更轻松地区分是对某个列 表条目进行点击还是选择。 3. 条目左边的图形部件创建了便捷的可视化提示,它会告诉 用户某个条目结束,而另⼀个条目开始,使用户对列表的 快速扫描更加轻松。 次要条目控制 ⼀些条目需要更多的交互可能性,而不仅仅是选择(勾选框)或 者导航(点击)。这种控制方式最常见的例子是对行条目加注星 号或者添加书签。次要控制的唯⼀正常位置是条目的最右端。放 在其它任何位置都会有点击区域方面的问题。 码农 76 Aldiko 和 GMail 是恰当运用列表的出色范例。Aldiko 选择将勾 选框放在右边,因为它们有可见的文件夹图标,如果再在其后放 置勾选框,将使UI失去平衡。 码农 77 永无止境的列表 很多列表中包含的项目都要通过网络来加载。加载过程可能会花 上⼀些时间,生成新的列表项的速度可能会赶不上用户滚动操作 的速度。当用户滚动到列表的底部时,应用应当自动开始获取更 多列表项。指示器(Indicator)则告诉用户,有更多正在加载的 条目将会出现在列表的尾部。其中,使用进度条这样的加载动画 是个不错的想法。用户会把动画和正在执行中的任务关联起来。 码农 78 到达列表的底部时,Android Market 和 Twitter 都会自动加载更 多列表项。 单行操作——长按——快速操作 给用户提供⼀种无须先进入条目画面,即可对单行条目执行操作 的方法。 码农 79 由于电话和平板设备没有鼠标右键(实际上也没有左键),触摸 屏特定的“右键点击”由此产生。通过长按某个条目,用户表明他 们想要对该特定条目执行某个操作。 有种“快速操作”用户界面模式,可用于显示某个条目对应的操 作。最初所使用的图形方法,现在看来几乎都已经绝迹,但其概 念犹存。通常是某种形式的覆盖菜单,显示⼀份非常简单的操作 列表,⼀般只有 3 到 5 项。无论快速操作是如何实现的,有几 点必须谨记: • 不要覆盖选中的条目!特别是在删除操作时。如果能够⼀ 直看到要操作的目标条目,用户的信心将会倍增。 • 只显示简单的操作。需要大量交互的操作应当在单独的条 目画面中处理,而不是在快速操作当中。 Aldiko和Astro都是良好的设计范例,但Google+ 用了⼀个简单的 弹出框,从而违背了“覆盖目标条目”这⼀规则。我希望他们能够 在将来的版本中修正这⼀可用性缺陷。 码农 80 Aldiko、Astro文件管理器和Google+ 在快速操作中使用了多种不 同的视觉风格。无论使用哪种风格,它们都通过长按画面中某个 条目来调用。 码农 81 多条目操作 如果列表中使用了前面谈到的勾选框控件,就可以允许用户选择 多个条目。通过选择多个条目,用户表达了他们要对所有选中条 目执行某个操作的意图。 处理多个条目操作的常见方法,是当用户勾选后,画面底部增加 ⼀个面板,提供多个可用操作的按钮。⼀段漂亮的滑动动画将会 给 UI 添加不少平滑和精致的感觉。当最后⼀个选项被选中或者 操作执行后,该面板将会自动消失。 码农 82 在多条目操作方面,Aldiko 和 GMail 都处理得不错。底部面板 出现时,两个应用都会播放⼀段精美的滑动动画。Aldiko 还在 import 按钮当中添加⼀个数字来告诉用户共选中了多少个条目。 这是个非常不错的额外功能,但并不适用于所有的情况。 码农 83 关于列表的更多信息 要了解关于列表的更多技术细节信息,请阅读以下两个系列的优 秀文章: Styling Android 的 Mark Allison: • ListView – Part 1 • ListView – Part 2 • ListView – Part 3 • ListView – Part 4 AndroidDevBlog 的 Cyril Mottier: • ListView Tips & Tricks #1: Handle emptiness • ListView Tips & Tricks #2: Section your ListView • ListView Tips & Tricks #3: Create fancy ListViews • ListView Tips & Tricks #4: Add several clickable areas 标签页 很多应用都通过某种形式使用标签页,来帮助用户在多个页面中 操作。Android 版本 Honeycomb (3.0) 和 Ice Cream Sandwich (4.0) 对标签页的工作模式及外观做了大幅修改。我认为,我们 应该尝试在所有应用中加入这些修改,无论是运行在哪个版本 中。 码农 84 我在这篇博文 中写过关于 ICS 的内容,在此我不打算重复该内 容。长话短说,是标签页间进行导航有了新的方法。用户的期待 是:如果应用中有标签页,他们可以通过拖动(Swiping)的方 式来切换。 码农 85 Android Market 和 Google+ 是通过拖动手势在多个标签页中进 行导航操作的不错范例。 Mark Allison 也曾撰写了关于该技术实现的多篇出色文章: • ViewPager – Part 1 • ViewPager – Part 2 • ViewPager – Part 3 如果需要实现细节方面的帮助,可以看看Jake Wharton 的项 目:ViewPagerIndicator at GitHub ▉ 码农 86 结论 Android 正在迅速发育成 熟成⼀个可靠且稳定的平 台。应用在观感方面开始 具备全面的稳定性,而用 户则开始期待使用确定的 方式来交互。尽管没有官 方的准则,但对出色的应 用进行深入研究,我们可 以更好地理解自己应该如 何去做。 译者 / 惑者 Python、 Django 等基于 开源社区项目的IT技术狂 热分子,业余级别的中翻 英译者,小型 Android +J2EE 团队项目协调者 (自我定义)。 查看英文原文:What Android Apps Should Look like? 我得说:我讨厌Pinterest。 哦,这么说也不准确,因为我对它可不单单是厌恶。我憎恶 Pinterest,而且希望它死得难看点儿;这不仅是为我自已考虑, 也是为了全人类着想。 吐槽两句之后,感觉心情好多了,唉……好吧,在你们开始喷我 之前,容我先辩解⼀下。 背景信息 对外行来说,Pinterest 是人们分享和浏览图片的地方,简单来讲 就是这样的。图片几乎可以来自网络上的任何地方(至少包括所 图灵访谈 作者 / Reggie Ugwu @ocugwu Complex 网站记者 码农 87 iTran乐译 为什么Pinterest是最 让人失望的社交网络? 有的非成人网站),Pinterest让人们只用⼀次点击(即所谓 的“Pinning”)即可分享这些图片,大大简化了操作。 每个用户都可以将照片(视频也可以,不过不常见)整理到各 种“pinboards”(别针板)上。这样,如果我在网上看到了喜欢的 小狗的照片,我就可以把它pin到名为“Dogs”的pinboard上。这 不仅是种社交行为,也是种自利行为。因为发布到Pinterest上的 东西默认都是公开的,人们可以表示喜欢或进行评论;而这些图 片同时也保存在了你的空间里,以后需要它们的时候,可以随时 调用。下次我去宠物店里买小狗,就可以将“Dogs”板给店家看, 告诉他们我需要哪种小狗。 Pinterest大约在两年前上线,之后很长⼀段时间里,这个网站都 比较封闭(尽管现在仍然需要被邀请才能注册,但已经容易多 了),所受关注不多。然而,在去年年底的时候,它开始急速成 长,而且出人意料地先在女性中流行起来 。Pinterest就是从那会 儿开始爆发的。 今年1月份,comScore的报道 称,Pinterest在之前⼀个月里积累 了1170 万的独立访客(UV)——这个数字对于成立不到两年的 网站来说是史无前例的。然后,关注这类产品的人们(包括我 们 )就宣称,Pinterest是下⼀个革命性产品(The Next Big Thing)。 为什么Pinterest最糟糕 这是我的理由:这个网站现在的形式,就是⼀个金玉其外的污水 坑,散发着其封闭的梦想。它引导甚至鼓励社交网络上最令人失 码农 88 望的⼀些动机——它从其他富有创意的网站上抽取内容,但却不 回馈任何东西。 根据我的Gmail记录,我从2010年7月7号开始就是Pinterest的用 户了,或多或少见证了这把火是怎么烧起来的。你不用在 Pinterest上花多少时间,就能感受到这个网站深层的、无处不在 的浅薄,而这种浅薄已经成为它赖以生存的要素。这些天来,主 页上充满了大量萌物照、高跟鞋照片,以及颇有艺术感的甜点照 片。 Pinterest的这个样子,并不是因为它是所谓“女性主导”的,而是 因为它让人们不再创造,而去分享。即使以社交网络的标准来 看,在鼓励人类进行有价值的活动方面,Pinterest依然代表了前 码农 89 码农 90 译者 / 张重骐 @candyhorse 北邮土著,本科学习设 计,研究生转攻技术。接 触 Python⼀年多,喜欢折 腾web应用开发。 热爱互联网,之前在百 度、创新工场做过16个月 的产品经理实习生,对 LBS产品、图片应用有⼀ 定了解和研究。现在果壳 网做实习Python工程师。 在奔向文青与极客的道路 上艰难前行。 所未有的低水准。它是缺少有力沟通工具和社区建设工具的 Facebook,是没有地道的自我表现平台的Tumblr ,是不需要拍 摄或编辑照片的Instagram。 在Pinterest上,人们挑选并分享那些据说是“启发”了他们的图 片,乍⼀看好像是⼀种很慷慨的举动。但我们在这儿关注的除了 被分享的东西外,还有分享者自身。Pinterest的用户竭力追 求“粉丝数”,所以他们要做的就是发布最漂亮、最幽默或是最鼓 舞人的照片、图片以及产品——然而这些东西中的绝大多数都是 其他人创作或拥有的,而且没有授权给你使用。Pinterest奉行⼀ 种宗旨:我喜欢这样做,所以我就这样做;在这⼀点上,它比同 时代的其他产品要严重得多。 Pinterest原则上鼓励用户标明作品的原始出处,但可以料想,其 用户大都不注意这些。目前看来,它会让你觉得像是身处 Tumblr,而作品却被贴在Pinterest,这⼀切怎么可能呢?上月末 的时候,它被迫发布了⼀个HTML代码“nopin”,让其他网站保护 其内容,以免在未经允许的情况下被分享到Pinterest上,像 Flickr这样的网站几乎立即加上了这个代码 。 此时此刻,要求我们的社交媒体不再追求“平均停留时间”的增 长,可能有些过分。网上的事物越来越注重是否能改善我们的生 活体验,即使扭曲或者重新定义了我们的生活,然而这已经是大 势所趋。不过,我们期盼的是更好的产品,而不是像Pinterest这 样的现代互联网蛀虫。这个“虚拟的别针板”所承诺的世界,就像 针头⼀样空洞。 ▉ 很明显HTML5的应用是用JavaScript写的,但是跟其他的开发环 境相比(例如⼀些原生的),JavaScript⼀直有个很严重的局限 性:它的所有执行进程都在同⼀个线程里。 对于如今像i5/i7 这种动辄就8个CPU的多核处理器来说,这就有 些麻烦了。最新的ARM手机处理器也都是双核或者4核。顺利的 话,我们有望看到HTML5为Web 开发提供⼀个应对这些又新又 强劲的处理器的方法,让我们可以拥抱⼀个Web 应用开发的新时 代。 图灵访谈 作者 / David Rousset @davrous Windows 8/HTML5布道师 码农 91 iTran乐译 JavaScript并行运算新机遇 ——Web Workers的神奇魔法 在没有 Workers 之前 这个JavaScript的局限性意味着⼀个长时间运行的进程会冻结主 窗口。我们常说我们被“UI 线程”阻塞,这是因为主线程在处理所 有的可视化元素及其相关任务:绘制,刷新,动画,用户输入事 件等等。 我们都知道这个线程过载的严重后果:页面冻结,并且用户不能 再与应用进行交互了,这时的用户体验相当差。用户可能关掉这 个Tab 或者整个浏览器,你当然不希望看到这发生在你的app 上。 为了避免这种情况,浏览器引入了⼀种保护机制:当⼀个脚本有 可能长时间运行时,会对用户进行提示。 悲剧的是,这种机制并不能正确分辨究竟是脚本编写得有问题, 还是它确实需要更多的时间来完成它的工作。尽管如此,因为它 阻塞了UI线程,所以还是提示现在可能发生错误了比较好。下面 是⼀些提示消息的例子(从Firefox 5 和 IE9 获得): 码农 92 迄今为止,由于以下两个原因,那些问题已经很少发生了: 1. 因为其他的技术可以完成多线程的任务,HTML和 JavaScript的使用方式和使用目的已经与不同于以往。与 本地应用相比,网站提供的体验更简单了。 2. 总有⼀些其他的办法可以或多或少地解决这些并发问题。 那些办法都是Web 开发者所熟知的。例如,通过 setTimeout() 和 setInterval()方法,我们可以尝试模拟并行 任务。通过 XMLHttpRequest对象,也可以异步地处理HTTP 请 求,避免从远程服务器载入资源时冻结UI。最后,应用DOM 事 件写出的应用程序能够给人⼀种错觉,让人误以为几个事件是在 同时发生。真的是错觉吗?是的! 为了更好的理解其原理,让我们来看⼀段伪代码,并且看看在浏 览器内部究竟发生了什么: 码农 93 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 让我们为这段代码建立⼀个模型。这个图表展示了在⼀个时间段 内,浏览器内部发生了什么: 这个图表很好地诠释了任务的非并行本质。5毫秒后,用户产生 ⼀个鼠标点击事件。然而,由于init()方法仍然在执行,并且独占 了主线程,所以这个事件不能被立即处理。点击事件将被保存并 且延迟处理。 • 从5毫秒到10毫秒之间:init()方法在这5毫秒中仍然执行, 然后在10毫秒时请求调用 timerTask() 方法。这个方法理 论上应该在20毫秒的时间点执行。 码农 94 • 从10毫秒到15毫秒之间:init()方法仍然需要5毫秒来完成 运行。这与15毫秒时的黄色区块相对应。由于我们冻结了 主线程,所以浏览器现在才可以继续进行刚才保存的请 求。 • 从15毫秒到23毫秒之间:浏览器开始执行 handleMouseClick()方法,该方法执行了8毫秒(蓝色区 块)。 • 从23毫秒到25毫秒之间:作为⼀个副作用,在20毫秒时间 点就应该执行的timerTask()方法被稍微平移了3毫秒。 而其他的时间点(例如30ms、40ms),被当作没有代码 占用CPU。 说明:这个例子和上面的图表(通过特征监测机制判断使用SVG 或者PNG)是受到这篇文章的启发:HTML5 Web Workers Multithreading in JavaScript 所有这些提示并没有解决我们最初的问题:所有东西都在主UI线 程里执行。 此外,即使JavaScript还没有被用来开发像其他“高级语言”⼀样 的应用,它仍然在随着HTML5和其相关技术所提供的新的可能 而改变。因此给JavaScript赋予更多新的能力,使之能够建立新 ⼀代的能够处理并行任务的应用,就变得更加重要了。这就是为 什么我们有了Web Workers。 码农 95 Web Workers或如何在UI线程外执行代 码 Web Workers APIs定义了⼀个在后台运行脚本的方法。你可以 在主页面之外的线程执行⼀些任务,而不影响页面的绘制性能。 然而,如同不是所有的算法都能并行执行,也不是所有的 JavaScript代码都能从Workers中受益。Ok,唠叨得够多了,我 们看看这些著名的Workers。 我的第⼀个Web Worker 由于Web Workers将在⼀个独立的线程里执行,你必须把代码从 主页面中分离出来,放到独立的文件中。完成这些后,需要实例 化⼀个Worker对象来调用它们: var myHelloWorker = new Worker('helloworkers.js'); 然后就可以给它发送⼀条信息来开启Worker(由此也开启了⼀ 个窗口之外的线程): myHelloWorker.postMessage(); 是的,Web Workers和主页面通过消息进行通信。这些消息可以 是⼀般的字符串或者JSON对象。为了演示简单的消息发送,我 们来review⼀个非常基础的例子。这个例子会发送⼀个字符串给 worker,将其与worker联系起来。首先,将下面代码放到“ helloworker.js”文件中: function messageHandler(event) { 码农 96 1 // Accessing to the message data sent by the main page var messageSent = event.data; // Preparing the message that we will send back var messageReturned = "Hello " + messageSent + " from a separate thread!"; // Posting back the message to the main page this.postMessage(messageReturned); } // Defining the callback function raised when the main page will call us this.addEventListener('message', messageHandler, false); 我们只在“helloworkers.js”中定义了⼀小段将在另⼀个线程执行 的代码。它可以从主页面接收消息,执行任务,并向主页面返回 ⼀个消息。然后我们需要在主页面编写⼀个接收者。下面是处理 消息的页面: Hello Web Workers
运行的结果将是:"Hello David from a separate thread!” ,你被 打动了,有木有? 你要注意worker会⼀直存活,直到它被终止。 既然没有自动垃圾收集,那么控制它们的状态就全靠你自己了。 要记住,初始化⼀个worker会消耗⼀定的内存……而且也不要忽 略冷启动时间。要想停止⼀个worker,有两种可能的方式: 1. 从主调用页面调用terminate()命令。 2. 在worker内部通过调用close()命令。 码农 98 12 13 14 15 16 17 18 19 20 21 22 23 24 25 演示:你可以在浏览器中测试这个稍微增强了⼀点的例子: http://david.blob.core.windows.net/html5/ HelloWebWorkers_EN.htm 通过JSON发送消息 当然,大多数时候我们会发送更加结构化的数据给Workers。 (顺便说⼀下,Web Workers也可以通过Message channels 进 行通讯)。 但是使用JSON格式是唯⼀可以给worker发送结构化消息的方 法。幸运的是,浏览器现在支持worker的程度已经与原生支持 JSON的程度⼀样好了。它们真是太好了! 让我们拿出之前的代码例子。我们打算增加⼀个 WorkerMessage类型的对象。该类型将被用于向Web Workers 发送⼀些带参数的命令。 我们使用下面这个简化版的HelloWebWorkersJSON_EN.htm 页 面: Hello Web Workers
我们使用⼀种非侵入式的JavaScript方法来分离表现层和逻辑 层。然后绑定的逻辑就存在于HelloWebWorkersJSON_EN.js 文 件中: // HelloWebWorkersJSON_EN.js associated to HelloWebWorkersJSON_EN.htm // Our WorkerMessage object will be automatically // serialized and de-serialized by the native JSON parser function WorkerMessage(cmd, parameter) { this.cmd = cmd; 码农 100 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 1 2 3 4 5 6 this.parameter = parameter; } // Output div where the messages sent back by the worker will be displayed var _output = document.getElementById("output"); /* Checking if Web Workers are supported by the browser */ if (window.Worker) { // Getting references to the 3 other HTML elements var _btnSubmit = document.getElementById("btnSubmit"); var _inputForWorker = document.getElementById("inputForWorker"); var _killWorker = document.getElementById("killWorker"); // Instantiating the Worker var myHelloWorker = new Worker('helloworkersJSON_EN.js'); // Getting ready to handle the message sent back // by the worker myHelloWorker.addEventListener("message", function (event) { _output.textContent = event.data; }, false); // Starting the worker by sending it the 'init' command myHelloWorker.postMessage(new WorkerMessage('init', null)); // Adding the OnClick event to the Submit button // which will send some messages to the worker 码农 101 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 _btnSubmit.addEventListener("click", function (event) { // We're now sending messages via the 'hello' command myHelloWorker.postMessage(new WorkerMessage('hello', _inputForWorker.value)); }, false); // Adding the OnClick event to the Kill button // which will stop the worker. It won't be usable anymore after that. _killWorker.addEventListener("click", function (event) { // Stopping the worker via the terminate() command myHelloWorker.terminate(); _output.textContent = "The worker has been stopped."; }, false); } else { _output.innerHTML = "Web Workers are not supported by your browser. Try with IE10: download the latest IE10 Platform Preview"; } 再次说明,这个例子是非常基础的。但是,它可以帮助你理解背 后的逻辑。当然,没人能阻止你发送⼀些可以被人工智能或者物 理引擎处理的游戏元素。 演示:可以在这儿测试JSON的例子: http://david.blob.core.windows.net/html5/ HelloWebWorkersJSON_EN.htm 码农 102 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 浏览器支持 Web Workers刚刚出现在了IE10平台预览版上。Firefox(3.6 以 上)、Safari(4.0 以上)、Chrome和Opera11也都支持它。然 而,这些浏览器的手机版并不支持。如果你想获得更详尽的浏览 器支持列表,可以看看这里: http://caniuse.com/#search=worker 要实时地了解代码的支持情况,请使用特性监测机制。(你不应 该使用神马用户代理嗅探!) 为了帮助你实现,这里有两个可用的解决方案。第⼀个是用这样 ⼀小段代码,自己简单地测试特性: /* Checking if Web Workers are supported by the browser */ if (window.Worker) { // Code using the Web Workers } 第二个是使用著名的Modernizr 库(现在已经原生的移到了 ASP.NET的MVC3项目模版中)。然后,只要用下面这样⼀段代 码即可: 例如,这就是你的浏览器支持情况:Web Workers are not supported inside your browser. 这将使你的应用产生两个版本。如果Web Workers不被支持,就 正常执行你的avaScript代码。在大多数现代浏览器中,Web Workers是被支持的,这种情况下就可以推送⼀些JavaScript代 码给workers,以便提高应用的性能。这样就不必中断任何事, 或为最新的浏览器单独建立⼀个版本了。在全部浏览器中,它都 能运行,只是性能稍有差别。 Worker不能访问的元素 ——Worker不能干什么 与其看看你用Workers不能干什么,不如让我们了解⼀下你只能 用worker干点儿什么: 码农 104 译者注:原文页面对当前 浏览器支持情况进行监 测,并将结果展示在这 里。 5 6 7 8 9 码农 105 Method Description void close(); Terminates the worker thread. void importScripts(urls); A comma-separated list of additional JavaScript files. void postMessage(data); Sends a message to or from the worker thread. Attributes Type Description location WorkerLocation Represents an absolute URL, including protocol, host, port, hostname, pathname, search, and hash components. navigator WorkerNavigator Represents the identity and onLine state of the user agent client. self WorkerGlobalScope The worker scope, which includes the WorkerLocation and WorkerNavigator objects. 说明:这些表格是从MSDN文档中引用的:HTML5 Web Worker 码农 106 Event Description onerror A runtime error occurred. onmessage Message data received. Method Description void clearInterval(handle); Cancels a timeout identified by handle. void clearTimeout(handle); Cancels a timeout identified by handle. long setInterval(handler, timeout value, arguments); Schedules a timeout to be run repeatedly after the specified number of milliseconds. Note that you can now pass additional arguments directly to the handler. If handler is a DOMString, it is compiled as JavaScript. Returns a handle to the timeout. Clear with clearInterval. long setTimeout(handler, timeout value, arguments); Schedules a timeout to run after the specified number of milliseconds. Note that you can now pass additional arguments directly to the handler. If handler is a DOMString, it is compiled as JavaScript. Returns a handle to the timeout. Clear with clearTimeout. 总之,你没有操作DOM 的权限。这有⼀个非常好的图表作为总 结: 举个例子,既然在worker中无法操作window对象,因此就无法 访问本地存储(Local Storage,反正看起来也不像线程安全 的)。对于在其他环境中习惯了多线程操作的开发者来说,这些 限制或许看起来过于严格了。然而,它带来的最大的优点,就是 我们不会再陷入那些经常遇到的问题:死锁、竞争条件等。在 Web Workers中,完全不用考虑对于这些。这样,当⼀些特定的 场景需要增强性能时,Web Workers是非常好用的。 码农 107 错误处理与调试 处理Web Workers的错误非常容易,用与注册OnMessage事件 同样的方法,注册⼀个OnError事件即可: myWorker.addEventListener("error", function (event) { _output.textContent = event.data; }, false) 这已经是为了调试代码,Web Worker所提供的最好的原生支持 了……非常有限,对吧? 通过F12 开发工具获得更好的调试体验 为了突破这些局限,IE10在它的脚本调试器中提供了⼀个直接调 试Web Workers 代码的功能,就像调试其他脚本⼀样。 对此,你需要通过F12 健调出开发者工具栏,并且打开“脚本“标 签。现在,应该还看不到与worker相关的JS文件。但⼀旦点 击”开始调试“按钮,它就应该神奇地出现了: 码农 108 1 2 下⼀步就是像调试以往的JavaScript代码⼀样,调试worker了! IE10是目前唯⼀支持这样调试的浏览器。如果想了解更多关于这 个特性的细节,可以读⼀下这篇文章:Debugging Web Workers in IE10 ⼀个用来模拟console.log()的有趣方法 最后,你要知道,在worker中是不能使用console对象的。通 过.log()方法来跟踪worker内部发生了什么是没有用的,因为 console对象没有定义。幸好,我找到⼀个有趣的方法,即通过 MessageChannel:console.log() for Web Workers ,它可以模 拟console.log()行为。该方法在IE10、Chrome和Opera中运行 良好,但是在Firefox中还不行,因为Firefox还不支持 MessageChannel。 码农 109 说明:为了使链接中的例子能在IE10下能运行,需要把下面这行 代码: console.log.apply(console, args); // Pass the args to the real log 修改成: console.log.apply(console, args); // Pass the args to the real log 然后,应该可以得到这样的结果: 例子:如果想使用这个console.log()模拟,请到这里: http://david.blob.core.windows.net/html5/ HelloWebWorkersJSONdebug.htm 码农 110 用例分析与可以取代的场景 在哪些场景中使用Web Workers ? 在网上查找Web Workers的例子,总会找到这⼀类:强化的数 学/科学计算。然后是⼀些JavaScript光线跟踪、分形、素数之类 的东西。它们虽然是理解Workers运行方式的好例子,但无法就 如何在”真实的世界“的应用中使用它们给出具体建议。 确实,上面展示的这些Web Workers的缺点缩小了限制了使用 Web Workers的有趣场景。尽管如此,花点儿时间仔细想想,就 会发现⼀些新的有趣用途: • 图像处理 通过使用或者

下载文档,方便阅读与编辑

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 5 金币 [ 分享文档获得金币 ] 2 人已下载

下载文档

相关文档