程序员必读书单 1.0

作者:Lucida

原文链接:http://lucida.me/blog/developer-reading-list/

本文把程序员所需掌握的关键知识总结为三大类19个关键概念,然后给出了掌握每个关键概念所需的入门书籍,必读书籍,以及延伸阅读。旨在成为最好最全面的程序员必读书单。

前言

Reading makes a full man; conference a ready man; and writing an exact man.

Francis Bacon

优秀的程序员应该具备两方面能力:

  • 良好的程序设计能力:
    • 掌握常用的数据结构和算法(例如链表,栈,堆,队列,排序和散列);
    • 理解计算机科学的核心概念(例如计算机系统结构、操作系统、编译原理和计算机网络);
    • 熟悉至少两门以上编程语言(例如C++,Java,C#,和Python);
  • 专业的软件开发素养:
    • 具备良好的编程实践,能够编写可测试(Testable),可扩展(Extensible),可维护(Maintainable)的代码;
    • 把握客户需求,按时交付客户所需要的软件产品;
    • 理解现代软件开发过程中的核心概念(例如面向对象程序设计,测试驱动开发,持续集成,和持续交付等等)。

和其它能力一样,程序设计能力和软件开发素养源自项目经验和书本知识。项目经验因人而异(来自不同领域的程序员,项目差异会很大);但书本知识是相通的——尤其是经典图书,它们都能够拓宽程序员的视野,提高程序员的成长速度。

在过去几年的学习和工作中,我阅读了大量的程序设计/软件开发书籍。随着阅读量的增长,我意识到:

  • 经典书籍需要不断被重读——每一次重读都会有新的体会;
  • 书籍并非读的越多越好——大多数书籍只是经典书籍中的概念延伸(有时甚至是照搬);

意识到这两点之后,我开始思考一个很功利的问题:如何从尽可能少的书中,获取尽可能多的关键知识?换句话说:

  • 优秀的程序员应该掌握哪些关键概念?
  • 哪些书籍来可以帮助程序员掌握这些关键概念?

这即是这篇文章的出发点——我试图通过程序员必读书单这篇文章来回答上面两个问题。

标准

进入必读书单之前,我先介绍下书单里的书籍选择标准和领域选择标准。当然你也点击这里直接跳转到书单开始阅读。

书籍选择标准

  1. 必读:什么是必读书籍呢?如果学习某项技术有一本书无论如何都不能错过,那么这本书就是必读书籍——例如Effective Java于Java,CLR via C#于C#;
    • 注意我没有使用“经典”这个词,因为经典计算机书籍往往和计算机科学联系在一起,而且经典往往需要10年甚至更长的时间进行考验;
  2. 注重实践,而非理论:所以这个书单不会包含过于原理性的书籍;
  3. 入门—必读—延伸:必读书籍的问题在于:1. 大多不适合入门;2. 不够全面。考虑到没有入门阅读和延伸阅读的阅读列表是不完整的——所以书单中每个关键概念都会由一本入门书籍,一本必读书籍(有时入门书籍和必读书籍是同一本),和若干延伸阅读书籍所构成。

概念选择标准

  1. 全面:全面覆盖软件开发中重要的概念;
  2. 通用:适用于每一个程序员,和领域特定方向无关;
  3. 注重基础,但不过于深入:优秀的程序员需要良好的计算机科学基础,但程序员并没必要掌握过于深入的计算机科学知识。以算法为例,每个程序员都应该掌握排序、链表、栈以及队列这些基本数据结构和算法,但计算几何、线性规划和网络流这些算法可能就不是每个程序员都需要掌握的了;

通过这几个标准,我把程序员应掌握的关键概念分为程序设计,软件开发,以及个人成长三大类,每一大类均由若干关键概念组成。

快速通道

自从开博以来,经常会有朋友在论坛,微博,和QQ上提问学习X技术读什么书合适(例如:学习Java读什么书合适?如何学习程序设计?)所以我在这 里列出了一个“快速通道”——把常见的问题集中在一起,点击问题,即可直接进入答案。(当然,如果你把本文从头读到尾帮助会更大 :–))

程序员必读书单

入门书籍

程序设计:

  1. 基础理论编码:隐匿在计算机软硬件背后的语言
  2. 编程语言
  3. 编程语言理论编程语言实现模式
  4. 程序设计程序设计方法
  5. 算法与数据结构算法(第4版)
  6. 程序调试调试九法——软硬件错误的排查之道

软件开发:

  1. 编程实践程序设计实践
  2. 面向对象程序设计Head First设计模式
  3. 重构重构
  4. 软件测试How to Break Software
  5. 项目管理极客与团队
  6. 专业开发程序员修炼之道:从小工到专家
  7. 大师之言奇思妙想:15位计算机天才及其重大发现
  8. 界面设计写给大家看的设计书
  9. 交互设计通用设计法则

个人成长:

  1. 职业规划软件开发者路线图
  2. 思维方式程序员的思维修炼:开发认知潜能的九堂课
  3. 求职面试金领简历:敲开苹果微软谷歌的大门
  4. 英语写作The Only Grammar Book You’ll Ever Need

必读书籍

程序设计:

  1. 基础理论深入理解计算机系统(第2版)
  2. 编程语言
  3. 编程语言理论程序设计语言——实践之路(第3版)
  4. 程序设计计算机程序的构造与解释(第2版)
  5. 算法与数据结构编程珠玑(第2版)
  6. 程序调试调试九法——软硬件错误的排查之道

软件开发:

  1. 编程实践代码大全(第2版)
  2. 面向对象程序设计设计模式
  3. 重构修改代码的艺术
  4. 软件测试xUnit Test Patterns
  5. 项目管理人月神话
  6. 专业开发程序员职业素养
  7. 大师之言编程人生:15位软件先驱访谈录
  8. 界面设计认知与设计:理解UI设计准则(第2版)
  9. 交互设计交互设计精髓(第3版)

个人成长:

  1. 职业规划软件开发者路线图
  2. 思维方式如何把事情做到最好
  3. 求职面试程序员面试金典(第5版)
  4. 英语写作风格的要素

这个阅读列表覆盖了软件开发各个关键领域的入门书籍和必读书籍,我相信它可以满足绝大多数程序员的需求,无论你是初学者,还是进阶者,都可以从中获益:

  • 基础理论包括了程序员应该掌握的计算机基础知识;
  • 编程语言对软件开发至关重要,我选择了CC++JavaC#Python,和JavaScript这六门主流编程语言进行介绍,如果想进一步理解编程语言,可以阅读编程语言理论里的书目;
  • 在理解编程语言的基础上,优秀的程序员还应该了解各种程序设计技巧,熟悉基本的算法数据结构,并且能够高效的进行程序调试
  • 良好的程序设计能力是成为优秀程序员的前提,但软件开发知识也是必不可少的:优秀的程序员应具备良好的编程实践,知道如何利用面向对象重构,和软件测试编写可复用,可扩展,可维护的代码,并具备软件项目管理知识和专业开发素养;
  • 就像我们可以从名人传记里学习名人的成功经验,程序员也可以通过追随优秀程序员的足迹使自己少走弯路。大师之言包含一系列对大师程序员/计算机科学家的访谈,任何程序员都可以从中获益良多;
  • 为了打造用户满意的软件产品,程序员应当掌握一定的界面设计知识和交互设计知识(是的,这些工作应该交给UI和UX,但如果你想独自打造一个产品呢?);
  • 专业程序员应当对自己进行职业规划,并熟悉程序员求职面试的流程,以便在职业道路上越走越远;
  • 软件开发是一项需要不断学习的技能,学习思维方式可以有效的提升学习能力和学习效率;
  • 软件开发是一项国际化的工作,为了让更多的人了解你的代码(工作),良好的英语写作能力必不可少。

尽管我尽可能的去完善这个书单,但受限于我的个人经历,这个书单难免会有所偏颇。所以如果你有不同的意见,或者认为这个书单漏掉了某些重要书籍,请在评论中指出,我会及时更新。:–)

程序设计

1. 基础理论

编码:隐匿在计算机软硬件背后的语言

编码:隐匿在计算机软硬件背后的语言这本书其实不应该叫编码——它更应该叫“Petzold教你造计算机”——作者Charles Petzold创造性的以编码为主题,从电报机和手电筒讲到数字电路,然后利用数字电路中的逻辑门构造出加法器触发器,最后构造出一个完整的存储程序计算机。不要被这些电路概念吓到——编码使用大量形象贴切的类比简化了这些概念,使其成为最精彩最通俗易懂的计算机入门读物。

深入理解计算机系统(第2版)

深入理解计算机系统(第2版)这本书的全名是:Computer Systems:A Programmer’s Perspective(所以它又被称为CSAPP),我个人习惯把它翻译为程序员所需了解的计算机系统知识,尽管土了些,但更名副其实。

深入理解计算机系统是我读过的最优秀的计算机系统导论型作品,它创造性的把操作系统,计算机组成结构,数字电路,以及编译原理这些计算机基础学科中的核心概念汇集在一起,从而覆盖了指令集体系架构,汇编语言,代码优化,计算机存储体系架构,链接,装载,进程,以及虚拟内存这些程序员所需了解的关键计算机系统知识。如果想打下扎实的计算机基础又不想把操作系统计算机结构编译原理这些书统统读一遍,阅读深入理解计算机系统是最有效率的方式。

延伸阅读:

2. 编程语言

编程语言是程序员必不可少的日常工具。工欲善其事,必先利其器。我在这里给出了C,C++,Java,C#,JavaScript,和Python这六种常用编程语言的书单(我个人不熟悉Objective-C和PHP,因此它们不在其中)。

需要注意的是:我在这里给出的是编程语言(Programming Language)书籍,而非编程平台(Programming Platform)书籍。以Java为例,Effective Java属于编程语言书籍,而Android编程权威指南就属于编程平台书籍。

C

C和指针

忘记谭浩强那本糟糕不堪的C程序设计,C和指针才是C语言的最佳入门书籍。它详细但又不失简练的介绍了C语言以及C标准库的方方面面。

对于C语言初学者,最难的概念不仅仅是指针和数组,还有指向数组的指针和指向指针的指针。C和指针花了大量的篇幅和图示来把这些难懂但重要的概念讲的清清楚楚,这也是我推荐它作为C语言入门读物的原因。

C程序设计语言(第2版)

尽管C程序设计语言是二十多年前的书籍,但它仍然是C语言——以及计算机科学中最重要的书籍之一,它的重要性不仅仅在于它用清晰的语言和简练的代码描述了C语言全貌,而且在于它为之后的计算机书籍——尤其是编程语言书籍树立了新的标杆。以至于在很多计算机书籍的扉页,都会有“感谢Kernighan教会我写作”这样的字样。

延伸阅读:

  • C专家编程:不要被标题中的“专家”吓到,这实际是一本很轻松的书籍,它既包含了大量C语言技术细节和编程技巧,也包含了很多有趣的编程轶事;
  • C陷阱与缺陷:书如其名,这本书介绍了C语言中常见的坑和一些稀奇古怪的编程“技巧”,不少刁钻的C语言面试题都源自这本小册子;
  • C语言参考手册:全面且权威的C语言参考手册,而且覆盖C99,如果你打算成为C语言专家,那么这本书不可错过;
  • C标准库:给出了15个C标准库的设计思路,实现代码,以及测试代码,配合C程序设计语言阅读效果更佳;
  • C语言接口与实现:这本书展示了如何使用C语言实现可复用的数据结构,其中包含大量C语言高级技巧,以至于Amazon上排行第一的评论是“Probably the best advanced C book in existance”,而排行第二的评论则是“By far the most advanced C book I read”。

C++

C++程序设计原理与实践

作为C++的发明者,没有人能比Bjarne Stroustrup更理解C++。Bjarne在Texas A&M大学任教时使用C++为大学新生讲授编程,从而就有了C++程序设计原理与实践这本书——它面向编程初学者,既包含C++教程,也包含大量程序设计原则。它不但是我读过最好的C++入门书,也是我读过最好的编程入门书。

比较有趣的是,C++程序设计原理与实践直到全书过半都没有出现指针,我想这可能是Bjarne为了证明不学C也可以学好C++吧。

C++程序设计语言(第4版)

同样是Bjarne Stroustrup的作品,C++程序设计语言是C++最权威且最全面的书籍。第4版相对于之前的版本进行了全面的更新,覆盖了第二新的C++ 11标准,并砍掉了部分过时的内容。

延伸阅读:

  • A Tour of C++:如果你觉得C++程序设计语言过于庞大,但你又想快速的浏览一遍新版C++的语言特色,那么可以试试这本小红书;
  • C++语言的设计与演化:C++的“历史书”,讲述了C++是如何一步一步从C with Classes走到如今这一步,以及C++语言特性背后的故事;
  • C++标准库(第2版):相对于其它语言的标准库,C++标准库虽然强大,但学习曲线十分陡峭,这本书是学习C++标准库有力的补充;
  • 深度探索C++对象模型:这本书系统的讲解了C++是如何以最小的性能代价实现对象模型,很多C++面试题(包括被问烂的虚函数指针)都可以在这本书里找到答案;
  • Effective C++More Effective C++:由于C++的特性实在繁杂,因此很容易就掉到坑里。Effective系列既讲述了C++的良好编程实践,也包含C++的使用误区,从而帮你绕过这些坑。

Java

Java核心技术(第9版)

平心而论Java核心技术(即Core Java)并不算是一本特别出色的书籍:示例代码不够严谨,充斥着很多与C/C++的比较,语言也不够简洁——问题在于Java并没有一本很出色的入门书籍,与同类型的Java编程思想相比,Java核心技术至少做到了废话不多,与时俱进(Java编程思想还停留在Java 6之前),矮子里面选将军,Java核心技术算不错了。

Effective Java(第2版)

尽管Java没有什么出色的入门书籍,但这不代表Java没有出色的必读书籍。Effective Java是我读过的最好的编程书籍之一,它包含大量的优秀Java编程实践,并对泛型和并发这两个充满陷阱的Java特性给出了充满洞察力的建议,以至于Java之父James Gosling为这本书作序:“我很希望10年前就拥有这本书。可能有人认为我不需要任何Java方面的书籍,但是我需要这本书。”

延伸阅读:

  • 深入理解Java虚拟机(第2版):非常优秀且难得的国产佳作,系统的介绍了Java虚拟机和相关工具,并给出了一些调优建议;
  • Java程序员修炼之道:在这本书之前,并没有一本Java书籍系统详细的介绍Java 7的新特性(例如新的垃圾收集器,try using结构和invokedynamic指令),这本书填补了这个空白;
  • Java并发编程实践:系统全面的介绍了Java的并发,如何设计支持并发的数据结构,以及如何编写正确的并发程序;
  • Java Puzzlers:包含了大量的Java陷阱——以至于读这本书时我说的最多的一个词就是WTF,这本书的意义在于它是一个反模式大全,Effective Java告诉你如何写好的Java程序,而Java Puzzlers则告诉你糟糕的Java程序是什么样子。更有意思的是,这两本书的作者都是Joshua Bloch

视频教程:

  • Java语言学习极速之旅:系统全面的Java语言教程,6个阶段Java基础入门,循序渐进掌握Java面向对象精髓。3个Java进阶方向,Java SE、Java EE、Android开发,每一个都包含相应的知识点精讲和项目开发实例,快速上手。
  • Android 0基础极速养成计划:Android开发快速入门视频教程,通过对Android基础知识讲解,详细介绍Android开发环境搭建,同时包含Android实战案例解析,通过全新实战的Android课程,系统学习Android开发。

C#

精通C#(第6版)

可能你会疑问我为什么会推荐这本接近1200页的“巨著”用作C#入门,这是我的答案:

  1. C#的语言特性非常丰富,很难用简短的篇幅概括这些特性;
  2. 精通C#之所以有近1200页的篇幅,是因为它不但全面介绍了C#语言,而且还覆盖了ADO.NET,WCF,WF,WPF,以及ASP.NET这些.Net框架。你可以把这本书视为两本书——一本500多页的C#语言教程和一本600多页的.Net平台框架快速上手手册。
  3. 尽管标题带有“精通”两字,精通C#实际上是一本面向初学者的C#书籍,你甚至不需要太多编程知识,就可以读懂它。

CLR via C#(第4版)

CLR via C#是C#/.Net最重要的书籍,没有之一。它全面介绍了.Net的基石——CLR的运行原理,以及构建于CLR之上的C#类型系统,运行时关系,泛型,以及线程/并行等高级内容。任何一个以C#为工作内容的程序员都应该阅读此书。

延伸阅读:

  • 深入理解C#(第3版):C#进阶必读,这本书偏重于C#的语言特性,它系统的介绍了C#从1.0到C# 4.0的语言特性演化,并展示了如何利用C#的语言特性编写优雅的程序;
  • .NET设计规范(第2版):C#专业程序员必读,从变量命名规范讲到类型系统设计原则,这本书提供了一套完整的.Net编程规范,使得程序员可以编写出一致,严谨的代码,
  • C# 5.0权威指南:来自O’Reilly的C#参考手册,严谨的介绍了C#语法,使用,以及核心类库,C#程序员案头必备;
  • LINQ to Objects Using C# 4.0Async in C# 5.0:LINQ和async分别是.Net 3.5和.Net 4.5中所引入的最重要的语言特性,所以我认为有必要在它们上面花点功夫——这两本书是介绍LINQ和async编程的最佳读物。

