Yaker's Ideal

原文：http://blog.ianbicking.org/2008/03/30/python-html-parser-performance/
作者：Ian Bicking
译者：Yaker Gong
本文链接：http://www.yakergong.com/blog/?p=487 转载请保留出处

在准备我的 PyCon上关于HTML的演讲 的时候我觉得我应该对现有的一些解析器和文档模型做个性能对比。

实际上，情况有点复杂，因为处理HTML需要几个步骤：

1. 解析这个 HTML
2. 把它解析为一个对象(比如一个文档对象)
3. 把它序列化

有些解析器只处理第一步，有些只处理第二步，有些能处理所有的三个步骤…。例如，ElementSoup 使用 ElementTree 来表示文档，却使用 BeautifulSoup 作为实际的解析器。而 BeautifulSoup 内部也拥有一个文档对象。 HTMLParser 仅仅做解析（不解析出任何对象），然而 html5lib 却能够生成几种不同的文档树（DOM树）。序列化也分为XML和HTML两种方式。

所以我选取了下面这些解析器的库做基准性能测试：

• lxml:包含一个解析器，能够产生文档对象，支持HTML序列化。它也可以不适用内置的解析器而使用 BeautifulSoup 或者 html5lib 进行解析。
• BeautifulSoup:nbsp;包含一个解析器，能够产生文档对象，支持HTML序列化。
• html5lib:有解析器。它也有一个序列化器，但是我没有使用它。它也有一个内置的文档对象（即simpletree），只是…除了自我测试我也不知道这东西还能做什么。
• ElementTree:这个包里有一个XML序列化器，ElementTree能够产生文档对象，它也是python内置的XML解析模块。（我觉得下个版本会带一个HTML序列化器，不过我也没测试这个XML序列化器）。它也有一个解析器，测试的时候我用html5lib当做解析器来测试ElementTree的。
• cElementTree:这是一个使用C语言扩展实现的python模块，实现了ElementTree。
• HTMLParser:包含一个解析器。但是其实它不能解析出文档对象，很多正常网页都不能正常处理（包含Table或者Script），有语法错误的网页就更处理不了了。它只是使用解析器遍历文档。
• htmlfill:它使用了HTMLParser作为解析器，相对HTMLParser，它在解析过程中对Element做了更多处理。
• Genshi^[1]:包含一个解析器，能够产生文档对象，支持HTML序列化。
• xml.dom.minidom:python标准库里的内置文档模型，html5lib 能够解析出这种文档对象。（我并不推荐使用minidom — 这篇文章里写了一些理由，还有很多理由我没写出来）

我预想 lxml 的性能会比较好，因为它基于 libxml2这个C库。但是实际上它的性能比我预计的还要好，超过其它所有的同类库。所以，除非考虑到一些难以解决的安装问题（尤其是在Mac上），我都推荐你用lxml 来进行HTML解析的工作。

我的测试代码在这里，你可以自己下载下来运行测试程序。里面包含了所有的样例数据，用来生成图表的命令在这里。这些测试数据来自于从 python.org 随机选取的一些页面（总共355个）。

解析

第一个测试运行这些解析器解析文档。需要注意的是：lxml 比 HTMLParser快6倍，尽管 HTMLParser
不生成任何文档对象（lxml在内存中建立了一个文档树)。这里也没有包含 html5lib 所能生成的全部种类的树，因为每一种花费的时间都差不多。之所以包含了使用 xml.dom.minidom 作为输出结果的 html5lib 测试结果是为了说明 minidom 有多慢。Genshi确实很快，只是它也是最不稳定的，相比之下，html5lib , lxml 以及 BeautifulSoup 都要健壮的多。html5lib 的好处是，总是能够正确的解析HTML（至少在理论上如此）。

lxml在解析过程中会释放 GIL ，但是我觉得应该影响不大。

序列化

