Meta's Wonderful World

Chrome源码剖析系列 - 开篇贴

2009-01-29T14:28:00.003+08:00

本系列将会详细记录我在阅读Chromium开源项目的源码过程中所收获的心得.
下一篇将会介绍Chromium项目的顶级JS引擎 - V8中所采用的RAII策略. :-)

空白骰子问题

2008-03-06T09:42:00.001+08:00

问题描述:
给出两个六面空白的骰子, 往上面填数字0-6, 使得两个骰子一起掷时1-12出现的概率都是一样的.

分析:
假设这两个骰子分别为A和B, 两两组合有36种情况(包含重复). 1-12出现的概率一样, 不妨假设他们出现的次数为n, 可以得知1 <= n <= 3. 下面考虑n的三种取值情况:

1. n = 1, 有12个组合分别取值 1 - 12, 其他24个组合全为0. 由此可以得知A, B的六个面: A { 0, 0, 0, 0, 0, 0 }, B { 0, 0, 0, 0, b1, b2 }. 这种假设情况下, b1和b2各出现6次, 很明显与假设是矛盾的, 不成立.

2. n = 2, 有24个组合分别取值 1 - 12, 其他12个组合全为0. 由此可以得知A, B的六个面的两种情况:(1). A { 0, 0, 0, 0, 0, 0 }, B { 0, 0, b3, b4, b5, b6 }; (2). A { 0, 0, 0, 0, a5, a6 }, B { 0, 0, 0, b4, b5, b6 }. 同理分析, 这两种情况都与假设矛盾, 不成立.

3. n = 3, 有36个组合分别取值 1 - 12. 我们不妨考虑如下两个特殊的数字: 12和1. 对于12, 组成其的唯一可能是2个6, 加上要出现3次, 则有 { 6 }, { 6, 6, 6 }, 于是得到 A { 6, ... }, B { 6, 6, 6, ... }.
对于1, 组成其的唯一可能则是 0, 1, 加上出现3次, 则可能有 { 0, 0, 0 }, { 1 } 或者 { 0 }, { 1, 1, 1 }. { 0, 0, 0 }, { 1, 1, 1 }不可能属于 A, 否则的话, 数字组合6和7出现的次数将会是9次, 与假设是矛盾的. 那么, { 0, 0, 0 }, { 1, 1, 1 } 只可能属于 B.
考察 A { 6, ..., 1 }, B { 6, 6, 6, 0, 0, 0 }. 由于n = 3, 满足条件的组合只可能由A中的6个数字(各不相同)与B中3个0的组合, 将产生 1 - 6数字组合各3个, 不难得知 A { 6, 5, 4, 3, 2, 1 }; 然后将A中数字与B中的3个6组合则得到7-12的组合各3个.
考察 A { 6, ..., 0 }, B{ 6, 6, 6, 1, 1, 1 }. 11这个数字, 只可能有A中5和B中的3个6组成; 如果A中包含5, 则6这个数字组合将要出现6次, 与假设矛盾, 不成立.

因此, 唯一的解就是A { 1, 2, 3, 4, 5, 6 }, B { 0, 0, 0, 6, 6, 6} .

Picasa的一些事

2008-01-24T10:58:00.000+08:00

今天启动Picasa，发现几个问题：

1. 默认Picasa不支持indexing .gif文件。后来，我把它选中了，结果在Picasa中显示的图片底色全是黑色。难道这是picasa的bug？
2. 发现Email发送图片的设置中除了系统默认的客户端邮件软件（我是outlook），Gmail Account以外，还加入了对第三方邮件的支持：Picasa Mail。

注册一个用户（其实就是Hello用户），通过给你所指定的邮箱发送一封确认信，确认你是owner后，就可以将这个注册的Picasa Mail帐户与多个验证过的邮箱地址绑定。Picasa Mail可以很方便地以你所指定的默认第三方邮箱地址去发送邮件，这是支持第三方邮箱的一个很好的方法。

