FireFox 3.0

Firefox 3.0的开发代号为"Gran Paradiso"，按照Mozilla基金会的计划，Firefox3.0将于2007年三季度正式推出。与现有的2.0不同，Firefox 3.0采用了全新的Gecko 1.9渲染引擎，这也是Firefox 3.0解决资源占用率高的关键。相比Firefox 2.0所采用的Gecko1.8引擎，Gecko 1.9在图形架构方面有了根本性的改变。Gecko 1.8采用传统的gfx图形架构，它是一种软件方案，由CPU来完成对2D图形图像的渲染；而Gecko 1.9改用"Cairo "图形架构，Cairo可以借助GPU来负责渲染2D图形图像，相当于实现网页渲染的GPU硬件加速，这样，CPU就被完全解放出来。由于现在的GPU普遍都拥有非常强劲的硬件效能，承担网页渲染任务会非常轻松，因此从理论上说，Gecko 1.9引擎既可以实现更快的渲染速度，又能够大幅度降低CPU资源占用率，实现真正意义上的飞跃。

作为系统应用的基础构件，Cairo提供了一个稳定的用户层API，它可以提供现代化的图形处理管理能力，例如绘制与填充、映射转换、合成以及改变Alpha半透明效果、高清晰文本显示等等，并且能够在不同的媒介上实现相同的显示输出。这个概念并不难理解，简单点说，它与OpenGL、 DirectX等图形API实际上是类似的东西，只不过OpenGL和DirectX属于3D加速的API，它们都可以让应用程序直接与图形硬件紧密地协作；而Cario则是针对2D图像绘制的API，它向更高级的应用程序提供了一系列的图形处理功能，同时又借助OpenGLAPI实现与图形硬件的互动（Cario与OpenGL的衔接由Glitz函数库完成）形成，借助GPU的运算能力来处理2D图像相关的应用。那么，如果我们将Cairo作为应用程序的图形架构，这个应用程序所涉及到的所有图像处理任务都可以由GPU来完成，在这一方面，专用化的GPU显然要比通用的 CPU更具效率。这样，应用程序不仅可以实现更丰富、更复杂的图像效果（如抗锯齿、半透明、阴影、映射转换、变形等等），同时还能在低CPU占用的前提下保证流畅的运行。

除了这些原本就有的后端外，Cairo的后端还包括pdf、svg等，分别可对pdf格式和svg格式提供原生支持，这将能显著提升pdf文件和svg矢量图形的渲染速度。现有PC还缺乏这样的能力，不论你拥有多么强劲的CPU，在浏览pdf文件或者放大缩小svg 矢量图形时都会感觉到显示的停滞感。但如果你的图形系统基于Cairo构建（例如Gnome），并且拥有一块主流性能的3D显卡，执行pdf、svg相关操作将会变得非常流畅，从而有效提升用户的使用体验。显然，基于Cairo的Gecko 1.9渲染引擎也可以获得相同的效果，如果你直接在Firefox3.0浏览器中打开pdf文档或者svg矢量图形，内容渲染速度将大大快于以往，并实现真正意义上的同步显示。

实现Gecko与Cairo的融合是一项费时费力的工作，开发者并没有试图一下子将Gecko的图形架构完全转为Cairo，而是以模块化的方式循序渐进地进行。事实上，早在Gecko 1.8/Firefox 1.1版本中，开发者们就着手Cairo的整合工作，如Cairo中的Canvas、SVG矢量图支持模块已经在Gecko 1.8中实现，而非Cairo的SVG实现方式（例如GDI+）仍得到保留，另外Gecko 1.8/Firefox 1.1的Windows版本也没有实现SVG功能。另外，GPU硬件加速功能也没有在Gecko 1.8中实现，依然只能通过软件的方式进行页面内容渲染。基本上，Gecko1.8只是实现最初级的Cairo整合， 图形架构仍然是基于2D的gfx API。除了Firefox 1.1外，后来的Firefox 1.5和现在的2.0版本也都是采用Gecko 1.8引擎，这三者的差异更多在浏览器外壳以及对安全功能的增强。

