博文

目前显示的是 十月, 2013的博文

Perfect Hash and the gperf Tool

MIT的算法导论课上,老师用了整整一节课来讲Perfect Hash这个问题。所以这是一个很重要的问题,但是内容太多,我这里只是做一个简要的介绍。感兴趣的请去MIT的网站上下载视频以了解的更详细。
Perfect Hash主要是为了降低或消灭Hash冲突。 当你用Hash表来存储一个集合或映射时,不同的key可能被映射到同一个槽(slot)当中,此时就得用链表或者Open Address或其它方法来解决Hash冲突。毫无疑问,冲突越多,查找性能越低。对于一个含有N个元素的Hash表,在最坏情况下,查找效率是O(N)的。但是如果这是一个静态的Hash表,所有的key预先已知,我们就可以挑选适当的Hash函数来把最坏情况降低到O(1)。 本文会先介绍通用散列函数族(Universal Hashing Functions),然后介绍Perfect Hash,然后介绍如何使用gperf这个工具生成这样的Hash函数。
通用散列函数族(Universal Hashing Functions) 先介绍一下背景。对于任何的Hash函数,我们都可以刻意构造一些特殊的输入,使得Hash冲突非常高,从而让Hash表的性能大大降低。为了抵御这种攻击,我们可以实现一大堆的Hash函数,然后在构造Hash表的时候从中随便挑一个。由于你不知道我挑的是哪一个,你也就没办法捣乱了。这有点像用随机化方法来优化quick sort在bad case下的表现。我们也打算用随机化方法来优化hash表面对bad case时的性能。
通用函数族的定义:设集合\(U\)是一个全域, \( \left| U \right| \geq n \),令集合\( V=\{0,1,2,3,...,n-1\} \),\(H\)是一个从\(U\)到\(V\)的Hash函数族。如果\(H\)满足:对于任意的元素\( x_1,x_2,x_3,...,x_k \) 以及从\(H\)中均匀随机选取的一个散列函数h,有\(h(x_1) = h(x_2) = h(x_3) =... = h(x_k)\)的概率小于\(\frac{1}{n^{k-1}}\),那么\(H\)就被称为k维通用Hash函数族。
所以,如果hash函数h是从一个2维通用hash函数族中选取的,那么对于任何两个元素x,y,它们的hash值h(x)=h(y)的概率最…

2013-10-22 学新概念、协和看痘痘

好久没更新了,继续记流水帐.首先是新概念的学习进度,严重拖后。本计划每天5篇,实际上,我今天才学完第26课,实际速度是一天2篇。说明我并没有坚持每天花两小时学英语,呃…… 只能默默的对自己说,"Hurry up!"协和就诊记:上周二,也就是10月15号,我闲着无聊去协和挂了个号看痘痘。痤疮一般主要成因是皮脂腺快速发育和皮脂过量分泌。因为皮脂分泌过多而导致毛囊皮脂腺导管阻塞,细菌繁殖、感染、炎症反应等等。由于我的痤疮很轻微,一般也就1-2颗,所以没有用维A酸。主要是涂抹抗生素。没想到这次去看,医生看了我一会儿,然后看看之前的用药,然后就一口断定我缺乏维生素B6,于是给我开了维生素B6片和班塞(一种外用抗生素)。我回来查了一下,缺维生素B6的主要症状除了脂溢性皮炎外,还有就是嘴唇干裂。难怪我之前嘴唇总是裂的出血,喝再多水都没用,涂润唇膏我又觉得别扭。嗯,恰好我一个朋友正在协和营养科进修,我准备去问问她食物中什么含维生素B6比较多,我估计和我之前挑食不爱吃粗粮有关。不过无论如何,一周过去了,我并没观察到药物对我脸上的痘痘有何影响。娱乐篇:最近迷上了一个美剧,The Newsroom。我刚把第一季看完。主题是美国政治辩论、记者的职业操守、办公室政治和恋情等。语言风格很严谨,逻辑清晰,考试作文典范。由于每一集的选题都是紧扣美国刚刚发生的重大新闻事件,所以看的时候我不得不来回查wikipidia.