所有这些库执行序列化都很快，可是 lxml 又一次遥遥领先。ElementTree 和 minidom 只做XML序列化，但是没有理由说HTML序列化更快。还有就是，Genshi居然比minidom要慢，实话说任何比minidom要慢的东西都挺让人震惊的。

内存占用

最后一项测试是内存。我并不是特别确信我做这个测试的方法很科学，但是数据总能说明一些问题。这项测试会解析所有的文档并把解析出来的DOM树保存在内存中，利用 ps 命令结果的RSS（resident set size）段来表示进程占用的内存。计算基准内存占用之后所有的库已经被import，所以只有解析HTML和生成文档对象会导致内存使用量上升。

我才用 HTMLParser 作为基准线，因为它把文档保存在内存中，只产生一些中间字符串。这些中间字符串最终也不回占用多少内存，因为内存占用基本上等同于这些html问价大小之和。

测量过程中有个棘手的问题就是python的内存分配器并不会释放它请求的内存，所以，如果一个解析器创建了很多中间对象（字符串等等）然后又释放了它们，进程仍然会持有这些内存。为了检测是否有这种情况，我试着分配一些新的字符串知道进程占用的内存增长（检测已经分配但是没有被使用的内存），但是实际上没检测到什么，只有 BeautifulSoup 解析器，在序列化到一个 lxml 树的时候，显示出使用了额外的内存。

只有在内存测试中，html5lib 使用 cElementTree 来表示文档对象同使用 ElementTree 能表现出明显的不同。我倒不是很惊讶，我猜因为我没有找到一个C语言编写的序列化工具，我猜使用 cElementTree 构建文档树的话，只有在用本地代码调用它的时候比较快（就像本地的libxml，并且不需要把数据结构传递到python中）。

lxml比较节省内存很可能是因为它使用了本地的libxml2的数据结构，并且只有在需要的时候才创建Python对象。

总结

在进行基准测试之前我就知道lxml会比较快，但是我自己也没料到会这么快。

所以呢，总结一下：lxml太牛逼了^[2]。你可以用很多种方式使用它，你可以对一个HTML进行解析，序列化，解析，再序列化，在机器卡机之前你能重复这些操作很多次。很多操作都是通过本地接口实现的，python只做了一层很浅的封装。例如，如果你做一次XPath查询，查询字符串会被编译为本地代码，然后遍历本地的libxml2对象，只在返回查询结果的时候才会产生一个python对象。 另外，测试中lxml内存占用比较小使我更有理由相信lxml在高负载的情况下仍然会很可靠。

我觉得，文档树相对按字符流解析（不生成树，只扫描一次文档并针对特定的标签做处理）更有优势。表面看起来按字符流解析更好：你不把整个文档放在内存里，处理的时间之和文档大小线性相关。HTMLParser就是这样一种解析器，遇到各种符号（标签开始和关闭，变迁中间的文字等等）。Genshi 也是用的这个模型，因为使用了一些更高级的特性（比如 filters
）所以使用起来更自然一些。其实字符流模型本身就不是一种特别自然的处理XML文档的方式，从某种程度上说，它只是用来处理一些本来就可以当做字符串处理的文档的一种笨拙的方法（regex可以实现同样的功能）。只有你需要处理上G的XML文件的时候按字符流解析才有意义（不过lxml和ElementTree针对这种情况都有额外的参数支持）。HTML文件不会有这么大，这些测试也有理由让我们相信lxml可以很好的处理大的HTML文件，所以一个大文档也不会导致一个为小文档优化过的系统崩溃。

Ian Bicking on Sunday, March30th, 2008

[1]. Genshi是EdgewallSoftware的产品，它的其他产品还包括大名鼎鼎的Trac。

[2]. 本文的作者Ian Bicking是lxml.html(lxml的一个模块)的开发者和维护者（这里修正一下）。

