每个 CS 系学生都应该知道的事

英文:Matt

译文:伯乐在线 – 阿喵

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

点击 → 了解如何加入专栏作者

考虑到计算机科学领域的膨胀增长,想要辨识现代计算机科学到底包含什么,成了一件有挑战性的事。我们系进行了这个讨论, 所以我整合一下自己的想法来当作这个问题的解答,“每个 CS 系的学生应当知道哪些事?”

我尝试从 4  方面来回答这个问题:

  • 学生想要获得好的工作应当知道哪些事?
  • 学生想要得到终生雇佣应当知道那些事?
  • 学生想要进入研究生院应当知道哪些事?
  • 学生想要有益于社会应当知道那些事?

下面我会把自己的想法分为现代计算机领域的一般性的原则和一些特别推荐两部分来写。

计算机系的学生:把本文当作自学指南随意使用。

作品集 portfolio ,而不是简历

自从计算机科学从工程学和数学分离出来之后,计算机程序行业就开始依靠简历来雇佣毕业生。

一份简历无法说明程序员的能力。

每一个计算机系的的学生都应当有其作品集。

一个作品集可以简单到是一个个人博客,上面有工程或实现的帖子。更好些的话每个工程的有其单独页面和可供公共浏览的代码(也许托管到 Github 或者 Google Code 上)。

对开源代码的贡献应当给出链接和说明。

一个代码作品集能够使雇主直接评价雇员的能力。

而 GPA 和简历却做不到。

教授应该设计课题来使作品集更出彩,学生在课程结束时应该花些时间更新这些课程项目。