对人的生命的平等尊重

昨天上口语课,主题是中美文化差异。我的外教老师对中国人不遵守红绿灯很不满。他说美国人开车的时候遇到红灯一定会停下来,不管其它方向能不能看到车和人经过,不管有没有摄像头。行人也一定等绿灯亮再走,不管路上有没有车。我说这不是中美文化差异,这是法律差异。在中国,只要我在斑马线,你开车撞了我,那就是你的全责,你要承担所有损失和医药费。不管当时是红灯还是绿灯。然后一个同学,35-40左右的大姐站起来,义愤填膺的说自己的经历。她的亲戚在西三环开着车,然后一个人突然冲出来,被撞死了。然后她亲戚全责,赔了好几十万。她如此愤怒的倒不因为责任怎么划分,是因为被撞虽然是外地人但是有北京暂住证,所以要按北京人的赔偿标准走。因为北京的平均工资比周边城市高很多,所以她亲戚要多赔很多钱。于是她觉得她亲戚被坑了。于是我走过去给她说,我学驾照时老师专门讲了一个案例:某一天有人突然从北京二环路的隔离带跑出来,然后被撞死了,然后开车的人全责。中国的交通法就是这么规定的。中国的交通法甚至规定在斑马线上汽车必须让行人先走(不管交通灯是什么颜色)。她说她知道,她学交规时也讲过。但是她依然很生气,觉得这是恶法。她觉得国家之所以这么规定,是因为行人身上没钱,你不可能让他给你赔什么。这就是核心点: 开车的总觉得他和走路的是处于不同阶层。开车的有钱、有固定工作、有固定居所,而路上走的都是穷人,甚至流浪汉、乞讨的,甚至不惜拿自己的命来讹一笔的。她不会对她瞧不起的人表示出应有的礼让,所以她不会看到人多就减速,不会刻意让行人先走。所有这一切都可归结为北京人口太多了,所以该死就死该滚就滚吧,别让我在这等着。我这位大姐甚至没有想过死亡赔偿为什么不能按户口走?户口可是世袭的啊! 会有人跑北京来就为了办个暂住证被撞死然后讹一笔吗?如果中国的穷人真被逼到这份儿,那这个社会完蛋好了!纵使你骄横一世,死后也不过一掬尘土。人与人到底又有多大差别呢?至于交通事故频繁、行人和车辆不遵守红绿灯,究其原因,是因为在中国遵纪守法的人都因自然选择而被饿死了,绝种了。运煤的货车为什么超载?不超载它利润就是负的啊!为什么不遵守规则?如果人人都遵纪守法,合法经营,谁还刻意去跟工商、税务、公安局搞好关系,吃喝送礼拜把子?所以规则必须要有缺口,那个缺口才是真正的"正路"。开饭馆的为什么要给黑社会交保护费? 因为不交就会有人来"找…

2013-10-11 新概念学习笔记