Adobe公司并未考虑通过加大技术力量来解决这一问题，而是采用一个十分英明的办法，将Flash源代码直接捐赠给Mozilla基金会，这也是Mozilla基金会有史以来收到的最大一次代码捐赠。Adobe表示未来将把最新的Flash源码直接提供给开源业界，以实现未来浏览器与Flash 播放功能的更佳整合。有鉴于此，Mozilla基金会决定建立一个名为"Tamarin"的新项目，专门用来管理使用Adobe所贡献的代码，而新项目将由Adobe与Mozilla共同管理监督，相关源代码将被下一代"SpiderMonkey （Gecko的JavaScript脚本引擎）"直接整合。除了贡献Flash源代码外，Adobe还将向Mozilla基金会提供 "ActionScript Virtual Machine（简称AVM）"虚拟机软件，该软件是Flash Player播放器中的一部分，它的功能就是负责对ActionScript代码的解释。ActionScript是Adobe Flash产品平台的脚本解释语言，该语言可以实现Flash中内容与内容，内容与用户之间的交互，目前它的最新版本为3.0。与广泛使用的Java Script和微软Jscript一样，ActionScript完全符合ECMA International的ECMAScript标准。

Firefox的锐意进取将给对手带来前所未见的压力，显卡加速网页浏览即将进入现实，而Firefox将无可争议成为最快的浏览器。微软将首当其冲面对这些压力，显然微软不会打算以IE 7.0应战，但IE 8.0似乎还没有将显卡加速渲染功能考虑在内，那么它就很难有效遏制Firefox 3.0/4.0对市场的进一步蚕食。Opera同样将大受影响，它一向被认为是浏览器家族族 中的速度冠军，在Firefox 3.0出现之后Opera很可能将失去光环。同样遭受Firefox3.0/4.0技术冲击的还有Konqueror，目前KDE项目组正在向KDE 4.0发起冲击，Konqueror也将升级到4.0版（KDE 4.0计划于07年第四季度推出），但Konqueror 4.0同样来不及增加显卡加速渲染功能，它的重点更多会放在W3C新标准新技术的支持方面。至于苹果的Safari，过去它一直采用Konqueror的渲染引擎，现在苹果打算与Konqueror分道扬镳自行发展，缺乏开源支持的Safari要实现网页3D加速就更加困难。对整个开源来说， Firefox 3.0/4.0标志着自由软件开始在技术上超越商业软件，而伴随着开源阵营的日益壮大，这样的事情未来将会越来越多。令人愉快的是，自由软件与商业软件并非迥然对立，两者已经开始进行紧密的合作─Adobe贡献源码、微软支持XEN莫不是如此。

转自小百合 http://bbs.nju.edu.cn/bbscon?board=LinuxUnix&file=M.1185380214.A&num=6489

最小乘数，使用遍历的方法和使用使用递归的方法那个更加效率一些

Which is a more efficient way to determine the optimal number of multiplications in a matrix-chain multiplication problem: enumerating all the ways of parenthesizing the product and computing the number of multiplications for each, or running RECURSIVE-MATRIX-CHAIN? Justify your answer.

定义遍历使用时间的函数为 T(n) = sigma(1..n-1):T(k)T(n-k)，

定义递归使用时间的函数为T1(n)，

T1(n) = 1 + sigma(1..n-1):sigma(2..n):sigma(i..j-1):(T(k) + T(n-k) + 1)

<>

< 1 + s(1..n-1):s(2..n):s(1..n-1):T(k) + s(1..n-1):s(2..n):s(1..n-1):T(n -k) + n*n*n

< 1 + 2n*n*s(1..n-1):T(k) + n*n*n

根据之前的证明，知道T(n)=Ω(2ⁿ)。于是有 T(n-k) > 2^{n-k >}2*n*n，