JavaScript

JavaScript DOM编程艺术(第2版)

尽管JavaScript现在可以做到客户端服务器端通吃,尽管JQuery之类的前端框架使得一些人可以不懂JavaScript也可以编程,但我还是认为学习JavaScript从HTML DOM开始最为适合,因为这是JavaScript设计的初衷。JavaScript DOM编程艺术系统的介绍了如何使用JavaScript,HTML,以及CSS创建可用的Web页面,是一本前端入门佳作。

JavaScript语言精粹

JavaScript语言包含大量的陷阱和误区,但它却又有一些相当不错的特性,这也是为什么Douglas Crockford称JavaScript为世界上最被误解的语言,并编写了JavaScript语言精粹一书来帮助前端开发者绕开JavaScript中的陷阱。和同类书籍不同,JavaScript语言精粹用精炼的语言讲解了JavaScript语言中好的那部分(例如闭包,函数是头等对象,以及对象字面量),并建议读者不要使用其它不好的部分(例如混乱的类型转换,默认全局命名空间,以及奇葩的相等判断符),毕竟,用糟糕的特性编写出来的程序往往也是糟糕的。

延伸阅读:

Python

Python基础教程(第二版)

Python的入门书籍很多,而且据说质量大多不错,我推荐Python基础教程的原因是因为它是我的Python入门读物——简洁,全面,代码质量很不错,而且有几个很有趣的课后作业,使得我可以快速上手。

这里顺便多说一句,不要用Python学习手册作为Python入门——它的废话实在太多,你能想象它用了15页的篇幅去讲解if语句吗?尽管O’Reilly出了很多经典编程书,但这本Python学习手册绝对不在其中。

Python参考手册(第4版)

权威且实用的Python书籍,覆盖Python 2和Python 3。尽管它名为参考手册,但Python参考手册在Python语法和标准库基础之上对其实现机制也给出了深入的讲解,不容错过。

延伸阅读:

3. 编程语言理论

编程语言实现模式

大多数程序员并不需要从头编写一个编译器或解释器,因此龙书(编译原理)就显得过于重量级;然而多数程序员还是需要解析文本,处理配置文件,或者写一个小语言,编程语言实现模式很好的满足了这个需求。它把常用的文本解析/代码生成方法组织成一个个模式,并为每个模式给出了实例和应用场景。这本书既会提高你的动手能力,也会加深你对编程语言的理解。Python发明者Guido van Rossum甚至为这本书给出了“Throw away your compiler theory book!”这样的超高评价。

程序设计语言——实践之路(第3版)

程序员每天都要和编程语言打交道,但是思考编程语言为什么会被设计成这个样子的程序员并不多,程序设计语言——实践之路完美的回答了这个问题。这本书从编程语言的解析和运行开始讲起,系统了介绍了命名空间,作用域,控制流,数据类型以及方法(控制抽象)这些程序设计语言的核心概念,然后展示了这些概念是如何被应用到过程式语言,面向对象语言,函数式语言,脚本式,逻辑编程语言以及并发编程语言这些具有不同编程范式的编程语言之上。这本书或极大的拓宽你的视野——无论你使用什么编程语言,都会从这本书中获益良多。理解这一本书,胜过学习十门新的编程语言。

延伸阅读:

  • 七周七语言:理解多种编程范型:尽管我们在日常工作中可能只使用两三门编程语言,但是了解其它编程语言范式是很重要的。七周七语言一书用精简的篇幅介绍了Ruby,Io,Prolog,Scala,Erlang,Clojure,和Haskell这七种具有不同编程范式的语言——是的,你没法通过这本书变成这七种语言的专家,但你的视野会得到极大的拓宽;
  • 自制编程语言:另一本优秀的编译原理作品,自制编程语言通过从零开始制作一门无类型语言Crowbar和一门静态类型语言Diksam,把类型系统,垃圾回收,和代码生成等编程语言的关键概念讲的清清楚楚;
  • 计算的本质:深入剖析程序和计算机:披着Ruby外衣的计算理论入门书籍,使你对编程语言的理解更上一层楼。

4. 程序设计

程序设计方法

现代编程语言的语法大多很繁杂,初学者使用这些语言学习编程会导致花大量的时间在编程语言语法(诸如指针,引用和类型定义)而不是程序设计方法(诸如数据抽象和过程抽象)之上。程序设计方法解决了这个问题——它专注于程序设计方法,使得读者无需把大量时间花在编程语言上。这本书还有一个与之配套的教学开发环境DrScheme,这个环境会根据读者的程度变换编程语言的深度,使得读者可以始终把注意力集中在程序设计方法上。

我个人很奇怪程序设计方法这样的佳作为什么会绝版,而谭浩强C语言这样的垃圾却大行其道——好在是程序设计方法第二版已经被免费发布在网上。

计算机程序的构造与解释(第2版)

计算机程序的构造与解释是另一本被国内大学忽视(至少在我本科时很少有人知道这本书)的教材,这本书和程序设计方法有很多共同点——都使用Scheme)作为教学语言;都专注于程序设计方法而非编程语言本身;都拥有相当出色的课后题。相对于程序设计方法计算机程序的构造与解释要更加深入程序设计的本质(过程抽象,数据抽象,以及元语言抽象),以至于Google技术总监Peter Norvig给了这本书超高的评价

延伸阅读:

  • 编程原本STL作者的关于程序设计方法佳作——他把关系代数和群论引入编程之中,试图为程序设计提供一个坚实的理论基础,从而构建出更加稳固的软件。这本书是程序设计方法计算机程序的构造与解释的绝好补充——前者使用函数式语言(Scheme)讲授程序设计,而编程原本则使用命令式语言(C++);
  • 元素模式设计模式总结了面向对象程序设计中的模式,而元素模式这本书分析了程序设计中的常见模式的本质,阅读这本书会让你对程序设计有更深的理解;
  • The Science of Programming:会编程的人很多,但能够编写正确程序的人就少多了。The Science of Programming通过前条件——不变式——后条件以及逻辑谓词演算,为编写正确程序提供了强有力的理论基础,然后这本书通过实例阐述了如何应用这些理论到具体程序上。任何一个想大幅提高开发效率的程序员都应阅读此书。

5. 算法与数据结构

算法(第4版)

我在算法学习之路一文中提到我的算法入门教材是数据结构与算法分析:C语言描述,我曾经认为它是最好的算法入门教材,但自从我读到Sedgewick算法之后我就改变了观点——这本算法才是最好的算法入门教材:

  • 使用更为容易的Java语言作为教学语言;
  • 覆盖所有常用的数据结构和算法,并均给出其完整实现;
  • 包含大量的图示用于可视化算法——事实上这是我读过的图示最为丰富形象的书籍,这也是我称其为最好的算法入门书籍的原因。

编程珠玑(第2版)

编程珠玑(第2版)是一本少见的实践型算法书籍——它并非一一介绍数据结构/算法的教材,而是实践性极强的算法应用手册。作者(Jon Bentley)从他多年的实际经验精选出一些有趣而又实用的问题,然后展示了他解决这些问题的过程(分析问题,选择合适的算法,解决问题,以及验证答案)。任何程序员都可以从中获益。

延伸阅读:

  • 编程珠玑(续):严格来说这本书并非编程珠玑的续作,而是一本类似于番外篇的编程技巧/实践手册;它不像编程珠玑那般重视算法的应用,而是全面覆盖了程序员所需的能力;
  • 算法导论(第3版):尽管我在这边文章开头提到会尽量避免理论性的书籍,但没有算法导论的算法阅读列表是不完整的,我想这本书就不需要我多介绍了; :–)
  • 算法设计与分析基础(第3版):侧重于算法设计,这本书创新的把常见算法分为分治,减治,变治三大类,并覆盖了动态规划,回溯,以及分支定界等高级算法设计方法,属于算法设计的入门佳作;

6. 程序调试

调试九法——软硬件错误的排查之道

一个让非编程从业人员惊讶的事实是程序员的绝大多时间都花在调试上,而不是写程序上,以至于Bob大叔调试时间占工作时间的比例作为衡量程序员开发能力的标准。调试九法——软硬件错误的排查之道既是调试领域的入门作品,也是必读经典之作。调试九法的作者是一个具有丰富实战经验的硬件工程师,他把他多年的调试经验总结成九条调试法则,并对每一条法则都给对应的实际案例。任何程序员都应通过阅读这本书改善调试效率,即便是非程序员,也可以从这本书中学到系统解决问题的方法。

延伸阅读:

  • Writing Solid Code最好的调试是不调试——Writing Solid Code介绍了断言,设计清晰的API,以及单步代码等技巧,用于编写健壮的代码,减少调试的时间;
  • 软件调试的艺术:调试工具书——这本书详细的介绍了常见的调试器工具,并通过具体案例展示了它们的使用技巧;

软件开发

1. 编程实践

程序设计实践

Brian Kernighan是这个星球上最好的计算机书籍作者:从上古时期的Software Tools,到早期的Unix编程环境C程序设计语言,再到这本程序设计实践,每本书都是必读之作。

尽管程序设计实践只有短短200余页,但它使用精炼的代码和简要的原则覆盖了程序设计的所有关键概念(包括编程风格,算法与数据结构,API设计,调试,测试,优化,移植,以及领域特定语言等概念)。如果你想快速掌握良好的编程实践,或者你觉着900多页的代码大全过于沉重,那么程序设计实践是你的不二之选。我第一次读这本书就被它简洁的语言和优雅的代码所吸引,以至于读研时我买了三本程序设计实践——一本放在学校实验室,一本放在宿舍,一本随身携带阅读。我想我至少把它读了十遍以上——每一次都有新的收获。

代码大全(第2版)

无论在哪个版本的程序员必读书单,代码大全都会高居首位。和其它程序设计书籍不同,代码大全用通俗清晰的语言覆盖了软件构建(Software Construction)中各个层次上所有的重要概念——从变量命名到类型设计,从控制循环到代码结构,从测试和调试到构建和集成,代码大全可谓无所不包,你可以把这本书看作为程序员的一站式(Once and for all)阅读手册。更珍贵的是,代码大全在每一章末尾都给出了价值很高的参考书目(参考我之前的如何阅读书籍一文),如果你是一个初出茅庐的程序员,代码大全是绝好的阅读起点。

延伸阅读:

  • 编写可读代码的艺术:专注于代码可读性(Code Readability),这本书来自Google的两位工程师对Google Code Readability的总结。它给出了大量命名,注释,代码结构,以及API设计等日常编码的最佳实践,并包含了很多看似细微但却可以显著提升代码可读性的编程技巧。这本书的翻译还不错,但如果你想体会书中的英语幽默(例如Tyrannosaurus——Stegosaurus——Thesaurus),建议阅读它的英文影印版
  • 卓有成效的程序员:专注于生产效率(Productivity),它既包含源自作者多年经验的高生产率原则,也包含大量的提高生产率的小工具,每个追求高生产率的程序员都应该阅读这本书;
  • UNIX编程艺术:专注于程序设计哲学,这本书首先总结出包括模块化,清晰化,可组合,可分离等17个Unix程序设计哲学,接下来通过Unix历史以及各种Unix编程工具展示了这些原则的应用。尽管个人觉的这本书有些过度拔高Unix且过度贬低Windows和M$,但书中的Unix设计哲学非常值得借鉴。

2. 面向对象程序设计

Head First设计模式

无论是在Amazon还是在Google上搜索设计模式相关书籍,Head First设计模式都会排在首位——它使用风趣的语言和诙谐的图示讲述了观察者,装饰者,抽象工厂,和单例等关键设计模式,使得初学者可以迅速的理解并掌握设计模式。Head First设计模式在Amazon上好评如潮,就连设计模式原书作者Erich Gamma都对它给出了很高的评价。

需要注意,Head First设计模式是非常好的设计模式入门书,但千万不要把这本书作为学习设计模式的唯一的书——是的,Head First设计模式拥有风趣的语言和诙谐的例子,但它既缺乏实际的工程范例,也没有给出设计模式的应用/适用场景。我个人建议是在读过这本书之后立即阅读“四人帮”)的设计模式Bob大叔敏捷软件开发,以便理解设计模式在实际中的应用。

设计模式

设计模式作为设计模式领域的开山之作,Erich Gamma,Richard Helm,Ralph Johnson等四位作者将各个领域面向对象程序开发的经验总结成三大类23种模式,并给出了每个模式的使用场景,变体,不足,以及如何克服这些不足。这本书行文严谨紧凑(四位作者都是PhD),并且代码源自实际项目,属于设计模式领域的必读之作。

需要注意:设计模式不适合初学者阅读——它更像是一篇博士论文而非技术书籍,加上它的范例都具有很强的领域背景(诸如GUI窗口系统和富文本编辑器),缺乏实际经验的程序员很难理解这本书。

延伸阅读:

3. 重构

重构

任何产品代码都不是一蹴而就,而是在反复不断的修改中进化而来。重构正是这样一本介绍如何改进代码的书籍——如何在保持代码行为的基础上,提升代码的质量(这也是重构的定义)。

我见过很多程序员,他们经常声称自己在重构代码,但他们实际只做了第二步(提升代码的质量),却没有保证第一步(保持代码行为),因此他们所谓的重构往往会适得其反——破坏现有代码或是引入新bug。这也是我推荐重构这本书的原因——它既介绍糟糕代码的特征(Bad smell)和改进代码的方法,也给出了重构的完整流程——1. 编写单元测试保持(Preserve)程序行为;2. 重构代码;3. 保证单元测试通过。重构还引入了一套重构术语(诸如封装字段,内联方法,和字段上移),以便程序员之间交流。只有理解了这三个方面,才能算是理解重构。

修改代码的艺术

这里再重复一遍重构的定义——在保持代码行为的基础上,提升代码的质量。重构专注于第二步,即如何提升代码的质量,而修改代码的艺术专注于第一步,即如何保持代码的行为。

提升代码质量并不困难,但保持代码行为就难多了,尤其是对没有测试的遗留代码(Legacy Code)而言——你需要首先引入测试,但遗留代码往往可测试性(Testability)很差,这时你就需要把代码变的可测试。修改代码的艺术包含大量的实用建议,用来把代码变的可测试(Testable),从而使重构变为可能,使提高代码质量变为可能。

延伸阅读:

  • 重构与模式:这本书的中文书名存在误导,它的原书书名是Refactoring to Patterns——通过重构,把模式引入代码。这本书阐述了重构和设计模式之间的关系,使得程序员可以在更高的层次上思考重构,进行重构。

4. 软件测试

How to Break Software

关于软件测试的书籍很多,但很少有一本测试书籍能像How to Break Software这般既有趣又实用。不同于传统的软件测试书籍(往往空话连篇,无法直接应用),How to Break Software非常实际——它从程序员的心理出发,分析软件错误/Bug最可能产生的路径,然后针对这些路径进行残酷的测试,以保证软件质量。

我在第一次阅读这本书时大呼作者太过“残忍”——连这些刁钻诡异的测试招数都能想出来。但这种毫不留情(Relentless)的测试风格正是每个专业程序员所应具备的心态。

注意:如果你是一个测试工程师,那么在阅读这本书前请三思——因为阅读它之后你会让你身边的程序员苦不堪言,甚至连掐死你的心都有 :-D。

xUnit Test Patterns

How to Break Software注重黑盒测试,而这本xUnit Test Patterns则注重白盒测试。正如书名所示,xUnit Test Patterns覆盖了单元测试的每个方面:从如何编写良好的单元测试,到如何设计可测试(Testable)的软件,再到如何重构测试——可以把它看作为单元测试的百科全书。

延伸阅读:

  • Practical Unit Testing with JUnit and Mockito:尽管xUnit Test Patterns覆盖了单元测试的方方面面,但它的问题在于不够与时俱进(07年出版)。Practical Unit Testing弥补了这个缺陷——它详细介绍了如何通过测试框架JUnit和Mock框架Mockito编写良好的单元测试,并给出了大量优秀单元测试的原则;
  • 单元测试的艺术(第2版):可以把这本书看作为前一本书的.Net版,适合.Net程序员;
  • Google软件测试之道:这本书详细介绍了Google如何测试软件——包括Google的软件测试流程以及Google软件测试工程师的日常工作/职业发展。需要注意的是:这本书中的测试流程在国内很可能行不通(国内企业缺乏像Google那般强大的基础设施(Infrastructure)),但它至少可以让国内企业有一个可以效仿的目标;
  • 探索式软件测试James Whittaker的另一本测试著作,不同于传统的黑盒/白盒测试,这本书创造性的把测试比喻为“探索”(Exploration),然后把不同的探索方式对应到不同的测试方式上,以便尽早发现更多的软件错误/Bug。

5. 项目管理

极客与团队

很多程序员都向往成为横扫千军(One-man Army)式的“编程英雄”,但卓越的软件并非一人之力,而是由团队合力而成。极客与团队就是这样一本写给程序员的如何在团队中工作的绝好书籍,它围绕着HRT三大原则(Humility谦逊,Respect尊重,和Trust信任),系统的介绍了如何融入团队,如何打造优秀的团队,如何领导团队,以及如何应对团队中的害群之马(Poisonous People)。这本书实用性极强,以至于Python之父Guido van Rossum都盛赞这本书“说出了我一直在做但总结不出来的东西”