英语学习进展:今天把新概念2的6-10课的习题做完了。主要复习的语法是a/an/the/some的用法几个简单的介词短语,如put on ,take off过去进行时与when/while.何时介词短语可以拆开用。比如 take off it可写成take it off,但是 look for 就不能拆开。形容词和副词的比较级、最高级时间短语前的介词, on/in/at/during。这个只能靠语感一般过去时中的被动语态。另外我买了个泛读课本(http://book.douban.com/subject/6560219/),发现里面的课文很有意思,我准备把习题挨个做一遍,可惜没有找到问题的所有标准答案。感觉,像跑步。第一天跑10km觉得just so so,第二天再跑就觉得要死了。加油!

2013-10-10 英语学习笔记

最近我开始非常正式的学英语,平均每天花4小时以上,以期有质的突破。先汇报下我现在的英语水平。现在阅读能力很强,随便扔给我一本数学或计算机方面的专业书籍,不管是1000多页的教材,还是新近发表的paper,我都可以不拿词典快速阅读完。因为我从2004年开始,买的专业书籍都是英文为主,只有买不到影印版的才买中文版。这样练了9年,阅读能力还算不错,专业词汇量积累很高。但是另一方面,口语、听力、写作等等只有初中生的水平。前几天我在网上看到北外杨立民教授的一段话:"英语水平高低只有一个可靠的标准:就是看一个人利用它能表达多少思想,表达到什么深度以及表达得如何精确,生动,流利。" 按照这个标准,我的英语水平仅仅是旅游够用,边说边比划着订个房间点个菜什么的,所以连及格分都拿不到。每个人都有学好英语的愿望,而我现在是把will变成doing,并为有突破进展而不惜花很大代价。那么是什么让我感到如此紧迫呢?我现在迫切需要从国外技术人员那里询问并获得答案,以解决工作中所遇到的问题。中美的软件技术水平相差很大,工作5-6年之后,在某些技术方向就会做的比较独到。此时遇到的问题在国内社区基本找不到答案。比如我把我遇到的IPSec的问题发到水木上去,常常一个回复都没有然后就沉下去了。但其实每个技术产品都有它官方的社区,从那能得到答案,但是它只使用英语交流。例如stackoverflow是块宝,但我却用不起来。能够准确的描述自己的问题,是一种基本的表达能力。如果想要在开源社区做出贡献,沟通比编码更重要。常规的流程是:了解现在有哪些任务,告诉他们我准备怎么做,然后写代码,然后我的mentor看完代码后告诉我哪里有问题,该如何修改。这一切的一切,都离不开反复的发邮件。不能只是被动的读文档、写代码,必须要能够把自己的想法用英语表达出来。试想一下,假如你现在招了一个程序员,他是个哑巴,而且也不会写邮件。即便他算法一流,高考数学考了148,你愿意雇他吗?你能把他的能力充分发挥出来吗?再拿新浪的程辉做例子,普通本科毕业2年就能在开源社区做的如此风生水起,可见技术能力真的不是很重要。会Argument的人在外企是紧缺人才,也是升senior level的重要的必备能力。我一直以来很想去Microsoft工作,但是前一段时间MS的朋友给我说,MS是一个很大的公司,如果你在中国这边工作,那么最…

GYP and Chrome

一、简介GYP是google的一套构建系统,和 cmake 的目的很像。GYP和CMake的主要作用是,从用户编写的一套配置文件,针对不同的工具链生成不同的项目文件(如Makefile/vc projects/xcode projects)。GYP安装:svn co http://gyp.googlecode.com/svn/trunk gyp cd gyp ./setup.py build ./setup.py install 下面是GYP的配置文件的示例:{ 'targets': [ { 'target_name': 'hello', 'type': 'executable', 'sources': [ 'main.cpp' ] } ] } 看上去基本就是一个json。它定义了一个名为hello的target。target的类型是executable,表明它是一个可执行文件。如果要编译库,就换成static_library或者shared_library。sources是一个数组,列出所有的源文件。然后用# gyp hello.gyp --depth=. -f make 生成makefile。然后执行make命令即可。从设计目标上来说,它和autotools还不大一样。autotools只针对make,且仅限于gnu make。autotools的核心是autoconf,如何利用shell脚本在不同的操作系统环境下生成相应的config.h文件。它利用它强大的检测功能很容易适应不同的Unix/Linux环境。而GYP和CMake都支持各种主流的构建系统。如make/Visual studio/XCode/Ninja。CMake支持构建系统的种类要更多些,比如eclipse cdt、Sublime Text 2、CodeBlocks、Borland C++等等。而这些非主流的东西GYP压根就不会去碰,不敢碰。按最理想的情况,我们写一套配置规则,在所有平台上都能执行。此时我们可以不关心操作系统是什么。拿autotools来说,假如你要include某…