示例

  • Edward Yang’s web site.(http://ezyang.com/)
  • Michael Bradshaw’s web site. (http://www.mjbshaw.com/)
  • Github is my resume. (http://pydanny.blogspot.com/2011/08/github-is-my-resume.html)

技术交流

在计算机科学界“独狼”已然成为濒危物种。

当代计算机科学家必须练习与非程序员清晰且有说服力地交流自己的想法。

在小公司,程序员能否和管理层交流她的想法能够影响到公司的成败。

不幸的是,单独增加一个课程并不能有什么改变(当然一个合理的科技交流课程没有坏处)。

应当提供给学生更多的机会来给予他们通过口头讲演的方式展示自己工作和想法。

特别推荐

我建议学生掌握一种演示工具,比如说 PowerPoint 或者(我最喜欢的)KeyNote。(抱歉,尽管我喜爱基于 LaTex 的演示工具,它们还是太静态了)。

不过,要是想生成漂亮的数学文档,LaTex 是无可比拟的。所有的科技课程的写作作业都应该以 LaTex 的形式提交。

建议阅读

  • Writing for Computer Science by Zobel.
  • Even a Geek Can Speak by Asher.
  • The LaTeX Companion.
  • The TeXbook by Knuth. (Warning: Experts only.)
  • Notes on Mathematical Writing.
  • Simon Peyton-Jones’s advice on How to Give a Good Research Talk.
  • My advice on how to send and reply to email.

一颗工程学的心

计算机科学不是完全的工程学。

但也差不多。

计算机科学家终会发现他们和工程师在一起工作。计算机科学家和传统的工程师需要说相同的语言——一种扎根于实分析、线性代数、概率论与物理学的语言。

计算机科学家理应掌握物理学中的电磁学,但要达到这一点,他们还需掌握多元微积分,(外加学习微分方程)。

在进行声音仿真时,精通概率论(通常还包括)线性代数是极有益处的。在说明计算结果时,对统计的牢固理解是无可替代的。

推荐阅读

  • Spivak 的 Calculus
  • Wasserman 的 All of Statistics: A Concise Course in Statistical Inference

Unix 哲学

计算机科学家应当习惯并且熟练使用 Unix 哲学的处理。

Unix 哲学(不同于 Unix 本身)是一种注重语言学抽象和整合来达到预期处理的方法。

在实践中,这意味着要习惯于命令行形式处理、文本文件进行配置和轻型IDE的软件开发。

特别推荐

考虑到 Unix 系统的流行度,当今的计算机科学家应当熟练地掌握基本的 Unix 能力:

  • 浏览和操作文件系统
  • 使用管道进行组合操作
  • 习惯于使用 emacs 和 vim 编辑文件
  • 新建、修改和运行一个软件项目的 Makefile 文件
  • 编写简单的 shell 脚本 学生在不理解 Unix 哲学强大能力时会抵制它。此时最好让学生尝试完成一些 Unix 有相对优势的有用的任务,比如:
  • 找到指定目录下占用空间最大的5个文件夹
  • 找到计算机中重复的 MP3 文件(相同的文件内容而不是文件名)
  • 找到名字列表中姓名首字母是小写的名字,并调整大小写
  • 找到第二个字母是 x,倒数第二个是 n 的英语单词
  • 把你的手机的声音输入经由网络传送到另一台电脑的音响播放
  • 把指定文件夹下的文件名中的空格替换为下划线
  • 报告指定 IP 地址接入 web 服务器的最近十个错误连接

建议阅读

  • The Unix Programming Environment by Kernighan and Pike.
  • The Linux Programming Interface: A Linux and UNIX System Programming Handbook by Kerrisk.
  • Unix Power Tools by Powers, Peek, O’Reilly and Loukides.
  • commandlinefu.
  • Linux Server Hacks.
  • The single Unix specification.

系统管理

一些计算机科学家嘲笑系统管理是一件“IT”任务。

他们的想法是可以自学技术人员能做得到的所有事。

这是正确的(嗯,理论上是)。

然而计算机科学家能够完全且安全地控制他们的系统和网络的态度是有些误导人的。

软件开发中很多任务不传给系统管理员来做是最高效的。

特别推荐

每个当代的计算机科学家应当能够:

  • 安装和管理一个 Linux 发行版
  • 配置和编译 Linux 内核
  • 使用 dig、ping 和 traceroute 命令来排解故障
  • 编译和配置 web 服务器,比如 apache
  • 编译和配置 DNS 守护进程,比如 bind
  • 使用文本编辑器维护一个站点
  • 自己制作水晶头

建议阅读

  • UNIX and Linux System Administration Handbook by Nemeth, Synder, Hein and Whaley.

编程语言

编程语言有周期的兴起与衰落。

而一个程序员的职业不应如此。

尽管教授与获得工作相关的语言很重要,学生能够自学新的编程语言也同等重要。

学习怎样学习新的编程语言的最好方式是学习多种编程语言和编程范式。

学习第n个语言的难度是第(n – 1)个的一半。

然而,要想真正理解编程语言,应该自己实现一个。理想情况下,每个计算机科学系的学生都参加过编译的课程。至少,每个学生应该实现一个解释器。

一些语言

下面的编程语言涵盖了编程范式和实际应用:

  • Racket
  • C
  • Javascript
  • Squeak
  • Java
  • Standard ML
  • Prolog
  • Scala
  • Haskell
  • C++ 和
  • 汇编

Racket

Racket,作为功能全面的 Lisp 的方言,有着极简单的语法。

对少部分的学生来说,这种语法是一种学习障碍。

不过坦率地讲,如若一个学生觉得即使是暂时接受一种相异的语法规则也是很大的脑力障碍的话,他缺乏从事计算机科学职业的灵巧心智。

Racket 丰富的宏系统和高阶编程组件彻底打破了数据和代码的分别。

如果教的合理,能够充分发挥 Lisp 的能力。

建议阅读

  • How to Design Programs by Felleisen, Findler, Flatt and Krishnamurthi.
  • The Racket Docs.

ANSI C

C 是对底层(硅)的简洁至极的抽象。

C 在嵌入式系统的编程中无可替代。

学习 C 能提供对冯·诺依曼体系的深入理解,其程度没有其他语言能匹拟。

考虑到差的 C 编码与普遍的缓冲区溢出安全隐患有着亲密的关系,程序员学习正确地编写 C 程序是很重要的。

建议阅读

  • ANSI C by Kernighan and Ritchie.

Javascript

Javascript是动态、高级语言比如 Python、Ruby 和 Perl 的语义模型的很好的一个代表。

作为 web 原生语言,它的实用性优势是独一无二的。

建议阅读

  • JavaScript: The Definitive Guide by Flanagan.
  • JavaScript: The Good Parts by Crockford.
  • Effective JavaScript: 68 Specific Ways to Harness the Power of JavaScript by Herman.

Squeak

Squeak 是最纯正的面向对象语言 Smalltalk 的现代方言,它展现了“面向对象”的本质。

建议阅读

  • Introductions to Squeak

Java

Java 将保持流行久到无法将其忽略。

建议阅读

  • Effective Java by Bloch.

Standard ML

Standard ML 是 Hindley-Milner 系统的一个干净实现。

Hindley-Milner 类型系统是现代计算计算机领域最伟大(然而却是最不知名)的成就。

尽管有着指数级的复杂性,Hindley-Milner 的类型推断对于正常的程序来说是足够快的。

类型系统支持复杂的结构化不变量表达,事实上,它丰富到类型定义良好的程序经常是没有 bug 的。

建议阅读

  • ML for the Working Programmer by Paulson.
  • The Definition of Standard ML by Milner, Harper, MacQueen and Tofte.

Prolog

尽管在应用上占有一席之地,逻辑编程是计算思维的另一种范式。

在程序员需要在其他编程范式里模拟逻辑编程时,理解逻辑编程是值得的。

另一种值得学习的逻辑编程语言是miniKanren。miniKanren强调纯粹的逻辑编程。这个约束逐步形成了另一种风格的逻辑编程称为关系程序设计,并且它授予通常Prolog程序不支持的属性。

建议阅读

  • Prolog Tutorial.
  • Another tutorial.

Scala

Scala 是定义良好的函数式与面向对象的融合语言。

Scala 是 Java 应该做到的样子。

建立于 Java 虚拟机之上,并兼容现存的 Java 代码库,Scala 最有可能成为 Java 的后继者。

建议阅读

  • Programming in Scala by Odersky, Spoon and Venners.
  • Programming Scalaby Wampler and Payne.

Haskell

Haskell 是 Hindley-Milner 语言家族的王冠。

充分利用惰性求值,Haskell 是主流编程语言中最接近于纯数学的。

建议阅读

  • Learn You a Haskell by Lipovaca.
  • Real World Haskell by O’Sullivan, Goerzen and Stewart.

标准 C++

C++ 是无法避免的灾祸。

但是既然必须要教 C++,那就教全。

特别地,计算机科学系的学生毕业时应该掌握模板元编程.

建议阅读

  • The C++ Programming Language by Stroustrup.
  • C++ Templates: The Complete Guide by Vandevoorde and Josuttis.
  • Programming Pearls by Bentley.

汇编

任何汇编语言都行。

既然 x86 很流行,最好学它。

学习编译器的最好方式便是学习汇编,因为汇编直观地展示了将高级代码转化为低级代码。

特别推荐

计算机科学家应该理解产生式编程(宏编程);词法(动态)范围;闭包;continuation;高阶函数;动态调度;子类型;模块和函子还有不同于其他特定语法的 monads 语义概念。

建议阅读

  • Structure and Interpretation of Computer Programs by Abelson, Sussman and Sussman.
  • Lisp in Small Pieces by Queinnec.

离散数学

计算机科学家必须要对形式逻辑及其证明有牢固的理解。代数操作和自然推理证明是处理例程任务的有力方法,归纳总结证明在构建递归函数时很有用处。

计算机科学家必须对形式数学记号很熟悉,并且对基本的离散数学结构–集合、元组、队列、方法和幂集能进行的严格推理。

建议阅读

对于计算机科学家,掌握这些理论很重要:

  • 树;
  • 图;
  • 形式语言;和
  • 自动机 学生应该学习足够多的数论知识来研究和实现基本的加密协议。

建议阅读

  • How to Prove It: A Structured Approach by Velleman.
  • How To Solve It by Polya.

数据结构和算法

学生应该必须见过常见(或者罕见但异常有效的)数据结构和算法。但是,比起知道特定算法和数据结构(这些经常是很容易查阅到的),计算机科学家应该理解知道如何去设计算法(比如贪心、动态规划策略等)并且知道如何将理想中的算法真正实现。

特别推荐

对于想获得长期雇佣关系的计算机科学家来说至少要知道这些:

  • 哈希表;
  • 链表;
  • 数;
  • 二分查找树;和
  • 有向、无向图 计算机科学家应该可以实现或者扩展操作这些数据结构的算法,包括增删改查特定元素。考虑到完备性,计算机科学家应该知道每个算法的指令式和函数式实现。

建议阅读

  • CLRS.
  • Any of the Art of Computer Programming series by Knuth.

理论

理解理论是在研究生院进行研究的先决条件。当能提供了一个问题的hard boundaries(或者是提供转化为最初是hard boundaries的方法) 时理论是无价的。

计算复杂度可以说是所有计算机“科学”的真正的预测理论之一。

计算机科学家必须 知道易处理性和可计算性的程度,如果忽略了这些限制,最好的情况是有些挫折,最差的情况是导致失败。

特别推荐

在本科阶段,理论至少应涵盖计算模型和计算复杂度。

计算模型应该包括有限状态自动机、正则语言(和正则表达式)、下推自动机、上下文无关语言、形式文法、图灵机、lambda 演算和不可判定性。

在本科阶段,学生至少要学习足够复杂的知识来理解 P、NP、NP-Hard 和 NP-Complete 的区别。

为了防止留下错误的印象,学生应该通过将一些 NP 的问题规约到 SAT(Boolean satisfiability problem,布尔可满足性问题)并使用 SAT 求解程序求解。

建议阅读

  • Introduction to the Theory of Computation by Sipser.
  • Computational Complexity by Papadimitriou.
  • Algorithms by Sedgewick and Wayne.
  • Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein.

架构

对软件架构有见识的理解是无可替代的。

计算机科学家应该从晶体管起理解一个计算机。

架构的理解包含一些标准的抽象:晶体管、逻辑门、加法器、多路复用器、触发器、算术逻辑单元、控制单元、缓存和随机存取存储器。

对高性能计算 GPU 模型的理解在可预知的未来是很重要的。

特别推荐

要想在现代系统上达到高性能对缓存、总线和物理内存管理的理解是很重要的。

要想理解机器架构,学生应该设计和仿真一个小的 CPU。

建议阅读

  • nand2tetris, which constructs a computer from the ground up.
  • Computer Organization and Design by Patterson and Hennessy.
  • “What every programmer should know about memory” by Drepper.

操作系统

任何足够大的程序最终都将成为一个操作系统。

正因如此,计算机科学家应该知道内核是如何处理系统调用、分页、调度、上下文切换、文件系统和内部资源管理的。

对操作系统的理解仅次于对编译器和实现高性能的架构的理解。

理解操作系统(我想当然也包括运行时的系统)在对嵌入式系统进行编程是非常重要。

特别推荐

学生必须在一个真正的操作系统上动手实践,在 Linux 和虚拟化技术的帮助下,这比之前容易些。想要对内核有很好的理解,学生应该:

在启动过程中输出 “hello world”;

设计他们自己的调度器;

修改分页策略;

创建他们自己的文件系统

建议阅读

  • Linux Kernel Development by Love.

网络

考虑到网络的普遍性,计算机科学家应该对网络栈和网络中的路由协议有坚实的理解。

对计算机科学家来说,在不可靠传输协议(比如 IP)的基础上构建可靠的传输协议(比如 TCP)的机制不应是不可思议的而应是核心知识。

他们应该理解在协议设计中的权衡—比如,什么时候选择 TCP,什么时候选择 UDP。(程序员需要知道在大型网络中有阻塞,他们也应更大规模地使用 UDP。)

特别推荐

考虑到当代程序员进行网络编程的频繁性,理解现存协议标准是有用的:

  • 802.3 和802.11;
  • IPv4 和 IPv6;
  • DNS, SMTP 和HTTP. 计算机科学家应该理解包冲突时的指数回退和在拥塞控制中的加法增大和乘法减少机制。每个计算机科学家应该实现:
  • 一个 HTTP 的客户端和守护进程;
  • 一个 DNS 解析器和服务器;以及
  • 一个命令行的 SMTP 的邮件程序 要想通过网络介绍课程,每个学生都应该使用wireshark来嗅探他们导师的谷歌搜索。

也许要求每个学生基于 IP 来从头实现一个可靠的传输协议是有些强人所难了,但可以说这是我学生时代的一个对我个人改变很大的经历。

建议阅读

  • Unix Network Programming by Stevens, Fenner and Rudoff.

安全

一个悲伤的事实是大多数安全漏洞都来源于粗心的编码,更悲哀的事实是很多学校在训练程序员编写安全代码上做的很差。

计算机科学家必须知道程序被攻破的方式。

他们需要形成防御型编码的意识——考虑他们自己的代码可能被攻击的方式。

安全最好在整个课程体系中分布开来进行训练:每个学科都应该提醒学生关于这个学科的原生漏洞。

特别推荐

每个计算机科学家至少应该了解:

  • 社会工程;
  • 缓冲区溢出;
  • 整数溢出;
  • 代码注入漏洞;
  • 竞态条件;
  • 权限混淆 一些读者指出计算机科学家也应知道基本的 IT 安全措施,比如选择合理的好密码和使用 iptables 配置防火墙。

建议阅读

  • Metasploit: The Penetration Tester’s Guide by Kennedy, O’Gorman, Kearns and Aharoni.
  • Security Engineering by Anderson.

密码学

密码学使得我们的大部分数字生活成为现实, 计算机科学家应该理解并能够实现下面的概念,并且知道实现这些的常见陷阱:

  • 对称密码系统;
  • 公钥密码系统;
  • 安全哈希函数;
  • 询问-响应认证;
  • 数字签名算法;
  • 门限密码系统 在实现这些密码系统时有个常见的错误——为手头工作获得 足够 随机的数,而这是每个计算机科学家应该知道的。
  • 最后,如此多的数据泄露表明,计算机科学家应该知道如何在存储密码时进行加盐和哈希处理。

特别推荐

每个计算机科学家应该有使用手工统计工具来破解使用前现代加密系统的密文的乐趣。

RSA 是容易实现的 ,每个人都应试试。

每个学生都应创建他们自己的数字签名并在 apache 上建立 https 连接(做这个是出乎意料的费劲)。

学生还应该写一个使用 SSL 进行连接的 web 客户端。

作为实践,计算机科学家应该知道如何使用 GPG、ssh 的公钥认证、加密一个文件夹或者硬盘。

建议阅读

  • Cryptography Engineering by Ferguson, Schneier and Kohno.

软件测试

软件测试必须贯穿整个课程体系。一个软件工程的课程可以涵盖基本的测试风格,但是只有练习才能掌握这项艺术。

应该根据学生上交的测试用例来给他们打分。

我使用学生上交来的测试用例来对其他学生进行测试。

学生看起来并不很在意防御性的测试用例,但是当向同学下手时却很是不客气。

用户体验设计

程序员大多是给其他程序员写程序,或者更糟糕,给他们自己写。

用户接口设计(更宽泛的讲,用户体验设计)可能是计算机科学最不受重视的方面。

即使是在专家之间也有这种误解,即用户体验是一种无法被教授的“软”技能。

在现实中,现代用户体验设计根植于人因工程学和工业设计中的人工经验。

如果没有别的办法,计算机科学家至少应知道接口执行任何任务的难易程度应该与任务的频率与重要性的乘积成比例。

为实用性考虑,每个程序员应该习惯于使用 HTML、CSS 和 Javascript 等设计可用的 web 接口。

建议阅读

  • Paul Graham’s essay on Web 2.0.
  • “The Absolute Minimum Every Software Developer Absolutely, Positively Must Know About Unicode and Character Sets” by Spolsky.
  • HTML and CSS: Design and Build Websites by Duckett.
  • JavaScript: The Definitive Guide by Flanagan.

可视化

好的可视化是可以将数据表现为人类可以感知的信息,而做到这点并不容易。

现代世界是数据的海洋,而开发人眼感知的局部最大值是理解这些信息的关键。

建议阅读

  • The Visual Display of Quantitative Information by Tufte.

并行化

如今并行化比以往更落后、更丑陋。

不幸的是要掌握并行化需要对架构:多核、缓存、总线、GPU 等等有很深的理解。

并且需要练习,大量练习。

特别推荐

并行化的“终极”答案还不得而知,但是一些领域特定的解决方案已经给出。

当下学生应该学习 CUDA 和 OpenCL。

线程是脆弱的并行化抽象,特别是引入缓存和缓存一致性之后。但是,线程很流行且微妙,所以值得学习,Pthread 是一个合理的轻量库。

对于对大规模并行化感兴趣的人来说,MPI是首要条件。

在理论上,map-reduce 是经久不衰的。

软件工程

软件工程的原理改变地和编程语言一样快。

一个好的动手实践的团队软件开发练习能够展现出软件工程固有误区并提供关于这些误区的工作知识。 一些读者建议说学生应该分为三人一组并且在不同的项目中轮流当作组长。

学习如何与现存大代码库打交道是每个程序员的必备技能,并且最好是在学校而不是在工作中掌握此项技能。

特别推荐

所有的学生都应知道集中版本控制系统如 svn 和分布式版本控制系统如 git。

对于调试工具如 gdb 和 valgrind 的使用很长时间后会有裨益。

建议阅读

  • Version Control by Example by Sink.

形式化方法

随着对安全可靠软件的需求提高,形式化方法也许将是开发这种软件的唯一方法。

当前软件的形式化模型和证明还很有挑战性,但是这项领域的进程是稳健的:一年比一年容易。

也许在当前的计算机系学生的有生之年,形式化软件开发能成为一种预期技能。

每个计算机科学家应至少熟练使用一种定理证明器(我认为具体是哪一种并不重要)。

学习使用定理证明方法能够立刻影响代码风格。

比如说,一个人本能的不愿写无法覆盖所有可能性的 match 和 switch 语句,。

再比如当写递归函数时,使用理论证明方法的人有很强的欲望去消除 ill-foundedness。

建议阅读

  • Software Foundations.

图形仿真

没有学科比图更能体现“聪明”。

这个领域是由“足够好”驱动甚至由之定义的。

因此,没有比图形仿真更好的方式来教授巧妙的编程和进行性能优化。

我所学到的半数编码技巧都来自于对图的学习。

特别推荐

简单的光线追踪器可以在百行代码内实现。

实现从 3D wireframe engine 获取 3D 投影是费些脑力的。

类似于 BSP 的数据结构以及类似于 z-buffer 渲染的算法是巧妙的设计的例子。

在图形仿真领域,还有很多其他实例。

建议阅读

  • Mathematics for 3D Game Programming and Computer Graphics by Lengyel.

机器人

机器人是教授编程入门的最具吸引力的方式之一。

并且随着机器人的价格持续走低,哪一款将引发个人机器人浪潮成为了门槛。

对于会编程的人来说,个人机器自动化的伟大时代即将来临。

相关推荐

  • Multitouch gesture control for a robot.

人工智能

仅是考虑到对早期计算历史的特大影响,计算机科学家也应学习人工智能。

即使人工智能的最初梦想还远未实现,人工智能在一些领域已有成效,比如机器学习、数据挖掘和自然语言处理等。

建议阅读

Artificial Intelligence by Russell and Norvig.

机器学习

除去出色的技术技术优点,对“relevance engineer”工作岗位的需求增大表示出每个计算机科学家都应该了解一下基本的机器学习。

机器学习也更加强调了理解概率论和统计的重要性。

推荐阅读

Machine Learning by Mitchell.

数据库

数据库十分常见和有用以至于人们常常忽略它。

理解支撑数据库引擎的数据结构与算法是有用的,因为程序员经常需要在一个大的软件系统中实现一个数据库系统。

在sub-Turing 的计算模型的极大成功背后关系代数和关系计算起了极大的作用。

比起 UML 模型,ER 模型更适于可视化编码设计和约束的软件设计。

建议阅读

  • SQL and Relational Theory by Date.

非特定的阅读推荐

  • Gödel, Escher, Bach by Hofstadter.
  • Nick Black’s advice for MS students.

还有什么?

由于我自己也是知识盲点的,所以上面这些建议也是有局限的。

如果还有哪些应当包含但没有列出的东西,请大家在评论中补充。

数据处理的 9 大编程语言

英文:Anna Nicolauo

译者:伯乐在线 – 胡波

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

有关大数据的话题一直很火热。伴随着信息的爆炸式增长,大数据渗透到了各行各业,广泛应用于公司中,同时也使得传统的软件比如 Excel 看起来很笨拙。数据分析不再只是书呆子的事,同时其对高复杂性分析、实时处理的需求也比以往更加庞大。

那么筛选海量数据集最优的工具是什么呢?我们咨询了一些数据黑客关于他们在数据分析的核心工作中最喜欢的编程语言和工具包。

R 语言

这份名单如果不以 R 开头,那就是彻头彻尾的疏忽。自 1997 年起,作为一门免费的,可替代 Matlab 或 SAS 等昂贵统计软件的语言,R 被抛弃。

但是在过去的几年中,它却成了数据科学的宠儿—甚至成了统计学家、 华尔街交易员、生物学家和硅谷开发者必不可少的工具。 随着其商业价值的不断增长和传播,诸如谷歌、Facebook、 美国银行和纽约时代周刊都在使用。

R 简单易用。通过 R ,短短几行代码就可以筛选复杂的数据集,通过成熟的模型函数处理数据,制作精美的图表进行数据可视化。简直就是 Excel 的加强灵活版。

R 最大的价值就是围绕其开发的活跃的生态圈: R 社区在持续不断地向现存丰富的函数集增添新的包和特性。据估计 R 的使用者已经超过 200 万人,最近的一项调查也显示 R目前是数据科学领域最受欢迎的语言,大约 61% 的受访者使用 R(第二名是 Python, 占比39%)。

在华尔街,R 的使用比例也在不断增长。美国银行副总裁Niall O’Connor 说:“以往,分析员通常是熬夜研究 Excel 文件,但是现在 R 正被逐渐地应用于金融建模,尤其是作为可视化工具。R 促使了表格化分析的出局。”

作为一门数据建模语言, R 正在走向成熟,尽管在公司需要大规模产品的时候 R 能力有限,也有些人说它已经被其他语言替代了。

Metamarkets 公司的 CEO Michael Driscoll 说:“ R 擅长的是勾画,而不是搭建,在 Google 的 page rank 算法和 Facebook 的好友推荐算法实现的核心中是不会有 R 的。工程师会用 R 进行原型设计,再用 Java 或者 Python将其实现。”

Paul Butler 在 2010 年用 R 构建了一个著名的 Facebook 世界地图,证明了 R 在数据可视化上的强大能力。然而他并不经常使用 R。

Butler 说:“由于在处理较大数据集时缓慢且笨拙,R 在行业中已经有些沦为明日黄花了 ”

那么使用什么作为它的替代呢?看下去。

Python

如果 R 是个有点神经质的可爱的极客,那么 Python 就是它容易相处的欢快的表弟。融合了 R 快速成熟的数据挖掘能力以及更实际的产品构建能力, Python 正迅速地获得主流的呼声。 Python 更直观,且比 R 更易学,近几年其整体的生态系统发展也成长得很快,使其在统计分析上的能力超越了之前的 R 语言。

Butler 说:“Python 是行业人员正在转换发展的方向。过去两年里,很明显存在由 R 向 Python 转化的趋势”

在数据处理中,通常存在规模和技巧的权衡,Python 作为一个折中出现了。 IPython notebook 和NumPy 可以用于轻量工作的处理, 而 Python 则是中级规模数据处理的有力工具。丰富的数据交流社区也是 Python 的优势,它提供了大量的Python 工具包和特性。

美国银行利用 Python 开发新产品以及基础设施接口,同时也用于处理金融数据。O’Donnell 说:“Python 用途宽广且灵活,所以人们蜂拥而至”。

然而, Driscoll 也提到它并不是高性能的语言,偶尔才会用于装配驱动大规模的核心基础设施。

JULIA

最主流的数据科学处理语言包括 R、 Python、 Java、 Matlab和 SAS。但是这些语言仍然存在一些不足之处,而Julia 正是待以观察的新人。

对大规模商用来说, Julia 还是太晦涩了。但在谈到其取代 R 和 Python 领先地位的潜力的时候,数据极客们都会变得很激动。 Julia 是一门高级的,非常快的函数式语言。速度上比 R 快, 可能比 Python 的扩展性更高,且相对易学。

Butler 说:“Julia 正在快速上升。最终将可以用 Julia 完成任何 R 和 Python 可以完成的事”。

如今的问题是 Julia 太“年轻”了。 其数据交流社区仍处在早期发展阶段,在没有足够的包和工具之前是不足以与 R 和 Python 竞争的。

Driscoll 说:“Julia 很年轻,但正在积攒力量而且未来很可观”。

JAVA

在硅谷最大的科技公司里,Java 和基于 Java 的框架构成了其底层的技术骨架。Driscoll 说:“如果深入观察Twitter,Linkedin 或者 Facebook,你会发现 Java 是他们公司数据引擎架构的基础语言”。

Java 并没有 R 和 Python 那样的数据可视化的能力, 同时也不是最好的用于统计模型的语言。但是如果需要进行原型的基础开发和构建大规模系统, Java 往往是最好的选择。

HADOOP 和 HIVE

为了满足数据处理的巨大需求,基于 Java 的工具群涌而现。 作为基于 Java 的框架,Hadoop 在批处理领域成为热点。Hadoop 比其他处理工具速度要慢,但是它非常精确且被广泛的应用于后台分析,它很好的融合了 Hive, 一个运行在 Hadoop 上的基于查询的框架。

SCALA

Scala 是另一个基于 Java的语言,和 Java 很相似,它正在逐渐成长为大规模机器学习或高级算法的工具。它是函数式语言,也能够构建健壮的系统。

Driscoll 说:“Java 就像是直接用钢筋进行搭建, Scala 则像是在处理黏土原材料,可以将其放进窖中烧制成钢筋”。

KAFKA 和 STORM

当需要快速、实时分析时怎么办?Kafka 可以帮助你。它已经发展了大概五年时间,但最近才成为一个流处理的流行框架。

Kafka 诞生于 Linkedin 公司的内部项目,是一个快速查询系统。至于 Kafka 的缺点呢? 它太快了,实时的操作也导致了自身的错误,且偶尔还会遗失信息。

Driscoll 说:“在精度和速度之间总需要做权衡,所以硅谷所有的大公司一般都双管齐下: 用 kafka 和 Storm 进行实时处理,用 Hadoop 做批处理系统,虽然会慢一点但却十分精确”。

Storm 是另一个用 Scala 写的框架,且它在硅谷以擅长流处理而受到极大的关注。毫无疑问, Twitter, 一个对快速消息处理有着巨大兴趣的公司会收购了 Storm。

荣幸的提到:

MATLAB

MATLAB 已经存在很长时间了,尽管价格昂贵,但它仍在某些特定领域被广泛使用: 机器学习研究、信号处理、图像识别等领域。

OCTAVE

Octave 与 Matlab 非常相似,只不过它是免费的。然而除了信号处理的学术圈之外很少见到使用。

GO

GO 是另外一个获得关注的新手。它由 Google 开发,与 C 有一定渊源,且在构建稳定系统方面与 Java 和 Python 展开了竞争。

Java性能优化全攻略

来自:慧都控件网

链接:https://www.evget.com/article/2016/5/17/24105.html

原文:http://www.oracle.com/technetwork/java/javaseproducts/mission-control/java-mission-control-wp-2008279.pdf

让Java应用程序运行是一回事,但让他们跑得快就是另外一回事了。在面对对象的环境中,性能问题就像来势凶猛的野兽。但JVM的复杂性将性能调整的复杂程度增加了一个级别。这里Refcard涵盖了JVM internals、class loading(Java8中更新以映射最新的元空间)、垃圾回收、故障诊断、检测、并发性,等等。

介绍

Java是目前软件开发领域中使用最广泛的编程语言之一。Java应用程序在许多垂直领域(银行、电信、医疗保健等)中都有广泛使用。Refcard的目的是,帮助开发者通过专注于JVM内部,性能调整原则和最佳实践,以及利用现有监测和故障诊断工具,来提升应用程序在商业环境中的性能。

它能以不同的方式定义“optimal performance(最佳性能)”,但基本要素是:Java程序在业务响应时间要求内执行计算任务的能力,程序在高容量下执行业务功能的能力,并具有可靠性高和延迟低的特点。有时,数字本身变得模式化:对于一些大型网站,优秀的页面响应时间应该在500ms以下。在适当的时候,Refcard包括目标数字。但在大多数情况下,您需要根据业务需求和现有的性能基准自己决定这些。

JVM Internals

基础知识

代码编译和JIT

编译Java字节码显然没有直接从主机执行本机代码那么快。为了提高性能,Hotspot JVM找出最繁忙的字节码区域,然后将其编译成更高效地原生、机器代码(自适应优化)。然后这种本地代码就会存储在非堆内存中的代码缓存中。

注意:多数的JVM是通过禁用JIT编译器实现的(Djava.compiler=NONE)。您只需要考虑禁用的关键性优化,比如JVM崩溃。

下图说明了Java源代码,即时编译流程和生命周期。

内存空间

HotSpot Java Virtual Machine是由以下的存储空间组成。

类加载

Java的另一个重要特点是,在JVM启动之后,它能够加载编译的Java类(字节码)。根据程序的大小,在刚刚重启之后,程序在类加载过程中性能会显著降低。这种现象是因为内部JIT编译器在重启之后需要重新开始优化。

自JDK 1.7版本之后,有一些改进值得大家重视。例如默认的JDK class loader具有更好的装在类并发能力。

热点


故障诊断和监视

垃圾回收

Java垃圾回收流程对于程序性能是至关重要的。为了提供有效的垃圾回收,Heap(堆)本质上是划分在子区域中。

堆区域


GC Collectors

选择正确的collector或GC policy可以将程序的性能、可扩展性和可靠性优化到最佳状态。许多应用程序对于响应时间延迟都很敏感,因此大多需要使用并发的回收器,例如HotSpot CMS或IBM GC policy balanced。

我们强烈建议您通过适当的性能和负载测试确定最合适的GC策略。应该在生产环境中执行全面监控策略,以跟踪整体的JVM性能,并确定在之后需要改进的领域。



Garbage First (G1) Collector

HotSpot G1 collector是专为是专为满足用户定义的垃圾回收(GC)高概率暂停时间设计的,同时实现高吞吐量。

最新的HotSpot collector将heap基本划分到一组大小相等的堆区域,虚拟内存的每个区域连续范围。它将回收压缩的活动集中在heap区域,那里充满了可回收的对象(garbage first)。换句话说就是,这个区域有最低限度的“live”对象。

Oracle建议在以下例子和情况下使用G1 collector,尤其是对于目前正在使用CMS或parallel collectors的:

  • 专为large heaps(>= 6 GB),并限制GC延迟(暂停时间<= 0.5秒)的应用程序设计。
  • 超过50%的Java heap被实时数据占用(对象不能被GC回收)。
  • 对象分析率和促进作用显著变化。
  • 不期望过长的垃圾回收或压缩停顿(超过0.5至1秒)。

Java Heap尺寸

你一定要知道没有GC策略可以挽救Java Heap尺寸不足的现象。这些演习涉及到为不同的存储空间(包括新旧不同的版本)配置最大和最小的容量,包括元数据和本地内存容量。这里有一些建议准则:

  • 在32-bit或64-bit JVM之间进行明智的选择。如果程序运行需要超过2GB内存,并且JVM暂停时间在可接受范围内,可以考虑使用64-bit JVM。
  • 永远将应用程序放在第一考虑。确保将其配置好,并根据程序的内存占用量调整heap尺寸。建议通过性能和负载测试来衡量实时数据占有量。
  • larger heap并不总是表现得更好、更快,因此不需要过度调整Java heap。并行中的JVM性能调优,找准机会减少或“spread”程序的内存占有量,以保证JVM的平均响应时间<1%。
  • 对于32-bit JVM,为了从元数据和本地heap中留出一些内存,考虑2GB的最大heap尺寸。
  • 对于64-bit JVM,我们要想办法在垂直和水平层面进行扩展,而不是试图将Java heap尺寸增加到15GB以上。这种做法往往提供更好的吞吐量,更好地利用硬件,提高应用程序的故障切换功能。
  • 不许重复开发:充分利用开源以及商业故障排除的优势和监控工具,使这些变成可能。APM(应用性能管理)产品在过去十年里发展迅猛。

JDK 1.8 Metaspace指南

Hot Spots

故障诊断和监视



Java并发性

Java并发性可以定义为程序同时执行多个任务的能力。对于大型的Java EE系统,这意味着执行多个用户的业务功能的同时,实现最佳的吞吐量和性能的能力。

无论是硬件能力还是JVM稳定状况,Java并发性问题可能引起程序的瘫痪,严重影响程序的整体性能和可用性。

Thread Lock Contention

当您评估Java应用程序的并发线程的稳定状况时,你会经常遇到Thread lock contention的问题,这是目前最常见的Java并发问题。

例如:Thread lock contention会触发non-stop,它会尝试将一个缺少Java类(ClassNotFoundException的)加载到默认的JDK 1.7 ClassLoader。

如果您在成熟的技术环境中遇见像Thread Dump analysis这样的问题,我们强烈建议您积极面对它。这个问题的根源通常不同于之前的Java synchronization to legitimate IO blocking或者其他的non-thread safe calls。Lock contention问题往往是另一个问题的“症状”。

Java-level Deadlocks

真正的Java-level deadlocks是不太常见的,它同样可以极大程度地影响应用程序的性能和稳定性。当遇到两个或多个线程永远阻塞的时候,就会触发这样的问题。这种情况不同于其他常见的那种“day-to-day”线程问题,例如 lock contention、threads waiting on blocking IO calls等等。真正的lock-ordering deadlock问题可以被看做如下:

Oracle HotSpot 和IBM JVM为大多数的deadlock detectors情况提供了解决方案,帮助您快速找出造成这种状况的罪魁祸首的线程。遇到类似lock contention troubleshooting的问题,建议从诸如线程转储分析为出发点来解决该问题。

一旦找到造成问题的代码根源,解决方案涉及lock-ordering条件寻址和来自JDK其他可用的并发编程技术,如java.util.concurrent.locks.ReentrantLock,提供了诸如tryLock()的方法。这种方法给予开发人员更大的灵活性,也为防止deadlock和thread lock “starvation”提供了更多方式。

Clock Time和CPU Burn

在进行JVM调优的同时,也有必要检查应用程序的行为,更确切地说是最高clock time和CPU burn的贡献者。

当Java垃圾回收和线程并发不再是压力点,深入到你的应用程序代码的执行模式,并专注于顶级响应时间贡献者(也叫作clock time)是很重要的。检查应用程序代码的消CPU耗和Java 线程(CPU burn)也同样至关重要。CPU使用率较高(>75%)是不正常的(良好的物理资源的利用率)。因为这往往意味着效率低下和容量问题。对于大型的Java EE企业应用,保持安全的CPU缓冲区是必要的,以应对突发的负载冲击情况。

摒弃那些传统的跟踪方法,如在代码中加入响应时间“日志”。Java剖析工具和APM解决方案恰恰可以帮助您分析这类型的问题。这种方式更加高效、可靠。对于Java生产环境缺乏一个强大的APM解决方案。您仍然可以依赖诸如Java VisualVM的工具,通过多个快照进行thread dump分析,并使用OS CPU分析每个线程。

最后的建议是,不要妄图同时解决所有的问题。列出排在最前面的5个clock time和CPU burn问题,然后寻找解决方案。

Application预算

其他关于Java应用程序性能的重要方面是稳定性和可靠性。在有着99.9%典型可用目标的SLA umbrella下,稳定和可靠对于程序的操作尤为重要。这些系统应该具有高容错级别,并对应用和资源进行严格的预算,以防止发生多米诺效应。用这种方法可以防止一些这样的情况,例如,一个业务流程使用所有可用的物理,中间件或JVM资源。

Hot Spots

超时管理

Java application与外部系统之间缺乏合理的超时时间,由于中间件和JVM线程消耗(blocking IO calls),可能导致严重的性能下降和中断。合理的超时时间可以避免在遇到外部服务提供商速度缓慢的时候,Java线程等待太久。

工具



Java 远程通讯技术及原理分析

来源:伯乐在线专栏作者-陶邦仁

在分布式服务框架中,一个最基础的问题就是远程服务是怎么通讯的,在Java领域中有很多可实现远程通讯的技术,例如:RMI、MINA、ESB、Burlap、Hessian、SOAP、EJB和JMS等,这些名词之间到底是些什么关系呢,它们背后到底是基于什么原理实现的呢,了解这些是实现分布式服务框架的基础知识,而如果在性能上有高的要求的话,那深入了解这些技术背后的机制就是必须的了。

1 基本原理

要实现网络机器间的通讯,首先得来看看计算机系统网络通信的基本原理,在底层层面去看,网络通信需要做的就是将流从一台计算机传输到另外一台计算机,基于传输协议和网络IO来实现,其中传输协议比较出名的有tcp、udp等等,tcp、udp都是在基于Socket概念上为某类应用场景而扩展出的传输协议,网络IO,主要有bio、nio、aio三种方式,所有的分布式应用通讯都基于这个原理而实现,只是为了应用的易用,各种语言通常都会提供一些更为贴近应用易用的应用层协议。

2 消息模式

归根结底,企业应用系统就是对数据的处理,而对于一个拥有多个子系统的企业应用系统而言,它的基础支撑无疑就是对消息的处理。与对象不同,消息本质上是一种数据结构(当然,对象也可以看做是一种特殊的消息),它包含消费者与服务双方都能识别的数据,这些数据需要在不同的进程(机器)之间进行传递,并可能会被多个完全不同的客户端消费。消息传递相较文件传递与远程过程调用(RPC)而言,似乎更胜一筹,因为它具有更好的平台无关性,并能够很好地支持并发与异步调用。

对于Web Service与RESTful而言,则可以看做是消息传递技术的一种衍生或封装。

2.1 消息通道(Message Channel)模式

我们常常运用的消息模式是Message Channel(消息通道)模式,如图所示。

消息通道作为在客户端(消费者,Consumer)与服务(生产者,Producer)之间引入的间接层,可以有效地解除二者之间的耦合。只要实现规定双方需要通信的消息格式,以及处理消息的机制与时机,就可以做到消费者对生产者的“无知”。事实上,该模式可以支持多个生产者与消费者。例如,我们可以让多个生产者向消息通道发送消息,因为消费者对生产者的无知性,它不必考虑究竟是哪个生产者发来的消息。

虽然消息通道解除了生产者与消费者之间的耦合,使得我们可以任意地对生产者与消费者进行扩展,但它又同时引入了各自对消息通道的依赖,因为它们必须知道通道资源的位置。要解除这种对通道的依赖,可以考虑引入Lookup服务来查找该通道资源。例如,在JMS中就可以通过JNDI来获取消息通道Queue。若要做到充分的灵活性,可以将与通道相关的信息存储到配置文件中,Lookup服务首先通过读取配置文件来获得通道。

消息通道通常以队列的形式存在,这种先进先出的数据结构无疑最为适合这种处理消息的场景。微软的MSMQ、IBM MQ、JBoss MQ以及开源的RabbitMQ、Apache ActiveMQ都通过队列实现了Message Channel模式。因此,在选择运用Message Channel模式时,更多地是要从质量属性的层面对各种实现了该模式的产品进行全方位的分析与权衡。例如,消息通道对并发的支持以及在性能上的表现;消息通道是否充分地考虑了错误处理;对消息安全的支持;以及关于消息持久化、灾备(fail over)与集群等方面的支持。

因为通道传递的消息往往是一些重要的业务数据,一旦通道成为故障点或安全性的突破点,对系统就会造成灾难性的影响。

此处也顺带的提下jndi的机制,由于JNDI取决于具体的实现,在这里只能是讲解下jboss的jndi的实现了:

在将对象实例绑定到jboss jnp server后,当远程端采用context.lookup()方式获取远程对象实例并开始调用时,jboss jndi的实现方法是从jnp server上获取对象实例,将其序列化回本地,然后在本地进行反序列化,之后在本地进行类调用。

通过这个机制,就可以知道了,本地其实是必须有绑定到jboss上的对象实例的class的,否则反序列化的时候肯定就失败了,而远程通讯需要做到的是在远程执行某动作,并获取到相应的结果,可见纯粹基于JNDI是无法实现远程通讯的。

但JNDI也是实现分布式服务框架一个很关键的技术点,因为可以通过它来实现透明化的远端和本地调用,就像ejb,另外它也是个很好的隐藏实际部署机制(就像datasource)等的方案。

2.2 发布者-订阅者(Publisher-Subscriber)模式

一旦消息通道需要支持多个消费者时,就可能面临两种模型的选择:拉模型与推模型。拉模型是由消息的消费者发起的,主动权把握在消费者手中,它会根据自己的情况对生产者发起调用。如图所示:

拉模型的另一种体现则由生产者在状态发生变更时,通知消费者其状态发生了改变。但得到通知的消费者却会以回调方式,通过调用传递过来的消费者对象获取更多细节消息。

在基于消息的分布式系统中,拉模型的消费者通常以Batch Job的形式,根据事先设定的时间间隔,定期侦听通道的情况。一旦发现有消息传递进来,就会转而将消息传递给真正的处理器(也可以看做是消费者)处理消息,执行相关的业务。

推模型的主动权常常掌握在生产者手中,消费者被动地等待生产者发出的通知,这就要求生产者必须了解消费者的相关信息。如图所示:

对于推模型而言,消费者无需了解生产者。在生产者通知消费者时,传递的往往是消息(或事件),而非生产者自身。同时,生产者还可以根据不同的情况,注册不同的消费者,又或者在封装的通知逻辑中,根据不同的状态变化,通知不同的消费者。

两种模型各有优势。拉模型的好处在于可以进一步解除消费者对通道的依赖,通过后台任务去定期访问消息通道。坏处是需要引入一个单独的服务进程,以Schedule形式执行。而对于推模型而言,消息通道事实上会作为消费者观察的主体,一旦发现消息进入,就会通知消费者执行对消息的处理。无论推模型,拉模型,对于消息对象而言,都可能采用类似Observer模式的机制,实现消费者对生产者的订阅,因此这种机制通常又被称为Publisher-Subscriber模式,如图所示:

通常情况下,发布者和订阅者都会被注册到用于传播变更的基础设施(即消息通道)上。发布者会主动地了解消息通道,使其能够将消息发送到通道中;消息通道一旦接收到消息,会主动地调用注册在通道中的订阅者,进而完成对消息内容的消费。

对于订阅者而言,有两种处理消息的方式。一种方式是广播机制,这时消息通道中的消息在出列的同时,还需要复制消息对象,将消息传递给多个订阅者。例如,有多个子系统都需要获取从CRM系统传来的客户信息,并根据传递过来的客户信息,进行相应的处理。此时的消息通道又被称为Propagation通道。另一种方式则属于抢占机制,它遵循同步方式,在同一时间只能有一个订阅者能够处理该消息。实现Publisher-Subscriber模式的消息通道会选择当前空闲的唯一订阅者,并将消息出列,并传递给订阅者的消息处理方法。

目前,有许多消息中间件都能够很好地支持Publisher-Subscriber模式,例如JMS接口规约中对于Topic对象提供的MessagePublisher与MessageSubscriber接口。RabbitMQ也提供了自己对该模式的实现。微软的MSMQ虽然引入了事件机制,可以在队列收到消息时触发事件,通知订阅者。但它并非严格意义上的Publisher-Subscriber模式实现。由微软MVP Udi Dahan作为主要贡献者的NServiceBus,则对MSMQ以及WCF做了进一层包装,并能够很好地实现这一模式。

2.3 消息路由(Message Router)模式

无论是Message Channel模式,还是Publisher-Subscriber模式,队列在其中都扮演了举足轻重的角色。然而,在企业应用系统中,当系统变得越来越复杂时,对性能的要求也会越来越高,此时对于系统而言,可能就需要支持同时部署多个队列,并可能要求分布式部署不同的队列。这些队列可以根据定义接收不同的消息,例如订单处理的消息,日志信息,查询任务消息等。这时,对于消息的生产者和消费者而言,并不适宜承担决定消息传递路径的职责。事实上,根据S单一职责原则,这种职责分配也是不合理的,它既不利于业务逻辑的重用,也会造成生产者、消费者与消息队列之间的耦合,从而影响系统的扩展。

既然这三种对象(组件)都不宜承担这样的职责,就有必要引入一个新的对象专门负责传递路径选择的功能,这就是所谓的Message Router模式,如图所示:

通过消息路由,我们可以配置路由规则指定消息传递的路径,以及指定具体的消费者消费对应的生产者。例如指定路由的关键字,并由它来绑定具体的队列与指定的生产者(或消费者)。路由的支持提供了消息传递与处理的灵活性,也有利于提高整个系统的消息处理能力。同时,路由对象有效地封装了寻找与匹配消息路径的逻辑,就好似一个调停者(Meditator),负责协调消息、队列与路径寻址之间关系。

3 应用级协议

远程服务通讯,需要达到的目标是在一台计算机发起请求,另外一台机器在接收到请求后进行相应的处理并将结果返回给请求端,这其中又会有诸如one way request、同步请求、异步请求等等请求方式,按照网络通信原理,需要实现这个需要做的就是将请求转换成流,通过传输协议传输至远端,远端计算机在接收到请求的流后进行处理,处理完毕后将结果转化为流,并通过传输协议返回给调用端。

原理是这样的,但为了应用的方便,业界推出了很多基于此原理之上的应用级的协议,使得大家可以不用去直接操作这么底层的东西,通常应用级的远程通信协议会提供:

  1. 为了避免直接做流操作这么麻烦,提供一种更加易用或贴合语言的标准传输格式;
  2. 网络通信机制的实现,就是替你完成了将传输格式转化为流,通过某种传输协议传输至远端计算机,远端计算机在接收到流后转化为传输格式,并进行存储或以某种方式通知远端计算机。

所以在学习应用级的远程通信协议时,我们可以带着这几个问题进行学习:

  1. 传输的标准格式是什么?
  2. 怎么样将请求转化为传输的流?
  3. 怎么接收和处理流?
  4. 传输协议是?

不过应用级的远程通信协议并不会在传输协议上做什么多大的改进,主要是在流操作方面,让应用层生成流和处理流的这个过程更加的贴合所使用的语言或标准,至于传输协议则通常都是可选的,在java领域中知名的有:RMI、XML-RPC、Binary-RPC、SOAP、CORBA、JMS、HTTP,来具体的看看这些远程通信的应用级协议。

3.1 RMI(远程方法调用)

RMI是个典型的为java定制的远程通信协议,我们都知道,在single vm中,我们可以通过直接调用java object instance来实现通信,那么在远程通信时,如果也能按照这种方式当然是最好了,这种远程通信的机制成为RPC(Remote Procedure Call),RMI正是朝着这个目标而诞生的。

RMI 采用stubs 和 skeletons 来进行远程对象(remote object)的通讯。stub 充当远程对象的客户端代理,有着和远程对象相同的远程接口,远程对象的调用实际是通过调用该对象的客户端代理对象stub来完成的,通过该机制RMI就好比它是本地工作,采用tcp/ip协议,客户端直接调用服务端上的一些方法。优点是强类型,编译期可检查错误,缺点是只能基于JAVA语言,客户机与服务器紧耦合。

来看下基于RMI的一次完整的远程通信过程的原理:

  1. 客户端发起请求,请求转交至RMI客户端的stub类;
  2. stub类将请求的接口、方法、参数等信息进行序列化;
  3. 基于socket将序列化后的流传输至服务器端;
  4. 服务器端接收到流后转发至相应的skelton类;
  5. skelton类将请求的信息反序列化后调用实际的处理类;
  6. 处理类处理完毕后将结果返回给skelton类;
  7. Skelton类将结果序列化,通过socket将流传送给客户端的stub;
  8. stub在接收到流后反序列化,将反序列化后的Java Object返回给调用者。

根据原理来回答下之前学习应用级协议带着的几个问题:

  1. 传输的标准格式是什么?是Java ObjectStream。
  2. 怎么样将请求转化为传输的流?基于Java串行化机制将请求的java object信息转化为流。
  3. 怎么接收和处理流?根据采用的协议启动相应的监听端口,当有流进入后基于Java串行化机制将流进行反序列化,并根据RMI协议获取到相应的处理对象信息,进行调用并处理,处理完毕后的结果同样基于java串行化机制进行返回。
  4. 传输协议是?Socket。

3.2 XML-RPC

RPC使用C/S方式,采用http协议,发送请求到服务器,等待服务器返回结果。这个请求包括一个参数集和一个文本集,通常形成“classname.methodname”形式。优点是跨语言跨平台,C端、S端有更大的独立性,缺点是不支持对象,无法在编译器检查错误,只能在运行期检查。

XML-RPC也是一种和RMI类似的远程调用的协议,它和RMI的不同之处在于它以标准的xml格式来定义请求的信息(请求的对象、方法、参数等),这样的好处是什么呢,就是在跨语言通讯的时候也可以使用。

来看下XML-RPC协议的一次远程通信过程:

  1. 客户端发起请求,按照XML-RPC协议将请求信息进行填充;
  2. 填充完毕后将xml转化为流,通过传输协议进行传输;
  3. 接收到在接收到流后转换为xml,按照XML-RPC协议获取请求的信息并进行处理;
  4. 处理完毕后将结果按照XML-RPC协议写入xml中并返回。

同样来回答问题:

  1. 传输的标准格式是?标准格式的XML。
  2. 怎么样将请求转化为传输的流?将XML转化为流。
  3. 怎么接收和处理流?通过监听的端口获取到请求的流,转化为XML,并根据协议获取请求的信息,进行处理并将结果写入XML中返回。
  4. 传输协议是?Http。

3.3 Binary-RPC

Binary-RPC看名字就知道和XML-RPC是差不多的了,不同之处仅在于传输的标准格式由XML转为了二进制的格式。

同样来回答问题:

  1. 传输的标准格式是?标准格式的二进制文件。
  2. 怎么样将请求转化为传输的流?将二进制格式文件转化为流。
  3. 怎么接收和处理流?通过监听的端口获取到请求的流,转化为二进制文件,根据协议获取请求的信息,进行处理并将结果写入XML中返回。
  4. 传输协议是?Http。

3.4 SOAP

SOAP原意为Simple Object Access Protocol,是一个用于分布式环境的、轻量级的、基于XML进行信息交换的通信协议,可以认为SOAP是XML RPC的高级版,两者的原理完全相同,都是http+XML,不同的仅在于两者定义的XML规范不同,SOAP也是Webservice采用的服务调用协议标准,因此在此就不多加阐述了。

Web Service提供的服务是基于web容器的,底层使用http协议,类似一个远程的服务提供者,比如天气预报服务,对各地客户端提供天气预报,是一种请求应答的机制,是跨系统跨平台的。就是通过一个servlet,提供服务出去。

首先客户端从服务器获得WebService的WSDL,同时在客户端生成一个代理类(Proxy Class),这个代理类负责与WebService服务器进行Request和Response。当一个数据(XML格式的)被封装成SOAP格式的数据流发送到服务器端的时候,就会生成一个进程对象并且把接收到这个Request的SOAP包进行解析,然后对事物进行处理,处理结束以后再对这个计算结果进行SOAP包装,然后把这个包作为一个Response发送给客户端的代理类(Proxy Class),同样地,这个代理类也对这个SOAP包进行解析处理,继而进行后续操作。这就是WebService的一个运行过程。

Web Service大体上分为5个层次:

  1. Http传输信道;
  2. XML的数据格式;
  3. SOAP封装格式;
  4. WSDL的描述方式;
  5. UDDI UDDI是一种目录服务,企业可以使用它对Webservices进行注册和搜索;

3.5 JMS

JMS是实现java领域远程通信的一种手段和方法,基于JMS实现远程通信时和RPC是不同的,虽然可以做到RPC的效果,但因为不是从协议级别定义的,因此我们不认为JMS是个RPC协议,但它确实是个远程通信协议,在其他的语言体系中也存在着类似JMS的东西,可以统一的将这类机制称为消息机制,而消息机制呢,通常是高并发、分布式领域推荐的一种通信机制,这里的主要一个问题是容错。

JMS是Java的消息服务,JMS的客户端之间可以通过JMS服务进行异步的消息传输。JMS支持两种消息模型:Point-to-Point(P2P)和Publish/Subscribe(Pub/Sub),即点对点和发布订阅模型。

来看JMS中的一次远程通信的过程:

  1. 客户端将请求转化为符合JMS规定的Message;
  2. 通过JMS API将Message放入JMS Queue或Topic中;
  3. 如为JMS Queue,则发送中相应的目标Queue中,如为Topic,则发送给订阅了此Topic的JMS Queue。
  4. 处理端则通过轮训JMS Queue,来获取消息,接收到消息后根据JMS协议来解析Message并处理。

同样来回答问题:

  1. 传输的标准格式是?JMS规定的Message。
  2. 怎么样将请求转化为传输的流?将参数信息放入Message中即可。
  3. 怎么接收和处理流?轮训JMS Queue来接收Message,接收到后进行处理,处理完毕后仍然是以Message的方式放入Queue中发送或Multicast。
  4. 传输协议是?不限。

基于JMS也是常用的实现远程异步调用的方法之一。

4 之间的区别

4.1 RPC与RMI

  1. RPC跨语言,而RMI只支持Java。
  2. RMI调用远程对象方法,允许方法返回Java对象以及基本数据类型,而RPC不支持对象的概念,传送到RPC服务的消息由外部数据表示 (External Data Representation, XDR) 语言表示,这种语言抽象了字节序类和数据类型结构之间的差异。只有由 XDR 定义的数据类型才能被传递,可以说 RMI 是面向对象方式的Java RPC。
  3. 在方法调用上,RMI中,远程接口使每个远程方法都具有方法签名。如果一个方法在服务器上执行,但是没有相匹配的签名被添加到这个远程接口上,那么这个新方法就不能被RMI客户方所调用。在RPC中,当一个请求到达RPC服务器时,这个请求就包含了一个参数集和一个文本值,通常形成“classname.methodname”的形式。这就向RPC服务器表明,被请求的方法在为 “classname”的类中,名叫“methodname”。然后RPC服务器就去搜索与之相匹配的类和方法,并把它作为那种方法参数类型的输入。这里的参数类型是与RPC请求中的类型是匹配的。一旦匹配成功,这个方法就被调用了,其结果被编码后返回客户方。
  4. RPC本身没有规范,但基本的工作机制是一样的,即:serialization/deserialization+stub+skeleton,宽泛的讲,只要能实现远程调用,都是RPC,如:rmi .net-remoting ws/soap/rest hessian xmlrpc thrift potocolbuffer。
  5. 在Java里提供了完整的sockets通讯接口,但sockets要求客户端和服务端必须进行应用级协议的编码交换数据,采用sockets是非常麻烦的。一个代替Sockets的协议是RPC(Remote Procedure Call), 它抽象出了通讯接口用于过程调用,使得编程者调用一个远程过程和调用本地过程同样方便。RPC 系统采用XDR来编码远程调用的参数和返回值。但RPC并不支持对象,所以,面向对象的远程调用RMI(Remote Method Invocation)成为必然选择。采用RMI,调用远程对象和调用本地对象同样方便。RMI 采用JRMP(Java Remote Method Protocol)通讯协议,是构建在TCP/IP协议上的一种远程调用方法。

4.2 JMS与RMI

  1. 采用JMS服务,对象是在物理上被异步从网络的某个JVM 上直接移动到另一个JVM 上(是消息通知机制),而RMI对象是绑定在本地JVM 中,只有函数参数和返回值是通过网络传送的(是请求应答机制)。
  2. RMI一般都是同步的,也就是说,当client调用Server的一个方法的时候,需要等到对方的返回,才能继续执行client端,这个过程调用本地方法感觉上是一样的,这也是RMI的一个特点。JMS 一般只是一个点发出一个Message到Message Server,发出之后一般不会关心谁用了这个message。所以,一般RMI的应用是紧耦合,JMS的应用相对来说是松散耦合应用。

4.3 Webservice与RMI

RMI是在tcp协议上传递可序列化的java对象,只能用在java虚拟机上,绑定语言,客户端和服务端都必须是java。webservice没有这个限制,webservice是在http协议上传递xml文本文件,与语言和平台无关。

4.4 Webservice与JMS

Webservice专注于远程服务调用,jms专注于信息交换。

大多数情况下Webservice是两系统间的直接交互(Consumer Producer),而大多数情况下jms是三方系统交互(Consumer Producer)。当然,JMS也可以实现request-response模式的通信,只要Consumer或Producer其中一方兼任broker即可。

JMS可以做到异步调用完全隔离了客户端和服务提供者,能够抵御流量洪峰;WebService服务通常为同步调用,需要有复杂的对象转换,相比SOAP,现在JSON,rest都是很好的http架构方案;

JMS是java平台上的消息规范。一般jms消息不是一个xml,而是一个java对象,很明显,jms没考虑异构系统,说白了,JMS就没考虑非java的东西。但是好在现在大多数的jms provider(就是JMS的各种实现产品)都解决了异构问题。相比WebService的跨平台各有千秋吧。

5 可选实现技术

目前java领域可用于实现远程通讯的框架或library,知名的有:JBoss-Remoting、Spring-Remoting、Hessian、Burlap、XFire(Axis)、ActiveMQ、Mina、Mule、EJB3等等,来对每种做个简单的介绍和评价,其实呢,要做分布式服务框架,这些东西都是要有非常深刻的了解的,因为分布式服务框架其实是包含了解决分布式领域以及应用层面领域两方面问题的。

当然,你也可以自己根据远程网络通信原理(transport protocol+Net IO)去实现自己的通讯框架或library。

那么在了解这些远程通讯的框架或library时,会带着什么问题去学习呢?

  1. 是基于什么协议实现的?
  2. 怎么发起请求?
  3. 怎么将请求转化为符合协议的格式的?
  4. 使用什么传输协议传输?
  5. 响应端基于什么机制来接收请求?
  6. 怎么将流还原为传输格式的?
  7. 处理完毕后怎么回应?

5.1 Spring-Remoting

Spring-remoting是Spring提供java领域的远程通讯框架,基于此框架,同样也可以很简单的将普通的spring bean以某种远程协议的方式来发布,同样也可以配置spring bean为远程调用的bean。

  1. 是基于什么协议实现的?作为一个远程通讯的框架,Spring通过集成多种远程通讯的library,从而实现了对多种协议的支持,例如rmi、http+io、xml-rpc、binary-rpc等。
  2. 怎么发起请求?在Spring中,由于其对于远程调用的bean采用的是proxy实现,发起请求完全是通过服务接口调用的方式。
  3. 怎么将请求转化为符合协议的格式的?Spring按照协议方式将请求的对象信息转化为流,例如Spring Http Invoker是基于Spring自己定义的一个协议来实现的,传输协议上采用的为http,请求信息是基于java串行化机制转化为流进行传输。
  4. 使用什么传输协议传输?支持多种传输协议,例如rmi、http等等。
  5. 响应端基于什么机制来接收请求?响应端遵循协议方式来接收请求,对于使用者而言,则只需通过spring的配置方式将普通的spring bean配置为响应端或者说提供服务端。
  6. 怎么将流还原为传输格式的?按照协议方式来进行还原。
  7. 处理完毕后怎么回应?处理完毕后直接返回即可,spring-remoting将根据协议方式来做相应的序列化。

5.2 Hessian

Hessian是由caucho提供的一个基于binary-RPC实现的远程通讯library。

  1. 是基于什么协议实现的?基于Binary-RPC协议实现。
  2. 怎么发起请求?需通过Hessian本身提供的API来发起请求。
  3. 怎么将请求转化为符合协议的格式的?Hessian通过其自定义的串行化机制将请求信息进行序列化,产生二进制流。
  4. 使用什么传输协议传输?Hessian基于Http协议进行传输。
  5. 响应端基于什么机制来接收请求?响应端根据Hessian提供的API来接收请求。
  6. 怎么将流还原为传输格式的?Hessian根据其私有的串行化机制来将请求信息进行反序列化,传递给使用者时已是相应的请求信息对象了。
  7. 处理完毕后怎么回应?处理完毕后直接返回,hessian将结果对象进行序列化,传输至调用端。

5.3 Burlap

Burlap也是有caucho提供,它和hessian的不同在于,它是基于XML-RPC协议的。

  1. 是基于什么协议实现的?基于XML-RPC协议实现。
  2. 怎么发起请求?根据Burlap提供的API。
  3. 怎么将请求转化为符合协议的格式的?将请求信息转化为符合协议的XML格式,转化为流进行传输。
  4. 使用什么传输协议传输?Http协议。
  5. 响应端基于什么机制来接收请求?监听Http请求。
  6. 怎么将流还原为传输格式的?根据XML-RPC协议进行还原。
  7. 处理完毕后怎么回应?返回结果写入XML中,由Burlap返回至调用端。

5.4 XFire、Axis

XFire、Axis是Webservice的实现框架,WebService可算是一个完整的SOA架构实现标准了,因此采用XFire、Axis这些也就意味着是采用webservice方式了。

  1. 是基于什么协议实现的?基于SOAP协议。
  2. 怎么发起请求?获取到远端service的proxy后直接调用。
  3. 怎么将请求转化为符合协议的格式的?将请求信息转化为遵循SOAP协议的XML格式,由框架转化为流进行传输。
  4. 使用什么传输协议传输?Http协议。
  5. 响应端基于什么机制来接收请求?监听Http请求。
  6. 怎么将流还原为传输格式的?根据SOAP协议进行还原。
  7. 处理完毕后怎么回应?返回结果写入XML中,由框架返回至调用端。

5.5 ActiveMQ

ActiveMQ是JMS的实现,基于JMS这类消息机制实现远程通讯是一种不错的选择,毕竟消息机制本身的功能使得基于它可以很容易的去实现同步/异步/单向调用等,而且消息机制从容错角度上来说也是个不错的选择,这是Erlang能够做到容错的重要基础。

  1. 是基于什么协议实现的?基于JMS协议。
  2. 怎么发起请求?遵循JMS API发起请求。
  3. 怎么将请求转化为符合协议的格式的?不太清楚,猜想应该是二进制流。
  4. 使用什么传输协议传输?支持多种传输协议,例如socket、http等等。
  5. 响应端基于什么机制来接收请求?监听符合协议的端口。
  6. 怎么将流还原为传输格式的?同问题3。
  7. 处理完毕后怎么回应?遵循JMS API生成消息,并写入JMS Queue中。

5.6 Mina

Mina是Apache提供的通讯框架,在之前一直没有提到网络IO这块,之前提及的框架或library基本都是基于BIO的,而Mina是采用NIO的,NIO在并发量增长时对比BIO而言会有明显的性能提升,而java性能的提升,与其NIO这块与OS的紧密结合是有不小的关系的。

  1. 是基于什么协议实现的?基于纯粹的Socket+NIO。
  2. 怎么发起请求?通过Mina提供的Client API。
  3. 怎么将请求转化为符合协议的格式的?Mina遵循java串行化机制对请求对象进行序列化。
  4. 使用什么传输协议传输?支持多种传输协议,例如socket、http等等。
  5. 响应端基于什么机制来接收请求?以NIO的方式监听协议端口。
  6. 怎么将流还原为传输格式的?遵循java串行化机制对请求对象进行反序列化。
  7. 处理完毕后怎么回应?遵循Mina API进行返回。

MINA是NIO方式的,因此支持异步调用是毫无悬念的。

6 RPC框架的发展与现状

RPC(Remote Procedure Call)是一种远程调用协议,简单地说就是能使应用像调用本地方法一样的调用远程的过程或服务,可以应用在分布式服务、分布式计算、远程服务调用等许多场景。说起 RPC 大家并不陌生,业界有很多开源的优秀 RPC 框架,例如 Dubbo、Thrift、gRPC、Hprose 等等。下面先简单介绍一下 RPC 与常用远程调用方式的特点,以及一些优秀的开源 RPC 框架。

RPC 与其它远程调用方式比较,RPC 与 HTTP、RMI、Web Service 都能完成远程调用,但是实现方式和侧重点各有不同。

6.1 RPC与HTTP

HTTP(HyperText Transfer Protocol)是应用层通信协议,使用标准语义访问指定资源(图片、接口等),网络中的中转服务器能识别协议内容。HTTP 协议是一种资源访问协议,通过 HTTP 协议可以完成远程请求并返回请求结果。

HTTP 的优点是简单、易用、可理解性强且语言无关,在远程服务调用中包括微博有着广泛应用。HTTP 的缺点是协议头较重,一般请求到具体服务器的链路较长,可能会有 DNS 解析、Nginx 代理等。

RPC 是一种协议规范,可以把 HTTP 看作是一种 RPC 的实现,也可以把 HTTP 作为 RPC 的传输协议来应用。RPC 服务的自动化程度比较高,能够实现强大的服务治理功能,和语言结合更友好,性能也十分优秀。与 HTTP 相比,RPC 的缺点就是相对复杂,学习成本稍高。

6.2 RPC与RMI

RMI(Remote Method Invocation)是指 Java 语言中的远程方法调用,RMI 中的每个方法都具有方法签名,RMI 客户端和服务器端通过方法签名进行远程方法调用。RMI 只能在 Java 语言中使用,可以把 RMI 看作面向对象的 Java RPC。

6.3 RPC与Web Service

Web Service 是一种基于 Web 进行服务发布、查询、调用的架构方式,重点在于服务的管理与使用。Web Service 一般通过 WSDL 描述服务,使用 SOAP通过 HTTP 调用服务。

RPC 是一种远程访问协议,而 Web Service 是一种体系结构,Web Service 也可以通过 RPC 来进行服务调用,因此 Web Service 更适合同一个 RPC 框架进行比较。当 RPC 框架提供了服务的发现与管理,并使用 HTTP 作为传输协议时,其实就是 Web Service。

相对 Web Service,RPC 框架可以对服务进行更细粒度的治理,包括流量控制、SLA 管理等,在微服务化、分布式计算方面有更大的优势。

RPC 可基于 HTTP 或 TCP 协议,Web Service 就是基于 HTTP 协议的 RPC,它具有良好的跨平台性,但其性能却不如基于 TCP 协议的 RPC。会两方面会直接影响 RPC 的性能,一是传输方式,二是序列化。

众所周知,TCP 是传输层协议,HTTP 是应用层协议,而传输层较应用层更加底层,在数据传输方面,越底层越快,因此,在一般情况下,TCP 一定比 HTTP 快。

7 总结

在远程通讯领域中,涉及的知识点还是相当的多的,例如有:通信协议(Socket/tcp/http/udp/rmi/xml-rpc etc.)、消息机制、网络IO(BIO/NIO/AIO)、MultiThread、本地调用与远程调用的透明化方案(涉及java classloader、Dynamic Proxy、Unit Test etc.)、异步与同步调用、网络通信处理机制(自动重连、广播、异常、池处理等等)、Java Serialization (各种协议的私有序列化机制等)、各种框架的实现原理(传输格式、如何将传输格式转化为流的、如何将请求信息转化为传输格式的、如何接收流的、如何将流还原为传输格式的等等),要精通其中的哪些东西,得根据实际需求来决定了,只有在了解了原理的情况下才能很容易的做出选择,甚至可以根据需求做私有的远程通讯协议,对于从事分布式服务平台或开发较大型的分布式应用的人而言,我觉得至少上面提及的知识点是需要比较了解的。

专栏作者简介


陶邦仁:专注于后端技术研究,前端技术略有涉猎,热衷于构建高性能、高可用网站,对平台服务化、分布式服务、分布式存储等方面的解决方案。目前就职于千丁互联,任技术经理一职,负责社区产品技术研发。曾就职于京东,负责库存组缓存方案技术实现;曾就职于百度糯米,负责PC首页、APP个性化排单服务化解决方案。

计算几何常用算法,ACM竞赛必备~

来自2010年百度文库

原作者不详

1、矢量减法

设二维矢量 P = (x1,y1) ,Q = (x2,y2)
则矢量减法定义为: P – Q = ( x1 – x2 , y1 – y2 )
显然有性质 P – Q = – ( Q – P )
如不加说明,下面所有的点都看作矢量,两点的减法就是矢量相减;

2、矢量叉积

设矢量P = (x1,y1) ,Q = (x2,y2)
则矢量叉积定义为: P × Q = x1*y2 – x2*y1   得到的是一个标量
显然有性质 P × Q = – ( Q × P )   P × ( – Q ) = – ( P × Q )
如不加说明,下面所有的点都看作矢量,点的乘法看作矢量叉积;
叉乘的重要性质:
> 若 P × Q > 0 , 则P 在Q的顺时针方向
> 若 P × Q < 0 , 则P 在Q的逆时针方向
> 若 P × Q = 0 , 则P 与Q共线,但可能同向也可能反向

3、判断点在线段上

设点为Q,线段为P1P2 ,判断点Q在该线段上的依据是:
( Q – P1 ) × ( P2 – P1 ) = 0 且 Q 在以 P1,P2为对角顶点的矩形内

4、判断两线段是否相交

我们分两步确定两条线段是否相交:

(1)快速排斥试验
设以线段 P1P2 为对角线的矩形为R, 设以线段 Q1Q2 为对角线的矩形为T,如果R和T不相
交,显然两线段不会相交;

(2)跨立试验
如果两线段相交,则两线段必然相互跨立对方,如图1所示。在图1中,P1P2跨立Q1Q2 ,则
矢量 ( P1 – Q1 ) 和( P2 – Q1 )位于矢量( Q2 – Q1 ) 的两侧,即
( P1 – Q1 ) × ( Q2 – Q1 ) * ( P2 – Q1 ) × ( Q2 – Q1 ) < 0
上式可改写成

( P1 – Q1 ) × ( Q2 – Q1 ) * ( Q2 – Q1 ) × ( P2 – Q1 ) > 0
当 ( P1 – Q1 ) × ( Q2 – Q1 ) = 0 时,说明   ( P1 – Q1 ) 和 ( Q2 – Q1 )共线,

但是因为已经通过快速排斥试验,所以 P1 一定在线段 Q1Q2上;同理,( Q2 – Q1 ) ×(
P2 – Q1 ) = 0 说明 P2 一定在线段 Q1Q2上。

所以判断P1P2跨立Q1Q2的依据是:
( P1 – Q1 ) × ( Q2 – Q1 ) * ( Q2 – Q1 ) × ( P2 – Q1 ) ≥ 0
同理判断Q1Q2跨立P1P2的依据是:
( Q1 – P1 ) × ( P2 – P1 ) * ( P2 – P1 ) × ( Q2 – P1 ) ≥ 0
至此已经完全解决判断线段是否相交的问题。

5、判断线段和直线是否相交

如果线段 P1P2和直线Q1Q2相交,则P1P2跨立Q1Q2,即:
( P1 – Q1 ) × ( Q2 – Q1 ) * ( Q2 – Q1 ) × ( P2 – Q1 ) ≥ 0

6、判断矩形是否包含点

只要判断该点的横坐标和纵坐标是否夹在矩形的左右边和上下边之间。
判断线段、折线、多边形是否在矩形中
因为矩形是个凸集,所以只要判断所有端点是否都在矩形中就可以了。

6、判断矩形是否在矩形中

只要比较左右边界和上下边界就可以了。

7、判断圆是否在矩形中

圆在矩形中的充要条件是:圆心在矩形中且圆的半径小于等于圆心到矩形四边的距离的最
小值。

8、判断点是否在多边形中

以点P为端点,向左方作射线L,由于多边形是有界的,所以射线L的左端一定在多边形外,
考虑沿着L从无穷远处开始自左向右移动,遇到和多边形的第一个交点的时候,进入到了多
边形的内部,遇到第二个交点的时候,离开了多边形,……所以很容易看出当L和多边形的
交点数目C是奇数的时候,P在多边形内,是偶数的话P在多边形外。
但是有些特殊情况要加以考虑。如果L和多边形的顶点相交,有些情况下交点只能计算一个
,有些情况下交点不应被计算(你自己画个图就明白了);如果L和多边形的一条边重合,
这条边应该被忽略不计。为了统一起见,我们在计算射线L和多边形的交点的时候,1。对
于多边形的水平边不作考虑;2。对于多边形的顶点和L相交的情况,如果该顶点是其所属
的边上纵坐标较大的顶点,则计数,否则忽略;3。对于P在多边形边上的情形,直接可判
断P属于多边行。由此得出算法的伪代码如下:

1、count ← 0;
2、以P为端点,作从右向左的射线L;
3、for 多边形的每条边s
4、do if P在边s上
5、then return true;
6、if s不是水平的
7、then if s的一个端点在L上且该端点是s两端点中纵坐标较大的端点
9、then count ← count+1
10、else if s和L相交
11、then count ← count+1;
12i、f count mod 2 = 1
13、then return true
14、else return false;

其中做射线L的方法是:设P’的纵坐标和P相同,横坐标为正无穷大(很大的一个正数),
则P和P’就确定了射线L。这个算法的复杂度为O(n)。

9、判断线段是否在多边形内

线段在多边形内的一个必要条件是线段的两个端点都在多边形内;
如果线段和多边形的某条边内交(两线段内交是指两线段相交且交点不在两线段的端点)
,因为多边形的边的左右两侧分属多边形内外不同部分,所以线段一定会有一部分在多边
形外。于是我们得到线段在多边形内的第二个必要条件:线段和多边形的所有边都不内交

线段和多边形交于线段的两端点并不会影响线段是否在多边形内;但是如果多边形的某个
顶点和线段相交,还必须判断两相邻交点之间的线段是否包含与多边形内部。因此我们可
以先求出所有和线段相交的多边形的顶点,然后按照X-Y坐标排序,这样相邻的两个点就是
在线段上相邻的两交点,如果任意相邻两点的中点也在多边形内,则该线段一定在多边形
内。证明如下:
命题1:
如果线段和多边形的两相邻交点P1 ,P2的中点P’ 也在多边形内,则P1, P2之间的所有点
都在多边形内。
证明:
假设P1,P2之间含有不在多边形内的点,不妨设该点为Q,在P1, P’之间,因为多边形是闭
合曲线,所以其内外部之间有界,而P1属于多边行内部,Q属于多边性外部,P’属于多边性
内部,P1-Q-P’完全连续,所以P1Q和QP’一定跨越多边形的边界,因此在P1,P’之间至少还
有两个该线段和多边形的交点,这和P1P2是相邻两交点矛盾,故命题成立。证毕
由命题1直接可得出推论:
推论2:
设多边形和线段PQ的交点依次为P1,P2,……Pn,其中Pi和Pi+1是相邻两交点,线段PQ在多
边形内的充要条件是:P,Q在多边形内且对于i =1, 2,……, n-1,Pi ,Pi+1的中点也在多
边形内。

在实际编程中,没有必要计算所有的交点,首先应判断线段和多边形的边是否内交,倘若
线段和多边形的某条边内交则线段一定在多边形外;如果线段和多边形的每一条边都不内
交,则线段和多边形的交点一定是线段的端点或者多边形的顶点,只要判断点是否在线段
上就可以了。
至此我们得出算法如下:
1、f 线端PQ的端点不都在多边形内
2、hen return false;
3、点集pointSet初始化为空;
4、for 多边形的每条边s
5、do if 线段的某个端点在s上
6、then 将该端点加入pointSet;
7、else if s的某个端点在线段PQ上
8、then 将该端点加入pointSet;
9、else if s和线段PQ相交           // 这时候可以肯定是内交
10、 then return false;
11、将pointSet中的点按照X-Y坐标排序,X坐标小的排在前面,对于X坐标相同的点,Y坐
标小的排在前面;
12、for pointSet中每两个相邻点 pointSet[i] , pointSet[ i+1]
13、do if pointSet[i] , pointSet[ i+1] 的中点不在多边形中
14、then return false;
15、return true;

这个算法的复杂度也是O(n)。其中的排序因为交点数目肯定远小于多边形的顶点数目n,所
以最多是常数级的复杂度,几乎可以忽略不计。

10、判断折线在多边形内

只要判断折线的每条线段是否都在多边形内即可。设折线有m条线段,多边形有n个顶点,
则复杂度为O(m*n)。

11、判断多边形是否在多边形内
只要判断多边形的每条边是否都在多边形内即可。判断一个有m个顶点的多边形是否在一个
有n个顶点的多边形内复杂度为O(m*n)。

12、判断矩形是否在多边形内

将矩形转化为多边形,然后再判断是否在多边形内。

13、判断圆是否在多边形内

只要计算圆心到多边形的每条边的最短距离,如果该距离大于等于圆半径则该圆在多边形
内。计算圆心到多边形每条边最短距离的算法在后文阐述。

14、判断点是否在圆内

计算圆心到该点的距离,如果小于等于半径则该点在圆内。

15、判断线段、折线、矩形、多边形是否在圆内

因为圆是凸集,所以只要判断是否每个顶点都在圆内即可。

16、判断圆是否在圆内

设两圆为O1,O2,半径分别为r1, r2,要判断O2是否在O1内。先比较r1,r2的大小,如果r
1<r2则O2不可能在O1内;否则如果两圆心的距离大于r1 – r2 ,则O2不在O1内;否则O2在
O1内。

17、计算点到线段的最近点

如果该线段平行于X轴(Y轴),则过点point作该线段所在直线的垂线,垂足很容易求得,
然后计算出垂足,如果垂足在线段上则返回垂足,否则返回离垂足近的端点;
如果该线段不平行于X轴也不平行于Y轴,则斜率存在且不为0。设线段的两端点为pt1和pt
2,斜率为:
k = ( pt2.y – pt1. y ) / (pt2.x – pt1.x );
该直线方程为:
y = k* ( x – pt1.x) + pt1.y
其垂线的斜率为 – 1 / k,
垂线方程为:
y = (-1/k) * (x – point.x) + point.y
联立两直线方程解得:
x = ( k^2 * pt1.x + k * (point.y – pt1.y ) + point.x ) / ( k^2 + 1)
y = k * ( x – pt1.x) + pt1.y;
然后再判断垂足是否在线段上,如果在线段上则返回垂足;如果不在则计算两端点到垂足
的距离,选择距离垂足较近的端点返回。

18、计算点到折线、矩形、多边形的最近点

只要分别计算点到每条线段的最近点,记录最近距离,取其中最近距离最小的点即可。

19、计算点到圆的最近距离
如果该点在圆心,则返回UNDEFINED
连接点P和圆心O,如果PO平行于X轴,则根据P在O的左边还是右边计算出最近点的横坐标为
centerPoint.x – radius 或 centerPoint.x + radius, 如图4 (a)所示;如果如果PO平
行于Y轴,则根据P在O的上边还是下边计算出最近点的纵坐标为 centerPoint.y -+radius
或 centerPoint.y – radius, 如图4 (b)所示。
如果PO不平行于X轴和Y轴,则PO的斜率存在且不为0,如图4(c)所示。这时直线PO斜率为

k = ( P.y – O.y )/ ( P.x – O.x )
直线PO的方程为:
y = k * ( x – P.x) + P.y
设圆方程为:
(x – O.x ) ^2 + ( y – O.y ) ^2 = r ^2,
联立两方程组可以解出直线PO和圆的交点,取其中离P点较近的交点即可。

20、计算两条共线的线段的交点

对于两条共线的线段,它们之间的位置关系有图5所示的几种情况。
图5(a)中两条线段没有交点;图5 (b) 和 (d) 中两条线段有无穷焦点;图5 (c) 中两条线
段有一个交点。设line1是两条线段中较长的一条,line2是较短的一条,如果line1包含了
line2的两个端点,则是图5(d)的情况,两线段有无穷交点;如果line1只包含line2的一个
端点,那么如果line1的某个端点等于被line1包含的line2的那个端点,则是图5(c)的情况
,这时两线段只有一个交点,否则就是图5(c)的情况,两线段也是有无穷的交点;如果li
ne1不包含line2的任何端点,则是图5(a)的情况,这时两线段没有交点。

21、计算线段或直线与线段的交点
设一条线段为L0 = P1P2,另一条线段或直线为L1 = Q1Q2 ,要计算的就是L0和L1的交点。

1、首先判断L0和L1是否相交(方法已在前文讨论过),如果不相交则没有交点,否则说
明L0和L1一定有交点,下面就将L0和L1都看作直线来考虑。
2、如果P1和P2横坐标相同,即L0平行于Y轴
a) 若L1也平行于Y轴,
i. 若P1的纵坐标和Q1的纵坐标相同,说明L0和L1共线,假如L1是直线的话他们有无穷的交
点,假如L1是线段的话可用”计算两条共线线段的交点”的算法求他们的交点(该方法在前
文已讨论过);
ii. 否则说明L0和L1平行,他们没有交点;
b) 若L1不平行于Y轴,则交点横坐标为P1的横坐标,代入到L1的直线方程中可以计算出交
点纵坐标;
3、如果P1和P2横坐标不同,但是Q1和Q2横坐标相同,即L1平行于Y轴,则交点横坐标为Q
1的横坐标,代入到L0的直线方程中可以计算出交点纵坐标;
4、如果P1和P2纵坐标相同,即L0平行于X轴
a) 若L1也平行于X轴,
i. 若P1的横坐标和Q1的横坐标相同,说明L0和L1共线,假如L1是直线的话他们有无穷的交
点,假如L1是线段的话可用”计算两条共线线段的交点”的算法求他们的交点(该方法在前
文已讨论过);
ii. 否则说明L0和L1平行,他们没有交点;
b) 若L1不平行于X轴,则交点纵坐标为P1的纵坐标,代入到L1的直线方程中可以计算出交
点横坐标;
5、如果P1和P2纵坐标不同,但是Q1和Q2纵坐标相同,即L1平行于X轴,则交点纵坐标为Q
1的纵坐标,代入到L0的直线方程中可以计算出交点横坐标;
6、剩下的情况就是L1和L0的斜率均存在且不为0的情况
a) 计算出L0的斜率K0,L1的斜率K1 ;
b) 如果K1 = K2
i. 如果Q1在L0上,则说明L0和L1共线,假如L1是直线的话有无穷交点,假如L1是线段的话
可用”计算两条共线线段的交点”的算法求他们的交点(该方法在前文已讨论过);
ii. 如果Q1不在L0上,则说明L0和L1平行,他们没有交点。
c) 联立两直线的方程组可以解出交点来

