2009年2月25日星期三

Second-hand Hash

二手散列这个名字是我起的,官方叫法是Cuckoo hashing,他是一个散列算法框架而不是一个散列函数。事实上,二手散列需要两个散列函数h1和h2,对应两个散列表T1和T2,散列函数从值域(domain of values)映射到键域(domain of keys),散列表把键应成值。判断值x是否存在于字典D中:lookup(x,D)=(T1[h1(x)]==x || T2[h2(x)]==x)。
插入的方式很有趣,如果有散列冲突,就把原有值的踢出去,提到另一个表里去,知道没有冲突为止。用伪代码来说:
insert x into D:
如果lookup(x,D)返回真,返回
重复maxloop次:
    若T1[h1(x)]为空,则T1[h1(x)]=x后返回
    交换T1[h1(x)]和x
    若T2[h2(x)]为空,则T2[h2(x)]=x后返回
    交换T2[h2(x)]和x
如果代码走到了这一行,调整T1,T2的大小和h1,h2的值域,重新insert x into D

这是一个完美散列,因为我们确定地知道,lookup至多探查两次,绝对O(1)。难点在insert的复杂度的分析。注意到在insert中使用了递归调用,因此必需首先证明,insert的做法能够以较大的概率在有限步内终止。然后还能证明,insert的均摊复杂度的期望也是常数。证明过程这里就不转载了。
------
另外有一种d手链式散列的框架,针对一种特殊的问题,也有很漂亮的结果,出自《概率与计算》一书。n个球放入n个箱子,每个球放的时候先从n个箱子中等概率地选d(>=2)个箱子,然后放入这d个箱子中球最少的那个箱子。可以证明,以1-o(1)的概率,球最多的箱子中球的个数(称为最大负荷)是
基于此,我们可以开发出确定性O(d)时间插入、依很大的概率在至多lnlnn/lnd时间查找的链式散列算法。
d=1时,没有选择的余地,书中引理5.12告诉我们:n个球独立等概率放入n个箱子,最大负荷以1-1/n的概率至少为lnn/lnlnn。这告诉我们,在散列表比较满的时候,“一手”链式散列的性能和二分查找相当。对比发现,d手链式散列对传统链式散列的改进还是挺大的。
------
应用中,二手散列或d手链式散列还有一个好处:在多核处理器上可以并行计算散列函数,进一步提高效率。
------
P.S.复杂度的概率分析中大量用到了切尔诺夫界技巧

2009年2月23日星期一

Export all SMS messages as xml file from your Windows Mobile

昨天觉得手机中病毒了,老莫名其妙拨号上网。准备重装系统,先备份短信。.NET Compact Framework类库中outlook类中的SMS若干方法形同虚设于是找了一个第三方.NET的类库,MAPIdotnet。他构建在Windows API的MAPIlib基础上,专门用来访问Windows Mobile的短信的。他本身是for Smartphone的,稍微改一下就能在我的Pocket PC上跑了。
            //export all
            FileStream fs = new FileStream("smsExport"+DateTime.Now.ToString("yy_MM_d_H_mm")+".xml", FileMode.OpenOrCreate);
            StreamWriter sw = new StreamWriter(fs, Encoding.UTF8);
            //
            sw.Write("<?xml version=\"1.0\" encoding=\"UTF-8\" ?><sms>");
            for (int k = 0, K = this.stores.Length; k < K; k++)
            {
                IMAPIMsgStore store = this.stores[k];
                sw.Write("<store name=\""+store.ToString()+"\">");
                IMAPIFolder folder = store.RootFolder.OpenFolder();
                IMAPIFolderID[] subFolders = folder.GetSubFolders((int)folder.NumSubFolders);
                foreach (IMAPIFolderID fId in subFolders)
                {
                    IMAPIFolder f = fId.OpenFolder();
                    sw.Write("<folder name=\"" + f.ToString() + "\">");
                    IMAPIMessage[] messages = f.GetNextMessages(f.NumSubItems);
                    for (int i = 0, length = messages.Length; i < length; i++)
                    {
                        IMAPIMessage msg = messages[i];
                        msg.PopulateProperties(EMessageProperties.DeliveryTime | EMessageProperties.Sender | EMessageProperties.Subject);
                        //store folder subfolder msg
                        sw.Write("<msg when=\"" + msg.LocalDeliveryTime.ToString("H:mm d/MM/yy") + "\">");
                        sw.Write("<Sender name=\"" + msg.Sender.Name + "\"><![CDATA[" + msg.Sender.FullAddress + "]]></Sender>");
                        sw.Write("<Recipients>");
                        for (int j = 0; j < msg.Recipients.Length; j++)
                        {
                            IMAPIContact recipient = msg.Recipients[j];
                            sw.Write("<Recipient name=\"" + recipient.Name + "\">" + recipient.FullAddress + "</Recipient>");
                        }
                        sw.Write("</Recipients>");
                        sw.Write("<Subject><![CDATA["+msg.Subject+"]]></Subject>");
                     //   sw.Write("<Body><![CDATA[" + msg.Body + "]]></Body>");
                        sw.Write("</msg>");
                    }
                    sw.Write("</folder>");
                }
                sw.Write("</store>");
            }
            sw.Write("</sms>");
            //
            sw.Close();
            fs.Close();