人月神话

尽管人月神话成书于40年前,但它仍是软件项目管理重要的书籍。人月神话源自作者Fred Brooks领导并完成System/360OS/360这两个即是放到现在也是巨型软件项目的里程碑项目的经验总结。它覆盖了软件项目各个方面的关键概念:从工期管理(Brooks定律)到团队建设(外科团队),从程序设计(编程的本质是使用正确的数据结构)到架构设计(概念完整性),从原型设计(Plan to Throw one away)到团队交流(形式化文档+会议)。令人惊讶的是,即便40年之后,人月神话中的关键概念(包括焦油坑,Brooks定律概念完整性外科团队第二版效应等等)依然适用,而软件开发的核心复杂度仍然没有得到解决(没有银弹)。

延伸阅读:

  • 人件(原书第3版):从人的角度分析软件项目。人件从雇佣正确的人,创建健康的工作环境,以及打造高效的开发团队等角度阐述了如何改善人,从而改善软件项目;
  • 门后的秘密:卓越管理的故事:这本书生动的再现了软件项目管理工作的场景,并给出了各种实用管理技巧,如果你有意转向管理岗位,这本书不容错过;
  • 大教堂与集市:这本书从黑客的历史说起,系统而又风趣的讲述了开源运动的理论和实践,以及开源软件项目是如何运作并发展的。了解开源,从这本书开始。

6. 专业开发

程序员修炼之道:从小工到专家

不要被庸俗的译名迷惑,程序员修炼之道是一本价值极高的程序员成长手册。这本书并不局限于特定的编程语言或框架,而是提出了一套切实可行的实效(Pragmatic)开发哲学,并通过程序设计,测试,编程工具,以及项目管理等方面的实例展示了如何应用这套开发哲学,从而使得程序员更加高效专业。有人把这本书称之为迷你版代码大全——代码大全给出了大量的优秀程序设计实践,偏向术;而程序员修炼之道给出了程序设计实践背后的思想,注重道。

程序员职业素养

程序员修炼之道指出了如何成为专业程序员,这本程序员职业素养则指出了专业程序员应该是什么样子——承担责任;知道自己在做什么;知道何时说不/何时说是;在正确的时间编写正确的代码;懂得自我时间管理和工期预估;知道如何应对压力。如果你想成为专业程序员(Professional Developer)(而不是码农(Code Monkey)),这本书会为你指明前进的方向。

延伸阅读:

7. 大师之言

奇思妙想:15位计算机天才及其重大发现

奇思妙想:15位计算机天才及其重大发现是一本极具眼光的技术访谈书籍——在这本书访谈的15位计算机科学家中,竟出现了12位图灵奖获得者——要知道图灵奖从1966年设奖到现在也只有六十几位获奖者而已。

奇思妙想把计算机科学分为四大领域:编程语言;算法;架构;人工智能。并选取了每个领域下最具代表性的计算机科学家进行访谈。因为这些计算机科学家都是其所在领域的开拓者,因此他们能给出常人无法给出的深刻见解。通过这本书,你可以了解前三十年的计算机科学的发展历程——计算机科学家做了什么,而计算机又能做到/做不到什么。从而避免把时间浪费在前人已经解决的问题(或者根本无法解决的问题)上面。

编程人生:15位软件先驱访谈录

同样是访谈录,同样访谈15个人,编程人生把重点放在程序员(Coders at work)上。它从各个领域选取了15位顶尖的程序员,这些程序员既包括Ken ThompsonJamie Zawinski这些老牌Unix黑客,也包括Brad Fitzpatrick这样的80后新生代,还包括Frances AllenDonald Knuth这样的计算机科学家。这种多样性(Diversity)使得编程人生兼具严谨性和趣味性,无论你是什么类型的程序员,都能从中受益良多。

延伸阅读:

  • 图灵和ACM图灵奖(1966-2011):通过图灵奖介绍整个计算机科学发展史,非常难得的国产精品图书;
  • 编程大师访谈录:可以把这本书看作为二十年前的编程人生,被访谈者都是当时叱咤风云的人物(例如微软的创造者Bill Gates,Macintosh的发明者Jeff Raskin,以及Adobe的创始人John Warnock等等)。有趣的是这本书中大量的经验和建议到如今依然适用;
  • 编程大师智慧:类似于编程人生,不同的是被访谈者都是编程语言的设计者——这本书覆盖了除C语言以外的几乎所有主流编程语言。通过这本书,你可以从中学到编程语言背后的设计思想——编程语言为什么要被设计成这样,是什么促使设计者要在语言中加入这个特性(或拒绝那个特性)。从而提升对编程语言的理解。

8. 界面设计

写给大家看的设计书

书如其名,写给大家看的设计书是一本面向初学者的快速设计入门。它覆盖了版式,色彩,和字体这三个设计中的关键元素,并创造性的为版式设计总结出CRAP四大原则(Contrast对比,Repetition重复,Alignment对齐,Proximity亲密)。全书使用丰富生动的范例告诉读者什么是好的设计,什么是不好的设计,使得即便是对设计一无所知的人,也可以从这本书快速入门。

认知与设计:理解UI设计准则(第2版)

写给大家看的设计书强调实践,即如何做出好的设计;认知与设计:理解UI设计准则强调理论,即为什么我们会接受这样的设计而反感那样的设计。如果你想要搞清楚设计背后的心理学知识,但又不想阅读大部头的心理学著作,那么认知与设计是你的首选。

延伸阅读:

  • GUI设计禁忌 2.0:这本书指出了GUI设计的原则和常见误区,然后通过具体范例指出了如何避免这些误区。如果你的工作涉及到用户界面,那么这本书会为你减少很多麻烦;
  • 界面设计模式(第2版):这本书将用户界面中的常见元素/行为组织成彼此关联的模式,以便读者理解并举一反三,从而将其运用到自己的应用中;
  • 移动应用UI设计模式:类似于界面设计模式,但面向移动平台。它给出了iOS,Android,以及Windows Phones上常用的90余种界面设计模式,从而使得你不必把这些平台的应用挨个玩一遍也可以掌握各个平台的设计精髓。如果你主攻Android平台,那么Android应用UI设计模式会是更好的选择;
  • 配色设计原理版式设计原理:如果你读过写给大家看的设计书之后想继续深入学习设计,这两本书是不错的起点。

9. 交互设计

通用设计法则

书如其名,通用设计法则给出了重要的125个设计原则,并用简练的语言和范例展示了这些原则的实际应用。每个原则都有对应的参考文献,以便读者进一步学习。我之所以推荐这本书,是因为:1. 程序员需要对设计有全面的认识;2. 程序员并不需要知道这些设计原则是怎么来的,知道怎么用即可。这本书很好的满足了这两个要求。

交互设计精髓(第3版)

交互设计精髓是交互设计领域的圣经级著作。交互设计专家(以及VB之父)Alan Cooper在这本书中详细介绍了交互设计的原则,流程,以及方法,然后通过各种范例(主要来自桌面系统)展示了如何应用这些原则。

需要注意的是这本书的第4版已经出版,它在第三版的基础上增加了移动设计以及Web设计等内容。

延伸阅读:

  • The Design of Everyday Things:交互设计领域的另一本经典之作,它通过解读人类行动背后的心理活动,展示了设计问题的根源,并给出了一系列方法用以解决设计问题(需要注意,尽管这本书有中译版,但中译版对应的是02年的旧版,而非13年的新版);
  • The Inmates Are Running the AsylumAlan Cooper的另一本经典,这本书非常辛辣的指出让不具备人机交互知识的程序员直接编写面向用户的软件就像让精神病人管理疯人院(The Inmates Are Running the Asylum),然后给出了一套交互设计流程以挽救这个局面;
  • 简约至上:交互式设计四策略:专注于把产品变的更加简单易用。作者通过删除,组织,隐藏,和转移这四个策略,展示了如何创造出简约优质的用户体验。

个人成长

1. 职业规划

软件开发者路线图

软件开发者路线图是一本优秀且实用的程序员职业规划手册。这本书由若干个模式组成,每个模式都对应于程序员职业生涯中的特定阶段。通过这本书,读者可以很方便的找到自己目前所处的模式(阶段),应该做什么,目标是什么,以及下一个模式(阶段)会是什么。如果你时常感到迷茫,那么请阅读这本路线图,找到自己的位置,确定接下来的方向。

延伸阅读:

  • 卡耐基全集:非常著名的为人处世书籍。很多人把这本书归类到成功学,但我并不这么认为——在我看来,这本书教的更多的是如何成为一个让大家喜欢的人。作为天天和机器打交道的程序员,这套书会帮助我们与人打交道;
  • 沃顿商学院最受欢迎的谈判课:这本书不是教你去谈判,而是教你通过谈判(Negotiation)去得到更多(Getting more,这也是这本书的原书书名)。小到买菜砍价,大到争取项目,这本书中的谈判原则会让你收益良多;
  • 程序员健康指南:作为长期与计算机打交道的职业,程序员往往会受到各式各样疾病的困扰,这本书正是为了解决这个问题而出现:它从改善工作环境,调整饮食结构,预防头痛眼痛,以及进行室内/室外锻炼等方面出发,给出了一套全面且可行的程序员健康改善计划,以帮助程序员打造健康的身体。

2. 思维方式

程序员的思维修炼:开发认知潜能的九堂课

作为程序员,我们需要不断地学习——既要学习新技术,也要学习如何解决各种领域的问题。为了提升学习效率,我们需要学习如何学习程序员的思维修炼正是这样一本讲如何学习的书,它集合了认知科学,神经学,以及行为理论的最新研究成果,并系统的介绍了大脑的工作机制。通过这本书,你将学会如何高效的使用自己的大脑,从而提高思考能力,改善学习效率。

如何把事情做到最好

Mastery is not about perfection. It’s about a process, a journey. The master is the one who stays on the path day after day, year after year. The master is the one who is willing to try, and fail, and try again, for as long as he or she lives.

为什么同样资质的人,大多数人会碌碌无为,而只有极少数能做到登峰造极?如何在领域内做到顶尖?如何克服通往顶尖之路上的重重险阻?如何把事情做到最好回答了这些问题,并极具哲理的指出登峰造极并不是结果,而是一段永不停止的旅程。阅读这本书不会让你立刻脱胎换骨,但它会指引你走向正确的道路——通往登峰造极之路。

延伸阅读:

  • 怎样解题:数学思维的新方法:不要被标题中的“数学思维”吓到,它并不仅仅只是一本数学解题书,它所提出的四步解题法(理解题目->拟定方案->执行计划->总结反思)适用于任何领域;
  • 暗时间刘未鹏所写的关于学习思维方法的文章集,既包含了他对学习方法的思考,也包含了大量进一步阅读的资源;
  • 批判性思维:带你走出思维的误区:这本书系统的分析了人类思维的常见误区,并针对各个误区给出了解决方案,从而帮助程序员养成严谨正确的思考方式;
  • Conceptual Blockbusting: A Guide to Better Ideas:与批判性思维相反,这本书专注于创造性思维(Creative Thinking),它分析了阻碍创造性思维的常见思维障碍(Blockbuster)以及这些思维障碍背后的成因,并给出了各种方法以破除这些障碍。

3. 求职面试

金领简历:敲开苹果微软谷歌的大门

知己知彼,百战不殆。金领简历:敲开苹果微软谷歌的大门是程序员求职的必读书籍,它覆盖了程序员求职的方方面面:从开始准备到编写简历,从技术面试到薪酬谈判。由于该书作者曾在Google,微软,和苹果任职并进行过技术招聘,因此这本书的内容非常实用。

顺便吐个槽:这本书翻译的还不错,但我实在无法理解封面上的“进入顶级科技公司的葵花宝典”这段文字——找个工作而已,用不着切JJ这么凶残吧。-_–#

程序员面试金典(第5版)

同样是来自金领简历作者的作品,程序员面试金典(第5版)专注于技术面试题,它既包含了IT企业(诸如微软,Google,和苹果)的面试流程以及如何准备技术面试,也包含了大量(超过200道)常见技术面试题题目以及解题思路。无论你打算进入国内企业还是外企,你都应该把这本书的题目练一遍,以找到技术面试的感觉(我在求职时就曾经专门搞了一块白板,然后每二十分钟一道题的练习,效果很不错)。

延伸阅读:

  • 编程之美:微软技术面试心得:恐怕是国内技术面试第一书,这本书里面的多数题目都曾经是国内IT企业面试的必问题目。这本书的缺点是它太旧而且被用滥了(以至于一些企业开始避免使用这本书上的题目)——但你可以把它当成一本算法趣题来读;
  • 剑指Offer:名企面试官精讲典型编程题:相对于东拼西凑的XX面试宝典,剑指Offer是一本少见的国产精品技术面试书籍,尽管这本书的技术面试题目不多(60余道),但作者为大多数题目都给出了不同方式的解法,并分析了这些解法之间的优劣,此外作者还以面试官的视角分析了技术面试的各个环节,从而帮助读者把握技术面试;
  • 人人都有好工作:IT行业求职面试必读:可以把它看做金领简历的补充阅读——这本书的特点在于它给出了非常详细的简历/求职信/电子邮件编写技巧,而这正是不少国内程序员所缺乏的。

4. 英语写作

The Only Grammar Book You'll Ever Need

词汇量决定阅读能力,语法决定写作能力。计算机专业词汇并不多,但精确性非常重要,因此每个程序员都应具备良好的英语语法,但程序员并不需要过于专业的英语语法——掌握常用语法并把它用对就可以。The Only Grammar Book You’ll Ever Need正好可以满足这个需求,尽管它篇幅不大(不足200页),却覆盖了英语中的关键语法以及常见错误。把这本书读两遍,它会大幅度提高你的英语写作能力。

风格的要素

既是最畅销的英语写作书籍,也是计算机书籍中引用最多的非计算机书籍。风格的要素用极其简练的语言讲述了如何进行严肃精确清楚的英语写作。从这本书中,你不仅可以学到英语写作,更可以学到一种严谨至简的处事态度,而这正是专业开发所必需的。

延伸阅读:

  • 牛津英语用法指南(第3版):全面且权威的英语用法指南,它覆盖语法,词汇,发音,以及修辞等方面,并兼顾口语和书面语,以帮助读者掌握合理的英语用法(Proper English Usage)。不要被这本书的篇幅(1000多页)吓到——原书并没有这么厚,因为这本书被翻译成中文但又得保留原有的英文内容,所以它的篇幅几乎翻了一倍。考虑到这本书使用的词汇都很基础,所以我认为具有英语基础的读者直接阅读原版(Practical English Usage)会更合适;
  • 写作法宝:非虚构写作指南(30周年纪念版):详尽的非虚构(Non-Fiction)写作指南,无论你要写地方,技术,商务,运动,艺术,还是自传,你都可以从这本书中找到珍贵的建议;
  • 中式英语之鉴:中国人使用英语最大的问题就是会把中式思维掺杂其中,从而形成啰里啰嗦不伦不类的中式英语(Chinglish)。中式英语之鉴系统的探讨了中式英语以及其成因,然后根据成因对中式英语进行归类,并对每个类别给出了大量的实际案例以及修改建议。如果你想摆脱中式英语,那么这本书是绝好的起点。

如何使用这个书单

学而不思则罔,思而不学则殆。

不愤不启,不悱不发。举一隅不以三隅反,则不复也。

不闻不若闻之,闻之不若见之,见之不若知之,知之不若行之,学至于行之而止矣。

来自他人的书单

它山之石,可以攻玉。我在本文最后给出其他中外优秀程序员的书单,以便参考&补充。

刘未鹏(暗时间作者)

以下同一条目下用“/”隔开的表示任选,当然也可以都读。

  1. 编码:隐匿在计算机软硬件背后的语言
  2. 深入理解计算机系统 / Windows核心编程 / 程序员的自我修养
  3. 代码大全 / 程序员修炼之道
  4. 编程珠玑 / 算法概论 / 算法设计 / 编程之美
  5. C程序设计语言
  6. C++程序设计语言 / C++程序设计原理与实践 / Accelerated C++
  7. 计算机程序的构造与解释
  8. 代码整洁之道 / 实现模式
  9. 设计模式 / 敏捷软件开发(原则模式与实践)
  10. 重构

云风(中国游戏编程先行者,前网易游戏部门资深程序员,简悦创始人)

  1. C++编程思想
  2. Effective C++
  3. 深度探索C++对象模型
  4. C++语言的设计与演化
  5. C专家编程
  6. C陷阱与缺陷
  7. C语言接口与实现
  8. Lua程序设计
  9. 链接器和加载器
  10. COM本质论
  11. Windows核心编程
  12. 深入解析Windows操作系统
  13. 程序员修炼之道
  14. 代码大全
  15. UNIX编程艺术
  16. 设计模式
  17. 代码优化:有效使用内存
  18. 深入理解计算机系统
  19. 深入理解LINUX内核
  20. TCP/IP详解

洪强宁(豆瓣技术总监)

  1. 代码大全
  2. 人月神话
  3. 编码:隐匿在计算机软硬件背后的语言
  4. 计算机程序设计艺术
  5. 程序员修炼之道
  6. 设计模式
  7. 计算机程序的构造与解释
  8. 重构
  9. C程序设计语言
  10. 算法导论