说明:这个算法并不复杂,但是要分情况讨论清楚,尤其是当两条线段共线的情况需要单
独考虑,所以在前文将求两条共线线段的算法单独写出来。另外,一开始就先利用矢量叉
乘判断线段与线段(或直线)是否相交,如果结果是相交,那么在后面就可以将线段全部
看作直线来考虑。

22、求线段或直线与折线、矩形、多边形的交点

分别求与每条边的交点即可。

23、求线段或直线与圆的交点

设圆心为O,圆半径为r,直线(或线段)L上的两点为P1,P2。
1、如果L是线段且P1,P2都包含在圆O内,则没有交点;否则进行下一步
2、如果L平行于Y轴,
a) 计算圆心到L的距离dis
b) 如果dis > r 则L和圆没有交点;
c) 利用勾股定理,可以求出两交点坐标,如图6(a)所示;但要注意考虑L和圆的相切情况
3、如果L平行于X轴,做法与L平行于Y轴的情况类似;
4、如果L既不平行X轴也不平行Y轴,可以求出L的斜率K,然后列出L的点斜式方程,和圆方程联立即可求解出L和圆的两个交点;
5、如果L是线段,对于2,3,4中求出的交点还要分别判断是否属于该线段的范围内。

How to Learn JavaScript Properly