P.S. 译者记：这里还有一个解析器没有提到就是python标准库里的SGMLParser，它也可以产生ElementTree，但是性能很差，本机测试解析600k的html文档（ddd的单页html文档）需要480秒，不推荐应用在性能要求比较高的场合。本文作者也是lxml的作者，对自己的作品大力推荐也是正常的，我实测过lxml性能确实很好。

今天在实验室做网页文本分类，要下载一段SVM(支持向量机)的代码，点开链接，咦，发现浏览器一片空白，然后显示Unable to connect…

要是一个正常的美国人或者香港人，第一反应是肯定网站坏了，作为一个正常的中国人，第一反应是很可能被墙了。打开代理(感谢xliu送的代理)，点开网页就看到这么一段:

Many researchers have told me that my site is not available in China. According to the company that is hosting my DNS entry, this is due to a Chinese access restrictions. To work around this problem, simply use the URL
http://www.cs.cornell.edu/People/tj/svm_light/
to enter the website. From this url, you can also navigate to SVM-struct, SVM-perf, and all my other software. When you want to download some file, replace “download.joachims.org” with “kodiak.cs.cornell.edu” in the URL.

我倒不是在抱怨有GFW这么一套制度，抱怨也没意义，反过来，我觉得有点…嗯…funny。

最近和其其在做个比赛，内容还跟GFW有点关系，希望能了解下某墙的工作原理。

最近读了《顾准文集》，这书买了半年了，一直在看，前前后后总共看了两三遍，总算把后半部分《从理想主义到经验主义》看完了。我阅读的速度并不慢，这个书理解起来比较费力，有太多问题需要考虑。这本书确实帮我解决了很多困惑(我一直挺迷惘的)，比如如何看待老子的学说(不是整个道家)，评孔子和韩非，中国和西方在文化上的差异，基督教的发展，如何看待马克思及其学说。凡事都有前因后果，要理解当代中国，就要了解春秋战国时代各家思想，要理解现代西方的民主和政治，就要从希腊开始，要理解马克思的学说，也总要看看他都站在什么人的肩膀上。

后面附带了一篇经济文稿《关于社会主义经济中价值及价值规律的问题》，可能因为专业知识不足，没有读懂。

给几个朋友推荐了这本书，下面做点摘抄：

其实，所谓科学精神，不过是哲学上多元主义的另一种说法而已。哲学上的多元主义，就是否认绝对真理的存在，否认有什么事物的第一原因和宇宙、人类的什么终极目的…现在，人们所认识的是：人，通过世世代代的努力，一点一滴的积累，他的处境改善了，还要改善下去，改善的程度，是没有止境的–历史上许多伟大人物曾经设想过人类改变的目标，确实有许多已被超越了。

中国文化的渊源，并非和工商业无关，然而它是史官文化。

你还可以觉得政党、政派，无非是政客组成的集团，可以认为他们当主角的这种民主，很不光彩，感到和“人民做主”这个原则不合，因此还是要直接民主。你也可以认为，人民教育水平不足，也许不幸只好如此，到共产主义时代，谁都知识丰富，目光明澈，那就不会如此了…人民群众在政治上永远是消极被动的，能够做到当前掌握行政权的人不发展为皇帝及其朝廷，已经很如容易了。奢望什么人民当家做主，要不是空洞的理想，就会沦入借民主之手实行独裁的人的拥护者之列。

马克思的哲学是培根和黑格尔神妙的结合…所以，《神圣家族》时代的马克思，几乎是反对唯理主义的，而就本性而言，马克思这个革命理想主义者不能不是唯理主义者…马克思取自黑格尔的，是他的唯理主义。略微说得具体一些，是黑格尔的“真理是整体”，黑格尔的一元主义…人是世界的主体，神性寓于人性之中，这个世界是一元地被决定的，真理是不可分的，这对于革命的理想主义确实都是不可少的…马克思对黑格尔加上了极重要的培根主义的改造…马克思要把黑格尔的哲学命题拉到政治经济学中来解决。