其实，Gmail早就支持其他邮箱的代收发功能（Gmail的野心是整合用户所有的已有邮箱），但Picasa并没有强迫用户去注册一个Gmail，然后使用Gmai的邮件代发功能。也许那会为Google带来更多的Gmail注册用户，但却忽视了用户的意见。我觉得，Picasa Mail是一个很好的支持第三方邮件的设计，尽管底层可能用的是同一套机制。对于没有Gmail的用户来说，可以很简单的将自己的多个邮件与Picasa绑定起来；即使有Gmail，如果你想用其他不同邮箱发送照片，也可以很方便地切换不同的邮件地址，而不用每次都去Gmail里面改设置。另外，Picasa Mail由于采用了Hello的技术，所以它可以发送更精致的图片。
在做产品整合的时候，永远不要强迫你的用户去使用他目前并不熟悉的产品，一定要有一个过渡的方法，把选择的权利留给用户。

Google输入法建议

2007-10-29T15:45:00.001+08:00

Google输入法，相信大部分喜欢Google产品的人都不会错过这款优秀的基于互联网的输入法。它最主要的特色也许就是它的词库是基于Google庞大的互联网数据库而生成的（其中包括用户的搜索记录，网页数据等等）。
但是，Google的输入法对于Google而言，其重要性与微软拼音对于微软而言是完全不一样的。通过Google输入法，可以更好地研究中文用户的输入习惯，从而改进Google中文搜索的分词技术；而且，还可以将输入与搜索直接绑定。毕竟，输入法对于中文用户而言，是每天必不可少的工具。但是在使用过程中，我却碰到了一些问题：

1. 词库的同步。 Google拼音默认的处理机制是：如果本地计算机不存在任何用户词库，第一次词库的生成要么就是直接从服务器同步，要么就是在用户第一次输入文字的时候建立。这种机制存在弊端：如果我A机器上有将近50KB的词库文件，然后我用用户ABC的账户登录，将A机器上的词库文件同步到服务器上的ABC账户中（假设第一次同步数据）。然后，在B机器上，如果有20KB的词库文件，我想要将其同步到服务器上的ABC帐户中，将其与之前A机器上所同步的数据进行merge，这是很实际的需求。但实际上，当你这么做了以后，服务器上将只存在20KB的B机器上的数据，A机器上的数据将会被直接冲掉！Google的做法实际上非常简单，仅仅是在本地不存在词库文件的时候，同步服务器的词库到本地；否则，就同步本地的词库到服务器。
我大概思索了一下解决方案，以下是我的设计思路：Google的词库文件对于每个词汇，都会记录它的使用次数。对于本地和服务器都存在的词汇，如何进行次数的合并是一个最关键的问题（对于那些只存在于服务器或者需要同步的本地一方的单词，我们可以直接将次数相加）。这个问题很类似于很多CVS工具附带的本地文件和服务器文件的merge功能，但是为了避免在Googl的服务器端备份太多的不同版本的词库，我打算为本地词库文件采用一种新的设计。这种设计仅仅为每个单词增加了一个field，姑且叫作diff，这个field记录单词上次与服务器同步之后在本地该再次使用所增加的次数。本地词库与服务器更新的步骤如下：将本地每个单词的diff值同步到服务器，与服务器上的相应单词的次数进行相加，最终得到的和就是该单词在服务器端和本地所使用的次数和。最后，同步服务器的最新内容到本地，并且将本地词库中同步完的每个单词的diff值清零。

2. 本地不同用户的词库。Google拼音目前貌似本地只有一个用户词库文件，不管哪个Google Account登录同步，都是与本地同一个用户词库文件同步。其实，用户自己的输入词库是很隐私的内容，不应该所有的用户都共享本地同一个词库文件。

3. 与搜索的集成。还是需要直接点击输入框上的某个按钮，为什么不支持搜索表达式语法呢？