Source: http://javascriptissexy.com/how-to-learn-JavaScript-properly/

Learn JavaScript Properly (For Beginners and Experienced Programmers)

This study guide, which I also refer to as a course outline and a road map, gives you a structured and instructive outline for learning JavaScript properly. In fact, you will find two study guides below, one for absolute beginners and the other for experienced programmers and web developers.

Our Career Paths and Courses Website Is Now Live

Learn.Modern Developer Launched

Our first cohort is in session: 97% of our first cohort on target to graduate. Enroll in the second cohort. Career Path 1: JavaScript Developer and Career Path 3: Modern Frontend Developer usually fill up quickly.

https://learn.moderndeveloper.com

You do want to learn JavaScript. I presume you are here for that reason, and you have made a wise decision. For if you want to develop modern websites and web applications (including an internet startup), or if you want a high-paying developer job ($75K to $250K+), JavaScript is undoubtedly the best web-development language to learn today, unless you want to develop native iOS or Android apps exclusively. And while there exist ample online resources to teach you JavaScript, finding the most efficient and beneficial method to learn the “language of the web” can be a frustrating endeavor. This study guide streamlines and simplifies the process; it has proven successful in helping thousands, and thousands more read and follow it each day.

Study Groups
People have started study groups for this study guide. You can find such groups on Reddit here and here, and other places, including Code Crew Meetup.