陈皓(CoolShell博主)

  1. 点石成金:访客至上的Web和移动可用性设计秘笈
  2. 重来:更为简单有效的商业思维
  3. 黑客与画家
  4. 清醒思考的艺术
  5. TCP/IP详解
  6. UNIX环境高级编程
  7. UNIX网络编程

张峥(微软亚洲研究院副院长)

  1. 算法概论
  2. Data Structure and Algorithms
  3. C程序设计语言
  4. UNIX操作系统设计
  5. 编译原理
  6. 计算机体系结构:量化研究方法
  7. 当下的幸福
  8. 异类:不一样的成功启示录

Jeff Atwood(Stackoverflow联合创始人)

  1. 代码大全
  2. 人月神话
  3. 点石成金:访客至上的Web和移动可用性设计秘笈
  4. 快速软件开发
  5. 人件
  6. The Design of Everyday Things
  7. 交互设计精髓
  8. The Inmates Are Running the Asylum
  9. GUI设计禁忌 2.0
  10. 编程珠玑
  11. 程序员修炼之道
  12. 精通正则表达式

Joel Spolsky(Stackoverflow联合创始人)

软件项目管理

  1. 人件
  2. 人月神话
  3. 快速软件开发

编程技艺

  1. 代码大全
  2. 程序员修炼之道

编程哲学

  1. 禅与摩托车维修艺术
  2. 哥德尔、艾舍尔、巴赫:集异璧之大成
  3. 建筑模式语言

界面设计

  1. 点石成金:访客至上的Web和移动可用性设计秘笈
  2. 交互设计精髓
  3. The Design of Everyday Things

资本运作

  1. 漫步华尔街

图形设计

  1. 写给大家看的设计书

思维方式

  1. 影响力
  2. Helplessness On Depression, Development and Death

编程入门

  1. 编码:隐匿在计算机软硬件背后的语言
  2. C程序设计语言

DHH(Ruby on Rails创始人)

  1. Smalltalk Best Practice Patterns
  2. 重构
  3. 企业应用架构模式
  4. 领域驱动设计
  5. 你的灯亮着吗?发现问题的真正所在

参考

  1. 怎样花两年时间去面试一个人
  2. What is the single most influential book every programmer should read?
  3. Recommended Reading for Developers
  4. Book Reviews — Joel Spolsky
  5. The five programming books that meant most to me

 

 

作者:Lucida

原文链接:http://lucida.me/blog/developer-reading-list/

CMU大师对软件工程师的系统建议

2016-04-16 新智元 新智元

 新智元翻译1

来源:Quora

【新智元导读】软件工程师想学机器学习,有什么好建议?机器学习专家、卡耐基梅隆大学教授、1-Page公司首席科学家 Alex Smola 在 Quora 上给出了系统、具体的回答,还列出了推荐图书和论文。当然,如果你认为还有其他值得推荐的内容,留下评论,欢迎补充!

 

问题:你对想要学习机器学习的软件工程师有哪些建议?(What would be your advice to a software engineer who wants to learn machine learning?)

Alex Smola: 这 很大程度上取决于软件工程师的背景及其具体想掌握机器学习的哪部分知识。简而言之,我们以一名拥有四年本科学位和一到两年行业经验的初级程序员为例,并假 设这位程序员希望学习计算广告学、自然语言处理、图像分析、社交网络以及搜索和排序。那么,我们先说掌握机器学习有哪些基本要求(致学术界同仁的免责声 明:下列内容并不完整,如果未列入你的论著,在此提前致歉)。

线性代数

机器学习以及数据统计和优化都需要这方面知识。这也是为什么GPU(图形处理器)远比CPU(中央处理器)适合进行机器学习。作为程序员,至少需要基本掌握以下内容:

  • 标量、向量、矩阵、张量
    把它们看作你可以组建并相互转换的零维、一维、二维、三维和更高维物体,有点像乐高玩具,它们使得基本的数据转换成为可能。
  • 特征向量、范数、矩阵近似、分解
    这些概念本质上是让你习惯线性代数的用法。如果你希望分析一个矩阵的情况(比如,检查为何循环神经网络中出现梯度消失,为何增强学习算法中控制器出现分歧(diverge)),你就必须要理解在应用矩阵和向量时可能出现的增长和减小范围是多少。如果你希望代码表现出色和稳定,那么低秩等矩阵近似算法或乔列斯基分解就很有用。
  • 数值线性代数

    如果你需要做很多最优化计算,那么这部分知识就很有用。对核方法和深度学习来说如此,对图像模型和采样器而言则不那么重要。

最优化(和基本演算)

在许多情况下,设置要问的问题是相当容易的,但得出答案却没没那么简单。举例来说,如果要对一些数据进行线性回归(即找到一条线),你可能希望尽量减少与观测值的距离平方的总和。同样,如果想获得一个好的点击率预测模型,你就得最大化对于人们点击广告概率预测的准确性。这意味着我们通常会有一些目标、一些参数和大量数据,而我们需要通过一种方式来解决问题。这一点很重要,尤其因为我们常常不会有一个闭合式解决方案。

凸优化

很多时候,在优化问题不存在许多局部解决方案的情况下是不错的。当问题为凸时就会发生这种情况。(若你能在一个集合内任意两点间画出一条直线且这条直线处于该集合内,则这一集合就是凸的。若你能在图上任意两点间画出一条直线且这条直线位于图形上方,则这一函数是凸的。)

也许这一领域的经典书籍是这本由Steven Boyd和Lieven Vandenberghe所撰写的 Convex Optimization 。本书免费且非常棒。(回复041501下载,共730页)此外,Boyd的课程里也有许多很不错的幻灯片集。Dimitri Bertsekas也已经编写了关于最优化、控制等的宝典。这些应该足以供任何人开始了解这个领域了。

随机梯度下降算法

这一算法早期在很大程度上只是凸优化的一种特殊情况(至少早期定理是这样的),但最近发展很大,并且绝非是由于数据的增多。原因是,想象一下你有一些数据要处理,而你的算法需要将所有的数据都浏览一遍后才能继续新的步骤。而如果我故意给你10份同样的数据,那么你就必须重复10次工作,却没有什么实质性用处。显然,现实情况不会如此糟糕,但如果你需要操作多次小的新步骤,而每个小步骤之后都需要观测,它就能帮上忙。这在机器学习领域带来了相当大的变革型影响。此外,许多关联算法都容易得多。

我们面临的挑战是如何将其并行化。也许这个方向的第一步之一就是我们2009年的 Slow Learners are Fast 论文(回复041502下载)。最新版本是无锁变异型,例如Niu等于2013年所著的Hogwild论文(回复041503下载)。简而言之,这些算法通过人工计算机计算局部梯度并以异步方式更新共识参数集来运作。