于是有2 *n*n*s(1..n-1):T(k) = s(1..n-1):2n*n*T(k) <　s(1..n-1):T(n-k)T(k)，同时n*n*n是2ⁿ

^{的低阶，即T(n)的低阶，可以忽略．}

^{根据以上的推导，我觉得递归的方法相对更效率．为什么？到底省掉了哪些部分？}

组合！！-嘁哭哭咔

无意中看到描述linux kernel 的一段话。大概是说linux kernel 是一个巨无霸内核。为了避免巨无霸内核的缺点，linux 内核进行了模块化的处理，并且定义了模块间的接口。Harmony 的类库也是这样！！合体的变形金刚也是这样：

大力神内核：
它有六个主要模块组成：

铲车 + 吊车 + 卡车 + 搅拌机 + 推土机 + 挖土机


机械之间都定义了很好的接口，每个组成部分都
能用性能更好的模块替换。比如卡车组成腰部，负责
进程调度；吊车组成胸部，负责内存管理。左臂挖土
机，管理IO；右臂推土机，网络接入。左腿铲车，负
责IPC；右腿搅拌机，存储设备管理。














下面从近处观察各个模块的状态：

铲车 卡车 搅拌机
[组成左腿] [组成腰部] [组成右腿]










推土机 挖土机 吊车
[组成右臂] [组成左臂] [组成胸部]

图片均来自：http://www.colourhill.com/01003.htm

Show that a full parenthesization of an n-element expression has exactly n - 1 pairs of parentheses.

如果n=1，只有一个元素，无需括号，所以有n-1个pair(1)
如果n小于l，这时有n-1个对 (2)
当 n=l，假设 1<=k 小于n，n个表达式可以分为e1..ek 和ek+1..en两个子表达式。分别有k-1和n-k-1个对，共n-2个对，加上e1..ek 和ek+1..en两个子表达式形成的对，这时有n-1个对。

证明最小乘数问题，解空间一共被引用的次数

Let R(i, j) be the number of times that table entry m[i, j] is referenced while computing other table entries in a call of MATRIX-CHAIN-ORDER. Show that the total number of references for the entire table is




证明，靠，太简单了，就是算个sigma。
R(i, j) = i - 1 + (n - j)，sigma(i = 1..n):sigma(j = i..n):(i - 1 + n - j)
= sigma(i = 1..n):sigma(j = i..n):[(n-1) + i - j]
= s(i=1..n):s(j=i..n):(n-1) + s(i=1..n):s(j=i..n):i - s(i=1..n):s(j=i..n):j
= s:(n2 - 1 - n*i + i) + s:(n *i - i*i + i) -s:(n2 - i2 + n + i)/2
=n3-n-n*s:i +s:i +n*s:i -s:i2 - s:(n2+n)/2 + s:i2/2 -s:i/2
=n3 - n +(3/2) *s:i - (1/2)*s:i2 - (n3+n2)/2
= n3/2 -n - n2/2 + (3/4)*n2 + (3/4)n - (n2+n)(2*n + 1)/12
= n3/3 - n/3

可是算了我这么长时间，妈妈的。

适用动态编程的两个条件

1。最优子结构
2。重叠子问题
昨天马云说，最简单的事情最难做好。我想把最简单的事情做好先。

证明-矩阵最小乘数问题

show that the solution to the recurrence is Ω(2ⁿ).
这个问题是这样的：
Ω(2ⁿ) 即只要 >= 2^{n
第一步，n=1，有p(1) = 1 =} 2⁰
第二步，n <>Ω(2ⁿ) >= 2ⁿ
第三步，n= l ，p(n) = sigma: p(k)p(n - k)。因为k & n-k 小于l，于是有
p(n) >= 2^k * 2^n-k= 2<sup>n

符号所代表的意义相当的重要，没有</sup>Ω(2ⁿ)>=2^{n的解释，基本很难证明这个命题。}