What You will Learn

You will learn the JavaScript language (up to advanced-intermediate, if you follow the “Beginners” study guide; or up to advanced, if you follow the “Experienced Programmers” study guide). You will also learn HTML, CSS, jQuery, and Git. And you will build a simple HTML/CSS website, an interactive HTML/CSS/JavaScript website, and a moderately sophisticated JavaScript quiz application.

  • Receive Updates

How Will Your Life Change After You Learn JavaScript Properly?

Maybe you will look more lovely and have a kinder, more pleasant personality after you learn JavaScript properly. Who knows? I don’t know.

But I do know that you will emerge more confident, more assured in your ability, and amply trained with a highly valued skill—a skill more valuable than most college degrees. For as a JavaScript developer, you will have the capacity not only to create whatever startup or web app you imagine, but also to work, making a handsome salary, as a front-end or full-stack developer, developing modern and futuristic applications. In fact, if you have never developed any kind of application before, you will experience ecstasy, so exultant and euphoric that you will want to enthusiastically practice more and build something—anything, like a hungry chef discovering a furnished kitchen with every tool, every utensil, and a stocked refrigerator.

It is worth noting that unlike just a couple of years ago—when you needed to know a true server-side language (such as PHP, Rails, Java, Python, or Perl) to develop scalable, dynamic, and database-driven web applications—today you can do as much and more with JavaScript alone.

This is the flourishing and glorious age of the JavaScript developer.

Be Empowered

This course outline transcends an entire semester of college coursework. If you complete the study guide, you will have learned enough programming to develop modern web applications, and with a bit of experience and a couple of completed projects, you will have become a sought-after programmer. Indeed, JavaScript developers are in high demand today. But you must prove your worth by developing a few impressive (interesting and non-trivial, though not necessarily complex) web applications.

How NOT To Learn JavaScript

  • Do not try to learn JavaScript the first time from bits of unrelated or related JavaScript tutorials online; this is the worst way to learn a programming language. It could work for some after countless such tutorials, but it is an inefficient process that lacks the proper hierarchical structure needed for learning a subject matter thoroughly. And this could lead to your being stuck quite frequently, when you start to build websites and web applications with the language. In short, you will not have the know-how—the comprehensive knowledge—you need to use that language as a tool—as your tool.
  • In addition, some will recommend you learn JavaScript from “JavaScript: The Good Parts,” by the venerable Douglas Crockford. While many regard Mr. Crockford as a JavaScript godfather, his book, The Good Parts, is not the best JavaScript book for beginners. It does not explain JavaScript’s core concepts in a detailed, clear, and easily digestible form. I do recommend you follow Crockford’s advanced videos, however, as part of the Learn Advanced JavaScript road map.
  • And do not try to learn the language by using only Codecademy; while you will learn how to program bits of small JavaScript tasks, you will not have learned enough to build complex web applications. Nonetheless, below I do recommend Codecademy as a supplemental learning resource.

Resources for the Two Study Guides

I have outlined two different study guides below, one for beginners and one for experienced web developers.

  1. Beginners should follow the Learn JavaScript Properly Study Guide for Beginners and get this book:
    Beginning JavaScript.Experienced programmers and web developers should follow the Learn JavaScript Properly Study Guide for Experienced Programmers and get this book:
    — The paperback Version: Professional JavaScript for Web Developers (3rd Edition)
    — The Kindle Version: Professional JavaScript for Web Developers (3rd Edition)
  2. Sign up for an account on Stack Overflow (a FREE service). It is a forum for asking and answering programming questions. This website will be considerably more useful than Codecademy for answering your programming questions, even very basic, seemingly stupid (remember, there is never a stupid question) questions.
  3. Sign up for an account on Codecademy. We will complete 4 Codecademy tracks. Codecademy is an online platform to learn programming: you can write code on their website, right in your browser. (It is also a FREE service.)
  4. JavaScriptIsSexy.com (this blog :) ): We will read 4 articles
  5. CodeSchool.com: We will complete 1 free course

Resources:
Beginning JavaScript (4th Edition)
— JavaScriptIsSexy.com (4 articles)
— Codecademy.com (4 tracks)
— CodeSchool.com (1 short course)
Notice for Visual Learners: If you are a visual learner, that is, if you prefer to see lots of images, schematics, and the like when learning a topic, you may find JavaScript and jQuery: Interactive Front-End Web Development more appealing than the Beginning JavaScript book. If you do get the JavaScript and jQuery book, note that the chapters are similar enough that you can use it (instead of Beginning JavaScript) to follow this study guide, though you will have to modify the sections a bit.

Learn JavaScript Properly Study Guide for Beginners

Prerequisite: Completed at least some high school (no programming experience necessary)

The Level of JavaScript Covered in this Study Guide: Absolute Beginner to Intermediate

How to Get the Best Out of This Study Guide

Type out and test every example code you encounter in the book. You can type the code and tweak it (experiment with it) in Firefox’s or Chrome’s console. The browser console is an area of the browser where you can write and run JavaScript code. Or use JSFiddle. JSFiddle is a web application that allows you to write and test your code online, right in your browser. You can test all sorts of code, including a combination of HTML, CSS, and JavaScript (and jQuery).

Don’t use Safari. I recommend Chrome, but if you use Firefox, get the Firebug Add on for Firefox; use it for testing and debugging your code.

Watch this Firefox’s and Chrome’s Console Tutorial on YouTube.

And watch this Chrome Dev Tools Tutorial (also on YouTube) to learn how to use Chrome Dev Tools.

Also, work all the end-of-chapter exercises.

Let’s get to work.

Weeks 1 and 2

Week 1: Making a Website with HTML and CSS; Learn JavaScript Data Types, Functions, Control Flow, and Loops

  1. Codecademy.com: If you do not already know HTML and CSS, complete the Web Fundamentals Track on Codecademy.
  2. Codecademy.com: Then follow the Make a Website track to make your first little website, using what you learned above.
  3. Beginning JavaScript: Read Chapter 1 (Introduction to JavaScript and the Web) and Chapter 2 (Data Types and Variables).
  4. Beginning JavaScript: Read Chapter 3 (Decisions, Loops, and Functions).
  5. Codecademy.com: Work through the JavaScript Track on Codecademy. Specifically, work through these sections: “Introduction to JavaScript,” “Functions,” “‘For’ Loops in JavaScript,” “‘While’ Loops in JavaScript,” and “Control Flow.”
  6. Beginning JavaScript: Read Chapter 4 (Common Mistakes, Debugging, and Error Handling).

Week 2: Learn JavaScript Objects, the Browser Object Model (BOM), and Events; Learn jQuery

  1. Beginning JavaScript: Read Chapter 5 (JavaScript — An Object- Based Language).
  2. JavaScriptIsSexy.com: Read my article, JavaScript Objects in Detail
  3. Codecademy.com: Work through the last three sections of the Codecademy JavaScript track: “Data Structures,” “Objects 1,” and “Objects 2.”
  4. Beginning JavaScript: Read Chapter 6 (Programming the Browser).
  5. Beginning JavaScript: Read Chapter 15 (JavaScript Frameworks), and stop just after you complete this section: “Digging Deeper Into jQuery”.
  6. Codecademy.com: Work through the entire jQuery Track on Codecademy.

Weeks 3 and 4

Week 3: HTML Forms and Frames; JavaScript Strings; Build Your First Interactive Website

  1. Beginning JavaScript: Read Chapter 7 (HTML Forms: Interacting with the User).
  2. Beginning JavaScript: Read Chapter 8 (Windows and Frames).
  3. Beginning JavaScript: Read Chapter 9 (String Manipulation).
  4. Codecademy.com: Now, make your first cool website. Work through the entire Make an Interactive Website track on Codecademy.

Week 4: JavaScript Date, Timers, and Cookies

  1. Beginning JavaScript: Read Chapter 10 (Date, Time, and Timers).
  2. Beginning JavaScript: Read Chapter 11 (Storing Information: Cookies).

Weeks 5 and 6

Week 5: JavaScript “this,” Variable Scope, and Hoisting, the DOM, JavaScript XML, and AJAX

  1. JavaScriptIsSexy.com: Read my post JavaScript Variable Scope and Hoisting Explained
  2. JavaScriptIsSexy.com: Read my post Understand JavaScript’s “this” With Clarity, and Master It
  3. Beginning JavaScript: Read Chapter 12 (Dynamic HTML and the W3C Document Object Model).
  4. Beginning JavaScript: Read Chapter 14 (Ajax).

Week 6: Build a Real-World JavaScript Quiz Application

At this juncture, you have learned enough to build a solid JavaScript web application. Don’t proceed any further until you can successfully build this application I describe below. Don’t be afraid to ask questions on Stack Overflow, and do reread sections of the book to properly understand the concepts.

You are building a JavaScript quiz web application (you will use HTML and CSS as well) that will function as follows:

  • It is a simple quiz that has radio button choices, and it will show the quiz taker his or her score upon completion.
  • The quiz can show any number of questions and any number of choices.
  • Tally the user’s score and display the final score on the last page. The last page will only show the score, so remove the last question.
  • Use an array to store all the questions. Each question, along with its choices and correct answer, should be stored in an object. The array of questions should look similar to this (Notice that only one question is in this example array; you will add many questions):
    var allQuestions = [{question: “Who is Prime Minister of the United Kingdom?”, choices: [“David Cameron”, “Gordon Brown”, “Winston Churchill”, “Tony Blair”], correctAnswer:0}];
  • Dynamically (with document.getElementById or jQuery) remove the current question and add the next question, when the user clicks the “Next” button. The Next button will be the only button to navigate this version of the quiz.
  • You can ask for help in the comments below or preferably on Stack Overflow. You will likely to get a prompt and accurate answer on Stack Overflow.

Improve Your Quiz

You should be very comfortable with JavaScript, probably feeling like a Jedi. No, you are not. Not yet. You must keep using your newly acquired knowledge and skills as often as possible to keep learning and improving.

Improve Your Quiz Application From Earlier:

  • Add client-side data validation: make sure the user answers each question before proceeding to the next question.
  • Add a “Back” button to allow the user to go back and change her answer. The user can go back up to the first question. For the questions that the user has answered already, be sure to show the radio button selected, so that the user is not forced to answer the questions again, which she has completed.
  • Use jQuery to add animation (fade out the current question and fade in the next question).
  • Test the quiz on IE 9, and fix any bugs. This will give you a good workout 😉
  • Store the quiz questions in an external JSON file.
  • Add user authentication: allow users to log in, and save their login credentials to local storage (HTML5 browser storage).
  • Use cookies to remember the user, and show a “Welcome, ‘First Name’” message when the user returns to the quiz.

Week 7 (Extra Credit)

Getting Started with Git; Objective Oriented JavaScript; Improve Your Quiz Even More

  1. CodeSchool.com: Take the FREE Try Git course.
  2. JavaScriptIsSexy.com: Read my post, OOP In JavaScript: What You NEED to Know.
  3. Improve Your Quiz Application Even Further:
    — Use Twitter Bootstrap for the entire page layout, including the quiz elements to make it look more polished. As an added bonus, use the tabs user interface component from Twitter Bootstrap and show 4 different quizzes, one on each tab.
    Learn Handlebars.js and add Handlebars.js templating to the quiz. You should no longer have any HTML in your JavaScript code. Your quiz is getting more advanced, bit by bit.
    — Keep a record of all the users who take the quiz and show each user how his or her score ranks among the scores from other quiz takers.
  4. Later (after you have learned Backbone.js and Node.js or Meteor.js), you can use these technologies to refactor your quiz code and turn the same quiz into a sophisticated, single-page, modern web application built with the latest JavaScript frameworks. And you will store the users’ authentication credentials and scores in a MongoDB database.
  5. Next: Decide on a personal project to build, and start building your project promptly (while everything remains fresh in your memory). Use the book as a reference. And of course be an active member on Stack Overflow: ask questions and answer other programmers’ questions. I am confident you will be able to answer a number of questions.

Continue Improving

    1. Learn Backbone.js Completely, if you want to be a front-end developer or learn how to develop web applications with a JavaScript front-end framework.

Alternatively, if you want to develop complete applications, that is, the front-end and the backend, learn Meteor.js properly.

  1. At this point, you will definitely need my book, MongoDB for JavaScript Applications, to help you build your own jQuery, Backbone.js, Node.js, or Meteor.js applications, since none of the noted resources, or any other book for that matter, cover MongoDB in depth for JavaScript applications.
  2. Learn Intermediate and Advanced JavaScript
  3. Learn Node.js Completely and With Confidence

Words of Encouragement

I wish you success with your studies and in your JavaScript career. Never give up! When you are struggling and feeling incompetent (you may from time to time), always remember that most (probably all) programmers, new and experienced alike, feel this way sometimes, or have felt this way at some point during their programming career.

Remember to dig deep and don’t get frustrated; just carry on and stick with the task until you figure it out, for a worthwhile reward awaits you when you triumph in the end: programming is fun, liberating, and lucrative. The ecstasy one gets from building an application is a powerful feeling that you must experience to understand. Even more satisfying, however, is the empowerment you experience when you realize you have attained the skill and knowledge to build applications from scratch, to change the world with any idea you dream up.

The moment will come when you realize that all the difficulties you endured were worth while. Just as the millions before you have triumphed, so too, you will vanquish the toughest bugs, master the incomprehensible topics, and overcome the seemingly impossible tasks.

Feel free to share your links with us below when you build something, even if it is a tiny, itsy-bitsy project. :)

一文读懂机器学习,大数据/自然语言处理/算法全有了

来自: 计算机的潜意识 – 博客园

链接:http://www.cnblogs.com/subconscious/p/4107357.html

在本篇文章中,我将对机器学习做个概要的介绍。本文的目的是能让即便完全不了解机器学习的人也能了解机器学习,并且上手相关的实践。这篇文档也算是EasyPR开发的番外篇,从这里开始,必须对机器学习了解才能进一步介绍EasyPR的内核。当然,本文也面对一般读者,不会对阅读有相关的前提要求。

在进入正题前,我想读者心中可能会有一个疑惑:机器学习有什么重要性,以至于要阅读完这篇非常长的文章呢?

我并不直接回答这个问题前。相反,我想请大家看两张图,下图是图一:

图1 机器学习界的执牛耳者与互联网界的大鳄的联姻

这幅图上上的三人是当今机器学习界的执牛耳者。中间的是Geoffrey Hinton, 加拿大多伦多大学的教授,如今被聘为“Google大脑”的负责人。右边的是Yann LeCun, 纽约大学教授,如今是Facebook人工智能实验室的主任。而左边的大家都很熟悉,Andrew Ng,中文名吴恩达,斯坦福大学副教授,如今也是“百度大脑”的负责人与百度首席科学家。这三位都是目前业界炙手可热的大牛,被互联网界大鳄求贤若渴的聘请,足见他们的重要性。而他们的研究方向,则全部都是机器学习的子类–深度学习。

下图是图二:

图2 语音助手产品

这幅图上描述的是什么?Windows Phone上的语音助手Cortana,名字来源于《光环》中士官长的助手。相比其他竞争对手,微软很迟才推出这个服务。Cortana背后的核心技术是什么,为什么它能够听懂人的语音?事实上,这个技术正是机器学习。机器学习是所有语音助手产品(包括Apple的siri与Google的Now)能够跟人交互的关键技术。

通过上面两图,我相信大家可以看出机器学习似乎是一个很重要的,有很多未知特性的技术。学习它似乎是一件有趣的任务。实际上,学习机器学习不仅可以帮助我们了解互联网界最新的趋势,同时也可以知道伴随我们的便利服务的实现技术。

机器学习是什么,为什么它能有这么大的魔力,这些问题正是本文要回答的。同时,本文叫做“从机器学习谈起”,因此会以漫谈的形式介绍跟机器学习相关的所有内容,包括学科(如数据挖掘、计算机视觉等),算法(神经网络,svm)等等。本文的主要目录如下:

1、一个故事说明什么是机器学习

2、机器学习的定义

3、机器学习的范围

4、机器学习的方法

5、机器学习的应用–大数据

6、机器学习的子类–深度学习

7、机器学习的父类–人工智能

8、机器学习的思考–计算机的潜意识

9、总结

10、后记

1、一个故事说明什么是机器学习

机器学习这个词是让人疑惑的,首先它是英文名称Machine Learning(简称ML)的直译,在计算界Machine一般指计算机。这个名字使用了拟人的手法,说明了这门技术是让机器“学习”的技术。但是计算机是死的,怎么可能像人类一样“学习”呢?

传统上如果我们想让计算机工作,我们给它一串指令,然后它遵照这个指令一步步执行下去。有因有果,非常明确。但这样的方式在机器学习中行不通。机器学习根本不接受你输入的指令,相反,它接受你输入的数据! 也就是说,机器学习是一种让计算机利用数据而不是指令来进行各种工作的方法。这听起来非常不可思议,但结果上却是非常可行的。“统计”思想将在你学习“机器学习”相关理念时无时无刻不伴随,相关而不是因果的概念将是支撑机器学习能够工作的核心概念。你会颠覆对你以前所有程序中建立的因果无处不在的根本理念。

下面我通过一个故事来简单地阐明什么是机器学习。这个故事比较适合用在知乎上作为一个概念的阐明。在这里,这个故事没有展开,但相关内容与核心是存在的。如果你想简单的了解一下什么是机器学习,那么看完这个故事就足够了。如果你想了解机器学习的更多知识以及与它关联紧密的当代技术,那么请你继续往下看,后面有更多的丰富的内容。

这个例子来源于我真实的生活经验,我在思考这个问题的时候突然发现它的过程可以被扩充化为一个完整的机器学习的过程,因此我决定使用这个例子作为所有介绍的开始。这个故事称为“等人问题”。

我相信大家都有跟别人相约,然后等人的经历。现实中不是每个人都那么守时的,于是当你碰到一些爱迟到的人,你的时间不可避免的要浪费。我就碰到过这样的一个例子。

对我的一个朋友小Y而言,他就不是那么守时,最常见的表现是他经常迟到。当有一次我跟他约好3点钟在某个麦当劳见面时,在我出门的那一刻我突然想到一个问题:我现在出发合适么?我会不会又到了地点后,花上30分钟去等他?我决定采取一个策略解决这个问题。

要想解决这个问题,有好几种方法。第一种方法是采用知识:我搜寻能够解决这个问题的知识。但很遗憾,没有人会把如何等人这个问题作为知识传授,因此我不可能找到已有的知识能够解决这个问题。第二种方法是问他人:我去询问他人获得解决这个问题的能力。但是同样的,这个问题没有人能够解答,因为可能没人碰上跟我一样的情况。第三种方法是准则法:我问自己的内心,我有否设立过什么准则去面对这个问题?例如,无论别人如何,我都会守时到达。但我不是个死板的人,我没有设立过这样的规则。

事实上,我相信有种方法比以上三种都合适。我把过往跟小Y相约的经历在脑海中重现一下,看看跟他相约的次数中,迟到占了多大的比例。而我利用这来预测他这次迟到的可能性。如果这个值超出了我心里的某个界限,那我选择等一会再出发。假设我跟小Y约过5次,他迟到的次数是1次,那么他按时到的比例为80%,我心中的阈值为70%,我认为这次小Y应该不会迟到,因此我按时出门。如果小Y在5次迟到的次数中占了4次,也就是他按时到达的比例为20%,由于这个值低于我的阈值,因此我选择推迟出门的时间。这个方法从它的利用层面来看,又称为经验法。在经验法的思考过程中,我事实上利用了以往所有相约的数据。因此也可以称之为依据数据做的判断。