2009年2月21日星期六

Chernoff bound

Chernoff bound

《概率与计算》一书中介绍了一个叫作“切尔诺夫界”的不等式,在概率论中,可以用来估计随机变量尾分布的性质,也就是随机变量在远离其期望值的某区域中取值的概率。切尔诺夫界可以用于分析算法的概率意义下的性能,具体来说,能给出算法运行时间超过某一阈值的概率的上界,或者解的相对误差超过某一阈值的概率的上界。

Wikipedia上有切尔诺夫界的若干中形式的公式。我在这里不加证明地引用其中一个比较简单的公式,然后给出一个它在算法分析上应用。

切尔懦夫定理:X1,...,Xn是独立随机变量,Xi服从0-1分布,,则对任意的ε,0<ε<1,有:

考虑这样一个判定问题:G=(V,E)为无向图,D={(si,ti),i=1,...,n,}为一个顶点对的集合,问是否存在{pi,i=1,...,n},其中pi为连接si到ti的路,使得任何一条边e属于E都没有被两条路pi、pj覆盖。
对应解一个优化问题:给一组路{pi,i=1,...,n},对于任一e属于E,定义cong(e)=|{pi|e属于pi,i=1,...,n}|,即通过e的路的条数。求{pi,i=1,...,n}使得C=max{cong(e),e属于E}达到最小,即让被通过次数最多的边,通过次数最少。

这个问题是NP难的,不过我们可以设计这样一个算法:线性规划松弛,然后随机近似。通过切尔诺夫界能够给出这个算法的近似率的一个估计。

令Pi为从si到ti的所有路的集合,记f(p,i)=1{p属于Pi},也就是表示p是否是一条从si到ti的路。优化目标是min C。约束条件有下面两个:
首先任何一对点si,ti恰有一条路p通过,
,对于任意i,
其次每一条边的冲突数不超过C,
,对任意e属于E。
我们把f(p,i)松弛到[0,1],用线性规划的方式求解。然后对每个i=1,...,n,用轮盘赌的方式以概率f(pi,i)选pi属于Pi。

上面就是线性规划松弛加随机近似的算法,下面用概率的方法分析这个算法。

定义随机变量表示路选中的路pi是否通过边e,i=1,...,n,e属于E。则:

定义,表示边e的被通过的次数。则:

由切尔诺夫界定理,立得:

2009年2月17日星期二

旁听《电视新闻研究》1

从这周开始,在北大旁听《电视新闻研究》,阿忆讲的。其实早就对电视媒体发生了兴趣,尤其是互联网对电视媒体的变革。要想读懂互联网电视,我认为首先应该读懂电视,然后才是读懂互联网。新闻,作为内容的一种,既出现于传统平面媒体、电视媒体,也出现于互联网后的新媒体。新闻,是媒体之所以存在的最原始也是最具有生命力的理由。
这个系列Blog是随记,不仅仅是课堂笔记,还记录了这门课上其他所见、所想。

2009年2月17日
"今天下午,我和丽冒着2009年的第一场雪骑车去北大找硕硕旁听阿忆的《电视新闻研究》。"
按照新闻学的分类,上面这句话是不折不扣的"硬新闻"。今天这堂课,主要就讲了一个"软新闻"的概念,它与"硬新闻"相对,有很多版本的定义,我理解的软新闻,就是讲故事,而硬新闻,则是中国人原来印象中的新闻。
"软新闻"不是电视媒体发明的,而是平面杂志发明的。1968年以前,电视新闻主要是硬新闻,因为它在时效性和感染力方面有着得天独厚的媒介优势,不需要用内容上的革新就能赢得广泛受众。而受到杂志上频见的"软新闻"的启发,CBS的《Cronkite晚间新闻》的执行制片人Don Hewitt在1968年引入了个性化新闻的理念,将"软新闻"带进电视媒体。值得注意的时间节点有两个,一个是1968年,当年《60 minutes》栏目就上线了,说明他的团队执行力强,另一个是在栏目不受好评的低谷中坚持摸索了7年,在1975年才成为相当于中国春晚一样的收视率极高的节目,说明他们能厚积薄发,耐得住寂寞。
这让我想到互联网电视,它相对于广播电视,和广播电视相对于平面媒体有很多相似之处。首先它们都是技术的革新带来媒介上的突破,使得新闻传播的更实时、更鲜活,影响力更大。其次,他们都在抢占传统媒体市场的同时,学习传统媒体中有价值的元素,例如电视从平面学来了"软新闻",而互联网也从电视学来了"文字直播"、"参与式新闻"等等。新事物的不会凭空产生,他们必须在旧事物中汲取养分,才能成长。互联网电视也一样。这也是我为什么想做互联网电视,却热心于学习传统电视媒体的原因。
《60 minutes》的Hewitt改变了新闻理念。Now, News is the story you never heard。好新闻的标准,据说是"昨晚播出的节目成为第二天早上人们的话题"。不过,我更认可另一种也许更保守、更古典的说法:新闻是历史的第一稿。仔细想想,二者并不矛盾,只是表意倾向不同罢了。
关于电视广告,有这样一个案例,每期《60 minutes》分为3个独立新闻故事,中间插播两个广告。即使这节目中抨击了广告主,广告主很不爽,却还要在这里打广告,因为其他地方的回报无法和这里相提并论。这让我想起以前经常听做互联网电视的朋友提起的一句话:内容为王。