喝茶，不知不觉，把开学时带过来的一桶茶叶喝掉了一半。一般都是晚上回来泡一杯，算是养成习惯了。计划每天要做的一些事情，读英语什么的，好多都没坚持下来。这个没怎么用心，反倒做到了。以前想喝茶，觉得对修身养性有好处，现在对我来说，茶是种咖啡的替代品罢了。

看美剧，lost s06大结局了。说说这个结局吧，我挺喜欢的，因为我本来就不拿lost当科幻片看。结局里jack成为jacob的继任者，用自己的牺牲挽救了众人，躺在竹林里的一幕和本剧的开始遥相呼应。关于结局我做过一些设想，小岛上的超级能量之谜揭开，或者是一个基督教的寓言，暗喻了圣经旧约里的一段故事(按那个故事来，黑烟的名字就是esau)。我有时也觉得sayid,jack,sun,sawyer…每个人都代表了人性的一面，暴力/救死扶伤/爱情/仇恨，不过这种解释很牵强。lost不是科幻小说，描述的是人在特殊境遇下的抉择，而且，很多事情并不需要一个理由的。其实jack和jacob在最后一个episode里的对话对全剧就是个很好的解释，jack之外的几个candidate都在问各种问题，我为什么在这里，这岛是怎么回事：

jack:I will do it.That’s why I’m here.This is..This is what I’m suppose to do
jacob:is that a question,jack?
jack:No.
jacob:Good.

打dota，玩了有四五年了，也是根深蒂固的习惯了，只是打的有感觉越来越难了，要阵容合理水平接近才有点意思。前几天在掌门人打了一盘，网通 RDSP1房，AM,DP,VIS,AA,TH vs SVEN,SF,OM,POM,TK，我们在天灾。我用TH，开始比较劣势，20分钟3杀8死，DP和VIS都超鬼，只有冰魂有几个人头，AM一路打钱。 对面TK抢了很多人头，反正超神了。然后发生了几次团战，对面缺团控吃了点亏，DP的大也显示出威力来。之后SF和SVEN都憋出了BKB，我出了刷新， 然后就是推来推去。89分钟，近卫被破一路，天灾被破两路，之后互拆主基的时候我们主基先挂了。DP前期装备有点问题，太倾向于魔法恢复装备，先锋血精狗皮龙心这种路线感觉更靠谱。还有就是VIS被削弱了很多，团战作用不大，后期太乏力了。

前些日子加入了黄师兄办的计算所桌游协会之后，玩的桌游种类更多了，研究得也更深入一些。我自己比较偏爱策略性的游戏，这篇里面也只谈这个。毕竟玩桌游有两年多了，桌游技巧自然懂一些，要说的话也可以写很多，不过这里要写的是一些桌游之间横向的对比。

我对桌游做了一个粗略的分类:动作性的/交流性的/策略性的。其实常见的桌游都是混合型的，既有策略的成份，也有交互的成份，有的还有动作的成份。不同种类的桌游它给你带来乐趣的方式是不同的，比如动作性的（比如通缉令），训练反应速度，我觉得它的乐趣根植于运动。交流性的桌游，比如经典的杀人游戏（包括狼人），大家一起坐下来，扮演自己的角色去说话，本身就是一种乐趣，所以它的乐趣在于交流。策略性的游戏则不同，主要的乐趣来源于对一个成功模式的重复应用，关于这个理论可以参考《游戏设计-原理与实践》。比如三国杀里你了解到黄忠配备特定攻击距离的武器之后对任何人打出杀都是命中的，下一次再使用这个角色的时候你就会注意到这一点，应用这个技巧并且成功会给你带来快乐。“植物大战僵尸”对于解释游戏的乐趣来源是个很好的例子，每一关都有一些新的植物新的技巧。可以说，策略性游戏的乐趣根植于学习。