依据数据所做的判断跟机器学习的思想根本上是一致的。刚才的思考过程我只考虑“频次”这种属性。在真实的机器学习中,这可能都不算是一个应用。一般的机器学习模型至少考虑两个量:一个是因变量,也就是我们希望预测的结果,在这个例子里就是小Y迟到与否的判断。另一个是自变量,也就是用来预测小Y是否迟到的量。假设我把时间作为自变量,譬如我发现小Y所有迟到的日子基本都是星期五,而在非星期五情况下他基本不迟到。于是我可以建立一个模型,来模拟小Y迟到与否跟日子是否是星期五的概率。见下图:

图3 决策树模型

这样的图就是一个最简单的机器学习模型,称之为决策树。当我们考虑的自变量只有一个时,情况较为简单。如果把我们的自变量再增加一个。例如小Y迟到的部分情况时是在他开车过来的时候(你可以理解为他开车水平较臭,或者路较堵)。于是我可以关联考虑这些信息。建立一个更复杂的模型,这个模型包含两个自变量与一个因变量。

再更复杂一点,小Y的迟到跟天气也有一定的原因,例如下雨的时候,这时候我需要考虑三个自变量。

如果我希望能够预测小Y迟到的具体时间,我可以把他每次迟到的时间跟雨量的大小以及前面考虑的自变量统一建立一个模型。于是我的模型可以预测值,例如他大概会迟到几分钟。这样可以帮助我更好的规划我出门的时间。在这样的情况下,决策树就无法很好地支撑了,因为决策树只能预测离散值。我们可以用节2所介绍的线型回归方法建立这个模型。

如果我把这些建立模型的过程交给电脑。比如把所有的自变量和因变量输入,然后让计算机帮我生成一个模型,同时让计算机根据我当前的情况,给出我是否需要迟出门,需要迟几分钟的建议。那么计算机执行这些辅助决策的过程就是机器学习的过程。

机器学习方法是计算机利用已有的数据(经验),得出了某种模型(迟到的规律),并利用此模型预测未来(是否迟到)的一种方法。

通过上面的分析,可以看出机器学习与人类思考的经验过程是类似的,不过它能考虑更多的情况,执行更加复杂的计算。事实上,机器学习的一个主要目的就是把人类思考归纳经验的过程转化为计算机通过对数据的处理计算得出模型的过程。经过计算机得出的模型能够以近似于人的方式解决很多灵活复杂的问题。

下面,我会开始对机器学习的正式介绍,包括定义、范围,方法、应用等等,都有所包含。

2、机器学习的定义

从广义上来说,机器学习是一种能够赋予机器学习的能力以此让它完成直接编程无法完成的功能的方法。但从实践的意义上来说,机器学习是一种通过利用数据,训练出模型,然后使用模型预测的一种方法。

让我们具体看一个例子。

图4 房价的例子

拿国民话题的房子来说。现在我手里有一栋房子需要售卖,我应该给它标上多大的价格?房子的面积是100平方米,价格是100万,120万,还是140万?

很显然,我希望获得房价与面积的某种规律。那么我该如何获得这个规律?用报纸上的房价平均数据么?还是参考别人面积相似的?无论哪种,似乎都并不是太靠谱。

我现在希望获得一个合理的,并且能够最大程度的反映面积与房价关系的规律。于是我调查了周边与我房型类似的一些房子,获得一组数据。这组数据中包含了大大小小房子的面积与价格,如果我能从这组数据中找出面积与价格的规律,那么我就可以得出房子的价格。

对规律的寻找很简单,拟合出一条直线,让它“穿过”所有的点,并且与各个点的距离尽可能的小。

通过这条直线,我获得了一个能够最佳反映房价与面积规律的规律。这条直线同时也是一个下式所表明的函数:

房价 = 面积 * a + b

上述中的a、b都是直线的参数。获得这些参数以后,我就可以计算出房子的价格。

假设a = 0.75,b = 50,则房价 = 100 * 0.75 + 50 = 125万。这个结果与我前面所列的100万,120万,140万都不一样。由于这条直线综合考虑了大部分的情况,因此从“统计”意义上来说,这是一个最合理的预测。

在求解过程中透露出了两个信息:

1、房价模型是根据拟合的函数类型决定的。如果是直线,那么拟合出的就是直线方程。如果是其他类型的线,例如抛物线,那么拟合出的就是抛物线方程。机器学习有众多算法,一些强力算法可以拟合出复杂的非线性模型,用来反映一些不是直线所能表达的情况。

2、如果我的数据越多,我的模型就越能够考虑到越多的情况,由此对于新情况的预测效果可能就越好。这是机器学习界“数据为王”思想的一个体现。一般来说(不是绝对),数据越多,最后机器学习生成的模型预测的效果越好。

通过我拟合直线的过程,我们可以对机器学习过程做一个完整的回顾。首先,我们需要在计算机中存储历史的数据。接着,我们将这些 数据通过机器学习算法进行处理,这个过程在机器学习中叫做“训练”,处理的结果可以被我们用来对新的数据进行预测,这个结果一般称之为“模型”。对新数据 的预测过程在机器学习中叫做“预测”。“训练”与“预测”是机器学习的两个过程,“模型”则是过程的中间输出结果,“训练”产生“模型”,“模型”指导 “预测”。

让我们把机器学习的过程与人类对历史经验归纳的过程做个比对。

图5 机器学习与人类思考的类比

人类在成长、生活过程中积累了很多的历史与经验。人类定期地对这些经验进行“归纳”,获得了生活的“规律”。当人类遇到未知的问题或者需要对未来进行“推测”的时候,人类使用这些“规律”,对未知问题与未来进行“推测”,从而指导自己的生活和工作。

机器学习中的“训练”与“预测”过程可以对应到人类的“归纳”和“推测”过程。通过这样的对应,我们可以发现,机器学习的思想并不复杂,仅仅是对人类在生活中学习成长的一个模拟。由于机器学习不是基于编程形成的结果,因此它的处理过程不是因果的逻辑,而是通过归纳思想得出的相关性结论。

这也可以联想到人类为什么要学习历史,历史实际上是人类过往经验的总结。有句话说得很好,“历史往往不一样,但历史总是惊人的相似”。通过学习历史,我们从历史中归纳出人生与国家的规律,从而指导我们的下一步工作,这是具有莫大价值的。当代一些人忽视了历史的本来价值,而是把其作为一种宣扬功绩的手段,这其实是对历史真实价值的一种误用。

3、机器学习的范围

上文虽然说明了机器学习是什么,但是并没有给出机器学习的范围。

其实,机器学习跟模式识别,统计学习,数据挖掘,计算机视觉,语音识别,自然语言处理等领域有着很深的联系。

从范围上来说,机器学习跟模式识别,统计学习,数据挖掘是类似的,同时,机器学习与其他领域的处理技术的结合,形成了计算机视觉、语音识别、自然语言处理等交叉学科。因此,一般说数据挖掘时,可以等同于说机器学习。同时,我们平常所说的机器学习应用,应该是通用的,不仅仅局限在结构化数据,还有图像,音频等应用。

在这节对机器学习这些相关领域的介绍有助于我们理清机器学习的应用场景与研究范围,更好的理解后面的算法与应用层次。

下图是机器学习所牵扯的一些相关范围的学科与研究领域。

图6 机器学习与相关学科

模式识别

模式识别=机器学习。两者的主要区别在于前者是从工业界发展起来的概念,后者则主要源自计算机学科。在著名的《Pattern Recognition And Machine Learning》这本书中,Christopher M. Bishop在开头是这样说的“模式识别源自工业界,而机器学习来自于计算机学科。不过,它们中的活动可以被视为同一个领域的两个方面,同时在过去的10年间,它们都有了长足的发展”。

数据挖掘

数据挖掘=机器学习+数据库。这几年数据挖掘的概念实在是太耳熟能详。几乎等同于炒作。但凡说数据挖掘都会吹嘘数据挖掘如何如何,例如从数据中挖出金子,以及将废弃的数据转化为价值等等。但是,我尽管可能会挖出金子,但我也可能挖的是“石头”啊。这个说法的意思是,数据挖掘仅仅是一种思考方式,告诉我们应该尝试从数据中挖掘出知识,但不是每个数据都能挖掘出金子的,所以不要神话它。一个系统绝对不会因为上了一个数据挖掘模块就变得无所不能(这是IBM最喜欢吹嘘的),恰恰相反,一个拥有数据挖掘思维的人员才是关键,而且他还必须对数据有深刻的认识,这样才可能从数据中导出模式指引业务的改善。大部分数据挖掘中的算法是机器学习的算法在数据库中的优化。

统计学习

统计学习近似等于机器学习。统计学习是个与机器学习高度重叠的学科。因为机器学习中的大多数方法来自统计学,甚至可以认为,统计学的发展促进机器学习的繁荣昌盛。例如著名的支持向量机算法,就是源自统计学科。但是在某种程度上两者是有分别的,这个分别在于:统计学习者重点关注的是统计模型的发展与优化,偏数学,而机器学习者更关注的是能够解决问题,偏实践,因此机器学习研究者会重点研究学习算法在计算机上执行的效率与准确性的提升。

计算机视觉

计算机视觉=图像处理+机器学习。图像处理技术用于将图像处理为适合进入机器学习模型中的输入,机器学习则负责从图像中识别出相关的模式。计算机视觉相关的应用非常的多,例如百度识图、手写字符识别、车牌识别等等应用。这个领域是应用前景非常火热的,同时也是研究的热门方向。随着机器学习的新领域深度学习的发展,大大促进了计算机图像识别的效果,因此未来计算机视觉界的发展前景不可估量。

语音识别

语音识别=语音处理+机器学习。语音识别就是音频处理技术与机器学习的结合。语音识别技术一般不会单独使用,一般会结合自然语言处理的相关技术。目前的相关应用有苹果的语音助手siri等。

自然语言处理

自然语言处理=文本处理+机器学习。自然语言处理技术主要是让机器理解人类的语言的一门领域。在自然语言处理技术中,大量使用了编译原理相关的技术,例如词法分析,语法分析等等,除此之外,在理解这个层面,则使用了语义理解,机器学习等技术。作为唯一由人类自身创造的符号,自然语言处理一直是机器学习界不断研究的方向。按照百度机器学习专家余凯的说法“听与看,说白了就是阿猫和阿狗都会的,而只有语言才是人类独有的”。如何利用机器学习技术进行自然语言的的深度理解,一直是工业和学术界关注的焦点。

可以看出机器学习在众多领域的外延和应用。机器学习技术的发展促使了很多智能领域的进步,改善着我们的生活。

4、机器学习的方法

通过上节的介绍我们知晓了机器学习的大致范围,那么机器学习里面究竟有多少经典的算法呢?在这个部分我会简要介绍一下机器学习中的经典代表方法。这部分介绍的重点是这些方法内涵的思想,数学与实践细节不会在这讨论。

1、回归算法

在大部分机器学习课程中,回归算法都是介绍的第一个算法。原因有两个:一.回归算法比较简单,介绍它可以让人平滑地从统计学迁移到机器学习中。二.回归算法是后面若干强大算法的基石,如果不理解回归算法,无法学习那些强大的算法。回归算法有两个重要的子类:即线性回归和逻辑回归。

线性回归就是我们前面说过的房价求解问题。如何拟合出一条直线最佳匹配我所有的数据?一般使用“最小二乘法”来求解。“最小二乘法”的思想是这样的,假设我们拟合出的直线代表数据的真实值,而观测到的数据代表拥有误差的值。为了尽可能减小误差的影响,需要求解一条直线使所有误差的平方和最小。最小二乘法将最优问题转化为求函数极值问题。函数极值在数学上我们一般会采用求导数为0的方法。但这种做法并不适合计算机,可能求解不出来,也可能计算量太大。

计算机科学界专门有一个学科叫“数值计算”,专门用来提升计算机进行各类计算时的准确性和效率问题。例如,著名的“梯度下降”以及“牛顿法”就是数值计算中的经典算法,也非常适合来处理求解函数极值的问题。梯度下降法是解决回归模型中最简单且有效的方法之一。从严格意义上来说,由于后文中的神经网络和推荐算法中都有线性回归的因子,因此梯度下降法在后面的算法实现中也有应用。

逻辑回归是一种与线性回归非常类似的算法,但是,从本质上讲,线型回归处理的问题类型与逻辑回归不一致。线性回归处理的是数值问题,也就是最后预测出的结果是数字,例如房价。而逻辑回归属于分类算法,也就是说,逻辑回归预测结果是离散的分类,例如判断这封邮件是否是垃圾邮件,以及用户是否会点击此广告等等。

实现方面的话,逻辑回归只是对对线性回归的计算结果加上了一个Sigmoid函数,将数值结果转化为了0到1之间的概率(Sigmoid函数的图像一般来说并不直观,你只需要理解对数值越大,函数越逼近1,数值越小,函数越逼近0),接着我们根据这个概率可以做预测,例如概率大于0.5,则这封邮件就是垃圾邮件,或者肿瘤是否是恶性的等等。从直观上来说,逻辑回归是画出了一条分类线,见下图。

图7 逻辑回归的直观解释

假设我们有一组肿瘤患者的数据,这些患者的肿瘤中有些是良性的(图中的蓝色点),有些是恶性的(图中的红色点)。这里肿瘤的红蓝色可以被称作数据的“标签”。同时每个数据包括两个“特征”:患者的年龄与肿瘤的大小。我们将这两个特征与标签映射到这个二维空间上,形成了我上图的数据。

当我有一个绿色的点时,我该判断这个肿瘤是恶性的还是良性的呢?根据红蓝点我们训练出了一个逻辑回归模型,也就是图中的分类线。这时,根据绿点出现在分类线的左侧,因此我们判断它的标签应该是红色,也就是说属于恶性肿瘤。

逻辑回归算法划出的分类线基本都是线性的(也有划出非线性分类线的逻辑回归,不过那样的模型在处理数据量较大的时候效率会很低),这意味着当两类之间的界线不是线性时,逻辑回归的表达能力就不足。下面的两个算法是机器学习界最强大且重要的算法,都可以拟合出非线性的分类线。

2、神经网络

神经网络(也称之为人工神经网络,ANN)算法是80年代机器学习界非常流行的算法,不过在90年代中途衰落。现在,携着“深度学习”之势,神经网络重装归来,重新成为最强大的机器学习算法之一。

神经网络的诞生起源于对大脑工作机理的研究。早期生物界学者们使用神经网络来模拟大脑。机器学习的学者们使用神经网络进行机器学习的实验,发现在视觉与语音的识别上效果都相当好。在BP算法(加速神经网络训练过程的数值算法)诞生以后,神经网络的发展进入了一个热潮。BP算法的发明人之一是前面介绍的机器学习大牛Geoffrey Hinton(图1中的中间者)。

具体说来,神经网络的学习机理是什么?简单来说,就是分解与整合。在著名的Hubel-Wiesel试验中,学者们研究猫的视觉分析机理是这样的。

图8 Hubel-Wiesel试验与大脑视觉机理

比方说,一个正方形,分解为四个折线进入视觉处理的下一层中。四个神经元分别处理一个折线。每个折线再继续被分解为两条直线,每条直线再被分解为黑白两个面。于是,一个复杂的图像变成了大量的细节进入神经元,神经元处理以后再进行整合,最后得出了看到的是正方形的结论。这就是大脑视觉识别的机理,也是神经网络工作的机理。

让我们看一个简单的神经网络的逻辑架构。在这个网络中,分成输入层,隐藏层,和输出层。输入层负责接收信号,隐藏层负责对数据的分解与处理,最后的结果被整合到输出层。每层中的一个圆代表一个处理单元,可以认为是模拟了一个神经元,若干个处理单元组成了一个层,若干个层再组成了一个网络,也就是”神经网络”。

图9 神经网络的逻辑架构

在神经网络中,每个处理单元事实上就是一个逻辑回归模型,逻辑回归模型接收上层的输入,把模型的预测结果作为输出传输到下一个层次。通过这样的过程,神经网络可以完成非常复杂的非线性分类。

下图会演示神经网络在图像识别领域的一个著名应用,这个程序叫做LeNet,是一个基于多个隐层构建的神经网络。通过LeNet可以识别多种手写数字,并且达到很高的识别精度与拥有较好的鲁棒性。

图10 LeNet的效果展示

右下方的方形中显示的是输入计算机的图像,方形上方的红色字样“answer”后面显示的是计算机的输出。左边的三条竖直的图像列显示的是神经网络中三个隐藏层的输出,可以看出,随着层次的不断深入,越深的层次处理的细节越低,例如层3基本处理的都已经是线的细节了。LeNet的发明人就是前文介绍过的机器学习的大牛Yann LeCun(图1右者)。

进入90年代,神经网络的发展进入了一个瓶颈期。其主要原因是尽管有BP算法的加速,神经网络的训练过程仍然很困难。因此90年代后期支持向量机(SVM)算法取代了神经网络的地位。

3、SVM(支持向量机)

支持向量机算法是诞生于统计学习界,同时在机器学习界大放光彩的经典算法。

支持向量机算法从某种意义上来说是逻辑回归算法的强化:通过给予逻辑回归算法更严格的优化条件,支持向量机算法可以获得比逻辑回归更好的分类界线。但是如果没有某类函数技术,则支持向量机算法最多算是一种更好的线性分类技术。

但是,通过跟高斯“核”的结合,支持向量机可以表达出非常复杂的分类界线,从而达成很好的的分类效果。“核”事实上就是一种特殊的函数,最典型的特征就是可以将低维的空间映射到高维的空间。

例如下图所示:

图11 支持向量机图例

我们如何在二维平面划分出一个圆形的分类界线?在二维平面可能会很困难,但是通过“核”可以将二维空间映射到三维空间,然后使用一个线性平面就可以达成类似效果。也就是说,二维平面划分出的非线性分类界线可以等价于三维平面的线性分类界线。于是,我们可以通过在三维空间中进行简单的线性划分就可以达到在二维平面中的非线性划分效果。

图12 三维空间的切割

支持向量机是一种数学成分很浓的机器学习算法(相对的,神经网络则有生物科学成分)。在算法的核心步骤中,有一步证明,即将数据从低维映射到高维不会带来最后计算复杂性的提升。于是,通过支持向量机算法,既可以保持计算效率,又可以获得非常好的分类效果。因此支持向量机在90年代后期一直占据着机器学习中最核心的地位,基本取代了神经网络算法。直到现在神经网络借着深度学习重新兴起,两者之间才又发生了微妙的平衡转变。

4、聚类算法

前面的算法中的一个显著特征就是我的训练数据中包含了标签,训练出的模型可以对其他未知数据预测标签。在下面的算法中,训练数据都是不含标签的,而算法的目的则是通过训练,推测出这些数据的标签。这类算法有一个统称,即无监督算法(前面有标签的数据的算法则是有监督算法)。无监督算法中最典型的代表就是聚类算法。

让我们还是拿一个二维的数据来说,某一个数据包含两个特征。我希望通过聚类算法,给他们中不同的种类打上标签,我该怎么做呢?简单来说,聚类算法就是计算种群中的距离,根据距离的远近将数据划分为多个族群。

聚类算法中最典型的代表就是K-Means算法。

5、降维算法

降维算法也是一种无监督学习算法,其主要特征是将数据从高维降低到低维层次。在这里,维度其实表示的是数据的特征量的大小,例如,房价包含房子的长、宽、面积与房间数量四个特征,也就是维度为4维的数据。可以看出来,长与宽事实上与面积表示的信息重叠了,例如面积=长 × 宽。通过降维算法我们就可以去除冗余信息,将特征减少为面积与房间数量两个特征,即从4维的数据压缩到2维。于是我们将数据从高维降低到低维,不仅利于表示,同时在计算上也能带来加速。

刚才说的降维过程中减少的维度属于肉眼可视的层次,同时压缩也不会带来信息的损失(因为信息冗余了)。如果肉眼不可视,或者没有冗余的特征,降维算法也能工作,不过这样会带来一些信息的损失。但是,降维算法可以从数学上证明,从高维压缩到的低维中最大程度地保留了数据的信息。因此,使用降维算法仍然有很多的好处。

降维算法的主要作用是压缩数据与提升机器学习其他算法的效率。通过降维算法,可以将具有几千个特征的数据压缩至若干个特征。另外,降维算法的另一个好处是数据的可视化,例如将5维的数据压缩至2维,然后可以用二维平面来可视。降维算法的主要代表是PCA算法(即主成分分析算法)。

6、推荐算法

推荐算法是目前业界非常火的一种算法,在电商界,如亚马逊,天猫,京东等得到了广泛的运用。推荐算法的主要特征就是可以自动向用户推荐他们最感兴趣的东西,从而增加购买率,提升效益。推荐算法有两个主要的类别:

一类是基于物品内容的推荐,是将与用户购买的内容近似的物品推荐给用户,这样的前提是每个物品都得有若干个标签,因此才可以找出与用户购买物品类似的物品,这样推荐的好处是关联程度较大,但是由于每个物品都需要贴标签,因此工作量较大。

另一类是基于用户相似度的推荐,则是将与目标用户兴趣相同的其他用户购买的东西推荐给目标用户,例如小A历史上买了物品B和C,经过算法分析,发现另一个与小A近似的用户小D购买了物品E,于是将物品E推荐给小A。

两类推荐都有各自的优缺点,在一般的电商应用中,一般是两类混合使用。推荐算法中最有名的算法就是协同过滤算法。

7、其他

除了以上算法之外,机器学习界还有其他的如高斯判别,朴素贝叶斯,决策树等等算法。但是上面列的六个算法是使用最多,影响最广,种类最全的典型。机器学习界的一个特色就是算法众多,发展百花齐放。