另一个挑战是如何应对控制过度拟合的各种方法,例如通过正则化来实现。对于凸罚函数来说,有一种所谓近端梯度算法。一种比较流行的选择是Amir Beck和Marc Teboulle的FISTA算法。部分代码参见Francis Bach的SPAM toolbox(http://spams-devel.gforge.inria.fr/)。

非凸方法

许多机器学习问题都是非凸问题。从本质上来说,任何与深度学习相关的问题都是。但聚类、主题模型和几乎任何潜变量方法和当前几乎所有在机器学习领域有意思的问题也都是。部分加速技术可以提供帮助。例如,我的学生 Sashank Reddy最近展示了在这种情况下如何获得收敛的良好比率。

有许多被称为谱方法的技术可以使用。 Anima Anandkumar在她最近的Quora session中已经非常详尽地回答了这一问题。请参阅她的回复,因为其回复无比详细(https://www.quora.com/profile/Anima-Anandkumar-1)。概括地说,凸问题并非唯一能够确切解决的问题。在某些情况下,可以得出一个难题的数学表达式以显示只有某一组特定的参数能找到所有的集群、主题、相关比例、神经元或所有数据中的任何东西。这仅在你有能力且愿意花很多数学的功夫时才有效。

在培训深层网络方面(Deep Networks),最近有许多新技巧。我会在后面的内容中提及这些,但在某些情况下,目标不仅仅是优化,而是制定出一套具体的解决方案(几乎像是那本题为The Journey is the goal《旅程即是目的》的书)。

系统

机器学习正在成为大部分有关于人、测量、传感器和数据的关键要素,这与过去十年标度算法(scaling algorithms)的突破密不可分。Jeff Dean去年出了六套机器学习教程,也并非偶然。如果有人过了十年与世隔绝的生活,在这里给补充一下,他就是MapReduce、谷歌文件系统、BigTable和其他十多项成就了谷歌的关键技术背后的男人。

说笑归说笑,关于系统的研究为解决分布、异步、容错、可扩展和简易问题提供了宝贵的工具。后者是机器学习研究人员常常忽视的一点。简易是一种特性,不是一个错误。一些基本的技巧将带给你很多:

分布式哈希表

这实质上是如分布式缓存(memcached)、dynamo、 pastry和orceph等方法

构建的基础。它们都解决同一个问题——如何在避免访问之前数据输往的中央储存库的情况下向多台机器发布数据。为了达到这一目的,你需要将地址以一种随机又确定的方式编码(也就是哈希)。此外,你需要解决如果任何一台机器出现故障时谁将负责处理。

这就是我们在参数服务器(Parameter Server)中使用的数据布局。我的学生李沐是这个项目背后的智囊。工具组合参见DMLC(http://dmlc.ml/)。

一致性和信息传送

所有这一切的教父是Leslie Lamport的PAXOS 协议。它解决了在不是所有机器任何时候都可用或有些机器出现故障时如何达成共识的问题(是的,我在这儿就一句带过了)。如果你曾经使用过版本控制,你可能靠直觉知道它是如何工作的——大量机器(或开发者)产生更新(或代码段),而你希望将这些都结合成有意义的信息(例如,你不该两次运用微分),但又不需要所有机器与其他所有机器一直传递着信息。

在系统中,解决方案是使用向量时钟(参见例子:谷歌的Chubby)。我们在参数服务器中使用它的一种变体。关键的区别在于(均引自李沐)在参数范围内使用向量时钟。这可以确保不会因为时间标识耗尽内存,就像一个文件系统并不需要为每一个字节都记录一个时间标识。

容错、Scaling和云


最简单的自学方法就是在亚马逊AWS、谷歌GWC、微软Azure, 或你可以找到的各个其他平台上运行算法。当你第一次启动1000个服务器,意识到你正在向一个实际上的合法僵尸网络发送大量指令时,还是很令人激动的。我在谷歌工作时,我们控制了欧洲某处了5000个高端机器,用于主题模型中的推理。我们所调用的能源价值如果和一个核电站相比,也要占很大的比重了。我的经理当时把我叫到一旁,说这真是个昂贵的实验……

或许最容易起步的是学习docker。为了让scaling更容易,人们热火朝天地开发了不少工具。Docker Machine和Docker Cloud或许是近来最好的新工具,使你能像更换打印机驱动一样方便地连接不同的云端。

硬件


这似乎显而易见,但如果你了解自己算法所运行的硬件,的确会很有帮助。这会让你知道你写的代码是否已经接近峰值性能。初学者可以阅读Jeff Dean的Numbers every engineer should know一书。我在面试时最喜欢问的问题(曾经)是,应聘者的电脑有多快。知道算法的局限大有裨益:是缓存、内存带宽、延迟时间还是硬盘等等。Anandtech上有非常棒的介绍性文章,以及对微处理器架构等相关内容的测评。只要英特尔、ARM、AMD发布新硬件时,都可以去看一看。

统计学


我特意把这点留到最后。因为每个人都知道这是关键(的确如此),然后就忽略了其他所有东西。统计学确保你能问出好问题,同时帮助你理解自己在数据建模时用了多少估算。
从图像模型、核方法到深度学习等等,很多改进其实来自提出对的问题,也即定义了合理的优化目标,从而进行最优化。

Statistics Proper


Larry Wasserman的《统计学完全教程》(All of Statistics)是不错的入门教材。另外也可以看一下 David McKay 的 Machine Learning 一书。该书免费(篇幅很长、内容全面,回复041504下载)。其他还有不少好书,比如说 Kevin Murphy, Chris Bishop, Trevor Hastie, RobTibshirani 以及 Jerome Friedman 的著作The Elements of Statistical Learning:Data Mining, Inference, and Prediction。是的,Bernhard Scholkopf 和我也写了一本Learning with Kernels

随机算法和概率统计


本质上就是用计算机科学解决一样的问题,关键区别在于他们是设计算法的一种工具,而非用来适配参数的一个问题。我特别喜欢 Michael Mitzenmacher 和Eli Upfal 写的书Probability and Computing: Randomized Algorithms and Probabilistic Analysis ,非常易读但同时谈到了许多深刻的问题。如果你想更深入地了解这些工具,还有 Rajeev Motwani 和 Prabhakar Raghavan 的书Randomized Algorithms,写得很好,不过如果你没有较好的统计学背景,可能较难读懂。

我的回答可能已经够长了,很少有人会一直读到这里。所以我接下来说得比较简短。网上有许多非常棒的视频资料。许多教授现在有自己YouTube频道,并上传自己的课程视频。如果你在学习比较复杂的工具,这些视频会有所帮助。我的视频在这里(https://www.youtube.com/user/smolix/playlists),Nando de Freitas的要好很多。

 

其他还有一些工具。DMLC是好的起点,其中有许多用于分布式可扩展推理的算法,包括基于MXNET的神经网络。

 

还有很多没谈到的:编程语言、数据源等等。但这个回答已经太长了,我会在其他问题中继续讨论。

附录,Alex Smola 著书:

  • G. Bakir, T. Hofmann, B. Schölkopf, A.J. Smola, B. Taskar, and S.V.N. Vishwanathan, editors. Predicting Structured Data. MIT Press, Cambridge, MA, 2006.
  • S. Mendelson and A. J. Smola, editors. Machine Learning, Proceedings of the Summer School 2002, Australian National University, volume 2600 of Lecture Notes in Computer Science. Springer, 2003.
  • B. Schölkopf and A. J. Smola. Learning with Kernels. MIT Press, 2002.
  • B. Schölkopf, C. J. C. Burges, and A. J. Smola, editors. Advances in Kernel Methods–Support Vector Learning. MIT Press, Cambridge, MA, 1999.
  • A. J. Smola, P. L. Bartlett, B. Schölkopf, and D. Schuurmans, editors. Advances in Large Margin Classifiers. MIT Press, Cambridge, MA, 2000.

Slow Learners are Fast 论文(回复041502下载)。最新版本是无锁变异型,例如Niu等于2013年所著的Hogwild论文(回复041503下载)

关于这一讨论,你认为还有其他值得推荐的内容?留下评论,欢迎补充!

购书可扫二维码或点击 阅读原文 获取促销链接

编程需要知道多少数学知识?

英文:Al Sweigart

译文:伯乐在线 – 唐小娟

链接:http://blog.jobbole.com/19348/

下面是我在Reddit的子论坛 r/learnprogramming 看到的几个帖子:

  • “要成为一个优秀的程序员需要学习多少数学?”
  • “我应该重新学习数学吗?”
  • “这可能是我提问过的最愚蠢的一个问题。成为一个优秀的程序员究竟需要学习多少数学?”

数学和编程有一种容易让人误解的联系。许多人认为在开始学习编程之前必须对数学很在行或者数学分数很高。但一个人为了编程的话,需要学习多少数学呢?

(【伯乐在线编注】:本文仅为 Al Sweigart 一家之言,再推荐 Alan Skorkin 的这篇文章《数学是成就卓越开发人员的必备技能》。)

实际上不需要很多。这篇文章中我会深入探讨编程中所需要的数学知识。你可能已经都知道了。

对于基本的编程,你需要知道下面的:

  • 加减乘除 — 实际上,电脑会帮你作加减乘除运算。你仅需要知道什么时候运用它们。
  • 模运算 — 模运算是用来计算余数,它的符号通常用%百分号来表示。所以23除以7等于3,余数是2。23 mod 7 = 2。
  • 判断是奇数还是偶数的模运算 — 如果你想知道一个数是奇数还是偶数,用它mod 2来作模运算。如果结果是0,它就是偶数。如果结果是1,就是奇数。23 mod 2等于1,所以23是奇数,24 mod 2等于0,24是偶数。
  • 对一个数作百分数运算,就是用这个数来乘以一个百分数。譬如你要得到279的54%,就是用0。54*279。这就意味着为什么1.0等于100%,0.0等于0%。
  • 知道负数是什么。负数乘以负数等于正数。负数乘以正数等于负数。就这么简单。
  • 知道笛卡尔坐标系统。在编程中,(0,0)代表屏幕左上角,Y坐标的正轴往下。
  • 知道勾股定律,因为它是用来计算笛卡尔坐标中两点之间的距离的。勾股定律a^2 + b^2 = c^2。(x1, y1)和(x2, y2)两点之间的距离等于( (x1 – x2)^2 + (y1 – y2)^2 )。
  • 知道十进制、二进制、十六进制。十进制就是我们通常用的十个数:0-9。通常认为这个十进制系统是人类发明的,因为我们有十个手指。

电脑采用二进制数据,只有两个数字:0和1。这是因为我们用电子元件来构建的电脑,让电脑只识别两种状态更便宜些(一种代表0,另一种代表1)。

数是一样的,但是在不同的进制系统里的表现形式不同,因为不同进制包含的数的个数不同。十六进制比十进制多六个数字,所以我们用A-F表示超过9的数。能够表现这些进制系统的最简单方法就是用一个计数器(odometer)。下面三种不同的计数器显示的是同一个数,但在不同的进制系统中的形式不同:

你甚至不需要知道怎么从一个进制系统转换成另一个系统。每种编程语言都有帮你转换的函数。

(提示一下,十六进制的使用是因为一个十六进制的数可以表示四个二进制的数。因为十六进制中的3和二进制中的0011对应,十六进制的A和二进制的1010对应,所以十六进制中的3A(十进制的58)可以写成二进制的00111010。十六进制在编程中的使用是因为它是对二进制的简化。没人喜欢写出的数全是0和1。)

就是这么多了。除了进制系统以外,你可以已经知道编程所需的数学知识了。虽然普遍认为编程需要学习许多数学,但实际上并不需要那么多。你可能为了编写一个程序,譬如说地震模拟器,而需要学习数学。其实你更需要学习地震的数学,而不是因为要编写地震模拟器而学习数学。

某些编程领域中更为高级的数学

有一些领域中需要更多的数学知识(但95%的软件中,你都不需要知道它们。)

某些编程领域中更为高级的数学

有一些领域中需要更多的数学知识(但95%的软件中,你都不需要知道它们。)

3D游戏和3D绘图 — 3D通常需要涉及三角函数和线性代数(用矩阵来解决问题的数学)。当然,有许多3D图形库已经实现了这些数学编程,你不需要知道这些数学。

2D物理(譬如愤怒的小鸟)和3D物理(譬如许多流行的3D游戏) — 为了写涉及到物理的编程,你需要学习一些物理方程和公式(尤其是力学,如弹力,重力,球滚下斜坡等物理。)然而,已经有一些物理引擎和软件库帮你实现了,所以你也不需要知道游戏(如愤怒的小鸟)中的物理公式。

加密学 — 事实上我指的是RSA。你需要知道质数的有关知识,以及如何求最大公约数(其实是个非常简单的算法,还有许多编程语言中都有gcd()函数,帮你求解最大公约数)其他的编码大部分就是将数据按照某种步骤挪动。举个例子,下面的flash就是AES“Rijndael”编码的步骤。所有的步骤包含用一些数减去另一些数,将行向上移,将列数字打乱,再作简单的加法运算。

如果你要写你自己的加密算法(通常不需要你做,因为已经有许多很好的工具了,并且如果你不是加密学的专家的话,你的程序也许会很容易被破解。)如果你仅仅想加密一些数据的话,已经有许多加密和解密的软件库了。

所以就算是以上的情况,你也不需要真正的知道3D图像,物理或者加密的数学。你只需要学习运用软件库就行了。

编程需要学习什么?

你需要学习的是如何建模和设计算法。这意味着,如何将真实世界的运算或者数据处理抽象出来,写出代码,让计算机来帮你运算。例如,在游戏“龙与地下城”(Dungeons and Dragons)中,角色和怪兽都有许多不同的战斗统计值:

● 生命值(Hit points)是一个人死前所能经受的伤害值。越高的生命值就意味着可以经受更多的伤害。

● 防御等级(armor class)是对你的武器防御能力的量度。防御值越低,武器的防御能力越高。

● THAC0(读作“thay-co”,“To Hit Armor Class 0”),是对一个人进行有效攻击的能力的测量。THAC0值越低,攻击越准。

● 武器的攻击力用类似1d6+2来表示,它表示摇一个六面骰得到的值,然后再加2。2d4就是摇2个4面骰,然后将它们相加。(“龙与地下城”采用的是4,6,8,10,12和20面骰。)

要看攻击者打防御者,让攻击者摇动一个20面骰。如果这个数字大于或等于攻击者的THAC0减去防御者的防御能力,那么这个攻击就成功,防御者将受到伤害。不然,防御者就阻击了这个攻击,并且不费血。

我们假设两个人物,Alice和Bob,她们具有以下值:

● Alice: HP 14, AC 5, THAC0 18, DAMAGE 1d6

● Bob: HP 12, AC 7, THAC0 16, DAMAGE 2d4

所以Alice有更多的生命值和防御力(记住,AC越低越好)。但是Bob更可能成功击中对方(记住,THAC0越低越好),并造成更多的伤害。我们说Bob的攻击力更强是因为2d4可以造成2-8点伤害,而Alice的1d6只能造成1-6点伤害。(如果你懂统计学,你可以计算出Bob的期望伤害值是5,比Alice的3。5要高。)

你会打赌Alice或者Bob会赢得比赛对吗?很难讲谁会赢,他们看起来势均力敌。尽管可能你的统计学学得很好,但做这个计算将会十分头疼。编写“龙与地下城”的程序(模拟战斗过程),你甚至不需要知道统计学。仅仅需要运行几百次或者几千次战斗,看看谁赢得更多。

下面是用Python写的程序:(下载代码 http://inventwithpython.com/dnd_simulator.py)

import random, copy

NUM_FIGHTS = 1

VERBOSE = True

# Lower thac0 and lower ac values are better. Higher damage & hp values are better.

aliceTemplate = {‘name’: ‘Alice’, ‘hp’: 14, ‘ac’: 5, ‘thac0’: 18, ‘dmgnum’: 1, ‘dmgsize’:6, ‘dmgmod’: 0}

bobTemplate   = {‘name’: ‘Bob’,   ‘hp’: 12, ‘ac’: 7, ‘thac0’: 16, ‘dmgnum’: 2, ‘dmgsize’:4, ‘dmgmod’: 0}

def display(s):

if VERBOSE:

print(s)

def attack(attacker, defender):

if random.randint(1, 20) >= attacker[‘thac0’] – defender[‘ac’]:

damage = 0

for i in range(attacker[‘dmgnum’]):

damage += random.randint(1, attacker[‘dmgsize’])

damage += attacker[‘dmgmod’]

display(‘%s (%s hp) hits %s (%s hp) for %s points of damage. %s is reduced to %s hp.’ % (attacker[‘name’], attacker[‘hp’], defender[‘name’], defender[‘hp’], damage, defender[‘name’], defender[‘hp’] – damage))

defender[‘hp’] -= damage

else:

display(‘%s misses %s.’ % (attacker[‘name’], defender[‘name’]))

aliceWins = 0

bobWins = 0

for i in range(NUM_FIGHTS):

display(‘======================’)

display(‘Start of combat #%s’ % (i+1))

alice = copy.deepcopy(aliceTemplate)

bob = copy.deepcopy(bobTemplate)

while True:

attack(alice, bob)

if bob[‘hp’] <= 0: break attack(bob, alice) if alice['hp'] <= 0: break if alice['hp'] <= 0: display('Alice has died.') bobWins += 1 if bob['hp'] <= 0: display('Bob has died.') aliceWins += 1 print() print('Alice won %s (%s%%) fights. Bob won %s (%s%%) fights.' % (aliceWins, round(aliceWins / NUM_FIGHTS * 100, 2), bobWins, round(bobWins / NUM_FIGHTS * 100, 2)))

当运行这个程序时,你会看到:

Start of combat #1

Alice misses Bob.

Bob (12 hp) hits Alice (14 hp) for 6 points of damage. Alice is reduced to 8 hp.

Alice misses Bob.

Bob misses Alice.

Alice misses Bob.

Bob misses Alice.

Alice misses Bob.

Bob misses Alice.

Alice (8 hp) hits Bob (12 hp) for 5 points of damage. Bob is reduced to 7 hp.

Bob misses Alice.

Alice misses Bob.

Bob misses Alice.

Alice misses Bob.

Bob (7 hp) hits Alice (8 hp) for 2 points of damage. Alice is reduced to 6 hp.

Alice (6 hp) hits Bob (7 hp) for 6 points of damage. Bob is reduced to 1 hp.

Bob misses Alice.

Alice (6 hp) hits Bob (1 hp) for 1 points of damage. Bob is reduced to 0 hp.

Bob has died.

Alice won 1 (100.0%) fights. Bob won 0 (0.0%) fights.

但是可能Alice正好在某一次战斗中很幸运。让我们关掉输出再重新运行程序(在屏幕输出比运行程序更耗时间),当战斗次数达到30,000次时(将NUM_FIGHTS改成30000,VERBOSE变量变成False):

Alice 赢得12909 (43.03%)次战斗. Bob赢得17091 (56.97%)战斗。

所以我们看到使用上面的数值,Bob稍稍占先。电脑进行了30,000次战斗模拟。如果我们用笔和纸还有骰来进行30000次战斗模拟的话,可能需要几个月来算出结果,而我的笔记本仅用了8秒。

那么如果Alice的生命值从14增加到20呢。谁会赢呢?

Alice赢得19438 (64.79%)次战斗. Bob赢得10562 (35.21%)次战斗.

我们看到给Alice增加6点生命值,结果倒过来了,Alice占先了。那么如果Alice的生命值只是增加到16呢?

Alice赢得15176 (50.59%)次战斗啊. Bob赢得14824 (49.41%)次战斗.

所以仅仅增加2个生命值,就已经足够扳回Bob更强攻击力的胜算。

来看这个程序,它只用了加减乘除来计算一个百分比。甚至在更复杂的程序中,需要表示magic spells,治愈部位,多次攻击,在战斗中切换武器等不同效果时,我们也不需要知道更多的数学了。

当然,去学更多的数学吧。可以让你成为更出色的程序员。但是为了学习编程需要多少数学?真的非常少。

更新:我想我应该在基本知识点中增加基本代数,但仅仅需要知道的如 如果X * 3 = 12,知道X等于4。

——————

虽然大多数开发人员会告诉你,他们在工作中从来不需要数学,但是经过一番沉思后,我有了个想法:就是反马斯洛的锤子理论:当你有一把锤子,你会把一切看成是钉子。

本文仅为 Al Sweigart 一家之言,再推荐 Alan Skorkin 的这篇文章《数学是成就卓越开发人员的必备技能

既懂数学又会编程,全方位解读如何成为一名投行Quant工

2016-04-12 UniCareer

Quant是做什么的?

Quant的工作就是设计并实现金融的数学模型(主要采用计算机编程),包括衍生物定价,风险估价或预测市场行为等。所以Quant更多可看为工程师,按中国的习惯性分类方法就是理工类人才,而不是文科人才,这个和金融有一定的区别(当然金融也有很多理工的内容)。

有哪几种 Quant?

(1) Desk Quant

Desk Quant 开发直接被交易员使用的价格模型,优势是接近交易中所遇到的Money和机会,劣势是压力很大。

(2) Model Validating Quant

Model Validating Quant 独立开发价格模型,不过是为了确定Desk Quant开发的模型的正确性。优势是更轻松,压力比较小,劣势是这种小组会比较没有作为而且远离Money。

(3) Research Quant

Research Quant 尝试发明新的价格公式和模型,有时还会执行Blue-Sky Research(不太清楚是什么),优势是比较有趣(对喜欢这些人来说),而且你学到很多东西。劣势是有时会比较难证明有你这个人存在(跟科学家一样,没有什么大的成果就没人注意你)

(4) Quant Developer

其实就是名字被美化的程序员,但收入很不错而且很容易找到工作。这种工作变化很大,它可能是一直在写代码,或者调试其他人的大型系统。

(5) Statistical Arbitrage Quant

Statistical Arbitrage Quant 在数据中寻找自动交易系统的模式(就是套利系统),这种技术比起衍生物定价的技术有很大的不同,它主要用在对冲基金里,而且这种位置的回报是极不稳定的。

(6) Capital Quant

Capital Quant 建立银行的信用和资本模型,相比衍生物定价相关的工作,它没有那么吸引人,但是随着巴塞尔II银行协议的到来,它变的越来越重要,你会得到不错的收入(但不会很多),更少的压力和更少的工作时间。

人们投资金融行业就是为了赚钱,如果你想获得更多的收入,你就要更靠近那些钱的”生产”的地方,这会产生一种接近钱的看不起那些离得比较远的人的现象,作为一个基本原则,靠近钱比远离钱要来得容易。

Quant工作的领域?

(1) FX

FX就是外汇交易的简写。合同趋向于短期,大量的金额和简单的规定,所以重点在于很快速度的建立模型。

(2) Equities

Equities的意思是股票和指数的期权,技术偏向于偏微分方程(PDE)。它并不是一个特别大的市场。

(3) Fixed Income

Fixed Income的意思是基于利息的衍生物,这从市值上来说可能是最大的市场,他用到的数学会更加复杂因为从根本上来说他是多维的,技术上的技巧会用的很多,他的收入比较高。

(4) Credit Derivatives

Credit Derivatives是建立在那些公司债务还清上的衍生产品,他发展的非常快并有大量需求,所以也有很高的收入,尽管如此,他表明了一些当前经济的泡沫因素。

(5) Commodities

Commodities因为最近几年生活用品价格的普遍涨价,也成为一个发展迅速的领域。

(6) Hybrids

Hybrids是多于一个市场的衍生物市场,典型情况是利息率加上一些其它东西,它主要的优势在于可以学到多种领域的知识,这也是当前非常流行的领域。

Quant一般在哪些公司工作?

(1) 商业银行 (HSBC, RBS)

商业银行对你要求少,也给的少,工作会比较稳定。

(2) 投行 (高盛, Lehman Brothers)

投行需要大量的工作时间但工资很高,不是很稳定的工作,总的来说,美国的银行收入比欧洲银行高,但工作时间更长。

(3) 对冲基金 (Citadel Group)

对冲基金需要大量的工作时间和内容,他们也处在高速发展同时不稳定的情况中,你可能会得到大量的回报,也可能几个月后就被开除。

(4) 会计公司

大型会计公司会有自己的顾问quant团队,有些还会送他们的员工去Oxford读Master,主要的劣势在于你远离具体的行为和决策,而且厉害的人更愿意去银行,所以你比较难找到人请教。

(5) 软件公司

外包quant模型变得越来越流行,所以你去软件公司也是一个选择,劣势和会计公司比较类似。

成为一个Quant需要看哪些书?
UniCareer诚意推荐书单
 
《Options Future and Other Derivatives》
John C. Hull

不管是找工作还是senior quant都会用到。John Hull本人也是非常厉害的,各个方面都有开创性的成果。现在Toronto Uni,经典中的经典,涉猎还算广泛,不过不够数学—-人称华尔街的圣经,自然不算很难。

《Stochastic Calculus for Finance II》
Steven E. Shreve

Shreve的新书,非常elegant, 非常仔细,非常数学完备,适合数学背景, 但是比较厚,对于入门来说还是3好。作者现在CMU纽约。教授。顶尖人物。I是讲离散模型,II讲连续模型。

《Liar’s Poker》
Michael Lewis 

讲以前Solomon brothers的Arb team的,当时是世界最厉害的quant trader。这本书搞trading的人都会看。

《C++ Design Patterns and Derivatives Pricing》
Mark S. Joshi 

对于懂得C++基础的人来说很重要,更重要的是教你学会Monte Carlo。

《Modeling Derivatives in C++ (Wiley Finance)》
Justin London 
学习了一年的金工,其实就这本书最核心最实用,其他的理论书看看就好。很多理论书还有重复部分,注意区分。
《The Concepts and Practice of Mathematical Finance》
Mark S. Joshi 
这本书的目标在于覆盖一个优秀quant应该知道的知识领域,其中包括强列推荐你在应聘工作之前看的一些编程项目。
《Interest Rate Models – Theory and Practice》
Damiano Brigo / Fabio Mercurio 
评价超高的书。这本书最大的精华是关于Libor market model的论述。本书的特点是作者将所有细节和盘托出,包括大量的数值结果,这样可以方便读者自学和验证。
《Probability with Martingales》
David Williams
主要是围绕martingale展开的,前面一部份介绍必要的measure theory的部分,点到即止,都是后面基本的probability theory需要用到的。即使你之前不懂measure theory也能看懂。难怪是给undergraduate用的。Williams是这个方向上文笔最好的数学家了。
 
《Monte Carlo Methods in Financial Engineering》
Paul Glasserman
本书很实用,紧扣标题,就是围绕着金融工程中蒙特卡洛的应用展开,真正读过的人可能会有感受,此书不太适合作为first book来读,最好两方面都已经有所涉及,再来读收获更大也更舒服些。
《My Life as a Quant: Reflections on Physics and Finance》
Emanuel Derman
作者是第一代quant,以前是GS的quant 研究部门head,现在哥大。是stochastic vol领域顶尖人物,其实也是很多其他领域顶尖人物。
福利领取方式
1. 关注公众号:UniCareer2. 回复关键字:我爱读书

3. 按照提示完成操作

3个工作日内,Quant十本书福利就会送到你的邮箱啦~

成为一个Quant需要知道一些什么?

根据你想工作的地方不同,你需要学习的知识变化很大,在写着篇文章的时间(1996),我会建议将我的书全部学会就可以了。很多人错误的把学习这些知识看作仅仅看书而已,你要做的是真正的学习,就像你在准备参加一个基于这些书内容的考试,如果你对能在这个考试里拿A都没有信心的话,就不要去面试任何的工作。

面试官更在乎你对基本知识的了解是否透彻,而不是你懂得多少东西,展示你对这个领域的兴趣也很重要,你需要经常阅读Economist, FT 和Wall Street Journal,面试会问到一些基本微积分或分析的问题,例如Logx的积分是什么。问到类似Black-Scholes公式怎么得出的问题也是很正常的,他们也会问到你的论文相关的问题。

面试同样也是让你选择公司的一个机会,他们喜欢什么样的人,他们关心的是什么之类的答案可以从他们的问题中得出,如果问了很多关于C++语法的问题,那么要小心选择除非那是你想做的工作。一般来说,一个PhD对得到Quant的Offer是必需的。

有一个金融数学的Master学位会让你在银行风险或交易支持方面却不是直接Quant方面的工作,银行业变得越来越需要数学知识,所以那些东西在银行的很多领域都有帮助。

在美国,读了一个PhD之后再读一个Master变得越来越普遍,在UK这依然比较少见。

一般哪些专业对口Quant?

据观察,Quant一般的专业会是数学,物理,金融工程(金融数学)。其实虽然不是特别多,但是还是有一些投行招手Master金工的Quant,一般几个好的FE专业都有去做Quant的硕士生。

编程      

所有类型的Quant都在编程方面花费大量时间(多于一半)。尽管如此,开发新的模型本身也是很有趣的一件事,标准的实现方法是用C++。一个想成为quant的人需要学习C++,有些其他地方使用Matlab所以也是一个很有用的技能,但没C++那么重要。VBA也用的很多,但你可以在工作中掌握它。

收入   

一个Quant能赚多少?一个没有经验的Quant每年大概会挣到税前60k-100k美元。奖金的话不会太高,但是如果行情好的话,也非常的客观,一般我听说的话,刚入职第一年一般可以拿到一两万刀的奖金。如果你的工资超出这个范围,你要问自己Why?收入会迅速的增长,奖金也是总收入中一个很大的组成部分,不要太在乎开始的工资是多少,而是看重这个工作的发展机会和学习的机会。

工作时间 

一个Quant工作的时间变化很大。在RBS我们8:30上班,6pm下班。压力也是变化很大的, 一些美国银行希望你工作时间更长。 在伦敦有5-6个星期的假期,而在美国2-3个是正常的。

怎样让小孩透彻理解基本的数学概念:可汗学院数学小视频合集

这年头,但凡和教育沾点边的,还有谁不知道可汗学院啊-Khan Academy?前段时间他的故事被编成了鸡汤文,弄得我妈都知道,因为比尔盖茨都为他唱赞歌。

好吧,这个故事你多少也知道,咱们就简单回顾一下,再进入正题:

萨尔曼·可汗是美籍孟加拉国移民,毕业于麻省理工学院和哈佛大学。

萨尔曼·可汗有个小侄女叫纳迪亚,2004年她在新奥尔良上七年级,数学成绩一直不好,要求可汗给她辅导。可汗和纳迪亚不在同一个城市,于是通过互联网教纳迪亚学数学,讲得生动有趣,概念清晰,纳迪亚的数学成绩提高神速。

很快,他的朋友就知道了,也让可汗给孩子辅导数学。经过可汗辅导的孩子,数学成绩都直线上升。

可汗想,这样辅导效率太低,不如做成视频,放到互联网上,让大家免费观看。结果回到家他就躲进衣帽间里,把自己关起来,拿摄像头开始录制视频。

他的视频非常生动,基本能在十分钟内把一个数学概念讲完,在互联网上引起了很大的关注。结果一发不可收拾,他把自己关在衣帽间录制了一年的视频,从小学数学,到高中的微积分,再到大学的高等数学,统统讲了个遍,共计4800个视频。

这些视频在互联网上获得了极大的成功,点击率接近5亿,共有4800万人观看。在美国,有2万多所学校,上数学课时老师会让学生不时观看可汗的视频,看完视频后老师负责答疑。老师们说:“如果你在美国教数学,你就不可能没听说过萨尔曼·可汗。”

2011年,可汗做了一次TED演讲,比尔盖茨为他站台,和他问答互动。演讲主题是:什么才是未来的教育模式?有兴趣的朋友可以点开看看。

盖茨是可汗粉。他曾经花费很多时间教3个孩子数学和科学的基本概念,可孩子们总是听得懵懵懂懂。2010年初,有人向他推荐了可汗的网站。没想到,那些他怎么也解释不清的知识点,汗通过短短12分钟的视频,就让孩子融会贯通。

檩子很早就知道可汗和他的小视频了。看过几个,可汗的确很牛,能用一块黑板,一枝笔把抽象的数学概念通过写写画画解释得很明白。

当时很想把可汗推荐给大家,不过这些视频虽好,却是全英文的,不要说小孩,英文六级的大人看得也会很费劲。所以就算了。

这次,既然大家让推荐资料,我又去网上搜了一下,发现网易公开课里可汗的不少小视频已经做了一定程度的汉化,配上了中英文字幕。虽然还没有中文配音,但是看懂是没问题了。

目前,很多可汗的视频都在网易公开课上能找到,有中英文字幕。虽然涵盖多个科目,不过数学小视频仍然是主打。大概有40个主题。
我看了一些,感觉最实际的使用方式是这样的:家长先去看,了解一下可汗的讲解方法,然后参照可汗的方法把这个概念亲自讲给孩子听。可汗视频的价值在于可汗能用简单的语言和例子把一个抽象的概念转化成孩子能听得明白的话,讲解方式是最值得借鉴的。

可汗的视频很多,不过最经典的还是数学的基本概念讲解。檩子做了一点小功课,把可汗学院的算术与代数预备课程的视频目录找出来了,列在这里,供大家检索参考。(点击阅读原文,可以看到所有视频的链接,大家也可以去网易公开课找找)

可汗学院的 算术与代数预备课程,是从零开始学习数学的起始点,是代数课程的先导课。对于那些想从最基础开始学习数学,或者以后想要学习代数课程的幼儿园大班和小学生来说,这套课程比较适合。

1、加法与减法

主要内容:正数和负数的相加减,从1+1=2开始

[第1集] 加法1

[第2集] 加法2

[第3集] 减法1

[第4集] 减法2

[第5集] 减法3

[第6集] 加法3

[第7集] 加法4

[第8集] 减法3

[第9集] 为什么可以借代

[第10集] 加法5

[第11集] 减法4

[第12集] 减法应用题

[第13集] 交替心算减法

[第14集] 负数介绍

[第15集] 加负数

[第16集] 加不同符号的数

[第17集] 加减负数

[第18集] 两位数相加

[第19集] 加减法应用题

2、乘法与除法

主要内容:乘法与除法,正数和负数的乘除法,位值等

[第1集] 基本乘法

[第2集] 乘法表

[第3集] 10 11 12的乘法表

[第4集] 除法1

[第5集] 除法2

[第6集] 将总数平分及其应用

[第7集] 两位数乘一位数

[第8集] 两位数乘两位数

[第9集] 数字相乘及其应用2

[第10集] 格形乘法

 

3、数的性质

主要内容:交换律,结合律,分配率,恒等式等等

[第1集] 加法交换律

[第2集] 乘法交换律

[第3集] 加法结合律

[第4集] 乘法结合律

[第5集] 加法结合律性质

[第6集] 分配律性质

[第7集] 分配律性质2

[第8集] 分配律性质例1

[第9集] 数性质和绝对值

[第10集] 恒等性质1

[第11集] 恒等性质例2

[第12集] 0的恒等性质

[第13集] 加法的逆的性质

[第14集] 乘法的逆的性质

[第15集] 为什么除以0没有定义

[第16集] 为什么0除以0没有定义

[第17集] 没有定义和不确定

 

 

4、分数

主要内容:分数的计算与转换

[第1集] 分数的分子和分母

[第2集] 解释分数的意义

[第3集] 等价分数

[第4集] 等价分数例题

[第5集] 分数比较大小

[第6集] 最简分数

[第7集] 分数比较大小第2部分

[第8集] 分数排序

 

5、小数

主要内容:概念的理解,对小数的计算,转换等

[第1集] 小数加法

[第2集] 小数位值

[第3集] 小数位值2

[第4集] 用数轴表示小数

[第5集] 小数近似

[第6集] 小数估计

[第7集] 小数比较

[第8集] 小数加法

[第9集] 小数减法

[第10集] 小数减法应用题

[第11集] 小数乘以10的指数

[第12集] 小数乘法

[第13集] 小数乘法

[第14集] 小数除以10的指数

[第15集] 小数除法1

[第16集] 小数除法2

[第17集] 小数除法3

[第18集] 小数乘法3

[第19集] 小数和分数互化

[第20集] 把分数化成小数例题

[第21集] 把分数化成小数

[第22集] 把分数转换为小数例1

[第23集] 把分数转换为小数例2

[第24集] 把循环小数化成分数1

[第25集] 把循环小数化成分数2

[第26集] 把小数化成分数1例1

[第27集] 把小数化成分数1例2

[第28集] 把小数化成分数1例3

[第29集] 把小数化成分数2例1

[第30集] 把小数化成分数2例2

[第31集] 百分数和小数

[第32集] 把一个数表示成小数 百分数 分数

[第33集] 把一个数表示成小数 百分数 分数2

[第34集] 数轴上一点

[第35集] 数字排序

 

 

6、负数

主要内容包括:理解与使用负数

[第1集] 负数介绍

[第2集] 负数的大小排序

[第3集] 加负数

[第4集] 加不同符号的数

[第5集] 加减负数

[第6集] 正数和负数相乘

[第7集] 正数和负数除法

[第8集] 为什么负数乘以负数得到正数

 

7、约数与倍数

主要内容:质数,最小公倍数,最大公约数

[第1集] 质数

[第2集] 判断质数

[第3集] 判断整除

[第4集] 共同整除的例题

[第5集] 找一个数的因数

[第6集] 质因数分解

[第7集] 最小公倍数

[第8集] 最小公倍数(LCM)

[第9集] 最大公约数

[第10集] 代数表达式的最小公倍数

[第11集] 3的整除性质

8、指数

主要内容:不用代数来理解指数

 

[第1集] 理解指数

[第2集] 理解指数2

[第3集] 指数第一级

[第4集] 指数第二级

[第5集] 指数第三级

[第6集] 指数法则1

[第7集] 指数法则2

 

9、比率和比例

主要内容:不用代数来理解比率
[第1集] 比例介绍

[第2集] 理解比例

[第3集] 比例分数的最简形式

[第4集] 比例化简

[第5集] 求比例中的未知数

[第6集] 求单位速度

 

10、计算顺序

内容包括:表达式中各种计算的运算顺序

[第1集] 运算顺序介绍

[第2集] 更复杂的运算顺序例子

[第3集] 运算顺序1

[第4集] 运算顺序2

点击阅读原文,去小花生网看这些视频的播放链接。

本文由小花生编写,公众号转载须获授权

相关阅读:

花生快讯:

感谢订阅 “小花生网”

每天推送国内外最优秀的教育资源

周一:新书开团

周二:国外实用的教育方法

周三:英文原版趣味学习资源

周四:不同年龄的中文好书

周五:儿童电影/动画片/纪录片

周六:美好生活画报

周日:引发深度思考的文章

纯粹数学的雪崩效应:庞加莱猜想何以造福了精准医疗?

2016-04-12 顾险峰 赛先生


图1 庞加莱猜想电脑三维模型

顾险峰 (纽约州立大学石溪分校终身教授,清华大学丘成桐数学科学中心访问教授,计算共形几何创始人)

最近英国上议院议员马特瑞德利(Matt Ridley)在《华尔街日报》上撰文《基础科学的迷思》(The Myth of Basic Science)。他认为“科学驱动创新,创新驱动商业”这一说法基本上是错误的,反而是商业驱动了创新,创新驱动了科学,正如科学家被实际需求所驱动,而不是科学家驱动实际需求一样。总之,他认为“科学突破是技术进步的结果,而不是原因”。

瑞德利先生的言论反映了许多人对基础科学的严重误解,会给年轻学子们带来思想混乱和价值观念上的困扰,有必要加以澄清。诚然,商业需求和工程实践会为基础科学提供研究的素材,比如历史上最优传输理论(OptimalMass Transportation Theory)和蒙日-安培方程(Monge-Ampere)起源于土石方的运输,最后猜想被康塔洛维奇解决,康塔洛维奇为此获得了诺贝尔经济学奖。数年前,为了解决医学图像的压缩问题,陶哲轩提出了压缩感知(Compressive Sensing)理论。但是,从根本上而言,基础科学的源动力来自于科学家对于自然真理的好奇和对美学价值的追求。基础科学上的突破,因为揭示了自然界的客观真理,往往会引发应用科学的革命。纯粹数学的研究因为其晦涩抽象,实用价值并不明显直观,普罗大众一直倾向于认为其“无用”。但实际上,纯粹数学对应用科学的指导作用是无可替代的。

计算机科学和技术发展的一个侧面就在于将人类数千年积累的知识转换成算法,使得没有经历过职业训练的人也可以直接使用最为艰深的数学理论。在拓扑和几何领域,往往很多具有数百年历史的定理仅仅在最近才被转换成算法。但是,依随计算机技术的迅猛发展,从定理到算法的过程日益加速。很多新近发展的数学理论被迅速转换成强有力的算法,并在工程和医疗领域被广泛应用。

历史一再表明,以满足人类好奇心为出发点的基础理论研究,其本质突破往往不能引起当时人类社会的重视,宛若冰川旷谷中一声微弱的呐喊,转瞬间随风消逝,但是这一声往往会引发令天空变色,大地颤抖的雪崩。庞加莱猜想的证明就是一个鲜明的实例,虽然雪崩效应还没有被大众所察觉,但是雪崩已经不可逆转地开始了!

1  庞加莱猜想

法国数学家庞加莱(Jules Henri Poincaré)是现代拓扑学的奠基人。拓扑学研究几何体,例如流形,在连续形变下的不变性质。我们可以想象曲面由橡皮膜制成,我们对橡皮膜拉伸压缩,扭转蜷曲,但是不会撕破或粘联,那么这些形变都是连续形变,或被称之为拓扑形变,在这些形变下保持不变的量就是拓扑不变量。如果一张橡皮膜曲面经由拓扑形变得到另外一张橡皮膜曲面,则这两张曲面具有相同的拓扑不变量,它们彼此拓扑等价。如图2 所示,假设兔子曲面由橡皮膜做成,我们象吹气球一样将其膨胀成标准单位球面,因此兔子曲面和单位球面拓扑等价。

图2. 兔子曲面可以连续形变成单位球面,因此兔子曲面和球面拓扑等价。

兔子曲面无法连续形变成轮胎的形状,或者图3中的任何曲面。直观上,图5中小猫曲面有一个“洞”,或称“环柄”;图3中的曲面则有两个环柄。拓扑上,环柄被称为亏格。亏格是最为重要的拓扑不变量。所有可定向封闭曲面依照亏格被完全分类。


图3. 亏格为2的封闭曲面。亏格是曲面最重要的拓扑不变量。

庞加莱思考了如下深刻的问题:封闭曲面上的“洞”是曲面自身的内蕴性质,还是曲面及其嵌入的背景空间之间的相对关系?这个问题本身就是费解深奥的,我们力图给出直观浅近的解释。我们人类能够看到环柄形成的“洞”,是因为曲面是嵌入在三维欧式空间中的,因此这些“洞”反应了曲面在背景空间的嵌入方式,我们有理由猜测亏格反映了曲面和背景空间之间的关系。

图4. 曲面上生活的蚂蚁如何检测曲面的拓扑?

但是另一方面,假设有一只蚂蚁自幼生活在一张曲面上,从未跳离过曲面,因此从未看到过曲面的整体情形。蚂蚁只有二维概念,没有三维概念。假设这只蚂蚁具有高度发达的智力,那么这只蚂蚁能否判断它所生活的曲面是个亏格为0的拓扑球面,还是高亏格曲面?

图5. 亏格为1的曲面上,无法缩成点的闭圈。

庞加莱最终悟到一个简单而又深刻的方法来判断曲面是否是亏格为0的拓扑球面:如果曲面上所有的封闭曲线都能在曲面上逐渐缩成一个点,那么曲面必为拓扑球面。比如,我们考虑图5中小猫的曲面,围绕脖子的一条封闭曲线,在曲面上无论怎样变形,都无法缩成一个点。换言之,只要曲面亏格非零,就存在不可收缩成点的闭圈。如果流形内所有的封闭圈都能缩成点,则流形被称为是单连通的。庞加莱将这一结果向高维推广,提出了著名的庞加莱猜想:假设M是一个封闭的单连通三维流形,则M和三维球面拓扑等价。

图6. 带边界的三流形,用三角剖分表示。

在现实世界中,无法看到封闭的三维流形:正如二维封闭曲面无法在二维平面上实现,三维封闭流形无法在三维欧式空间中实现。图6显示了带有边界的三维流形,例如实心的兔子和实心的球体拓扑等价。这些三维流形用三角剖分来表示,就是用许多四面体粘合而成。如图所示,体的三角剖分诱导了其二维边界曲面的三角剖分。实心球实际上是三维拓扑圆盘,我们可以将两个三维拓扑圆盘沿着边界粘合,就得到三维球面,恰如我们可以将两个二维拓扑圆盘沿着边界粘合而得到二维球面一样。当然,这已经超出人们的日常生活经验。

2  曲面单值化定理

近百年来,庞加莱猜想一直是拓扑学最为基本的问题,无数拓扑学家和几何学家为证明庞加莱猜想而鞠躬尽瘁死而后已。相比那些最后成功的幸运儿,众多默默无闻,潦倒终生的失败者更加令人肃然起敬。老顾曾经访问过吉林大学数学学院,听闻了有关何伯和教授的生平事迹。何教授终生痴迷于庞加莱猜想的证明,苦心孤诣,废寝忘食,愈挫愈奋,九死不悔,直至生命终结,对于庞加莱猜想依然念念不忘。何教授绝对不是为了任何实用价值或者商业利益而奋斗终生的,而是为了对于自然界奥秘的好奇,对于美学价值的热切追求,这种纯粹和崇高,是人类进步的真正动力!


图7. 人脸曲面上连接两点的测地线。

作为拓扑学最为基本的问题,庞加莱猜想的本质突破却来自于几何。给定一个拓扑流形,如给定图6中四面体网格的组合结构,我们可以为每条边指定一个长度,使得每个四面体都是一个欧式的四面体,这样我们就给出了一个黎曼度量。所谓黎曼度量,就是定义在流形上的一种数据结构,使得我们可以确定任意两点间的最短测地线。图7显示了人脸曲面上的两条测地线。黎曼度量自然诱导了流形的曲率。曲率是表征空间弯曲的一种精确描述。给定曲面上三个点,我们用测地线连接它们成一个测地三角形。如果曲面为欧几里德平面,那么测地三角形内角和为180度。球面测地三角形的内角和大于180度,马鞍面的测地三角形的内角和小于180度。测地三角形内角和与180度的差别就是三角形的总曲率。那么,给定一个拓扑流形,我们能否选择一个最为简单的黎曼度量,使得曲率为常数呢?

图8. 曲面单值化定理,所有封闭曲面都可以保角地形变成常曲率曲面。

这一问题的答案是肯定的,这就是曲面微分几何中最为根本的单值化定理。单值化定理是说大千世界,各种几何形状千变万化,但是无论它们如何变化,都是万变不离其宗:所有的曲面都可以共形地变换成三种标准曲面中的一种,单位球面,欧几里德平面和双曲平面。标准空间对应着常数值曲率,+1,0和-1,如图8所示。所谓共形变换,就是保持局部形状的变换,局部上看就是相似变换。相似变换保持角度不变,因此共形变换也被称为是保角变换。图9显示了从曲面到平面的一个共形变换。单值化定理断言了所有封闭曲面可以配有三种几何中的一种:球面几何,欧氏几何和双曲几何。曲面微分几何中几乎所有的重要定理都绕不过单值化定理。


图9. 共形变换保持局部形状。

3  瑟斯顿几何化猜想

为了证明庞加莱猜想,菲尔兹奖得主瑟斯顿推广了单值化定理到三维流形情形。任何三维流形,都可以经历一套标准手续分解成一系列的最为简单的三维流形,即所谓的素流形。素流形本身无法被进一步分解,同时这种分解本质上是唯一的。瑟斯顿提出了石破天惊的几何化猜想:所有的素三维流形可以配有标准黎曼度量,从而具有8种几何中的一种。特别地,单连通的三维流形可被配有正的常值曲率度量,配有正的常值曲率的3维流形必为3维球面。因此庞加莱猜想是瑟斯顿几何化猜想的一个特例。

图10. 瑟斯顿的苹果,几何化猜想。

图10显示了瑟斯顿几何化的一个实例。假设我们有一个苹果,三只蛀虫蛀蚀了三条管道,如左帧所示,这样我们得到了一个带边界的三维流形。根据几何化纲领,这个被蛀蚀的苹果内部容许一个双曲黎曼度量,使得其边界曲面的曲率处处为-1。我们将配有双曲度量的苹果周期性地嵌在三维双曲空间之中,得到右帧所示图形。

4  哈密尔顿的里奇曲率

本质的突破来自于哈密尔顿的里奇曲率流(Hamilton’s Ricci Flow)。哈密尔顿的想法来自经典的热力学扩散现象。假设我们有一只铁皮兔子,初始时刻兔子表面的温度分布并不均匀,依随时间流逝,温度渐趋一致,最后在热平衡状态,温度为常数。哈密尔顿设想:如果黎曼度量依随时间变化,度量的变化率和曲率成正比,那么曲率就像温度一样扩散,逐渐变得均匀,直至变成常数。如图11所示,初始的哑铃曲面经由曲率流,曲率变得越来越均匀,最后变成常数,曲面变成了球面。

图11. 曲率流使得曲率越来越均匀,直至变成常数,曲面变成球面。

在二维曲面情形,哈密尔顿和Ben Chow证明了曲率流的确将任何一个黎曼度量形变成常值曲率度量,从而给出了曲面单值化定理的一个构造性证明。但是在三维流形情形,里奇曲率流遇到了巨大的挑战。在二维曲面情形,在曲率流过程中,在任意时刻,曲面上任意一点的曲率都是有限的;在三维流形情形,在有限时间内,流形的某一点处,曲率有可能趋向于无穷,这种情况被称为是曲率爆破(blowup),爆破点被称为是奇异点(singularity)。

如果发生曲率爆破,我们可以将流形沿着爆破点一切两半,然后将每一半接着实施曲率流。如果我们能够证明在曲率流的过程中,曲率爆破发生的次数有限,那么流形被分割成有限个子流形,每个子流形最终变成了三维球面。如果这样,原来流形由有限个球粘合而成,因而是三维球面,这样就证明了庞加莱猜想。由此可见,对于奇异点的精细分析成为问题的关键。哈密尔顿厘清了大多数种类奇异点的情况,佩雷尔曼解决了剩余的奇异点种类。同时,佩雷尔曼敏锐地洞察到哈密尔顿的里奇流是所谓熵能量的梯度流,从而将里奇流纳入了变分的框架。佩雷尔曼给出了证明的关键思想和主要梗概,证明的细节被众多数学家进一步补充完成。至此,瑟斯顿几何化猜想被完全证明,庞加莱猜想历经百年探索,终于被彻底解决。

5 庞加莱猜想带来的计算技术

庞加莱猜想本身异常抽象而枯燥:单连通的闭3-流形是三维球面,似乎没有任何实用价值。但是为了证明庞加莱猜想,人类发展了瑟斯顿几何化纲领,发明了哈密尔顿的里奇曲率流,深刻地理解了三维流形的拓扑和几何,将奇异点的形成过程纳入了数学的视野。这些基础数学上的进展,必将引起工程科学和实用技术领域的“雪崩”。比如,里奇曲率流技术实际上给出了一种强有力的方法,使得我们可以用曲率来构造黎曼度量

里奇曲率流属于非线性几何偏微分方程,里奇流的方法实际上是典型的几何分析方法,即用偏微分方程的技术来证明几何问题。几何分析由丘成桐先生创立,庞加莱猜想的证明是几何分析的又一巨大胜利。当年瑟斯顿提倡用相对传统的拓扑和几何方法,例如泰西米勒理论和双曲几何理论来证明,也有数学家主张用相对组合的方法来证明,最终还是几何分析的方法拔得头筹。

哈密尔顿的里奇流是定义在光滑流形上的,在计算机的表示中,所有的流形都被离散化。因此,我们需要建立一套离散里奇流理论来发展相应的计算方法。历经多年的努力,笔者和合作者们建立了离散曲面的里奇曲率流理论,证明了离散解的存在性和唯一性。因为几乎所有曲面微分几何的重要问题,都无法绕过单值化定理。我们相信离散曲率流的计算方法必将在工程实践中发挥越来越重要的作用 [1]


图12. 离散里奇流计算的带边曲面单值化。

图8和图12显示了离散里奇流算出的封闭曲面和带边界曲面的单值化。本质上,这两幅图统摄了现实生活中所有可能的曲面,它们都被共形地映到了三种标准曲面上,球面、欧氏平面和双曲平面。这意味着,如果我们发明了一种新的几何算法,适用于这三种标准曲面,那么这一算法也适用于所有曲面。因此,离散曲率流的技术极大地简化了几何算法设计。

6 精准医疗

庞加莱猜想所诱发的离散曲率流方法被广泛应用于精准医疗领域。人体的各种器官本质上都是二维曲面或三维流形,曲率流方法对于这些器官几何特征的分析和比较起到了不可替代的作用。


图13. 虚拟肠镜技术。

虚拟肠镜 

直肠癌是男子的第四号杀手,仅在心脑血管疾病之后。中年之后,每个人都会自然长出直肠息肉,息肉会逐年增长,如果息肉直径达到一定尺寸,由于摩擦息肉会发生溃疡,长期溃疡会导致癌变。但是直肠息肉的生长非常缓慢, 一般从息肉出现直到临界尺寸需要七八年,因此对息肉的监控对于预防直肠癌起着至关重要的作用。中年人应该每两年做一次肠镜检查。传统的肠镜检查方法需要对受检者全身麻醉,将光学内窥镜探入直肠。老年人肠壁比较薄弱,容易产生并发症。同时,肠壁上有很多皱褶,如果息肉隐藏在皱褶中,医生会无法看到而产生漏检。

近些年来,北美和日本采用了虚拟肠镜技术。受检者的直肠图像由断层扫描技术来获取,直肠曲面可以从图像重建出来,如图14所示。我们需要将直肠展开摊平,从而使所有皱褶暴露出来,以便于寻找息肉和测量它们的尺寸。同时,如图13所示,在检查中同一受检者的直肠被扫描两次,每次扫描都是采用不同的姿态。直肠曲面柔软而富有弹性,不同的扫描得到的曲面之间相差很大的弹性形变。我们需要在两张曲面间建立光滑双射。在两张三维曲面间建立映射相对困难,当我们将曲面摊开展平成平面长方形后,在平面区域间计算映射会简单很多。将直肠曲面摊开展平等价于为曲面赋上一个曲率处处为0的黎曼度量,我们可以直接应用里奇曲率流的算法加以实现,如图14所示。

图14. 用里奇曲率流将直肠曲面摊开展平。

目前,虚拟肠镜技术在北美和日本被广泛采用,(但在中国还没有普及),主要是因为这种方法可以提高安全性,降低漏检率,降低人力成本。虚拟肠镜技术的普及极大地提高了早期直肠癌的发现几率,降低了直肠癌的死亡率,为人类的健康事业做出了巨大贡献。


图15. 虚拟膀胱镜。

同样的方法可以用于膀胱等其他器官,如图15所示。膀胱癌的最主要特征是膀胱壁变厚,同时内壁不再光滑,出现菜花状的几何纹理。这些症状可以用虚拟膀胱镜的方法定量得到。传统膀胱镜的方法病人需要忍受很大的痛苦,虚拟膀胱镜的方法极大地减轻了病患的疼痛,因而具有很大的优势。


图16. 用里奇曲率流将大脑皮层曲面共形映到单位球面,以便于对照比较。

脑神经疾病的预防诊断

脑退化症(Alzheimer’s disease,俗称老年痴呆症),癫痫,儿童自闭症等脑神经疾病严重地威胁着人类的健康安全。对于这些疾病的预防和诊断具有重要的现实意义。通过核磁共振成像技术,我们能够获取人类的大脑皮层曲面,如图16所示。大脑皮层曲面的几何非常复杂,有大量的皱褶沟回结构,并且这些几何结构因人而异,依随年龄变化而变化。例如老年痴呆症往往伴随大脑皮层一部分区域的萎缩。为了监控病情的发展,我们需要每隔几个月就扫描一下病人的大脑,然后将不同时期得到的大脑皮层曲面进行精确地对比。在三维空间中直接对比难度很高,我们非常容易将不同的沟回错误地对齐,算法落入在局部最优陷阱中。如图16所示,我们将大脑皮层曲面共形地映到球面上,然后在球面之间建立光滑映射,这种方法更加简单而精确。将大脑皮层映到球面等价于为大脑皮层曲面赋以曲率为+1的黎曼度量,我们可以用里奇曲率流的方法得到。


图17. 大脑海马体的几何分析。

如果说大脑皮层是数据库,那么海马体就是数据库的索引,如图17所示。如果海马体发生病变,长期记忆就无法形成,同时大脑中的长期记忆也无法被取出。很多神经疾病都能够引起海马体的变形,例如癫痫、吸毒、脑退化症等等。对海马体的几何形状进行定量比较分类是非常重要的。一种精确的方法是将海马体共形映到单位球面上,则面积的变化率给出了初始黎曼度量的全部信息,再加上平均曲率,那么海马体的所有几何信息被完美保留。换言之,我们将海马体曲面转换为球面上的两个函数(面积变化率,平均曲率)。在球面上比较不同的海马体曲面,从而精确衡量曲面之间的相似程度,进行分类诊断。相比于传统方法,这种基于几何的诊断方法更加定量而精确。

图18. 人脸曲面的精确匹配。

美容技术

在美容手术领域中,术后效果评估是重要的一个环节,这需要将术前和术后的人脸曲面进行精确的匹配。如图18所示,我们扫描了同一个人的带有不同表情的两张人脸曲面,然后在人脸曲面之间建立了精确的双射。平静表情的人脸上每一个小圆映到微笑表情的人脸上对应的小椭圆,由此我们可以测量对应点的几何变化。因此,三维人脸曲面间精确映射是美容领域中至关重要的技术。


图19. 三维人脸曲面被共形地映到二维平面上,所用方法就是里奇曲率流。

如图19所示,我们用里奇曲率流方法,将人脸曲面的黎曼度量变成曲率为0的平直度量,将三维人脸曲面平铺到二维平面上面,然后在二维平面区域之间建立光滑双射,从而诱导三维人脸曲面间的双射。当然,这种方法也可以用于三维人脸识别,但是人脸识别对于映射的精确度要求没有如此之高。

在精准医疗的其他领域,例如牙齿整形、人造心脏瓣膜、人造骨骼、放射治疗实时监控、肝脏手术计划等等,都需要对各种人体器官进行影像获取、几何重建、特征分析等,里奇流方法都会起到重要的作用。

7 总结和展望

庞加莱猜想本身纯粹而抽象:单连通的闭三维流形是三维球面,这一猜想本身似乎并没有任何实用价值。其结论的简单直观,往往给非数学专业人员无病呻吟之感。但是纯粹数学所追求的严密性迫使无数拓扑和几何学家们前仆后继,奉献终身,终于在众多数学家的共同努力下完成了证明。二维曲面的几何化定理——单值化定理从理论证明到算法提出,历经了百年;三维流形的瑟斯顿几何化纲领从理论证明到算法提出,几乎是同时。三维流形的拓扑理论和计算理论一开始就深刻地纠缠在一起。这表明,在现代,依随计算机技术的发展,纯粹理论到应用算法的开发周期越来越短。

同时,我们看到,在证明庞加莱猜想的过程中,瑟斯顿的几何化纲领将三维流形的风景一览无遗,哈密尔顿的里奇流给出从曲率来构造黎曼度量的强有力的工具,哈密尔顿和佩雷尔曼的奇点演化理论使得原来理论的禁区被彻底打破。笔者和许多数学家发展了离散里奇流的理论和算法,并且系统性地将曲率流应用到许多工程和医疗领域。在实践中,我们深深体会到,在许多关键的应用中,曲率流的方法无法被其它任何方法所取代。目前在社会实践中,里奇流在二维曲面上的应用已经开始逐步展开。但是里奇流在三维流形上的应用更为深邃奥妙,强悍有力,目前还没有任何实际应用。一方面因为三维流形远远超越日常生活经验,另一方面也是因为和曲面微分几何相比,三维流形的拓扑和几何知识远未普及。但是作为自然真理的忠实刻画,迟早三维流形的拓扑和几何会在社会实践中大行其道。庞加莱猜想所引发的雪崩效应终究会改写历史进程。

当庞加莱提出他的拓扑猜想,瑟斯顿洞察三维流形的基本几何结构,哈密尔顿悟出里奇曲率流,佩雷尔曼看出哈密尔顿的曲率流本质上是所谓熵能量的梯度流,他们所追求的是体悟几何结构的壮美,和自然真理的深邃。他们绝不会将实用价值作为其终极目的。实用技术的积累往往只能带来进化(Evolutio),好奇心的满足却能真正带来革命(Revolution)。愿更多的年轻人在万丈红尘中,在浮躁喧嚣中,能够保持诚挚纯真,保持强烈好奇,保持对自然界美丽的敏感,保持对科学真理的激情!

(如果读者对于离散曲面里奇流的理论、算法和应用有兴趣,可以进一步查阅专著【1】)

参考文献

[1] W. Zeng and X. Gu, Ricci Flow for Shape Analysis and Surface Registration Theories, Algorithms and Applications, Springer 2013

延伸阅读

  如果没有基础科学,我们将会失去什么?②  视频 | 拓扑为何?

③  纯粹数学走出象牙塔:丘成桐和三维科技有何关系?

算法的力量

李开复写于 2006 年

算法是计算机科学领域最重要的基石之一,但却受到了国内一些程序员的冷落。许多学生看到一些公司在招聘时要求的编程语言五花八门就产生了一种误解,认为学计算机就是学各种编程语言,或者认为,学习最新的语言、技术、标准就是最好的铺路方法。其实大家都被这些公司误导了。编程语言虽然该学,但是学习计算机算法和理论更重要,因为计算机算法和理论更重要,因为计算机语言和开发平台日新月异,但万变不离其宗的是那些算法和理论,例如数据结构、算法、编译原理、计算机体系结构、关系型数据库原理等等。在“开复学生网”上,有位同学生动地把这些基础课程比拟为“内功”,把新的语言、技术、标准比拟为“外功”。整天赶时髦的人最后只懂得招式,没有功力,是不可能成为高手的。

算法与我

当我在1980年转入计算机科学系时,还没有多少人的专业方向是计算机科学。有许多其他系的人嘲笑我们说:“知道为什么只有你们系要加一个‘科学’,而没有‘物理科学系’或‘化学科学系’吗?因为人家是真的科学,不需要画蛇添足,而你们自己心虚,生怕不‘科学’,才这样欲盖弥彰。”其实,这点他们彻底弄错了。真正学懂计算机的人(不只是“编程匠”)都对数学有相当的造诣,既能用科学家的严谨思维来求证,也能用工程师的务实手段来解决问题——而这种思维和手段的最佳演绎就是“算法”。

记得我读博时写的Othello对弈软件获得了世界冠军。当时,得第二名的人认为我是靠侥幸才打赢他,不服气地问我的程序平均每秒能搜索多少步棋,当他发现我的软件在搜索效率上比他快60多倍时,才彻底服输。为什么在同样的机器上,我可以多做60倍的工作呢?这是因为我用了一个最新的算法,能够把一个指数函数转换成四个近似的表,只要用常数时间就可得到近似的答案。在这个例子中,是否用对算法才是能否赢得世界冠军的关键。

还记得1988年贝尔实验室副总裁亲自来访问我的学校,目的就是为了想了解为什么他们的语音识别系统比我开发的慢几十倍,而且,在扩大至大词汇系统后,速度差异更有几百倍之多。他们虽然买了几台超级计算机,勉强让系统跑了起来,但这么贵的计算资源让他们的产品部门很反感,因为“昂贵”的技术是没有应用前景的。在与他们探讨的过程中,我惊讶地发现一个O(n*m)的动态规划(dynamic programming)居然被他们做成了O (n*n*m)。更惊讶的是,他们还为此发表了不少文章,甚至为自己的算法起了一个很特别的名字,并将算法提名到一个科学会议里,希望能得到大奖。当时,贝尔实验室的研究员当然绝顶聪明,但他们全都是学数学、物理或电机出身,从未学过计算机科学或算法,才犯了这么基本的错误。我想那些人以后再也不会嘲笑学计算机科学的人了吧!

网络时代的算法

有人也许会说:“今天计算机这么快,算法还重要吗?”其实永远不会有太快的计算机,因为我们总会想出新的应用。虽然在摩尔定律的作用下,计算机的计算能力每年都在飞快增长,价格也在不断下降。可我们不要忘记,需要处理的信息量更是呈指数级的增长。现在每人每天都会创造出大量数据(照片,视频,语音,文本等等)。日益先进的纪录和存储手段使我们每个人的信息量都在爆炸式的增长。互联网的信息流量和日志容量也在飞快增长。在科学研究方面,随着研究手段的进步,数据量更是达到了前所未有的程度。无论是三维图形、海量数据处理、机器学习、语音识别,都需要极大的计算量。在网络时代,越来越多的挑战需要靠卓越的算法来解决。

再举另一个网络时代的例子。在互联网和手机搜索,如果要找附近的咖啡店,那么搜索引擎该怎么处理这个请求呢?最简单的办法就是把整个城市的咖啡馆都找出来,然后计算出它们的所在位置与你之间的距离,再进行排序,然后返回最近的结果。但该如何计算距离呢?图论里有不少算法可以解决这个问题。

这么做也许是最直观的,但绝对不是最迅速的。如果一个城市只有为数不多的咖啡馆,那么这么做应该没什么问题,反正计算量不大。但如果一个城市里有很多咖啡馆,又有很多用户都需要类似的搜索,那么服务器所承受的压力就大多了。在这种情况下,我们该怎样优化算法呢?

首先,我们可以把整个城市的咖啡馆做一次“预处理”。比如,把一个城市分成若干个“格子(grid)”,然后根据用户所在的位置把他放到某一个格子里,只对格子里的咖啡馆进行距离排序。

问题又来了,如果格子大小一样,那么绝大多数结果都可能出现在市中心的一个格子里,而郊区的格子里只有极少的结果。在这种情况下,我们应该把市中心多分出几个格子。更进一步,格子应该是一个“树结构”,最顶层是一个大格——整个城市,然后逐层下降,格子越来越小,这样有利于用户进行精确搜索——如果在最底层的格子里搜索结果不多,用户可以逐级上升,放大搜索范围。

上述算法对咖啡馆的例子很实用,但是它具有通用性吗?答案是否定的。把咖啡馆抽象一下,它是一个“点”,如果要搜索一个“面”该怎么办呢?比如,用户想去一个水库玩,而一个水库有好几个入口,那么哪一个离用户最近呢?这个时候,上述“树结构”就要改成“r-tree”,因为树中间的每一个节点都是一个范围,一个有边界的范围(参考:http://www.cs.umd.edu/~hjs/rtrees/index.html)。

通过这个小例子,我们看到,应用程序的要求千变万化,很多时候需要把一个复杂的问题分解成若干简单的小问题,然后再选用合适的算法和数据结构。

并行算法:Google的核心优势

上面的例子在Google里就要算是小case了!每天Google的网站要处理十亿个以上的搜索,GMail要储存几千万用户的2G邮箱, Google Earth要让数十万用户同时在整个地球上遨游,并将合适的图片经过互联网提交给每个用户。如果没有好的算法,这些应用都无法成为现实。

在这些的应用中,哪怕是最基本的问题都会给传统的计算带来很大的挑战。例如,每天都有十亿以上的用户访问Google的网站,使用Google的服务,也产生很多很多的日志(Log)。因为Log每份每秒都在飞速增加,我们必须有聪明的办法来进行处理。我曾经在面试中问过关于如何对Log进行一些分析处理的问题,有很多面试者的回答虽然在逻辑上正确,但是实际应用中是几乎不可行的。按照它们的算法,即便用上几万台机器,我们的处理速度都根不上数据产生的速度。

那么Google是如何解决这些问题的?

首先,在网络时代,就算有最好的算法,也要能在并行计算的环境下执行。在Google的数据中心,我们使用的是超大的并行计算机。但传统的并行算法运行时,效率会在增加机器数量后迅速降低,也就是说,十台机器如果有五倍的效果,增加到一千台时也许就只有几十倍的效果。这种事倍功半的代价是没有哪家公司可以负担得起的。而且,在许多并行算法中,只要一个结点犯错误,所有计算都会前功尽弃。

那么Google是如何开发出既有效率又能容错的并行计算的呢?

Google最资深的计算机科学家Jeff Dean认识到,Google所需的绝大部分数据处理都可以归结为一个简单的并行算法:MapReduce。这个算法能够在很多种计算中达到相当高的效率,而且是可扩展的(也就是说,一千台机器就算不能达到一千倍的效果,至少也可以达到几百倍的效果)。 MapReduce的另外一大特色是它可以利用大批廉价的机器组成功能强大的server farm。最后,它的容错性能异常出色,就算一个 server farm宕掉一半,整个fram依然能够运行。正是因为这个天才的认识,才有了MapReduce算法。借助该算法, Google几乎能无限地增加计算量,与日新月异的互联网应用一同成长。

算法并不局限于计算机和网络

举一个计算机领域外的例子:在高能物理研究方面,很多实验每秒钟都能几个TB的数据量。但因为处理能力和存储能力的不足,科学家不得不把绝大部分未经处理的数据丢弃掉。可大家要知道,新元素的信息很有可能就藏在我们来不及处理的数据里面。同样的,在其他任何领域里,算法可以改变人类的生活。例如人类基因的研究,就可能因为算法而发明新的医疗方式。在国家安全领域,有效的算法可能避免下一个911的发生。在气象方面,算法可以更好地预测未来天灾的发生,以拯救生命。

所以,如果你把计算机的发展放到应用和数据飞速增长的大环境下,你一定会发现;算法的重要性不是在日益减小,而是在日益加强。

有哪些优秀程序员知道而新手不知道的秘诀?

原载:伯乐在线

Jens Rantil 的观点:2.9k 顶

大多数情况下,使用继承从长远看来是一个很糟糕的面向对象设计。它影响了代码的重用性和可测试性。推荐使用组件和接口的方式替代它。

避免过早引入接口,除非你能够完全控制它。“过早接口”同样会导致设计问题。

深度代码嵌套(both intra-function and inter-function) 1 ) 难于维护 2 )更容易产生bug 3 ) 难于复用。精炼的代码层次划分更利于以后的代码测试和代码复用。参照上一条关于继承的问题。

预估时间在开发中是一件很难的事情。这就是为什么在很多地方使用敏捷开发(Scrum)和 Sprints 。参见:《为什么程序员总是不能准确估测项目时间?》、《趣文:为什么软件开发周期通常是预期的两三倍?

完美的加密是很难做到的。除非有一个很好的理由,否则不要尝试自己去发明它。

无副作用逻辑(Side-effect free logic)是非常棒的,这使了解程序状态更简单(参看下一条),同时也简化了自动化测试。

学习去了解程序的状态切换和生命周期。参看 Jens Rantil 的博客

如果选则合适的实现方式,并发并不难。线程池、队列、观察者模式、非可变性和Actor模型编程可以帮你很多。

过早优化是万恶之源。一个好的开发过程一般是: 1 ) 让它工作。 2 ) 使代码很漂亮。 3 ) 优化。

了解程序的基本数据结构和理解时间复杂度。这是一个有效使代码变得更快在的方法,且不会增加代码复杂度。

练习粗略计算。一段代码通常在内存中占用多少?相关;

应用程序早晚会出问题;不好的部署,意想不到的行为,意想不到的输入或意想不到的外部加载。为了应对这些问题。我们需要确保用日志记录下那些未捕获的异常,在部署工作完成后进行测试(并可能回滚),并不停地运行测试,也要确保为所有内存中的队列和线程池设置限制(理智的)。相关;

如果你监控队列大小的时候,发现它通常总是满的或空的。应对好这些。

网络服务和外部服务应该一直保持片状(易剥离的,即插即播)。为每一个套接字(Socket)设置超时,在每次HTTP读或者连接操作时都设置超时。建议可以将外部网络封装到一个重试/循环断路库中。(参考 Netflix/Hystrix 和 rholder/guava-retrying)

写出你自己都愿意读的代码。增加注释,除非你认为还能在一年后看懂它。在一个月后你会需要这些注释的。有些相关;

为项目设置构建工具,这样别人可以更快开始工作。在你的README文件中记录下要构建、运行、测试和打包的命令。

确保你的项目可以从命令行构建,会使事情变的容易得多。

在许多语言中,处理第三方依赖关系是一个真正混乱的事情(看看你的Java和Python工程)。特别是当两个不同的库依赖于不同版本。使你远离这些麻烦的好方法: 1 ) 不断审视你的依赖库。 2 ) 自动化测试有助于解决此类问题。 3 ) 总是关注你应该使用哪个版本的第三方依赖库。