我们在承认上面的关于策略性游戏的乐趣来源的结论的基础上继续讨论。所以一个让人持久觉得有趣的桌游，应该是玩家能够经常学习到一些技巧的，游戏本身也应该是多变的。拿矮人矿工来说，规则比较简单，虽然入门门槛低，但是很难让玩家有持久的兴趣。三国杀就是一个完全相反的例子，规则太复杂了。一个熟练的三国杀玩家，不仅要了解各种技能，出牌的规则，还要了解每个人物的特技以及一些特定的组合。如果按每星期两三盘的频率玩，一个玩家大概要2~3个月才能完全了解这个游戏的规则，这2~3个月内，可以保证每次都学会一些规则和技巧。在我玩过的桌游里，三国杀是规则最复杂的一款。游戏规则复杂，有很多技巧，是很重要的，同时呢，又不能太复杂，太复杂容易让玩家产生挫折感，要让一个只懂得基本规则的玩家也可以正常的进行游戏。

桌游不能过于优势积累，这样的话前期劣势的玩家就会觉得整盘游戏都没有意思，必须有方法来限制优势的玩家，比如“富饶之城”里小偷和魔法师这两种角色可以一定程度上限制金钱和手牌，“马尼拉”里的海盗也有类似的作用。劣势玩家要有一定的概率可以翻盘，这样才会均衡大家的乐趣。感觉卡坦岛这方面就稍差一些，优势积累很快，占有土地越多的，概率上讲生产的产品也越多，反过来又可以用产品换取更多的土地，这样最长道路和最强军事经常是同一个人得到的。

要让每个玩家都体验到乐趣。其实个人水平不过分影响游戏结果，以及劣势玩家有机会翻盘都有这个目的，另外就是就是挂掉的玩家不能继续游戏。我觉得三国杀和杀人都有这个问题，粗看起来这很合理，其实这很影响游戏乐趣的，先挂掉的玩家作为一个看客，就少了参与感，少了那种交互的乐趣。三国杀得复活规则应该目的就是解决这个问题的，感觉实际执行起来效果不大。这跟三国杀模仿杀人游戏的角色设置有关，如果是两种角色，两边对砍，死人也可复活了。

还想起银河竞逐的一个问题，银河竞逐是一个纯建设型的桌游，也就是自己建设自己的你极难对你的对手造成破坏。其实玩桌游，大家互相拆拆台也是很有趣的事情，在银河竞逐里这个成分基本没有。

这里的内容是我自己想过之后，又跟一些朋友讨论过的结果，也有很多值得商榷的地方，欢迎大家批评指正。

前些日子去武汉，和朋友一起坐长江上的轮渡，江面宽阔，让自己觉得很渺小。在自然的风景中，很多琐碎的烦恼倒是也消失了。不觉想起苏子的“大江东去，浪淘尽，千古风流人物。”，想想人这一生，其实也很快就过去了，多有感动。

最近听陈胖子的歌很多，蛮喜欢《浮夸》的

幸运儿并不多
若然未当过就知我为何
用十倍苦心做突出一个
正常人够我富议论性麽
你叫我做浮夸吧
加几声嘘声也不怕我在场
有闷场的话表演你看吗

超哥的心境，大抵如此吧。

8周年团庆网站 http://8.dian.org.cn

这个是侯捷老师04年九月应微软公司演讲的摘要。前些日子整理硬盘上的电子书，重读一下，还是觉得写的非常有道理。于是把繁体版的原文转换为简体，方便大家阅读。繁简转换是用了cconv作为工具。

之前发邮件联系过侯捷老师，但是@csdn和@ccca.nctu.edu.tw两个邮箱均退信。

programming.life.jjhou.pdf

从去年的三月到现在一年有余，看了不少书，于孔孟，申韩，黄老皆有心得，然则问题也出在这里，看的多，做得少，还是没什么长进。再看侯捷老师的经历，从一个毕业时都没接受受过计算机教育的本科生到写译著作及腰(《笑谈程式人生》里说：谈不上等身，却已及腰)的作家，其中辛苦，可想而知。我想我缺失的便是那份“疯狂的学习，疯狂的工作”精神。