下面做一个总结,按照训练的数据有无标签,可以将上面算法分为监督学习算法和无监督学习算法,但推荐算法较为特殊,既不属于监督学习,也不属于非监督学习,是单独的一类。

监督学习算法:线性回归,逻辑回归,神经网络,SVM

无监督学习算法:聚类算法,降维算法

特殊算法:推荐算法

除了这些算法以外,有一些算法的名字在机器学习领域中也经常出现。但他们本身并不算是一个机器学习算法,而是为了解决某个子问题而诞生的。你可以理解他们为以上算法的子算法,用于大幅度提高训练过程。其中的代表有:梯度下降法,主要运用在线型回归,逻辑回归,神经网络,推荐算法中;牛顿法,主要运用在线型回归中;BP算法,主要运用在神经网络中;SMO算法,主要运用在SVM中。

5、机器学习的应用–大数据

说完机器学习的方法,下面要谈一谈机器学习的应用了。无疑,在2010年以前,机器学习的应用在某些特定领域发挥了巨大的作用,如车牌识别,网络攻击防范,手写字符识别等等。但是,从2010年以后,随着大数据概念的兴起,机器学习大量的应用都与大数据高度耦合,几乎可以认为大数据是机器学习应用的最佳场景。

譬如,但凡你能找到的介绍大数据魔力的文章,都会说大数据如何准确准确预测到了某些事。例如经典的Google利用大数据预测了H1N1在美国某小镇的爆发。

图13 Google成功预测H1N1

百度预测2014年世界杯,从淘汰赛到决赛全部预测正确。

图14 百度世界杯成功预测了所有比赛结果

这些实在太神奇了,那么究竟是什么原因导致大数据具有这些魔力的呢?简单来说,就是机器学习技术。正是基于机器学习技术的应用,数据才能发挥其魔力。

大数据的核心是利用数据的价值,机器学习是利用数据价值的关键技术,对于大数据而言,机器学习是不可或缺的。相反,对于机器学习而言,越多的数据会越 可能提升模型的精确性,同时,复杂的机器学习算法的计算时间也迫切需要分布式计算与内存计算这样的关键技术。因此,机器学习的兴盛也离不开大数据的帮助。 大数据与机器学习两者是互相促进,相依相存的关系。

机器学习与大数据紧密联系。但是,必须清醒的认识到,大数据并不等同于机器学习,同理,机器学习也不等同于大数据。大数据中包含有分布式计算,内存数据库,多维分析等等多种技术。单从分析方法来看,大数据也包含以下四种分析方法:

1、大数据,小分析:即数据仓库领域的OLAP分析思路,也就是多维分析思想。

2、大数据,大分析:这个代表的就是数据挖掘与机器学习分析法。

3、流式分析:这个主要指的是事件驱动架构。

4、查询分析:经典代表是NoSQL数据库。

也就是说,机器学习仅仅是大数据分析中的一种而已。尽管机器学习的一些结果具有很大的魔力,在某种场合下是大数据价值最好的说明。但这并不代表机器学习是大数据下的唯一的分析方法。

机器学习与大数据的结合产生了巨大的价值。基于机器学习技术的发展,数据能够“预测”。对人类而言,积累的经验越丰富,阅历也广泛,对未来的判断越准确。例如常说的“经验丰富”的人比“初出茅庐”的小伙子更有工作上的优势,就在于经验丰富的人获得的规律比他人更准确。而在机器学习领域,根据著名的一个实验,有效的证实了机器学习界一个理论:即机器学习模型的数据越多,机器学习的预测的效率就越好。见下图:

图15 机器学习准确率与数据的关系

通过这张图可以看出,各种不同算法在输入的数据量达到一定级数后,都有相近的高准确度。于是诞生了机器学习界的名言:成功的机器学习应用不是拥有最好的算法,而是拥有最多的数据!

在大数据的时代,有好多优势促使机器学习能够应用更广泛。例如随着物联网和移动设备的发展,我们拥有的数据越来越多,种类也包括图片、文本、视频等非结构化数据,这使得机器学习模型可以获得越来越多的数据。同时大数据技术中的分布式计算Map-Reduce使得机器学习的速度越来越快,可以更方便的使用。种种优势使得在大数据时代,机器学习的优势可以得到最佳的发挥。

6、机器学习的子类–深度学习

近来,机器学习的发展产生了一个新的方向,即“深度学习”。

虽然深度学习这四字听起来颇为高大上,但其理念却非常简单,就是传统的神经网络发展到了多隐藏层的情况。

在上文介绍过,自从90年代以后,神经网络已经消寂了一段时间。但是BP算法的发明人Geoffrey Hinton一直没有放弃对神经网络的研究。由于神经网络在隐藏层扩大到两个以上,其训练速度就会非常慢,因此实用性一直低于支持向量机。2006年,Geoffrey Hinton在科学杂志《Science》上发表了一篇文章,论证了两个观点:

1、多隐层的神经网络具有优异的特征学习能力,学习得到的特征对数据有更本质的刻画,从而有利于可视化或分类;

2、深度神经网络在训练上的难度,可以通过“逐层初始化” 来有效克服。

图16 Geoffrey Hinton与他的学生在Science上发表文章

通过这样的发现,不仅解决了神经网络在计算上的难度,同时也说明了深层神经网络在学习上的优异性。从此,神经网络重新成为了机器学习界中的主流强大学习技术。同时,具有多个隐藏层的神经网络被称为深度神经网络,基于深度神经网络的学习研究称之为深度学习。

由于深度学习的重要性质,在各方面都取得极大的关注,按照时间轴排序,有以下四个标志性事件值得一说:

  • 2012年6月 ,《纽约时报》披露了Google Brain项目,这个项目是由Andrew Ng和Map-Reduce发明人Jeff Dean共同主导,用16000个CPU Core的并行计算平台训练一种称为“深层神经网络”的机器学习模型,在语音识别和图像识别等领域获得了巨大的成功。Andrew Ng就是文章开始所介绍的机器学习的大牛(图1中右者)。
  • 2012年11月, 微软在中国天津的一次活动上公开演示了一个全自动的同声传译系统,讲演者用英文演讲,后台的计算机一气呵成自动完成语音识别、英中机器翻译,以及中文语音合成,效果非常流畅,其中支撑的关键技术是深度学习;
  • 2013年1月 ,在百度的年会上,创始人兼CEO李彦宏高调宣布要成立百度研究院,其中第一个重点方向就是深度学习,并为此而成立深度学习研究院(IDL)。
  • 2013年4月 ,《麻省理工学院技术评论》杂志将深度学习列为2013年十大突破性技术(Breakthrough Technology)之首。

图17 深度学习的发展热潮

文章开头所列的三位机器学习的大牛,不仅都是机器学习界的专家,更是深度学习研究领域的先驱。因此,使他们担任各个大型互联网公司技术掌舵者的原因不仅在于他们的技术实力,更在于他们研究的领域是前景无限的深度学习技术。

目前业界许多的图像识别技术与语音识别技术的进步都源于深度学习的发展,除了本文开头所提的Cortana等语音助手,还包括一些图像识别应用,其中典型的代表就是下图的百度识图功能。

图18 百度识图

深度学习属于机器学习的子类。基于深度学习的发展极大的促进了机器学习的地位提高,更进一步地,推动了业界对机器学习父类人工智能梦想的再次重视。

7、机器学习的父类–人工智能

人工智能是机器学习的父类。深度学习则是机器学习的子类。如果把三者的关系用图来表明的话,则是下图:

图19 深度学习、机器学习、人工智能三者关系

毫无疑问,人工智能(AI)是人类所能想象的科技界最突破性的发明了,某种意义上来说,人工智能就像游戏最终幻想的名字一样,是人类对于科技界的最终梦想。从50年代提出人工智能的理念以后,科技界,产业界不断在探索,研究。这段时间各种小说、电影都在以各种方式展现对于人工智能的想象。人类可以发明类似于人类的机器,这是多么伟大的一种理念!但事实上,自从50年代以后,人工智能的发展就磕磕碰碰,未有见到足够震撼的科学技术的进步。

总结起来,人工智能的发展经历了如下若干阶段,从早期的逻辑推理,到中期的专家系统,这些科研进步确实使我们离机器的智能有点接近了,但还有一大段距离。直到机器学习诞生以后,人工智能界感觉终于找对了方向。基于机器学习的图像识别和语音识别在某些垂直领域达到了跟人相媲美的程度。机器学习使人类第一次如此接近人工智能的梦想。

事实上,如果我们把人工智能相关的技术以及其他业界的技术做一个类比,就可以发现机器学习在人工智能中的重要地位不是没有理由的。

人类区别于其他物体,植物,动物的最主要区别,作者认为是 “智慧”。而智慧的最佳体现是什 么?

是计算能力么,应该不是,心算速度快的人我们一般称之为天才。

是反应能力么,也不是,反应快的人我们称之为灵敏。

是记忆能力么,也不是,记忆好的人我们一般称之为过目不忘。

是推理能力么,这样的人我也许会称他智力很高,类似“福尔摩斯”,但不会称他拥有智慧。

是知识能力么,这样的人我们称之为博闻广,也不会称他拥有智慧。

想想看我们一般形容谁有大智慧?圣人,诸如庄子,老子等。智慧是对生活的感悟,是对人生的积淀与思考,这与我们机器学习的思想何其相似?通过经验获取规律,指导人生与未来。没有经验就没有智慧。

图20 机器学习与智慧

那么,从计算机来看,以上的种种能力都有种种技术去应对。

例如计算能力我们有分布式计算,反应能力我们有事件驱动架构,检索能力我们有搜索引擎,知识存储能力我们有数据仓库,逻辑推理能力我们有专家系统,但是,唯有对应智慧中最显著特征的归纳与感悟能力,只有机器学习与之对应。这也是机器学习能力最能表征智慧的根本原因。

让我们再看一下机器人的制造,在我们具有了强大的计算,海量的存储,快速的检索,迅速的反应,优秀的逻辑推理后我们如果再配合上一个强大的智慧大脑,一个真正意义上的人工智能也许就会诞生,这也是为什么说在机器学习快速发展的现在,人工智能可能不再是梦想的原因。

人工智能的发展可能不仅取决于机器学习,更取决于前面所介绍的深度学习,深度学习技术由于深度模拟了人类大脑的构成,在视觉识别与语音识别上显著性的突破了原有机器学习技术的界限,因此极有可能是真正实现人工智能梦想的关键技术。无论是谷歌大脑还是百度大脑,都是通过海量层次的深度学习网络所构成的。也许借助于深度学习技术,在不远的将来,一个具有人类智能的计算机真的有可能实现。

最后再说一下题外话,由于人工智能借助于深度学习技术的快速发展,已经在某些地方引起了传统技术界达人的担忧。真实世界的“钢铁侠”,特斯拉CEO马斯克就是其中之一。最近马斯克在参加MIT讨论会时,就表达了对于人工智能的担忧。“人工智能的研究就类似于召唤恶魔,我们必须在某些地方加强注意。”

图21 马斯克与人工智能

尽管马斯克的担心有些危言耸听,但是马斯克的推理不无道理。“如果人工智能想要消除垃圾邮件的话,可能它最后的决定就是消灭人类。”马斯克认为预防此类现象的方法是引入政府的监管。在这里作者的观点与马斯克类似,在人工智能诞生之初就给其加上若干规则限制可能有效,也就是不应该使用单纯的机器学习,而应该是机器学习与规则引擎等系统的综合能够较好的解决这类问题。因为如果学习没有限制,极有可能进入某个误区,必须要加上某些引导。正如人类社会中,法律就是一个最好的规则,杀人者死就是对于人类在探索提高生产力时不可逾越的界限。

在这里,必须提一下这里的规则与机器学习引出的规律的不同,规律不是一个严格意义的准则,其代表的更多是概率上的指导,而规则则是神圣不可侵犯,不可修改的。规律可以调整,但规则是不能改变的。有效的结合规律与规则的特点,可以引导出一个合理的,可控的学习型人工智能。

8、机器学习的思考–计算机的潜意识

最后,作者想谈一谈关于机器学习的一些思考。主要是作者在日常生活总结出来的一些感悟。

回想一下我在节1里所说的故事,我把小Y过往跟我相约的经历做了一个罗列。但是这种罗列以往所有经历的方法只有少数人会这么做,大部分的人采用的是更直接的方法,即利用直觉。那么,直觉是什么?其实直觉也是你在潜意识状态下思考经验后得出的规律。就像你通过机器学习算法,得到了一个模型,那么你下次只要直接使用就行了。那么这个规律你是什么时候思考的?可能是在你无意识的情况下,例如睡觉,走路等情况。这种时候,大脑其实也在默默地做一些你察觉不到的工作。

这种直觉与潜意识,我把它与另一种人类思考经验的方式做了区分。如果一个人勤于思考,例如他会每天做一个小结,譬如“吾日三省吾身”,或者他经常与同伴讨论最近工作的得失,那么他这种训练模型的方式是直接的,明意识的思考与归纳。这样的效果很好,记忆性强,并且更能得出有效反应现实的规律。但是大部分的人可能很少做这样的总结,那么他们得出生活中规律的方法使用的就是潜意识法。

举一个作者本人关于潜意识的例子。作者本人以前没开过车,最近一段时间买了车后,天天开车上班。我每天都走固定的路线。有趣的是,在一开始的几天,我非常紧张的注意着前方的路况,而现在我已经在无意识中就把车开到了目标。这个过程中我的眼睛是注视着前方的,我的大脑是没有思考,但是我手握着的方向盘会自动的调整方向。也就是说。随着我开车次数的增多,我已经把我开车的动作交给了潜意识。这是非常有趣的一件事。在这段过程中,我的大脑将前方路况的图像记录了下来,同时大脑也记忆了我转动方向盘的动作。经过大脑自己的潜意识思考,最后生成的潜意识可以直接根据前方的图像调整我手的动作。假设我们将前方的录像交给计算机,然后让计算机记录与图像对应的驾驶员的动作。经过一段时间的学习,计算机生成的机器学习模型就可以进行自动驾驶了。这很神奇,不是么。其实包括Google、特斯拉在内的自动驾驶汽车技术的原理就是这样。

除了自动驾驶汽车以外,潜意识的思想还可以扩展到人的交际。譬如说服别人,一个最佳的方法就是给他展示一些信息,然后让他自己去归纳得出我们想要的结论。这就好比在阐述一个观点时,用一个事实,或者一个故事,比大段的道理要好很多。古往今来,但凡优秀的说客,无不采用的是这种方法。春秋战国时期,各国合纵连横,经常有各种说客去跟一国之君交流,直接告诉君主该做什么,无异于自寻死路,但是跟君主讲故事,通过这些故事让君主恍然大悟,就是一种正确的过程。这里面有许多杰出的代表,如墨子,苏秦等等。

基本上所有的交流过程,使用故事说明的效果都要远胜于阐述道义之类的效果好很多。为什么用故事的方法比道理或者其他的方法好很多,这是因为在人成长的过程,经过自己的思考,已经形成了很多规律与潜意识。如果你告诉的规律与对方的不相符,很有可能出于保护,他们会本能的拒绝你的新规律,但是如果你跟他讲一个故事,传递一些信息,输送一些数据给他,他会思考并自我改变。他的思考过程实际上就是机器学习的过程,他把新的数据纳入到他的旧有的记忆与数据中,经过重新训练。如果你给出的数据的信息量非常大,大到调整了他的模型,那么他就会按照你希望的规律去做事。有的时候,他会本能的拒绝执行这个思考过程,但是数据一旦输入,无论他希望与否,他的大脑都会在潜意识状态下思考,并且可能改变他的看法。

如果计算机也拥有潜意识(正如本博客的名称一样),那么会怎么样?譬如让计算机在工作的过程中,逐渐产生了自身的潜意识,于是甚至可以在你不需要告诉它做什么时它就会完成那件事。这是个非常有意思的设想,这里留给各位读者去发散思考吧。

9、总结

本文首先介绍了互联网界与机器学习大牛结合的趋势,以及使用机器学习的相关应用,接着以一个“等人故事”展开对机器学习的介绍。介绍中首先是机器学习的概念与定义,然后是机器学习的相关学科,机器学习中包含的各类学习算法,接着介绍机器学习与大数据的关系,机器学习的新子类深度学习,最后探讨了一下机器学习与人工智能发展的联系以及机器学习与潜意识的关联。经过本文的介绍,相信大家对机器学习技术有一定的了解,例如机器学习是什么,它的内核思想是什么(即统计和归纳),通过了解机器学习与人类思考的近似联系可以知晓机器学习为什么具有智慧能力的原因等等。其次,本文漫谈了机器学习与外延学科的关系,机器学习与大数据相互促进相得益彰的联系,机器学习界最新的深度学习的迅猛发展,以及对于人类基于机器学习开发智能机器人的一种展望与思考,最后作者简单谈了一点关于让计算机拥有潜意识的设想。

机器学习是目前业界最为Amazing与火热的一项技术,从网上的每一次淘宝的购买东西,到自动驾驶汽车技术,以及网络攻击抵御系统等等,都有机器学习的因子在内,同时机器学习也是最有可能使人类完成AI dream的一项技术,各种人工智能目前的应用,如微软小冰聊天机器人,到计算机视觉技术的进步,都有机器学习努力的成分。作为一名当代的计算机领域的开发或管理人员,以及身处这个世界,使用者IT技术带来便利的人们,最好都应该了解一些机器学习的相关知识与概念,因为这可以帮你更好的理解为你带来莫大便利技术的背后原理,以及让你更好的理解当代科技的进程。

10、后记

这篇文档花了作者两个月的时间,终于在2014年的最后一天的前一天基本完成。通过这篇文章,作者希望对机器学习在国内的普及做一点贡献,同时也是作者本人自己对于所学机器学习知识的一个融汇贯通,整体归纳的提高过程。作者把这么多的知识经过自己的大脑思考,训练出了一个模型,形成了这篇文档,可以说这也是一种机器学习的过程吧(笑)。

作者所在的行业会接触到大量的数据,因此对于数据的处理和分析是平常非常重要的工作,机器学习课程的思想和理念对于作者日常的工作指引作用极大,几乎导致了作者对于数据价值的重新认识。想想半年前,作者还对机器学习似懂非懂,如今也可以算是一个机器学习的Expert了(笑)。但作者始终认为,机器学习的真正应用不是通过概念或者思想的方式,而是通过实践。只有当把机器学习技术真正应用时,才可算是对机器学习的理解进入了一个层次。正所谓再“阳春白雪”的技术,也必须落到“下里巴人”的场景下运用。目前有一种风气,国内外研究机器学习的某些学者,有一种高贵的逼格,认为自己的研究是普通人无法理解的,但是这样的理念是根本错误的,没有在真正实际的地方发挥作用,凭什么证明你的研究有所价值呢?作者认为必须将高大上的技术用在改变普通人的生活上,才能发挥其根本的价值。一些简单的场景,恰恰是实践机器学习技术的最好地方。

数据挖掘相关的数学基础

来自:张迪的blog

链接:http://www.storagelab.org.cn/zhangdi/2014/01/12/数据挖掘相关的数学基础/

最近我在看《数学之美》和《信息简史》两本书,感觉十分受用。计划在本博客内开放读书专栏,记录心得体会。但在这之前,先大致描述一下我现在热衷的数据挖掘方向的相关基础知识,为了以后写文章做准备也是相当必要的。

引言

数据挖掘,是指从大量数据中获取隐含的、潜在的是有价值信息的过程,是近年来计算机领域火热的研究内容。作为一个大的命题,为了便于引入讨论,这里以本人目前涉及的游戏工业领域的数据挖掘方法展开讨论。

数据挖掘方法在游戏工业领域最初的应用,常常是游戏中的人工智能的开发。例如游戏中的电脑对手,对战类游戏的天梯系统,游戏开发时的关卡自动生成器。这些功能对应着数据挖掘方法中的专家系统、机器学习、模式识别、自然语言理解、自动定理证明、自动程序设计、机器人学、博弈、人工神经网络等。

事实上,数据挖掘的方法本质上就是人工智能的方法,数据挖掘的出现是人工智能发展史上具有重大意义的事件。传统人工智能的研究在20世纪末期事实上进入了一个低谷,这是因为20世纪80年代初,美国、欧洲和日本制定的一批针对人工智能的大型项目都面临了重重困难:一是所谓的交叉问题,即传统方法只能模拟人类深思熟虑的行为,而不包括人与环境的交互行为;二是所谓的扩展问题,即传统人工智能方法只适合于建造领域狭窄的专家系统,不能把这种方法简单地推广到规模更大、领域更宽的复杂系统中去。以上两个根本性问题使人工智能研究进入低谷。而数据挖掘的出现使人们又重新看到了人工智能的希望。 原因就在于数据挖掘方法将人工智能方法带进了广域数据集中,突破了专家系统的限制。

在最近的研究中,游戏行业的研究者们更多地使用数据挖掘方法去分析用户行为,从而进行更精准的商业方案定制。一方面这是因为资本的逐利性使然,现代游戏开发已经走进了一个不断推升制作成本和玩家期望之间的循环,高额的开发费用已经使很多游戏公司不堪重负。另外一方面,大数据时代的数据采集,令大量用户行为成为保存在服务器端的数据,令我们有能力进行分析与研究。通过数据挖掘方法,我们可以做到对游戏用户行为进行建模,并进行自动程序设计。典型的应用例如分析玩家行为和动机,探寻在线角色扮演游戏中的玩家社交群体的变化,识别玩家人物和公会的命名模式,检测游戏玩家感到沮丧的原因,揭露游戏中玩家的社会关系。

数据挖掘过程中相关的主要数学领域

面对复杂数据,数据挖掘的基本流程是:首先对原始数据进行填补遗漏、消除异常、平滑噪声等处理,提高数据挖掘的有效性和准确性。然后使用专门的算法对原始数据进行归纳抽象,去掉取之过多且不均匀的属性和概念层次树中不存在的属性,最终得到一个关系模型。当新的数据加入数据集中时,可以根据该关系模型决定新数据的分类和处理模式。同时,新数据也将带来对整体模型的变化,数据和模型处于动态对应的状态。