阅读流行的开源项目,是学习编写可维护代码和软件开发流程的好方法。

为应用添加的每一行代码都会增加项目的复杂性,同时使它发生错误的可能性更高。删除代码是一个消除错误的好方式。相关;

应用中的每一个基础服务(数据库、缓存、消息队列等)都是一个bug的来源,需要对它们进行维护,同时也需要学习新知识。更不用说,这种依赖性可能会降低你的生产力。仔细衡量新基础设施的效率。你还需要用一个新的基础设施取代一个旧的吗?

代码路径导致的失败,很少在测试或执行中出现。但往往这就是bug的原因。

输入验证不仅仅是出于安全原因的,它能帮助你尽早发现bug。

和上一条有一些关系:有些相关状态验证和输出验证可以作为输入验证同样有用,无论是为了发现内在的bug,还是为了安全性。

代码评审(code review)是一个用来提高程序员的好方法。你会得到关于你代码的批评,同时你将学会描述为什么其他人的代码的好坏。它还引导你发现常见的错误。

学习一门新编程语言是一种很好的方式,以了解新的范式和旧的习惯问题。

总是指定编码转换文本与字节;当读/写网络、文件或加密时。如果你依赖于语言环境的字符集最终你一定会遇到数据损坏。如果你可以自己选择,请使用UTF字符。