也许是学校不同,也许是专业不同,北大新闻系的同学给我感觉放的更开。上课时,阿忆一度困扰于笔记本电脑接到音箱上没有声音,很快第一排主动站起来一个男生一个女生,走上讲台帮阿忆解决问题。女生打电话,和物业的人员沟通,按照提示尝试讲台上的各种开关,沟通很得体很有效率,男生则和女生配合,帮着拉开讲台的柜门、查看各种开关的说明等,很快找到了正确的开关,解决了问题:能听到阿忆笔记本电脑的声音了。他们也许上过阿忆的课,也许在坐很多都是他俩的同学罢,所以感觉特别自然,就像中学的一个班上,同学帮老师去拿粉笔或帮老师擦黑板一样,给人感觉很亲切很温馨。在清华理工科的课堂上,我从没见过这种场面。遇到笔记本电脑声音放不出来,要么是所有同学都对老师的无助无动于衷或爱莫能助,要么是于无声处跳出来一个惊世骇俗的大牛,上去一按,电脑就出声了。

2009年2月15日星期日

正心诚意读书不二

最近经历了一些大悲大喜,发现自己内心越发平静了。
正心诚意,出自《大学》,刚上大学时特别特别喜欢的一句话,烙在了骨子里。虽然多年来学习成绩一直很一般,但是却自以为学得很洒脱,很愿意砸时间去享受自由的思考的乐趣。"古之欲明明德于天下者,先治其国;欲治其国者,先齐其家;欲齐其家者,先修其身;欲修其身者,先正其心;欲正其心者,先诚其意;欲诚其意者,先致其知,致知在格物。"格物,我以为指的是学好物理和数学,或者说了解自然和理性。这一串"责任链"中最重要的,我认为是正心诚意。自古以来,许多治国者没有很好的根基,风光一时甚至一世,但最终被人民群众和历史否定,无法达到"明明德于天下"的儒家理想。也许是我的唯物历史观太教条了罢。。。
读书不二,出自曾文正公的自律条款。"敬、静坐、早起、读书不二、读史、谨言、养气、保身、日知所亡、月无亡不能、作字、夜不出门"。我特别喜欢其中"读书不二"这句,以为是不要同时读两本书的意思。很多时候,我们到图书馆会搞一大堆书,东翻翻西看看结果哪一本都没看透。这样不好。最近我在潜心读一本书《Algorithms for hard problems》,去图书馆只带这一本书、一支笔、一个笔记本(纸的)。只读一本书时,心灵会觉得特别纯净。虽然这本书很难啃,而且对眼下的毕设、对即将面对的工作没有多少直接帮助,却提供了很多我认为很有价值的算法设计与分析的思想,读起来很享受。专注,是一种做学问的态度,也是一种做人的态度,适合一小撮人。他们是畏惧社会吗?看你怎么看了。
正心诚意,读书不二。继续,作我的快乐学术男。

2009年2月6日星期五

赫鲁晓夫在哪里

1965年2月14日,苏共第二十次代表大会在莫斯科召开。2月24日深夜,赫鲁晓夫忽然做了《秘密报告》,系统揭露和批评斯大林的重大错误,要求肃清个人崇拜的流毒。顿时在国内外引起强烈反响。很多人就有疑问,你既然知道他的错误,为什么在斯大林生前不提出来呢?后来,在党的代表会上,赫鲁晓夫又谈此问题时,有人从听众席传来一张纸条,上面写着:当时你在哪里?
赫鲁晓夫不愧是政治家,看看他是如何机智应对的。
他拿起纸条,大声念出了上面的内容,然后向台下喊道:"请写这张纸条的人,马上从座位上站起来,并走到台上。"台下鸦雀无声。赫鲁晓夫又重复了一遍,台下依然一片死寂。于是,赫鲁晓夫淡淡地说:"好吧,就让我告诉你,当时我就坐在你现在坐的那个位置上"。

这个故事来自一本博弈论的科普读物,当时正在讲多人博弈的人质困境。