从以上过程中可以明显感到,所谓数据挖掘,就是一个典型的数学建模过程。当然,这里已经有较为成熟的工具、方法和理论。例如,统计机器学习所需要的主要理论和技术:泛函分析、逼近论与测度论、统计理论、VC维理论、覆盖数、描述长度理论与算法复杂度研究、核方法、非线性规划技术、几何变换。下文简要介绍涉及的数学学科。

 

1、线性代数和统计学

在这个建模过程中,基础是两大数学学科:线性代数和统计学。这代表了机器学习中最主流的两大类方法的基础。一种是以研究函数和变换为重点的代数方法,比如降维,特征值提取等,一种是以研究统计模型和样本分布为重点的统计方法,比如图模型、信息理论模型等。它们侧重虽有不同,但是常常是共同使用的,对于代数方法,往往需要统计上的解释,对于统计模型,其具体计算则需要代数的帮助。以代数和统计为出发点,继续往深处走,我们会发现需要更多的数学。传统的统计学所研究的主要是渐进理论(大样本情况下的统计性质),而样本数目通常有限(甚至还十分有限)。人们过去一直采用样本数目无穷为假设条件推导各种算法,然后将算法用于样本较小的情况,希望能有较好的效果,然而,算法往往不令人满意。由此,人们提出了学习的推广能力(泛化能力)的重要问题。过去多数工作集中在对大样本统计学习方法的改进和修改,或利用启发式方法设计特殊算法。

2、微积分

微积分只是数学分析体系的基础。其基础性作用不言而喻。机器学习研究的大部分问题是在连续的度量空间进行的,无论代数还是统计,在研究优化问题的时候,对一个映射的微分或者梯度的分析总是不可避免。

3、泛函分析

泛函分析体现了数学模型从特殊到一般的发展过程。

函数在19世纪前期的定义还是数与数的对应关系,空间的概念也只有欧几里德空间。十九世纪以来,数学的发展进入了一个新的阶段。这就是,由于对欧几里得第五公理的研究,引出了非欧几何这门新的学科;对于代数方程求解的一般思考,最后建立并发展了群论;对数学分析的研究又建立了集合论。这些新的理论都为用统一的观点把古典分析的基本概念和方法一般化准备了条件。泛函分析作为数学分析的分支,将函数扩展到函数与函数之间的关系,乃至任意两个集合之间的关系,空间则从有限维空间拓展到无限维空间。

在这个地方,函数以及其所作用的对象之间存在的对偶关系扮演了非常重要的角色。机器学习发展至今,也在向无限维延伸——从研究有限维向量的问题到以无限维的函数为研究对象。内核学习和高斯过程是其中典型的例子。

4、测度理论

这是和实分析关系非常密切的学科。概率本身就是一种测度。测度理论对于机器学习的意义是根本的,现代统计学整个就是建立在测度理论的基础之上——虽然初级的概率论教科书一般不这样引入。在一些统计方面的文章中它们会把统计的公式改用测度来表达,这样做有两个好处:所有的推导和结论不用分别给连续分布和离散分布各自写一遍了,这两种东西都可以用同一的测度形式表达:连续分布的积分基于Lebesgue测度,离散分布的求和基于计数测度,而且还能推广到那种既不连续又不离散的分布中去。而且,即使是连续积分,如果不是在欧氏空间进行,而是在更一般的拓扑空间(比如微分流形或者变换群),那么就不能使用传统的黎曼积分了,需要使用,比如哈尔测度或者Lebesgue-Stieltjes积分。

5、拓扑学

这是学术中很基础的学科。它一般不直接提供方法,但是它的很多概念和定理是其它数学分支的基石。看很多别的数学的时候,会经常接触这样一些概念:开集,闭集,连续函数度量空间,柯西序列,邻接性,连续性。很多这些也许在大学一年级就学习过一些,当时是基于极限的概念获得的。但是看过拓扑学之后,对这些概念的认识会有根本性的拓展。值得一提的是,计算机学科的基础布尔代数与拓扑学有重要的联系。

6、图论

图,由于它在表述各种关系的强大能力以及优雅的理论,高效的算法,越来越受到数据挖掘领域的欢迎。而从目前我所接触的范围内,图论仅在数据结构这门课中提到过。经典图论,在数据挖掘领域中的一个最重要应用就是图模型了,它被成功运用于分析统计网络的结构和规划统计推断。例如,分析社交网络的用户关系,常用邻接链表和邻接矩阵综合表示。在遍历时也离不开深度优先和广度优先算法。

Webkit是如何加载网页的

作者:陈文(@Aaron陈文)

链接:http://www.cnblogs.com/aaronjs/archive/2012/06/29/2570328.html

在WebKit渲染网页之前,它需要将页面和所有引用的资源加载完毕。其中会涉及到不同层面的工作。在本文中,我将重点关注WebCore(WebKit中主要渲染组件)是如何在加载过程中发挥作用的。

WebKit包含两条加载流水线,其中一条负责将文档加载到frames当中,另一条负责加载其他资源(比如图片、脚本一类)。下图描述了两条流水线中涉及的主要对象。

加载Frames

FrameLoader负责将文档加载到frames当中,当点击链接时,FrameLoader会创建一个新的DocumentLoader对象,并置于“policy”状态,接着就等待WebKit客户端决定该如何处理这次加载。通常,客户端会告诉FrameLoader将加载操作视为一次导航(而不是一次加载阻塞)

一旦客户端告诉FrameLoader将加载视作导航,FrameLoader将DocumentLoader置于“provisional”状态,此时将开始网络请求并等待结论:这个网络请求最终是下载一个文件还是一份可解析的文档。

DocumentLoader接下来会创建MainResourceLoader对象,它的作用是与浏览器所运行的系统所提供的网络库打交道,网络库通过ResourceHandle接口提供。将MainResourceLoader和DocumentLoader分离开主要有两个目的:(1) MainResourceLoader处理ResourceHandle回调过程与DocumentLoader分离。(2) MainResourceLoader对象的生命周期与DocumentLoader的生命周期解耦(DocumentLoader的生命周期与Document对象绑定在一起)。

一旦加载系统通过网络获得足够多信息,以便把文档进行呈现,FrameLoader将DocumentLoader置于“committed”状态,这时Frame对象就要显示这个新加载的文档了。

加载子资源

网页不仅仅由HTML组成。我们还需要加载其中的图片、脚本等等。DocLoader对象就来负责加载这些资源(注意DocLoader和DocumentLoader名字很像,但是分工是不同的)。

我们以加载图片为例。为了加载一张图片,DocLoader首先询问Cache是否已经有该图片的副本(以CachedImage对象存在)。如果存在,DocLoader则可快速响应。为了更加高效,Cache经常在内存中保存解码之后的图片数据,这样避免解码两次。

如果图片没有在Cache中,Cache会创建一个CachedImage对象来表示这个图片。CachedImage对象让Loader对象来发起网络请求,Loader会创建SubresourceLoader来做这个事情。SubresourceLoader所扮演的角色与刚刚介绍的MainResourceLoader的角色类似。

改进点

WebKit加载流水线当中有很多需要改进的地方。FrameLoader过于复杂,除了加载frame以外还承担了很多其他工作。比如,FrameLoader有好几个名为“load”的方法,很容混淆。它来负责创建窗口,看上去和加载frame没有什么关系。另外,加载流水线的若干阶段没有必要像现在耦合的这么紧,层次划分也不合理,存在不同层次的对象互相访问,比如:MainResourceLoader将获取到的字节直接丢给FrameLoader而不是DocumentLoader。

如果研究了上面的图,你会发现Cache只会被子资源利用。主要资源的加载并没有得到WebKit内存缓存的支持。如果能够统一这两个加载过程,那么主资源的加载性能也会得到提升。一直以来我们都在不断优化性能来让页面加载的越来越快。

这可能是史上最全的CSS自适应布局总结

作者:茄果

链接:http://www.cnblogs.com/qieguo/p/5421252.html

标题严格遵守了新广告法,你再不爽,我也没犯法呀!屁话不多说,直入!

所谓布局,其实包含两个含义:尺寸与定位。也就是说,所有与尺寸和定位相关的属性,都可以用来布局。

大体上,布局中会用到的有:尺寸相关的盒子模型,普通流、浮动、绝对定位三种定位机制,CSS3中的transform、弹性盒子模块、试验中的grid模块。逛园子的时候经常可以看到浮动布局,inline-block布局,弹性盒布局这几个名词。现在对布局也算有一点了解,做个总结巩固一下。如果你也看了很多资料,但是实际动手时对布局还是无从下手的话,希望本文可以帮你理清思路。

唠叨一句:看到一个效果图的时候,千万不要急着手贱去敲代码!先思考清楚页面的构造,理清各元素之间的关系,特别需要注意的是在不同的设备下需要有怎样的展现,当你思路清晰找到最好的布局方案时,coding其实真的不需要多少时间。

尺寸相关

为什么要先说尺寸呢?因为尺寸在布局中的作用非常核心,布局方式定位这些只是改变了元素之间的关系,没有尺寸就什么也不是。比如我们通常会用margin来控制跟其他元素的距离,这就是布局。

很多人都会觉得,什么width、margin太简单了,早就掌握了。这种心态我一开始学习CSS的时候也有,觉得很好理解很简单,但是后面才发现自己原来很多东西都没真正掌握。看看张鑫旭大神给我们上的政治课:http://www.zhangxinxu.com/wordpress/2012/07/bottleneck-css-study/

先说说百分比,百分比是相对父对象的,这里特性非常好用,很多时候会用在自适应布局上面。浏览器尺寸的改变,就是根节点html的长宽改变,我们可以用%来将浏览器尺寸和元素尺寸联系起来,做到自适应。

另外一个比较有意思的是auto,auto是很多尺寸值的默认值,也就是由浏览器自动计算。首先是块级元素水平方向的auto,块级元素的margin、border、padding以及content宽度之和等于父元素width。使用auto属性在父元素宽度变化的时候,该元素的宽度也会随之变化。

但是当该元素被设为浮动时,该元素的width就变成了内容的宽度了,由内容撑开,也就是所谓的有了包裹性。overflow | position:absolute | float:left/right都可以产生包裹性,替换元素也同样具有包裹性。在具有包裹性的元素上想利用width : auto;来让元素宽度自适应浏览器宽是不行的。

高度方向:外边距重叠,外边距auto为0,这两点需要注意。书写方向什么的,接触比较少就不扯了。

那为什么margin:auto对不能计算垂直方向的值呢?很简单,垂直方向是被设计成可以无限扩展的,内容越多浏览器便产生滚动条来扩展,所以垂直方向都找不到一个计算基准,以此返回一个false,便成了0。

用处:通过width、height控制大小,各个方向的margin值控制与边界或者其他元素的距离来定位。

浮动

目前PC网站大多使用float布局,从成本上考虑大改的概率很小,所以不要说浮动无用,总是会有机会让你维护的!代表网站:淘宝、腾讯、百度,好吧BAT都到齐了。

浮动听得多了,博客园上关于用浮动布局的介绍也非常的多。浮动原本用于文本环绕,但却在布局被发扬光大,这就是命!我的理解:浮动布局的核心就是让元素脱离普通流,然后使用width/height,margin/padding将元素定位。脱离普通流的元素,就像脱离地心引力一样,与普通流不在一个高度上。这个跟图层的概念类似。高度不同所以可以叠在其他元素上面产生重叠或者使用负边距跑到父元素外,理解了这一点浮动布局就很好理解了。

下面用个圣杯布局的例子说明一下,理解了这个之后其他布局更加简单:

left,宽度固定,高度可固定也可由内容撑开

right,宽度固定,高度可固定也可由内容撑开

center,可以自适应浏览器宽度,高度可固定也可由内容撑开。

HTML & CSS:

原理非常简单,左右侧边栏定宽并浮动,中部内容区放最后不浮动、默认width:auto并设置相应外边距,让左右侧边栏浮动到上面。注意:子元素设置为浮动之后,父对象的高度就坍塌了,需要设置父对象后的元素清除浮动,这样父对象的高度才能被浮动子元素撑起来了。

当然,我们也要问一下,为啥父对象高度会坍塌呢?上面也说过了,浮动元素已经脱离了普通流,父对象所在的普通流比喻成地表,那浮动元素就已经上天了。但是父对象还在地表啊,从外太空看浮动元素在父对象里面,但是其实并不在,又怎么能撑开父对象呢?宽度如果我们不设置的话,其实也是为0的,因为父对象里面空空如也,所以宽高为0。

要撑开的办法就两个,1是让父对象也上天(。。。你咋不上天呢),2是把浮动元素的边框边界拉下来。

父对象也上天(即浮动)的话,那就不能实现宽度自适应了。因为float元素的width:auto是包裹内容的,参考前面说的!

办法2就是在后面的元素里加一个clear语句。说到这个问题就要扯到clear与BFC了,我就不献丑了。传送门:https://developer.mozilla.org/zh-CN/docs/Web/CSS/clear

这个三列布局还有个双飞(是双飞翼!想啥呢)的变种,就是在HTML中center部分也就是内容区提到最前面,也就是内容先行渲染。在网络不好的时候,左右双翼能不能出来不要紧,先让主体内容出来!这种想法,明显的优秀工程师思维,但,尼玛的双翼都是广告啊。广告不出来,哪能赚钱养你们这群工程师?所以提出双飞的玉伯才离开了淘宝???(纯属意淫,如真属实,当我扯淡,哈哈哈!)

先上码:

思路:

1)既然HTML里面要让center放前面,为了让left跑到center前面,那center也必须浮动了,否则因为都是块元素他们会分两行。

2)浮动之后还要让center宽度自适应,那明显width只能100%,然后在父元素中设width:auto,还有两侧margin,其实也就是父对象宽度自适应,center只是继承content的宽度。

3)对left使用负的margin让他们浮动到上方去。

代码里面我用到了一个calc(),这个CSS3带来的计算函数简直酷毙了!本例里如果不使用calc函数,那么就需要wrap左边距为0,left左边距-100%,然后center多加一层子块DIV设置margin-left:100px,可以达到同样的效果!calc函数与百分比配合就足以实现自适应的要求!目前所有的自适应布局都在利用浏览器来为我们计算尺寸,但是有了calc之后我们就可以自己制定规则!单是想想都高潮了吧?

总结:使用浮动来进行布局,一个比较大的问题是清除浮动。这个可以使用一个after伪类来清除。更大的问题是浮动性像水一样向上流动,难以把握。在元素较多而且元素高度尺寸不一的情况下,单纯使用浮动只能实现上端对齐,这对于适应多种设备的布局就显得力不从心了。目前的做法是牺牲一部分内容,将元素做成等高排列,从美观上看也当然也是极好的,比参差不齐的排列要美观。

普通流布局

普通流布局:display : inline-block!这是一个传说中取代float布局的存在。看了一些网站,PC端浮动为主,移动端的也用的不多啊,已经有些使用flex的了,说好的inline-block一统江湖呢?

使用inline-block之前先处理点小障碍:inline-block元素会有4px左右的空隙,这个是因为我们写代码时候的换行符所致。

解决办法很简单:在inline-block的父元素中设置样式font-size:0;letter-spacing: -4px; 然后设置inline-block的所有兄弟元素 font-size:值;letter-spacing: 值px;  恢复正常的显示。

另外还有一点需要注意的是inline-block默认是基线对齐的,而inline-block的基线又跟文本基线一致,所以在内容不同的时候并不能水平对齐。只需要用vertical-align显式声明一下top/bottom/middle对齐即可。这里补充一下基线的内容,没你想的那么简单哦。分有文字和无文字两种情况:

1)无文字:容器的margin-bottom下边缘。与容器内部的元素没一毛钱关系。

2)有文字:最后一行文字的下边缘,跟文字块(p,h等)的margin、padding没关系!注意是最后一行,无论文字在什么子对象容器内在什么位置都没关系,浏览器会找到最后一行文字对齐底部。

你们感受一下:

警示:inline-block的基线是最后一行文字的底部,flex里面的基线是第一行文字的底部(请看下文阮老师的文章)

满满的都是泪啊。。。既然都叫baseline,何必呢?

使用inline-block进行圣杯布局:

这里也没什么好说的,用到的也是width:auto和width:100%这两点,简单知识点的简单用法。

双飞的话,代码跟圣杯的基本相同,注意在html的顺序变为center>right>left,只改左栏移动的margin-left: calc(-100% – 100px)到预定位置即可。不能用calc的话可以在center里面再加一层,跟浮动一样的处理方式。更简单的方法是使用CSS3带给我们的box-sizing属性。请看代码:

总结:相比浮动inline-block更加容易理解,也更符合我们的认知,结合盒子模型的几个控制属性就可以进行布局了。对于元素高度不同的情况,目前浮动布局的做法都是将元素做成等高元素进行展现,这从美学上看也符合整齐的要求,不过牺牲了一部分内容。但inline-block有vertical-align属性,可以很好地解决元素高度不同而带来的布局问题。用过之后,你也会喜欢上inline-block的。。。至少我会!

绝对定位

前面的浮动和普通流中其实定位都是靠盒子模型控制的,与我们常说的定位还是有差别的。而绝对定位就是我们平常所说的定位,给定参考坐标系+坐标确定位置。关于绝对定位的资料太多,我就不说了。提一点就是absolute定位的基准是最近的非static定位父对象,而fixed是相对html根节点的定位。两种定位都会脱离普通流,跟之前说的浮动一样,上天了。

当然,他们跟浮动在空间中的位置还是有差别的,项目中有遇到这个问题的请参考张大婶的文章: http://www.zhangxinxu.com/wordpress/2016/01/understand-css-stacking-context-order-z-index/  还是要结合项目来看,否则看过也只是看过而已,并不会存到你的脑子里,毕竟还是相当抽象相当理论性的东西。借用张大神的一个总结图:

使用绝对定位(特指absolute)做自适应布局跟前面两种方式没太大差别,宽度自适应还是在auto和100%上做文章,而位置则由top/bottom/left/right等控制。还是以圣杯布局来举例:

<!DOCTYPE html>

<html>

    <head>

        <meta charset=“utf-8” />

        <title>宽度自适应布局</title>

        <style>

            .wrap {

                position: relative;

                background-color: #FBD570;

                margin-left: 100px;

                margin-right: 150px;

                height: 250px;

            }

            .left {

                position: absolute;

                top: 0;

                left: -100px;

                width: 100px;

                background: #00f;

                height: 180px;

            }

            .right {

                position: absolute;

                top: 0;

                right: 0;

                   width: 150px;

                background: #0f0;

                height: 200px;

                margin-right: -150px;

            }

            .center {

                position: absolute;

                top: 0;

                left: 0;

                background: #B373DA;

                height: 150px;

                min-width: 150px;

                width: 100%;

            }

        </style>

    </head>

    <body>

        <div class=“wrap”>

            <div class=“center”>

                center,可以自适应浏览器宽度,高度固定。

            </div>

            <div class=“left”>left,宽度高度固定</div>

            <div class=“right”>right,宽度高度固定</div>

        </div>

    </body>

</html>

父元素为relative,子元素为absolute,这样的话,又会出现跟浮动一样的问题:父对象高度坍塌,子元素不能撑起父对象。原因也跟浮动一样,解决办法的话目前我知道的只有给父对象指定一个确定height值,大家如果有更好的办法,请联系我!

总结:单纯使用绝对定位进行自适应布局的情况很少,一般绝对定位都用在尺寸固定的元素定位上。而且fixed定位的渲染效率很低,因为它会频繁触发浏览器的重排。另外提一点:CSS3的transform会对绝对定位产生影响哦~比如说让fixed定位不再固定在浏览器视窗的黑魔法:http://www.zhangxinxu.com/wordpress/2015/05/css3-transform-affect/

弹性盒子

CSS3中对布局影响最大的莫过于弹性盒子模块了,这是一套区别于以往盒子模型布局的全新方案。上面几种方法你可以看到,为了实现自适应我们用的都是width:auto和100%的嵌套以及各种边距的移动定位,这套规则并不符合我们的认知。为什么不能开拓出一块区域,横竖排列都可以,内部所有元素的尺寸可以按照一个规则和这个区域的大小联系起来?终于CSS3做出了改变,引入了flex弹性布局方案,弹性盒布局有如下优势:

1.独立的高度控制与对齐。

2.独立的元素顺序。

3.指定元素之间的关系。

4.灵活的尺寸与对齐方式。

在MDN上有非常简单易懂的基础教程:https://developer.mozilla.org/zh-CN/docs/Web/CSS/CSS_Flexible_Box_Layout/Using_CSS_flexible_boxes

上面也已经给出了圣杯布局的自适应布局方案,所以代码就不贴了不过这个例子实现的是3栏成比例缩放,左右栏如果需要固定值的话可以写成  flex: 0 0 150px; 的样式。

但是上面的教程没有给出各个属性的详细解释,建议看看阮一峰的博文,详细易懂而且配图超漂亮的有木有:http://www.ruanyifeng.com/blog/2015/07/flex-grammar.html

总结:弹性盒子在移动端的应用会越来越普遍,这套模型值得去好好研究。语法规则都是非常贴近人性,非常灵活,浏览器兼容性也非常好,当然国内百花齐放的移动浏览器会有哪些大坑呢?我们拭目以待~

其他

其他包括position:relative和CSS3中的transform都可以实现定位,但是由于他们在原来的普通流中还占着一个坑,所以很少用来布局啥的。transform是个很酷炫的东西,可以用平面的素材做出很多3D的效果,而且不需要js就可以做,非常好玩。此文已经很长,就不多说了,以后会写一篇文章来专门说说她的故事。