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的解释，基本很难证明这个命题。}

今天最后一个

There might exist some e_i, a_i,j, and t_i,j values for which FASTEST-WAY produces l_i[j] values such that l₁[j] = 2 and l₂[j] = 1 for some station number j. Assuming that all transfer costs t_i,j are nonnegative.

证明：
l₁[j] = 2 说明 f1[j] = f2[j-1] + a1[j] + t2[j-1] 说明 f2[j-1] + a1[j] + t2[j-1] < f1[j-1] + a1[j]，说明f2[j-1] + t2[j-1] < f1[j-1] ，(1)
l₂[j] = 1 说明 f2[j] = f1[j-1] + a2[j] + t1[j-1] 说明 f1[j-1] + a2[j] + t1[j-1] < f2[j-1] + a2[j]，说明
f1[j-1] + t1[j-1] < f2[j-1]， (2)
(1) + (2) 得到：t2[j-1] + t1[j-1] < 0
但是t_i,j are nonnegative，所以产生了矛盾．命题错误．

这个命题说明了什么？为什么反过来不正确呢？难道不应该是对称的吗？
以上是纯形式化的证明，由于没有用我的实际经验进行验证，所以让我觉得心中没有底．

再请证明

∑²_i=1∑ⁿ_j=1 r_i(j) is exactly 2ⁿ⁺¹ - 2

证明如下：
∑²_i=1∑ⁿ_j=1 r_i(j) = ∑²_i=1∑ⁿ_j=1 2^n-j = ∑²_i=1(2⁰ + ... + 2^n-1_{) = (}2¹ + ... + 2ⁿ) = 2ⁿ⁺¹ - 2

请证明

r1(n) = r2(n) = 1

r1(j) = r2(j) = r1(j+1) + r2(j+1)

Use above equations to show that r_i(j), the number of references made to f_i[j] in a recursive algorithm, equals 2^{n - j}.

证明如下：

第一步：n - j = 1
r1(j)=r2(j) = r1(j+1) + r2(j+1) = r1(n) + r2(n) = 2 = 2<sup>n - j

第二步：若n - j = k</sup>
r1(j)=r2(j) = r1(j+1) + r2(j+1) = 2^{n - j}

若当n - j = k + 1
r1(j) = r1(j+1) + r2(j+1)
因为 n - (j+1) = k，所以 r1(j) = 2^{n - (j +1)} + 2^{n - (j +1)} = 2<sup>n - j

综上，命题得证。
纪念，走出数学系后的第五个年头的一个归纳法证明。</sup>

妹妹、妹妹，我想你

好想你啊。虽然上海很逍遥，挣钱也比较多，还是很想你。么么。

周末 - 2007/7/21 to 2007/7/22

周末和表妹看了哚啦A梦什么恐龙之类的。早上11点到1点。影片中几个搞笑场景我笑了笑。也感觉到导演想搞点温情，可是心里不感动，难道长大了？柯达电影院1号厅的空调坏了，忍了大半场的高温看了部动画片。。。散场出来一个男小朋友吐了，他妈妈对着工作人员大吼。。。五年后我是那个吼的人，还是工作人员。。。
看电影之前，在升降梯碰到了leo，他是机器猫的粉丝，可是看了变形金刚，鄙视他。。。而且35度左右的温度，他穿了一件长袖衬衫，还把扣子都扣上了，拿了把折扇不停的扇风。我想如果他那芭蕉扇效果应该更好些。
之后碰到了octaxal 大爷，带了他的剪刀腿妹妹（他妹妹拍照片的时候喜欢将两条腿反交叉）。他妹妹比我高！！！
下午电影散了场，锅锅我心一横，去游泳。不错所料，以水池饺子。大的小的都有。5点上岸。
去公司看帖，发现persistenceDelegate的test在DRLVM上fail!!! 算了，回家睡觉。
不过，我记住了Dynamic programming 中的两个算法，现背诵如下：
FASTEST-WAY(a, t, x, e, n)
/* a is assembly time
t is transfer time between lines
x is the exit time
e is the entry time
n is the number of station */
f[1][1] = e[1] + a[1][1];
f[2][1] = e[2] + a[2][1];
for j = 2 to n
do if f[[1][j - 1] + a[1][j] <= f[2][j - 1] + t[2][j - 1] + a[1][j]
then f[1][j] = f[[1][j - 1] + a[1][j]
l[1][j] = 1;
else f[1][j] = f[2][j - 1] + t[2][j - 1] + a[1][j]
l[1][j] = 2;
if f[[2][j - 1] + a[2][j] <= f[1][j - 1] + t[1][j - 1] + a[2][j]
then f[2][j] = f[[2][j - 1] + a[2][j]
l[2][j] = 2;
else f[2][j] = f[1][j - 1] + t[1][j - 1] + a[2][j]
l[2][j] = 1;
if f[[1][n] + x[1]<= f[2][n] + x[2]
then f*= f[[1][n] + x[1]
l* = 1;
else f* = f[[2][n] + x[2]
l* = 2;
哇靠，我居然背对了
MAXTRIX-MULTIPLY-ORDER(p)
n = lenght(p) - 1;
for i = 1 to n
m[i, i] = 0;
for l = 2 to n
do for i = 1 to n - l + 1
do j = i + l - 1
m[i, j] =max
for k = i to j
do q = m[i][k] + m[k + 1][j] + p[i -1]*p[k]*p[j]
if q < m[ i, j ] then m[ i, j ] =q, s[ i, j ] = k
return m and s
娘的，锅锅又背对了。看来在我这个年纪的人，记忆是建立在理解的基础上的 ：）

Dynamic programming - Pattern to find optimal substructure

1. Solution to the problem consists of making a choice.
2. Suppose for a given problem, a choice is given to lead to an optimal solution.
3. Given this choice, determine which subproblems ensue and how to best characterize the resulting space of subproblems.
4. Show solution to subproblem must be optimal by using "cut-and-paste" technique.

变形金刚

不过瘾。
很多特技场景时间短，镜头晃来晃去。比如沙漠中对付蝎子，只看见双方弹药对打，然后天上飞机轰炸。蝎子的结构表现的很不清楚。之前蝎子从沙中窜出也同样，很多镜头用沙雾挡住了。
片中各种无关的元素表现过多。女主角是一个勾人的惹火女郎，身世传奇，熟悉机械，是完美的女友。第七区的人员等等，挤出了变形金刚的很多戏。
最后对战场面结束的太仓促，至少可以强化3个场景。一个是红蜘蛛的空战，二个是擎天柱和威震天的对打，还有就是其余汽车人的巷战。
期待续集。既然是视觉系的，希望下一集更炫。