Trie vs BST vs HashTable

http://en.wikipedia.org/wiki/Trie

Unlike most other algorithms, tries have the peculiar feature that the time to insert, or to delete or to find is almost identical because the code paths followed for each are almost identical. As a result, for situations where code is inserting, deleting and finding in equal measure tries can handily beat binary search trees, as well as being better for the CPU's instruction and branch caches.

The following are the main advantages of tries over binary search trees (BSTs):

• Looking up keys is faster. Looking up a key of length m takes worst case O(m) time. A BST performs O(log(n)) comparisons of keys, where n is the number of elements in the tree, because lookups depend on the depth of the tree, which is logarithmic in the number of keys if the tree is balanced. Hence in the worst case, a BST takes O(m log n) time. Moreover, in the worst case log(n) will approach m. Also, the simple operations tries use during lookup, such as array indexing using a character, are fast on real machines.
• Tries are more space efficient when they contain a large number of short keys, because nodes are shared between keys with common initial subsequences.
• Tries facilitate longest-prefix matching, helping to find the key sharing the longest possible prefix of characters all unique.
• The number of internal nodes from root to leaf equals the length of the key. Balancing the tree is therefore no concern.

The following are the main advantages of tries over hash tables:

• Tries support ordered iteration, whereas iteration over a hash table will result in a pseudorandom order given by the hash function (also, the order of hash collisions is implementation defined), which is usually meaningless.
• Tries facilitate longest-prefix matching, but hashing does not, as a consequence of the above. Performing such a "closest fit" find can, depending on implementation, be as quick as an exact find.
• Tries tend to be faster on average at insertion than hash tables because hash tables must rebuild their index when it becomes full - a very expensive operation. Tries therefore have much better bounded worst case time costs, which is important for latency sensitive programs.
• By avoiding the hash function, tries are generally faster than hash tables for small keys like integers and pointers.

Applications

As replacement of other data structures

As mentioned, a trie has a number of advantages over binary search trees.^[4] A trie can also be used to replace a hash table, over which it has the following advantages:

• Looking up data in a trie is faster in the worst case, O(m) time, compared to an imperfect hash table. An imperfect hash table can have key collisions. A key collision is the hash function mapping of different keys to the same position in a hash table. The worst-case lookup speed in an imperfect hash table is O(N) time, but far more typically is O(1), with O(m) time spent evaluating the hash.
• There are no collisions of different keys in a trie.
• Buckets in a trie which are analogous to hash table buckets that store key collisions are necessary only if a single key is associated with more than one value.
• There is no need to provide a hash function or to change hash functions as more keys are added to a trie.
• A trie can provide an alphabetical ordering of the entries by key.

Tries do have some drawbacks as well:

• Tries can be slower in some cases than hash tables for looking up data, especially if the data is directly accessed on a hard disk drive or some other secondary storage device where the random-access time is high compared to main memory.^[5]
• Some keys, such as floating point numbers, can lead to long chains and prefixes that are not particularly meaningful. Nevertheless a bitwise trie can handle standard IEEE single and double format floating point numbers.

Dictionary representation

A common application of a trie is storing a dictionary, such as one found on a mobile telephone. Such applications take advantage of a trie's ability to quickly search for, insert, and delete entries; however, if storing dictionary words is all that is required (i.e. storage of information auxiliary to each word is not required), a minimal acyclic deterministic finite automaton would use less space than a trie. This is because an acyclic deterministic finite automaton can compress identical branches from the trie which correspond to the same suffixes (or parts) of different words being stored.

Tries are also well suited for implementing approximate matching algorithms, including those used in spell checking and hyphenation^[2] software.

Algorithms

We can describe trie lookup (and membership) easily. Given a recursive trie type, storing an optional value at each node, and a list of children tries, indexed by the next character, (here, represented as a Haskell data type):

Perl 简介

Perl

Perl 最初的设计者为拉里·沃尔（Larry Wall），他于1987年12月18日发表。Perl借取了C、sed、awk、shell scripting以及很多其他程序语言的特性。其中最重要的特性是它内部集成了正则表达式的功能，以及巨大的第三方代码库CPAN。简而言之，Perl象C一样强大，象awk、sed等脚本描述语言一样方便。Perl 一般被称为“实用报表提取语言”（Practical Extraction and Report Language），你也可能看到“perl”，所有的字母都是小写的。一般，“Perl”，有大写的 P，是指语言本身，而“perl”，小写的 p，是指程序运行的解释器。