了解你的工具,包括编辑器、终端、版本控制系统(如git)和编译工具。

学会在使用你的开发工具时不用鼠标。学习尽可能多的键盘快捷键。它会让你更高效而且这更符合人体工学。

重用代码不是一个最终的目标,也不会使你的代码更易于维护。重用复杂的代码,但请注意,两个域之间的代码重用可能使它们产生过度的依赖。

长时间坐在电脑会伤害你的身体。 1 ) 了解你的身体状况。看看你的背、脖子和手腕。当你身体感到不适的时候休息一会。养成一个暂停的习惯(泡茶,拿咖啡)对你的身心会有意想不到的益处。 2 ) 时不时的远离屏幕来休息一下你的眼睛。 3 ) 选一个适合你手腕的好的键盘。

自动化测试,特别是单元测试,不仅仅是测试您的代码。它们还: 1 ) 告诉大家代码的使用范围; 2 ) 还能帮助你提前的适应生产环境。后者是为什么一些人声称测试优先的开发方法可以产生干净的API。

适度的测试。因为缺少测试会导致bug,而查找bug会降低你的开发速度。过度的测试也会降低你的速度,因为每个改变都需要更新太多的测试。

和编译语言相比,动态语言通常需要更多的测试工作来保证它的正常工作。(离线代码分析工具也很有用。)