4. 词库的网络管理。用户可以直接去网络上搜索其他人所共享的最新词库，将其加到自己的词库中，然后根据使用情况给其做rating；也可以将自己的词库进行分类，根据不同的使用环境，进行切换（垂直输入法:-))。呵呵，以上就是所谓的利用群体的智慧打造一款无敌的输入法。我想Google应该会考虑利用服务器端所备份的用户词库，但最好是在用户愿意公开自己词库的前提下。

5. 将Google中文输入法定位成一个平台：整合全世界中文词库的平台。在此基础上，提供相关的词库API，供第三方用户进行开发，这样子，Google的输入法可以迅速渗透到各种平台。用户可以和方便的将各种词库导入到Google的中文输入法词库。越多的输入法开发人员使用Google的中文词库API，Google就越从中受益。互联网时代，越开放的平台越容易成功！

BTW,写这个文章的时候，Google拼音（1.0.23.40）已经解决了本地词库文件冲掉服务端词库文件的问题。通过查看导出词库文件的格式，发现也没啥变化。我猜其做法有可能是本地和服务器同步时，将同步下来的文件备份一份，作为将来再次同步的时候做diff用。本地新增加的词频，将会更新到上次同步后的另外一个词库文件（与备份的词库文件内容完全一致）。当再次与服务器同步时，则会将本地最新的词库文件与上次同步时所备份的词库文件进行diff，将增加的词频到同步到服务器，然后再同步到本地。不过，这也导致了另外一个问题：我怎么将我服务器上的词库清零呢？如果永远备份在服务器，而用户只能不断地用本地新词库去与之同步，而对其没有完全的掌控权，其结果将是非常可怕的。

Gmail宣传片

2007-02-27T12:23:00.000+08:00

GOS上的关于Gmail的宣传片,非常有意思. :- )

My Heritage

2007-02-14T11:57:00.000+08:00

第一张照片的Heritage

第二张照片的Heritage

Free Computer Science Video Lectures Online

2007-02-06T21:55:00.000+08:00

Thanks very much to Kevin Greers and Peteris, they gave us a lot of useful computer science resources.

Video Sources

Audio Sources

Free University Courses - without video
OpenCourseWare

The Apple iPhone runs OS X

2007-01-10T13:57:00.000+08:00

Apple终于进军手机市场了, 下面是我从The Apple iPhone runs OS X上搜集的部分iPhone的照片:

的确令人惊讶, 不知道会不会在中国大陆发行. 至于价格嘛, 4GB的$499, 8GB的599$. 亚洲貌似要到2008年才发布. 不知道iPhone会不会成为2008年北京奥运会指定通讯设备.

Sorting Algorithms Visualized

2007-01-10T11:43:00.000+08:00

I got this "Sorting Algorithms Visualized" demo from Arno, it seems to be one of the coolest demos I've seen.

Mathematics books for Computer Science Students

2006-10-10T23:28:00.000+08:00

There're some classical math books for students of CS. If you wanna devote yourself into the field of TCS, you should improve your mathematics analysis ability. Remeber, computer scientists are better than mathematicians,because they know how to do it, not only what is it. Followings are the books that I'm reading now:
1. An Introduction to Probability Theory and Its Applications, Volume 1 by William Feller
2. Introductory Combinatorics (4th Edition) by Richard A.Brualdi

第一次尝试使用Blogger

2006-10-09T11:09:00.000+08:00

实在无法忍受Live Space的速度,所以打算转到此处开始我的新博客. Live Space上的内容以后不会更新了,我只保留2个blog:此处和cpper的.
BTW,今天下午收到了2本牛书:一本是关于算法分析的,另一本是关于复杂性理论的.主要是受了zero同学的刺激,打算挑战一下自己有没有毅力肯完这种TCS书籍.
1. An Introduction to the Analysis of Algorithms by Robert Sedgewick
2. Computational Complexity by Christos H. Papadimitriou