　　Perl 最初的设计者为拉里·沃尔（Larry Wall），他于1987年12月18日发表。Perl借取了C、sed、awk、shell scripting以及很多其他程序语言的特性。`其中最重要的特性是它内部集成了正则表达式的功能，以及巨大的第三方代码库CPAN。
　　Perl 一般被称为“实用报表提取语言”（Practical Extraction and Report Language），虽然有时被称做“病态折中垃圾列表器”(Pathologically Eclectic Rubbish Lister)。它是术语，而不仅仅是简写，Perl的创造者，Larry Wall提出第一个，但很快又扩展到第二个。那就是为什么“Perl”没有所有字母都大写。没必要争论哪一个正确，Larry 两个都认可。

编程语言

　　Perl是由Larry Wall设计的，并由他不断更新和维护的编程语言。
　　.Perl具有高级语言（如C）的强大能力和灵活性。事实上，你将看到，它的许多特性是从C语言中借用来的。
　　.与脚本语言一样，Perl不需要编译器和链接器来运行代码，你要做的只是写出程序并告诉Perl来运行而已。这意味着Perl对于小的编程问题的快速解决方案和为大型事件创建原型来测试潜在的解决方案是十分理想的。
　　.Perl提供脚本语言（如sed和awk）的所有功能，还具有它们所不具备的很多功能。Perl还支持sed到Perl及awk到Perl的翻译器。
　　简而言之，Perl象C一样强大，像awk、sed等脚本描述语言一样方便。

特点

　　Perl的解释程序是开放源码的免费软件，使用Perl不必担心费用。Perl能在绝大多数操作系统运行，可以方便地向不同操作系统迁移。
　　Perl 是一种能完成任务的语言。从一开始，Perl 就设计成可以把简单工作简单化，同时又不失去处理困难问题能力的语言。它可以很容易操作数字，文本，文件和目录，计算机和网络，特别是程序的语言。这种语言应该很容易运行外部的程序并且扫描这些程序的输出获取感兴趣的东西。而且它还应该很容易能把这些你感兴趣的东西交给其它程序做特殊的处理。当然，这种语言还应该很容易在任何现代的操作系统上可以移植地编译和运行。

基本语法

　　变量定义，以$号开头，如：$num =1;
　　数组定义，以@开头，如：@array = (1,2,3);
　　数组元素调用 $array[index]，其中index表示数组下标，如上例，$array[0]的值是1
　　散列定义，以%开头，如：%hash=("a",1,"b",2);
　　散列调用 %hash，其中keys表示键值，多用字符串表示，注意hash的key必须具有唯一性，但value可以不唯一，为此hash的key经常被用来做唯一化处理，如上例中的"a", "b", vaules是keys对应的值，如1，2。$hash{"b"}的值是2。

优点

　　Perl追求的是简单, 解决一个一般的问题用它几行代码就完成了. 一个稍复杂一点的问题代码也不会超过一屏! 在软件测试中，Perl通常是非常重要的角色。一般一个测试通用函数库就要分十几个文件，甚至更多，包含多达上千个定制功能。而这些函数将在主函数运行时，不定数量的被调用。几乎可以说，一切自动过程都是由Perl自己完成的，可见其功能的强大和在当今计算机技术高速发展的时期仍然发挥着重要的作用。
　　Perl 最初是当做一种 Unix 的脚本语言设计的，但是她早就移植到大多数其它操作系统里了。因为 Perl 几乎可以在任何地方运行，所以 Perl 可以说是当今最具有移植性的编程环境。要想写可移植的 C/C++ 程序，你得在程序里加上一大堆 #ifdef 标签来区分不同的系统。要想写可移植的 Java 程序，你必须理解每种新的 Java 实现的特质。要想写可移植的shell，你可能要记住每条命令在每种操作系统上的语法，走运的时候你可能可以找到一些公共的东西。而要想写可移植的 Visual Basic 程序，那么你只需要对“移植”有个更灵活的定义就可以了。
　　我们很高兴的是 Perl 避免了所有这些问题，同时还保留了这些语言中的许多优点，同时还有一些自己的特色。Perl 的特色来自许多方面：它的特性集的工具，Perl 社区的创造性，以及开源运动的大环境。不过，许多这些特性都是混合的东西；Perl 的身世复杂，它总是把事物看成是优点的不同方面，而不是弱点。Perl 是“背黑锅我来”的语言。如果你觉得自己陷入一团乱麻之中，非常渴望自由，那么请使用 Perl。
　　Perl 是跨文化的。Perl 的爆炸性增长很大程度上是因为那些前 Unix 系统程序员的渴望，他们希望从他们的“老家”带着尽可能多的东西。对于他们而言，Perl 是可移植的 Unix 文化蒸馏器，是"此路不通"的沙漠中的绿洲。从另外一个角度来看，Perl 还可以从另外一个方向运转：在 Windows 上工作的 web 设计者通常会非常开心地发现他们的 Perl 程序可以不加修改地在 Unix 服务器上跑。
　　尽管 Perl 在系统程序员和 web 设计师中间非常流行，但这只是因为是他们最早发现 Perl 的，Perl 可以用于更广泛的用途。从 Perl 最早的文本处理语言开始，它已经发展成为一种非常复杂的，通用的编程语言，以及完整的开发环境，包括调试器，调节器，交叉引用，编译器，库，语法提示编辑器，以及所有其它“真正”的编程语言所具有的所有挂勾，只要你需要。当然这些东西都是让我们可能处理难的问题的东西，而且很多其它语言也可以做到这一点。Perl 之所以成为 Perl 是因为它从来不会因为保持简单事情简单化而丢失其他方面的特性。
　　因为 Perl 既强大又好用，所以它被广泛地用于日常生活的方方面面，从宇航工程到分子生物学，从数学到语言学，从图形处理到文档处理，从数据库操作到网络管理。很多人用 Perl 进行快速处理那些很难分析或转换的大批量数据，不管你是处理 DNA 序列，网页，还是猪肚皮的未来都无所谓。实际上，在 Perl 社区有一个笑话就是，下次股市大崩盘就很有可能是哪个家伙写的脚本里头有臭虫造成的。（不过，乐观点来看就是，任何还在失业的股票分析师仍然有可以利用的技巧。）
　　Perl 的成功有许多原因。Perl 早在开源软件的名字出现之前就已经是一个成功的开源项目了。Perl 是自由的，并将永远自由下去。你可以在任何合适的场合使用 Perl，只需要遵守一个非常自由的版权就可以了。如果你在从事商业活动并且还想使用 Perl，那么用就是了。你可以把 Perl 嵌入到你写的商业软件中而不需要支付任何费用也没有任何限制。如果你碰上一个 Perl 社区解决不了的问题，那你也还有最后的一招：源程序本身。 Perl 社区不会在“升级”的伪装下租给你它们的商业秘密。而且 Perl 社区也不会“停业 ”，更不会让你孤立无援。
　　Perl 是自由软件这一点无疑对它是有帮助的。但这一条并不足以解释 Perl 现象，因为许多自由软件包没有能繁荣起来。Perl 不仅自由；而且好玩。人们觉得自己在 Perl 里可以有创造力，因为它们有表达的自由：他们可以选择是为计算机速度优化还是为程序员的速度优化，是冗长还是简洁，是选择可读性还是可维护性，或者选择复用性，移植性，接受性和传授性等等。假如你进入一次模糊的 Perl 比赛，甚至你还可以为模糊性做优化。
　　Perl 可以给予你所有这些自由，因为它是一门有着分裂人格的语言。Perl 同时是很简单并且很富有的语言。Perl 从其它地方拿来好主意，然后把它们安装到易用的框架里面。对于只是喜欢她的人来说，Perl 是实用抽取和报表语言（Practical Extractoin and Report Language）。对那些热爱她的人而言，她是变态电子垃圾制造者（Pathologically Electric Rubbish Lister）。在少数人眼里，Perl 是毫无意义的重复练习。不过世界需要一点点冗余。精简主义者总是想把事物分隔开。而我们则总是企图把它们合并到一起。
　　Perl 之所以是简单的语言是有很多原因的。比如你用不着知道什么特殊的指令就可以编译 Perl 程序--只要把它当做批处理或者 shell 脚本执行就可以了。Perl 的类型和结构很容易使用和理解。Perl 对你的数据没有任何限制--你的字串和数组可以要多长就多长（只要你有足够的内存），而且它们都会自动增长。Perl 不会强迫你学习新的语法和语意，Perl 改从许多其它你已经熟悉的语言里（比如 C, awk, BASIC 和 Python, 英文，希腊语等）借来语法。实际上，任何程序员都可以从书写良好的 Perl 代码段中读懂它的含义。
　　最重要的是，你不用先学习所有 Perl 的东西就可以开始写有用的程序。你可以写很小的 Perl 程序。你也可以象小孩那样写 Perl 程序，我们保证不会笑话你。或者更准确地说是，我们绝不会笑话小孩做事情的创造性。Perl 里的许多观点都是从自然语言中借来的，其中一条最好的观点就是只要你能把自己的意思表述清楚，那么你就可以使用这些语言的一个子集。Perl 文化可以接受任何熟练程度的成员。我们不会在你背后放个语言警察。如果你的老板不炒你，而且你的 Perl 脚本也能完成工作，那么它就是“正确”的。
　　尽管 Perl 很简单，但它仍然是一种特性很丰富的语言，如果你想用那些特性的话，那你就要学习一些东西。这也是把难题变简单的学费。虽然你要想把所有 Perl 能做的事情吸收还需要一些时间，但到你需要这些功能的时候你就会非常开心地发现 Perl 已经可以做这些事情了。
　　由于 Perl 的继承性，就算它只是用做数据归纳语言的时候也有丰富的特性，Perl 一开始就设计成可以浏览文件，扫描大量文本并且生成动态数据以及打印出这些数据的良好格式化的报表。不过，随后 Perl 就开始风行，于是它就成了可以操作文件系统，进程管理，数据库管理，进行 C/S 编程和安全编程，web 信息管理，甚至可以进行面向对象和面向功能的编程的语言。而且这些功能并非只是在 Perl 这边，每种新功能都和其它东西交流得很好，别忘了 Perl 从一开始就是设计成胶水语言的。
　　而且 Perl 并不仅仅只能黏合它自己的特性。Perl 是设计成可以用模块扩展的语言。你可以用 Perl 快速设计，编写，调试和部署 Perl 应用，并且你还可以在需要的时候很方便地扩展这些应用。你可以在其它语言里嵌入 Perl，而且你也可以在 Perl 里嵌入其它语言。通过模块输入机制，你可以把这些外部的扩展当做内置于 Perl 的特性。那些面向对象的外部库在 Perl 内部仍然保持面向对象的特征。
　　Perl 还在许多其它方面协助你。和严格的每次执行一条命令的命令文件和 shell 脚本不同的是，Perl 先把你的程序快速编译成一种内部格式。和其它任何编译器一样，这个时候还进行各种优化，同时把碰到的任何问题反馈给你。一旦 Perl 的编译器前端对你的程序表示满意了，它就把这些中间代码交给解释器执行（或者是给其它的能生成 C 或者字节码的模块后端）。听起来挺复杂，不过 Perl 的编译器和解释器干这些活效率相当高，我们的编译-运行-修改的过程几乎都是以秒计。再加上 Perl 的许多其他开发特性，这种快速的角色转换很适合做快速原型设计。然后随着你的程序的成熟，你可以逐步拧紧身上的螺母，减少散漫增强纪律。如果你做得好，Perl 也能帮你这个忙。
　　Perl 还可以帮你写更安全的程序。除了其它语言提供的典型的安全接口之外，Perl 还通过一种跟踪数据的机制给你提供预防意外安全错误的保护，这样就可以在灾害发生之前预防其发生。最后，Perl 还可以让你设置一个特殊的防护隔段运行那些来源不明的 Perl 代码，以此来杜绝危险操作。
　　不过，偏执一点儿说，Perl 帮你的大部分内容和 Perl 本身没有什么关系，而是和使用 Perl 的人有关。坦率地说，Perl 社区的人们可以说是地球上最热心的人了。如果 Perl 运动里面有那么一点点宗教色彩的话，那么这就是它的核心了。Larry 希望 Perl 社区像一小片天堂那样运转，目前看来他的愿望基本上是实现了。我们也请你为此做出自己的努力。
　　Perl之所以强大, 是因为有CPAN, CPAN上面有无数的开源模块, 从科学计算到桌面应用到网络等等各个方面都有大量的模块! 并且现在世界上也还有无数的人在向上面添加模块! 如果你想要用PERL实现某功能, 不用自己做, 在CPAN上面搜一搜, 多半都会得到已有的结果! CPAN（"the Comprehensive Perl Archive Network"全面的 Perl 存档网络）是查找任何 Perl 有关的东西的中心仓库。它包含从整个 Perl 社区收集来的智慧：成百上千的 Perl 模块和脚本，相当于好几本书的文档，以及整个 Perl 发布。如果有东西是用 Perl 写的，而且这个东西很有用而且是自由的，那么它很有可能就在 CPAN 上。CPAN 在全世界都有镜象，你可以在位于 http://www.perl. com/CPAN 的 CPAN 路牌上找到离你最近的镜象。那块路牌会记住你选择的是哪个镜象并且你以后再访问 http://www.perl. com/CPAN/（注意最后的斜杠）的时候就会自动重新定向到那个镜象。另外，你也可以从 www.cpan. org开始。这个站的界面不同，但是数据是一样的。

缺点

　　也正是因为Perl的灵活性和“过度”的冗余语法，也因此获得了write-only的“美誉”，因为许多Perl程序的代码令人难以阅读，实现相同功能的程序代码长度可以相差十倍百倍。但Perl同样可以将代码书写得像Python或Ruby等语言一样优雅。

相关文化

时势造英雄
　　为了理解 Perl 为什么用现在这样的样子定义（或者为什么不定义成其他的样子），我们必须首先明白为什么会有 Perl。所以，让我们先挖掘一下布满尘灰的历史书....
　　退回到 1986 年，Larry 是一个系统程序员，在做一个多层安全的广域网项目的开发。他负责这么一个系统，这个系统由西海岸的三台 VAX 和三台 sun 机器，通过一条加密了的 1200 波特的串行线路和东海岸类似配置的系统连接组成的，因为 Larry 的主要工作是支持（他不是该项目的程序员，只是系统专家），所以他就有机会利用他的三种优点（懒惰，不耐心，和狂傲）来开发和提高所有有用的工具——比如 rn，patch，和 warp。（注：正是在这个时候，Larry 被划入了“计算机动物”的范畴，这是以那些人的不可遏止的“再加一个特性”的渴望为基础评判的，因为这种行为几乎成了生物必须。毕竟，如果生活就是太复杂的话，难道程序就不会吗？尤其是想 rn 这样的程序，它真是应该当作一个高级的人工智能项目来看待，因为他们就可以为你阅读新闻。当然，有些人已经在说 patch 程序太复杂了。）
　　一天，Larry 刚刚把 rn 撕成碎片，把它一片一片地放在他的目录里，大管理员就跑进来说， “Larry，我们需要一个管理配置，用它控制所有六台 VAX 和六台 sun。我们想在一个月里就要它。你做一个吧！”
　　所以，从不逃避工作的 Larry，开始问自己做一个两个海岸的 CM 系统的最好的方法是什么，它必须不用自己从头开始写，并且还可以查阅两个海岸的问题报告以及核准和控制。他想到的答案只有一个词：B-news。（注：也就是 Usenet 传输软件的第二种实现。）
　　Larry 着手在这些机器上安装了新闻软件并且增加了两条控制命令：一条“append”命令用于向现有的文章追加内容，和一条“synchronize”命令保持两个海岸的文章数目相同。CM 可以用 RCS （版本控制系统）做，而核准和控制可以用新闻和 rn 来做。到目前挺好。
　　然后大管理员让他生成报告。新闻是在核心机器里的一个独立的文件里维护的，里面有许多文件间的交叉引用。Larry 的第一个反应是“用 awk。”糟糕的是，那个时候的 awk 无法做到以文件里的信息为基础打开和关闭多个文件。Larry 不想编写一个特殊目的的工具。结果就是产生了一种新的语言。
　　最初这种新的语言并不叫 Perl。Larry 和他的同事及亲友（Dan Faigin，写这段历史的人，和 Mark Biggar，他的妻弟，在初始设计阶段帮了大忙）交换了一大堆名字。实际上 Larry 考虑并抛弃了字典里的所有三个或四个字母的单词。最早的名字是“Gloria”，以他的宝贝（和老婆）命名。但他很快就发现这样会产生太多家庭混乱。
　　然后名字就成了“Pearl”，最后它变成了我们现在的“Perl”，部分原因是 Larry 看到另外一种叫 PEARL 的语言的介绍，但最主要的原因是他懒得总要敲五个键。当然，这样 Perl 就可以用做一个四字母的词。（不过，你会注意到，这里有以前首字缩写的残余： “Practical Extraction And Report Language”。）
　　最早的 Perl 没有今天的 Perl 那么多的特性。那时候有模式匹配和文件句柄，有标量，有格式化，但是很少有函数，没有相关的数组，而且只有一个实现得不怎么样的正则表达式，（从 rn 借来的）。手册页也只有 15 页。但是 Perl 比 sed 和 awk 快，并且开始在该项目的其他应用里使用。
　　但是其他地方又开始需要 Larry 了。有一天另外一个大经理来了并且说：“Larry，给 R&D 做支持。”并且 Larry 说，好吧。他带上 Perl 并且很快发现它逐渐成为系统管理的好工具。他借来 Henry Spencer 漂亮的正则表达式软件包并且把它变成更有男人味（不过 Henry 可能不会愿意在正餐的时候考虑这些特性。）然后 Larry 增加了大部分他想要的特性，以及一些别人想要的特性。然后它就把 Perl 发布到网络上。（注：更让人吃惊的是，他先后工作于喷气推进实验室（JPL），然后是 NetLabs? 和 Seagate 之后，仍然不断发布新 Perl。现在，其他人做了大部分工作，而 Larry 假装为 O'Reilly & Associates（一个小公司，印刷关于计算机和相关事物的小册子。）其余的就是历史了。（注：而这些东西，是历史的一个注解。当开始 Perl 的工作的时候，Larry 已经把 rn 分解成碎片，并且准备做一次全面的重写。但因为他开始在 Perl 上干活，所以 Larry 没有再碰 rn。它仍然是碎片。有时候 Larry 说要用 Perl 重写 rn，但是从来没当真。）
　　然后事情的发展就是这样的：Perl 1.0 在 1987 年十二月十八日发布；有些人仍然很认真地对待 Perl 的生日。Perl 2.0 在 1988 年六月发布，并且 Randal Schwartz 开始了“另外一个 Perl 黑客”的签名的传奇。在 1989 年，Tom Christiansen 在巴尔的摩 Usenix 拿出了第一个公开的 Perl 教程。1989 年十月的 Perl 3.0开始，这门语言第一次以 GNU 公众版权（GPL）发布和分发。
　　1990 年三月，Larry 写了第一首 Perl 小诗（见下一节）。然后他和 Randal 写了本书的第一版，The Pink Camel；该书在 1991 年早期发行。然后 Perl 4.0 就立即发布了；除 GPL 之外，它还包括了 Artistic License（艺术版权）。
　　万众期待的 Perl 5 在 1994 年十月发布。这是一个完全重写的 Perl 版本，它包括对象和模块。 Perl 5 的到来甚至连 The Ecomomist 杂志都提到。到了 1995 年，正式向 Perl 社区引入 CPAN。在 1996 年，Jon Orwant 开始出版 The Perl Journal 杂志。在长时间的猜测之后，本书的第二版，The Blue Camel，在那年的年末出版。第一次 O'Reilly Perl 大会（TPC） 1997 年夏季在加州 San Jose 举行。现在，重大时间几乎是每天都在发生，所以，关于历史的其他部分，请检查 CPAST （Comprehensive Perl Arcana Society Tapestry （history.perl. org））上的 Perl 纪年表。

Perl 的下载与安装

　　在Linux 系统下、大部分类UNIX 系统(包括Mac OS X)，perl是随系统安装的，可在命令行终端输入命令perl -v，查看版本，对于Windows有两种版本可用：Strawberry Perl 与 ActivePerl

扩展阅读：
1. http://www.oschina.net/p/perl 开源Perl
2. http://www.google.com/search?hl=zh-CN&newwindow=1&q=define%3Aperl&lr=
3. Perl的正式网站是 http://www.perl.org。
4. Perl 编程 (Author: Larry Wall)
5. Perl语言入门(Learning Perl)
6. 精通Perl（Mastering Perl）
7. Windows下的Perl下载：http://www.perl.org/get.html

QuantNet 最新金融工程MFE排名 20110919发布

2011 QuantNet Ranking of Financial Engineering Programs

原文可见：
http://www.quantnet.com/mfe-programs-rankings/

2011年9月19日发布，是以U.S.News & World Report美国新闻与世界报道的Business School Rankings Methodology为基础的算法进行排名，截至到目前为止最有参考价值的MFE排名.

RANK	UNIVERSITY	PROGRAM	TYPE	DURATION
1	Carnegie Mellon University Pittsburgh, PA	Computational Finance	FT/PT	1.5 years
2	Princeton University Princeton, NJ	Master in Finance	FT	2 years
3	Columbia University New York, NY	Financial Engineering	FT	1 year
4	New York University New York, NY	Mathematics in Finance	FT/PT	1.5 years
5	Baruch College, City University of New York New York, NY	Financial Engineering	FT/PT	1.5 years
6	Stanford University Stanford, CA	Financial Mathematics	FT	1 year
6	University of California, Berkeley Berkeley, CA	Financial Engineering	FT	1 year
8	Columbia University New York, NY	Mathematics of Finance	FT/PT	1 year
9	Cornell University Ithaca, NY	MEng, FE concentration	FT	1.5 years
10	Massachusetts Institute of Technology Cambridge, MA	Master of Finance	FT	1 year
10	University of California, Los Angeles Los Angeles, CA	Financial Engineering	FT	1 year
12	Rutgers University New Brunswick, NJ	Mathematical Finance	FT/PT	1.5 years
12	University of Chicago Chicago, IL	Financial Mathematics	FT/PT	1 year
14	Georgia Institute of Technology Atlanta, GA	Quantitative and Computational Finance	FT/PT	1.5 years
14	University of Toronto Toronto, Canada	Mathematical Finance	FT	1 year
16	University of Michigan Ann Arbor, MI	Financial Engineering	FT	1.5 years
17	Boston University Boston, MA	Mathematical Finance	FT/PT	1.5 years
17	NYU-Poly Brooklyn, NY	Financial Engineering	FT/PT	1.5 years
19	North Carolina State University Raleigh, NC	Financial Mathematics	FT/PT	2 years
20	Claremont Graduate University Claremont, CA	Financial Engineering	FT/PT	1.5 years
21	Illinois Institute of Technology Chicago, IL	Mathematical Finance	FT/PT	2 years
22	Kent State University Kent, OH	Financial Engineering	FT	1 year

2011 MFE Programs Rankings Methodology:

Employer Survey Score (25%)

From August to early September 2011, Quantnet surveyed hiring managers and corporate recruiters representing a wide range of quantitative groups across financial institutions in US, UK and Asia to indentify which of the 22 programs in the 2011 ranking whose graduates they have interviewed or hired from within the last three years.

Placement Success (50%)

• Starting Salary (20%) The average starting salaries of the most recent graduated cohort were normalized by mean and standard deviation and separated into quintiles, with each quantile being awarded points from 20 to 100 in increments of 20 points.
• Employment Rate at Graduation (10%) The employment rates were separated into five different groups, each group being awarded points from 20 to 100 in increments of 20.
• Employment Rate Three Months after Graduation (15%) The employment rates were separated into five different groups, each group being awarded points from 20 to 100 in increments of 20.
• Students/Administrator Ratio (5%) The Class Size was divided by the number of administrators supporting the students; the ratios were normalized by mean and standard deviation and separated into quintiles, with each quantile being awarded points from 20 to 100 in increments of 20.

Student selectivity (25%)

• GRE Scores (10%) The average GRE Quant scores of the admitted students were separated into five different groups, each group being awarded points from 20 to 100 in increments of 20.
• Undergraduate GPA (5%) The average GPAs of the admitted students were separated into five different groups, each group being awarded points from 20 to 100 in increments of 20.
• Acceptance Rate (10%) The scores were separated into five different groups, each group being awarded points from 20 to 100 in increments of 20.

Overall score/rank

A score for each program is accumulated from the points in each category multiplied by the category’s assigned weighted average.

Book/Website for Technical Interview

Books:

Crack the Coding Interview (强烈推荐)

Programming Interviews Exposed (强烈推荐)
编程之美
data structures with java
algorithm design
database management system
computer networking
thinking in java
thinking in c++
software testing
java how to program

Websites:

http://www.mitbbs.com/bbsdoc/JobHunting.html
http://www.careercup.com
http://www.glassdoor.com
http://www.dice.com
http://www.geeksforgeeks.org
http://www.javacertificate.net/core_java_iqns.htm
http://www.techinterviews.com/core-java-interview-questions
http://javaquestion.tripod.com/InterviewWithAnswer.html
http://www.freejavaguide.com/java-interview-questions.html
http://www.roseindia.net/interviewquestions/
http://www.geekinterview.com/Interview-Questions/J2EE/Core-Java
http://javaquestion.tripod.com/InterviewWithAnswer.html
http://www.indiabix.com/technical/core-java/

***********************************************************************************************************
http://www.indiabix.com/technical/core-java/

Interview In Investment Bank: http://javarevisited.blogspot.com

http://www.iteye.com/blogs/tag/%E7%AE%97%E6%B3%95

http://www.quant-strategy.com

http://leetcode.com

面试(转载)

首先来个小测验,看你能看懂多少
1.array,list,BST,Hashtable,queue,stack,suffix tree,collection...
2.BFS,DFS,DP,D&C,Greedy,Dijkstra,tree traversal,recursion,quick sort...
3.A,F,G,L,M,O,T,Y...
4.OOP,GC,Polymorphism,interface,abstract class,singleton...
5.bar raiser,white board programming,lunch interview...

如果以上任何概念不能熟练给出详细解答,请在往下面看之后抓紧复习1.数据结构(这个如果一个没看懂可以按后退关窗口了)2.算法3.公司背景4.面向对象编程5.onsite流程.全看懂了也别骄傲,这其实只是很简单的小测验,拿笔每行接着写10项.

[公司面试心得]

下面按照公司我大概讲讲面试题的注意事项,由于有不少是1年前的题目,记得不太清楚,我以框架为主,后面主要讨论复习要点和经验教训:

A:phone interview会问到关于OOD的概念和设计,onsite有问过题:数组找定和,Hash table溢出, sBST,Rome letter,GC设计,byte[] getIP(int),deadlock,优化搜索速度.数组求定和是最最常见的问题,基本每两个interview就有一个问这个,后面还会说到,一定不要陷入固定思维,自己多想想不同的condition下的解答.听说最近在狂面人,可以在linkedin上面直接找到HR要面试.

F:现在已经很难进了,主页能找到一些puzzle,很多很tricky,不过也还算不难,觉得普通面试题缺乏挑战的童鞋可以拿做当onsite前热手,phone里面主要是基础题目,只记得链表反转,以OOP为主,没有onsite过. http://www.facebook.com/careers/puzzles.php

G:被问到都是非主流问题和设计,什么"估算躺在地上硬币总价值",无语.设计也都是开放性的,没啥参考价值,可能天生相克吧.

L:很注重java的概念,例如hash原理,多态,继承,gc等的深层概念和implementation,对于概念有点要求的过严了,但是还算是让人向往的公司吧

M:注重flawless的编程,pointer的操作(能用array/bitwise不要用hashtable),DP, dictionary/index,recursion.最近狠狠的涨了一下工资,让人很眼红的说

O:基本只看GPA3.8以上或者内荐,面试主要是algorithm,SQL

其实我大公司的面试经历不算多,也只能这样点到为止,但是还有一些公司,招人规模不及以上,但是我也稍微点评一下.

Bloomberg:变态的测试,据说除了c的测试外其他没有过的记录.面试也是集中与算法和数据结构,以c/c++为主要背景,压力大工作辛苦薪水高,一但进黑名单貌似是永远不会考虑了

ebay:招人不是很给力,最好内荐,OOP为主,一流的流量一流的薪水二流的软件,我的意思不是说ebay不好,而是说其实他家软件,尤其比起A来,还有很大上升空间,其实趁着软件还不够好参与开发是种机会,你懂的

rapleaf:漫天广告,实际上没啥诚意,现在市场转好,建议不要考虑

D.E.shawn/two sigma/citadel:面试门槛很高,但是效率也很高,舍得花钱,就是录取率不高,建议阅读相应金融知识,并且有相关实习经验或者大公司背景,new grad很有难度

laserfiche:坑爹专业户,如果你从没onsite经历可以去一下,否则就是浪费时间,薪水超低(尤其以LA为背景)

ning:新兴social network,100人不大但也还算不错的startup,不过他们manager很对不起我,估计我这辈子是不考虑了,推荐想做social network但是去不了F,L,T的

quantcast:强烈推荐,感觉非常棒,但是codetest也很难,时间很紧张,2个小时测试,到点的时候只写出2/7个答案,4小时写出完美程序,大概200行的样子,加上10个testcase,然后就悲剧了,估计就是嫌我慢

addepar:很个性的公司,先一轮phone,然后做蚂蚁大战,时间不限, http://addepar.com/challenge.php,要是我在学校可能还有心情测一测根本不太可能静心给他做这个,若是能达到400-600turn过关,那么可以拿到下轮面试,你要是觉得自己很牛没有题做,试试这个

epic:狂招人,面试比较简单,需要准备presentation,有性格测试

cisco/emc/ibm/adobe:感觉对local看的很重,不太招外州的人

yahoo/SAP:没落中,需求量越来越小

apple:对SDE需求不大,有些ee的职位,手机卖这么好,没听有招人(店面不算)

GS/UBS/Citi/boa:看重GPA,如果你喜欢做纯技术,去了会后悔的;如果想做金融软件,但是达不到bloomberg和hf标准,是个不错的跳板

fiverings:很小的HF,10几个人吧,问一下brain teaser和古怪的程序,有兴趣可以试一下,老板是从jane street出来自己做的

其实还有数不完的公司,不过本人主要经历也就这些.

[复习清单]

我只列出关键字和一些特别注意的要点,其实一个词可能包含无数知识点:
Array(pointer)
list(reverse,loop,ring)
tree(traversal,search)
sort
queue/stack(BFS,DFS)
hash table
string(suffix tree)
recursion
graph/greedy
divide and conquer
dynamic programming
bitwise
OOD(GC,serialization,exception,UML,singleton)
regular expression
deadlock/multi-thread
I/O,memory,buffer
testing(unit test,white box,black box,development cycle)
Network(TCP/IP,socket)
SQL(index,bcnf,3nf,optimization)
Scale(distributed system)
Security(buffer overflow,protocol)
Machine learning/AI
probability(bayes)
Web programming
最后是behavior(strength,weakness,goals)

参考书和网站:
crack the technical interview(强烈推荐)
programming interviews exposed(强烈推荐)
编程之美
data structures with java
algorithm design
database management system
computer networking
thinking in java
thinking in c++
software testing
java how to program
http://www.mitbbs.com/bbsdoc/JobHunting.html (还用多说么)
http://www.careercup.com (会上面的题不代表就能过面试!)
http://www.glassdoor.com
http://www.dice.com
http://www.javacertificate.net/core_java_iqns.htm
http://www.techinterviews.com/core-java-interview-questions
http://javaquestion.tripod.com/InterviewWithAnswer.html
http://www.freejavaguide.com/java-interview-questions.html
http://www.roseindia.net/interviewquestions/
http://www.geekinterview.com/Interview-Questions/J2EE/Core-Java
http://javaquestion.tripod.com/InterviewWithAnswer.html
http://www.indiabix.com/technical/core-java/

[经验教训]

最后一部分,琐碎的经验教训

1.对方电话里问你下周能不能来,一定要问清楚他们急不急用人,急得话要当机立断,我因此疏忽本想拖延一下面试避免时间紧张,结果一周后被告知不用去了,四大皆空,干脆悲剧

2.地区是一个很重要的因素,如果你还没开始h1b或者绿卡,在找工作受阻的情况下可以考虑申请opt然后搬去加州或者纽约,在local找,很多公司为了省phone的多回合和onsite的开销,只找local或者优先在local找.至于有些在职的人想辞职裸奔挂语言学校,也是个办法.

3.不要背题.迄今为止我还没见到过一模一样的面试题,优秀的面试官一定不会只准备所谓经典的面试题,一定有改动和引伸.举个例子,数组找定和很简单吧,怎么不用hash table照样O(n),找3数定和?4数(有O(n^2)解)?负数?已排序数列?写白板!再举个例子hash table大家都知道,让你用数组实现?hash function?碰撞处理?碰撞处理方法的利弊比较?equal和hashcode的关系?写白板!希望大家准备的时候能够多问自己问题,写程序也不要只完成题目,多想想如果哪个要求换了应该怎么改.

4.练习口语.比起阿三,老美不见得喜欢中国的口音,很多人的发音和语法不正确,自己从来没用心改正过.这里推荐一款iphone的免费app-dragon, http://itunes.apple.com/us/app/dragon-dictation/id341446764?mt=
是一语音识别软件,你找一篇新闻,认真读看看老美的软件能听懂你多少,反复训练,更上一层楼.说话的时候尽量嘴巴变化明显一点,试着拉长放慢大声和夸张的读每个单词,尤其是字母lnr的卷舌鼻音

5.实习经历还是很重要的,重要程度多过绝大部分in class project,争取毕业前能在美国公司里面有过实习经历.

6.linkedin其实是一个很好的平台,很多recruiter在上面搜罗人才,你要表现的活跃一些,完善自己的资料.另外如果通过朋友等渠道,你可以找到recruiter的邮箱,一定要主动自报家门,我干过无数回了,直接email给recruiter,附上简历,说明背景,百试不爽,基本每次都有面试

7.搞好和同学前辈的关系,最大化争取referral(朋友的朋友也行),有面试什么都能靠你自己,没面试你自己再牛也不行

8.白板练习很必要.为了面试我用eclipse至少写了60个函数的题目,但是换成白板/白纸,还是无法每次写出flawless的程序,这个必须多加练习,而且尽量找一些自己没听过的题目或者变形的题目

9.准备好所有工作经历包括实习的描述,控制好时间,另外着重准备1-2个对你来说重要的project/design,一定要做到拿起来就能说,而且说的简洁明了重点突出,让不很懂的人也能听明白

10.behavior question要花时间准备,准备过的话一问就能问出来,说话要简洁,用多个简短的句子回答,不要用冗长的从句.给面试官一个好的印象.

11.屡试不行的童鞋请考虑 i.改简历 ii.monk interview iii不同type的职位.原则上找能给你反馈的人的意见,反馈可以说是非常难得到的,是指引你进步的关键.monk interview要涉及技术和behavior,而且面试人要认真准备,问题要有深度,当场要卡时间写白板,不要觉得认识面试人就跳过诸如自我介绍,project描述等环节.

12.木桶原理,找到自己的不足,尽量提高综合能力,不要让任何不足拖你后腿.举个不一定合适的例子,如果你是路痴,面试前多查查map要不就打出来,留一个紧急求助电话像是tax或者HR的电话,一定要保证按时到达.路痴不能怪你,不守时那就是你的责任.现在公司招人,基本上都是找综合能力强并且有亮点的人,弥补你的短板往往能更加有效的留下好印象.

13.列个表或者找个日历,合理安排面试顺序和集中程度,确保面试前对公司有所了解,尤其是要看至少一遍job description,知道他们的需求是什么.这里废话一句,对于dream company,最好不要放在面试经历少或者时间仓促的时候,如果你从来没去过onsite或者很久没去过onsite,用其他公司热身是有必要的.一般一年左右的黑名单还是很难熬的,况且有些像F这样的公司,2年前和现在的口气明显就不一样,现在连要个面试都很难.

14.学会换位思考,从面试官公司角度考虑他究竟在考察你什么.如果可以,你甚至也可以给别人做interview,你会体会良多.crack technical interview里面说的比较夸张,面试官其实在找"Would I have a beer with this guy?"的答案,但是你不可否认的是,他们如果觉得和你在一起不舒服,随便找个借口就可以把你打发了.

15.面试过程中很多东西是无形的,面试前题目,公司招人的主要原因,老板性格态度,职位竞争的激烈程度,面试评价标准等等,所以要尽可能的把握自己看的见的,技术要点,措辞态度,白板编程等等.未知因素不由得你,不要老想着哪里有窍门哪里有小道消息来投机取巧;超越自己,把握自己才是真正的提高.

16.这里再废话一段,面过这么多公司,感觉中国人还是比较受压迫,比起阿三,中国人在软件公司中层的人数明显少,很少人接触到核心技术和做决策.准备面试的时候,要多与朋友交流互相帮助,阿三老美的优点要尽量学来,以后职场做的久了,也要多帮助后生.我们的爷爷辈受尽别人压迫欺负,父辈受自己人欺负,能提供机会我们出来,很不容易.我们这一代其实是肩负着历史使命的,而在美国的各路精英应该是民族复兴的领军人,希望有朝一日中国能有更多的AFGM为世界贡献优秀的软件.

话说到这里也差不多了,以上的话也都是小弟自己的体会,有不到位的地方也希望和大家讨论切磋.关于详细的每家的面试题,还有比本版(尤其是精华贴)更好的地方么.最后用一句话与大家共勉,机会青睐有准备的头脑,还等什么,继续打怪升级吧!