竞态比普遍认为的更常见。这是因为计算机通常比我们习惯于TPS。

理解吞吐量和延迟之间的关系在优化您的系统时非常有用。相关;

很多时候高吞吐量可以通过引入智能匹配的方式来完成。

保持你提交的代码简短、可用,提交代码的时候写下你做了什么的日志,告诉大家你为什么做这些。有效的提交信息是解决bug的先决条件。

保持你的本地分支尽可能的新。我的经验是:失败发生的风险和你本地版本保持的时间成正比。不要在一个分支上工作超过两周时间。那些比较大的特性,我们可以将它分为多个小的特性并分多次提交它。

尽早的了解你的产品运行环境,并根据环境对部署策略进行调整。

令人惊讶的是,频繁的发布代码会降低风险,而不是增加。

学习面向对象的语言是很容易的。掌握良好的面向对象设计是困难的。了解面向对象设计和面向对象的设计模式将改善你的面相对象设计的理解。

好的架构师很可能会写出很糟糕的代码。然而,一个优秀的架构师知道如果保证系统是解耦的,可更替的。首先要保证这是一个理智的分离的架构。其余的问题可以在时间不紧的时候进行清理。

巴士系数也是你团队中的一个严重风险。(一个项目至少失去若干关键成员的参与(被巴士撞了,比喻)即导致项目陷入混乱、瘫痪而无法存续时,这些成员的数量即为巴士系数。)作为团队的一员,大多数你写的代码需要被别人读或者修改。这包括你早些时期在项目中写的代码。在一开始你就应该写好文档和提交信息。此外,代码评审和脚本也可以帮助你分享一些知识。最后,确定你不是唯一一个知道密码的人。等等

 

Jeff Darcy 的观点,4.6k 顶

了解概念

通过记忆和模式识别来解决问题要比单纯的寻找问题的原因快的多。如果你曾经解决了一个类似的问题,那么你很可能直观的想起解决方案。就算做不到这一点,至少过去保留的经历会让你更容易的找到解决问题的灵感。“自动化”的解决一个问题看起来很像魔术,但是这就是 Miguel Paraz 建议的“练习 练习 再练习”的真实效果。

了解你的工具

这是一个在编程时维持而不是终止连续性的方法。每当你不得不考虑如何去学习编辑器、版本控制系统、调试器,这将打断你的深度思考。这些“小插曲”虽 小,但是它们加起来就不小了。比起什么也不做,那些愿意花时间学习工具、练习使用工具、用自动化工具的人的生产力会得到几倍的提高。

做好时间管理

使自己再次进入工作状态。你想写代码,写代码。你想回顾一些修改补丁,回顾一些修改补丁。如果想头脑风暴新的算法……你懂得,不要试图将这些事情一 起做完,一定不要让自己被电子邮件、IRC、Twitter和Quora打断。让你的大脑专注于一件事,在做完这件事情之后再转向做其他的事情。

安排好处理事情的顺序

我发现这方面很多人做的很失败。每一个问题都可以从不同的方面来对待。通常,解决一个问题的一方面会比其他方面容易很多。因此,正确的顺序尤为重要。恐怕没人能说出如何排序的标准答案,但是当你在当前领域经验越来越丰富的时候,再去实践,你的经验会给你很多启发。

重用所有你能重用的

重用的想法。重用代码。每次你把一个新问题变成一个你已经知道如何解决问题,计算充满这样的机会——你可以节省时间。不要担心如果转换后的解决方案并不是绝对完美的当前问题。你可以完善之后,如果你真的需要,通常你会发现,你最好继续下一个问题。

这些事情真的会降低你的效率。随着你每天遇到更多的问题,你将获得更多的经验,这会让你能更快的解决更多的问题,这样一直下去。这是一个循环,一旦你能够正确的对待这些事情时,你的效率和价值将会得到大幅度的提升。