帖子

目前显示的是 2013的博文

乙肝疫苗是否值得接种?乙肝是否会通过食物传染?

乙肝会通过食物传染。中国是一个乙肝大国。中国疾病预防控制中心在黑龙江、河北、河南及湖南四省做了一次抽样调查,结果表明58%的人感染过乙肝。而其中60以下人群HBsAg携带率为7.18%,即9300万慢性HBV感染,约占全世界的27%。何以至此?其实乙肝病毒很难传播。人类是乙肝病毒的唯一宿主。乙肝只能通过人传人。主要传播方式为:母婴传播、儿童间传播、不安全注射、输血和性接触。所以只要人人都从出生就接种乙肝疫苗,那么乙肝就很容易被消灭了。不打疫苗风险很大,儿童是最需要接种乙肝疫苗的。中国乙肝病毒携带率高(7%),儿童因为免疫机制不完善所以很容易感染,一旦感染大多会变成慢性乙肝。儿童间传播的机理大多数是由于接触皮肤的破损部位或黏膜血液或皮肤渗出的分泌物而感染病毒。乙肝病毒也可通过唾液经过咬破部位或其它破损部位传播,所以它也可通过咀嚼食物传播,甚至可以通过公用毛巾、牙具传播。既然中国有高达7%的乙肝病毒携带率,有什么理由不给孩子打疫苗呢? 相比而下,成人有完善的获得性免疫机制,乙肝病毒只能通过性行为和血液传播,而且成人在感染乙肝病毒后一般都可以自行清除,只有5%-10%会发展成慢性乙肝。所以成人不必对乙肝太惊慌,也不要害怕与乙肝病人共餐。慢性乙肝一旦得上,终身受累,它很难治愈。目前FDA批准用于治疗慢性乙肝的药物,主要是抑制乙肝病毒,或者缓解患者的肝脏疾病。且如果病毒载量持续很高,它会加大肝硬化的发生率。而肝硬化患者又较容易发生肝细胞癌(年3%-6%)。乙肝病毒可通过基因组重组间接或直接作用引发肝细胞癌症(HCC)发生。 乙肝疫苗理论来说很安全。在世卫组织的安慰剂对照的研究中,除局部疼痛外,接种组中报告的不良事件(如肌痛和一过性发热)并不比安慰剂组多。 实际上每年确实有很多婴儿在接种疫苗后死亡,但是这真的是因为疫苗导致的吗?未必。但确实,全球范围内,越来越多的父母因此而拒绝给孩子打疫苗,他们在媒体上联合起来公开抗议。可我不认为他们这么做是对的。我希望通过免费计划免疫,让乙肝留着我们这一代人,不要再传给下一代。更多资料请见美国CDC网站:http://www.cdc.gov/vaccines/vpd-vac/hepb/fs-parents.html

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某…

腾迅入股搜狗,是张朝阳想套现?

9.16日,腾迅以4.48亿美元现金加上旗下的搜索资产,换取了搜狗的36.5%的股份和20.6%的投票权。搜狗为什么要出售?首先,此次交易对应的股份都是增发的新股,而且是B类优先股(一部分有投票权)。SEC公告上说,这部分资金中的3亿美元在交易结束后会发放给sogou现有的A类优先股的持有者。"Sogou will use a portion of the cash proceeds of Tencent’s investment to pay a special dividend in the amount of approximately $301 million to the holders of Series A Preferred Shares of Sogou, payable promptly following the closing of the transaction."记者会上说"这一次增发新股,后面会给原来老股东派股息,然后回馈小股东。最重要的是拿到腾讯的资源。"我十分不明白为什么要在此时发放特殊股利给A类优先股的持有者。那么这些持有者又是谁呢?根据历史公告,在2010年10月22日,搜狗出售了24.0 million, 14.4 million and 38.4 million份A类优先股分别给阿里、Yunfeng基金以及张朝阳自己的Photon基金,当时的价格分别是1500万美元、900万美元、2400万美元。对应的份额约为10%, 6% and 16%。此时搜狗依然保留搜狗53%的股份。根据2011年6月的公告:As of June 30, 2011, Sogou had outstanding a combined total of 216,000,000 ordinary shares and Series A preferred shares, consisting of (i) 139,200,000 ordinary shares held by Sohu; (ii) 24,000,000 Series A preferred shares held by Alibaba; (iii) 14,400,000 Series A preferred shares held by China…

UVA 最大递增子序列(LIS)相关题目总结

基本的: (直接用LIS算法就可以解决的)231 Testing the CATCHER497 Strategic Defense Initiative481 What Goes Up 关于LIS算法的基本实现,可参考我之前写的: http://www.sunchangming.com/blog/post/4583.html下面列些非基本的 10534 - Wavio Sequence这个问题求Wavio Sequence的最大长度。Wavio Sequence是指,先递增再递减,递增部分的长度和递减部分的长度一样,所以最终这个序列的长度必须是2N+1。比如 1 2 3 2 1 就是一个Wavio Sequence。假设给1 2 3 4 5 4 3 2 1 10 这样一个序列,怎么求出它长度最大的Wavio Sequence呢?假设原数组为A[0...n],可以证明,对于任意的A[i],以它为中心的最大长度的Wavio Sequence就是向左找最长上升序列,向右找最长下降序列,然后拼接起来。最后为了满足2N+1的条件,裁减一下。我的做法是,做两次LIS,一次从头往尾做,另一次从尾往头做。然后遍历求max。代码如下:std::vector<size_t> ret1=lis(nums.begin(),nums.end()); std::vector<size_t> ret2=lis(nums.rbegin(),nums.rend()); size_t maxlen(1); for(size_t i=0;i!=ret1.size();++i){ size_t l=ret1[i]; size_t r=ret2[ret1.size()-i-1]; if(l==1 || r==1) continue; maxlen=std::max(std::min(l,r)*2-1,maxlen); } std::cout<<maxlen<<"\n"; 其中lis算法可以用O(nlgn)的实现,具体我省略掉了,请参见我之前的日志。10131 - Is Bigger Smarter?参见 http://www.sunchangming.…

致身为儿女的80s们,我们的父母真的开始老了

我是一个北漂,85年出生,今年28岁,无房无车无户口。在此讲一些我身边的事情,提醒大家要开始注意父母的身体健康了。人都会老,而我们的父母现在就在这个坎上。先从我一个朋友的事情说起。她两年前工作调动来的北京。她母亲是教师,恰逢放假,就过来看看。她母亲身体一向很好,连感冒都很少得。每天她去上班,她母亲就下楼去晨练。等周末了,就一起去颐和园什么地方去逛逛。然后突然有一天,她母亲就倒下了,急匆匆的送进了301的ICU(不是急诊科)。她开始四处筹钱,不先准备个10万不行。还好,最终有惊无险,阿姨过了两周顺利出院,又乐滋滋的跟我们去逛公园了。只有医生清楚她是多么幸运。我姨,也就是我妈妈的亲姐,刚去世没几年,地里正收庄稼呢,突然就脑溢血倒下了,在送去医院的当天就过世了,那时她还不到60岁。我妈,多年来一直体重不过百,吃饭很少,血压偏低。然后突然有一天,就高血压、脑梗塞了。多次晕倒在地上,以至于我们很不敢放她独自在家,但是又没有办法。该上班的要上班,我弟弟该上学还要上学,谁能天天在家守着她呢?谁也没有料到,刚到50岁,就从低血压变成高血压了。她是突然晕倒在地然后被送去医院然后抢救过来,她才知道自己有高血压。并且已经有颈动脉斑块,腔隙性脑梗塞。之所以想写这篇长文是因为今天,又是一个中学同学,打电话咨询我,他父亲颈椎有问题,老觉得身体麻木,是该看骨科还是神经科?我说,当然该看骨科啊!问题是你咋知道颈椎有问题呢,拍片子了?他说拍了,说是颈动脉有点问题,好像是有点堵。我晕,我赶紧改口让他去看神经内科,并且很严肃的告诉他,那就是一个定时炸弹,不定什么时候爆发,重则瘫痪。但要是积极治疗一直保持注意,其实也没事。我们当务之急是,多关心父母的健康,向他们灌输正确的健康观念。每年体检对于50岁以上人太重要!我第一次带我爸去做体检,花了300多,除了腰围太粗之外什么都没查出来。所以他觉得体检不值得。他很愤恨,腰围太粗这需要你查吗?我照照镜子自己都知道。在他看来,花了钱,却什么都没查出来,这钱是白花了。他说他健康的很,不用查就知道。嗯……他不知道腰臀比过高意味着什么,难道要像我妈一样,直到突然有一天晕倒被送到急诊科了,才知道自己有高血压吗?话说我妈比我姨幸运多了。但是我妈也2多了,一边在病房挂着点滴,一边偷偷的跑出去买酱鸡爪啃着吃。她向我们抱怨医院的伙食太差,整天清汤寡水的,像坐牢一样。她说我们故意虐…

uva 10131 - Is Bigger Smarter?

题目http://uva.onlinejudge.org/external/101/10131.html输入是一些有序整数对(a1,b1)
(a2,b2)
(a3,b3)要求从中挑取一部分输出。 输出需要满足满足第一列严格递减,第二列严格递增,即 a(i) < a(i+1) && b(i+1) < b(i) 输出的序列可以不保持原先的相对顺序。求输出的序列的最大长度。分析这是一个与LIS相关的题目。我想套用之前的代码,在O(nlgn)的时间内解决这个问题。 关于LIS的讨论参见 http://www.sunchangming.com/blog/post/4583.html首先,我的想法是,把输入的序列按照第一列排序,然后扔到我之前写好的LIS函数中求解(求LIS时只考虑b的值,不管a)。可惜,失败了。因为第一列有可能重复。(1,3)
(1,2)的LIS的长度应该是1。如果LIS的时候不考虑第一列,会出错。于是我把LIS的时候的comp函数换成了booloperator<(const elephant& r) const{ returnthis->first < r.first && this->second > r.second; } 结果还是错了!这跟我采用的LIS算法有关。假设输入为A[0]={500,1}
A[1]={500,2000}
A[2]={600,1000}在处理第二行的时候, 因为A[1] < A[0] == false ,所以我不能拿它来替换M[0]。并且 A[0] < A[1] == false,我也不能把它放在原来的LIS的末尾构成一个更长的LIS。综上所述,我只能在处理中把它丢弃。结果是,在处理A[2]的时候遇到了同样的情况。所以,要使我的算法能正常工作,如果有A[1]<A[2] && !(A[0]<A[2]) 必须有 A[1] < A[0]于是我最终这样:排序的时候,两列都按照升序排计算LIS的时候,对于第一列,只判断是否相等。booloperator<(const elephant& r) const{ returnthis->first != r.first &&…

Longest Increasing Subsequence

题目uva 481: What Goes Up http://uva.onlinejudge.org/external/106/10684.html这个问题是这样:给定一个数组a[0...n],求它的单调严格递增子序列的最大长度,并给出一个示例解。子序列是从最初序列通过去除0个或多个元素但不破坏余下元素的相对位置而形成的新序列。严格单调递增是这个序列中每个元素都小于后一个元素,不能等于,也不能大于。例如:-7 10 9 2 3 8 8 1 的解是4,其中一个长度为4的LIS是:-7 2 3 8例如:0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 的解是6,其中一个长度为6的LIS是:0, 2, 6, 9, 11, 15这就是一个很普通的求 LIS(Longest Increasing Subsequence)的问题。我本来LIS以为和LCS很像,但是实际写一下发现,这个东西挺难的,花了我整整一下午的时间才写好。解法一首先,基本思路是用动态规划,自下而上的把解构造出来。要使用动态规划,就得有最优子结构。下面来分析一下。把原来的问题稍微加点限制。设LIS(i) : 以a[i]为右端点的单调严格递增子序列 (加了以a[i]为右端点这个限制)那么显然有LIS(0) = a[0];LIS(i) = max { LIS(j)  : a[j]<a[i] && 0<=j<i } .append( a[i] );所以在O(n^2) 的时间内,就能求出最大长度。另外,如果我们直接存储n个LIS,那么空间消耗是O(n^2)的。所以实际计算中可以采用下面这样的方法:先用一个数组m,其中m[i] =  LIS(i)的长度。所以m最终的长度和输入数组a的长度一样。另外一个数组indexesindexes[i]: 以a[i]为结尾的lis的a[i]的上一个的(index+1)。0,没了 。这个有点像链表。我用0来标志结束,所以不得不在存index的时候都先加1,再存入。最终通过遍历链表的方式遍历这个数组,就可以得到子序列。 代码如下: //return the indexes of the origin array template <typename T> std::vector<…

UVA 11264: Coin Collector

http://uva.onlinejudge.org/external/112/11264.html原问题是这样:小明去国外玩,想兑换些货币。他希望每种面值的货币都兑换点。但是兑换处的人可不理会他这个需求,兑换处的原则是,尽量挑选面值最大的给他。比如货币的面值是100、50、20、10、5、2、1,你要76块钱,那我先给你50,还差你26。于是再给你20,还差6块。那我再给5块,再给1块。嗯……一般人都是这样给钱的吧?但是小明就是喜欢收集钱币啊。假如货币的面值种类已知,问用这种方法最多能换到多少种?假设小明很富有,钱无限多。例如:1 2 4 8 16 32 6种1 3 6 8 15 20 4种1 3 6 8 11 3种答:假设输入的数组为A[1...n] ,它代表了N中不同面值。假设我们已经按照从小到大排序,其中A[1]最小,A[n]最大。如果小明拿m元换得了k种货币,那么m最小是多少? 答:把这几种货币的面值加起来。另外,A[n](即面值最大的)一定会被选中,反证:如果花了m元却没有选中它,可知m<A[n],于是用m+A[n]元去兑换可以得到一个更优解。假设S(i)是A[1]...A[i] 中那些被选中的货币的面值的和。那么一定有 S(i) < A[i+1]。假如我们已经知道最优解是k种货币,那么它对应的具体哪k种呢?这个答案是否唯一? 不。 拿1 3 4来说, 1 4 和 3 4 都是最优解。所以我们想办法构造一个这样的序列出来。按照规则:如果有S(i-1) + A[i] < A[i+1],那么A[i] 被选中。首先,这个序列很显然是一个合法的序列,所以它是解。其次,要证明它是最优的,即,不存在比它更长的合法序列。longresolve(std::vector<long>& nums){ if(nums.size()<=2) return nums.size(); std::sort(nums.begin(),nums.end()); nums.push_back(LONG_MAX); //now,nums.size()>=3longret(2); longsum(nums[0]+nums[1]); for(size_t i=2;i!=nums.size()-1;++i){�…

uva 624 - CD (0-1 knapsack)

http://uva.onlinejudge.org/external/6/624.html我把这个问题复述一下。输入有很多行,每行都是如下格式sum n a1 a2 a3 a4 这样的格式。如5 3 1 3 4sum = 5 背包的容量是多少n =3 有多少个物品1 3 4 每个物品的体积是多少。然后要你把物品塞进背包里,把这个背包尽可能的塞满。对于上面的输入,输出是这样:1 4 sum:5含义是:体积最多能塞到5。 因为1+4=5。
例如:
10 4 9 8 4 2
对应的输出是:
8 2 sum:10例如:
20 4 10 5 7 4对应的输出是:
10 5 4 sum:19
例如:
45 8 4 10 44 43 12 9 8 2
对应的输出是:
4 10 12 9 8 2 sum:45或者:
43 2 sum:45也就是说答案并不唯一,但是online judge系统都能接受。这个问题是经典的动态规划问题,但是我看大多数地方把它归为backtracking。他们是用backtracking and pruning 的方式来解决这个问题。However,即便是用动态规划解,程序也有很多不同的写法。有的人是用一个大的矩阵保存计算的中间结果,但是只保存total value,不保存每个物品具体的index。然后最终,backtracking一次这个矩阵,把最大值对应的所有的index计算出来。而我是在计算的每一步都把index记住,这样我就可以只用两个vector,或者甚至只用一个vector就保存所有的中间值。struct Result{ std::vector<size_t> indexes; long total; Result():total(0){} voidadd(long v,size_t index){ total+=v; indexes.push_back(index); } }; Result resolve(conststd::vector& values,long cap){ if(cap<=0) return Result(); std::vector* memo=newstd::vector; memo->resize(cap+1); for(size_t …

Catalan Number and parentheses

Question:print all valid (properly opened and closed combinations of n-pairs of parentheses, and how many they would be?for example, when n=2, there are 2 kinds:(()) , ()()when n=3, there are 5 kinds:((())), (()()),(())(),()(()),()()()Anwser:如果直接按照题意写,可得到如下代码:staticvoidprint_parentheses(std::string s,int ln,int rn){ if(!ln && !rn){ std::cout<<s<<std::endl; return ; } if(ln>0) print_parentheses(s+"(",ln-1,rn); if(rn>ln) print_parentheses(s+")",ln,rn-1); } int n=4; std::string s; print_parentheses(s,n,n); 但是,为了减少string的copy次数,可以改成传引用。staticvoidprint_parentheses(std::string& s,int ln,int rn){ if(!ln && !rn){ std::cout<<s<<std::endl; s.resize(s.size()-1); return ; } if(ln>0) print_parentheses(s.append(1,'('),ln-1,rn); if(rn>ln) print_parentheses(s.append(1,')'),ln,rn-1); if(!s.empty()) s.resize(s.size()-1); } 但是,到底会输出多少结果呢? 分析的过程比较麻烦。下面我的分析不好,请参见算法导论第三版的思考…

BST functions in libc

我今天刚发现,原来libc里面自带的就有二叉搜索树相关函数.void *tdelete(constvoid * restrict key, void ** restrict rootp, int (*compar) (constvoid *, constvoid *)); void *tfind(constvoid *key, void * const *rootp, int (*compar) (constvoid *, constvoid *)); void *tsearch(constvoid *key, void **rootp, int (*compar) (constvoid *, constvoid *)); voidtwalk(constvoid *root, void (*action)(constvoid *, VISIT, int)); 其中tsearch其实是insert函数,名字有点歧义。另外我看了下实现,发现FreeBSD下,这几个函数实现的是最最基本的BST,就是一点旋转、平衡都没有的。而在Linux下,它们是红黑树。freebsd下没有destroy函数。其实这个只需要按照中序遍历,对每个节点delete/free就行了。

BFS与水罐灌水问题

图片
三个水桶,最大容量为10L, 7L, 4L。初始状态为,10L,0L,0L。 即,第一个是满的,后两个是空的。可进行的操作:把某个水桶的水倒入另一个水桶中,直到这两个水桶的某一个满了或者空了。 比如 (10,0,0) -> (3,7,0)问:至少进行几次操作,使得某一个水桶的水为2。就是说,怎么倒来倒去,能量出2L水来。这是一个很古典的智力题。解:我们先画一个圆圈,写上(10,0,0),代表水桶的初始状态。然后把它能通过一步操作转移到哪些状态,也画出来,用线连起来。如此反复。最终我们会得到一个很大的无向图,每个节点都是一种状态,每条边代表一次倒水操作。我们要做的,是从(10,0,0)这个节点开始,进行广度优先搜索。/** * 三个水桶,最大容量为10,7,4 * 初始状态为,10,0,0 * 可进行的操作:把某个水桶的水倒入另一个水桶中,直到这两个水桶的某一个满了或者空了。 * 问:至少进行几次操作,使得某一个水桶的水为2 */#include <iostream>#include <queue>#include <algorithm>#include <unordered_map>#include <string.h>struct Node { int state[3]; Node(int x, int y, int z) { state[0] = x; state[1] = y; state[2] = z; } Node(const Node& n) { memcpy(state, n.state, sizeof(state)); } booloperator==(const Node& n) const { return !memcmp(state, n.state, sizeof(state)); } boolisFound(int n)const{ return state[0] == n || state[1] == n || state[2] == n; } }; struct NodeHash { size_t operator()(const Node* n)const{ si…

UVA 138 - Street Numbers

QuestionA computer programmer lives in a street with houses numbered consecutively (from 1) down one side of the street. Every evening she walks her dog by leaving her house and randomly turning left or right and walking to the end of the street and back. One night she adds up the street numbers of the houses she passes (excluding her own). The next time she walks the other way she repeats this and finds, to her astonishment, that the two sums are the same. Although this is determined in part by her house number and in part by the number of houses in the street, she nevertheless feels that this is a desirable property for her house to have and decides that all her subsequent houses should exhibit it.Write a program to find pairs of numbers that satisfy this condition. To start your list the first two pairs are: (house number, last number):6 8
35 49Anwser完整的输出是6 8
35 49
204 288
1189 1681
6930 9800
40391 57121
235416 332928
1372105 1940449
7997214 11309768
46611179 65918161这个问题用数学语言描述就是,找到正整数n,m,…

Max subarray problem

原始问题给一个数组a[0...n],假设a[s...t]是它的子数组,那么这个子数组的所有元素加起来最大是多少?用数学语言形式化的描述就是:求0<=s<=t<=n 使得 a[s]+a[s+1] .... + a[t] 最大。这是算法导论书上的一个经典例题。书上给出了怎么用Divide and Conque的方式求解,算法复杂度为O(nlgn)。但是它同时也说了,有更好的做法,能在O(n)复杂度内解决这个问题,并且把这个留成了课后习题。这个问题具有最优子结构特性,可以采用类似于动态规划的方式自下而上的构造出来。假设原文题的最优解为OPT(n),下面探讨它与OPT(n-1)、a[n]的关系。貌似没有直接关系……比如:{0,0,10,10,0,8,20} 的最优解是sum{8,20} = 28而{0,0,10,10,0,8} 的最优解是sum{10,10} = 20这两者之间没有直接的关系。为了找到最优子结构特性,对上述问题稍稍做下变形。加一个限制条件,要求这个子数组的最右端必须是n。即问题2:给一个数组a[0...n],假设a[s...n]是它的子数组,那么这个子数组的所有元素加起来最大是多少?假设这个问题的最优解为OPT2(n)分析问题2:先考虑退化情况,假设原数组只有一个元素,那么它唯一的子数组就是它自己啦。这种情况下,OPT2(0) = a[0]; 然后考虑当有多个元素时,OPT2(i)与OPT2(i-1)的关系。假设问题2中a[0...n]的的最优解是a[s...n]。假设从最优解中去掉a[n]后剩下的数组不为空,那么a[s...n-1]也应该是a[0...n-1]的最优解。即当i>0时,有OPT2(i)= max(OPT2(i-1)+a[i] , a[i]);所以,这个问题的解很容易通过一次遍历就能得到,算法复杂度为O(n)。回头再看问题1,假设问题1的最优解是子数组a[s...t] ,那么它的和应该等于OPT2(t)所以问题1的最优解 OPT(n) = max{OPT2(i)| i=0,....n-1}实际写代码,扫描一次即可。仿照std::max_element的代码写,但是多加一个临时变量。一个用来保存问题1的答案,一个用来保存问题2的答案。//[begin,end]//[begin,end]. include the end…

Random Sampling

随机算法中一个很基本的问题是怎么做随机抽样。比如,如何从N个元素中等概率随机抽n个出来。(n<N)总的来说这个问题有三种解法:选择抽样、蓄水池抽样、随机洗牌。一. 选择抽样。理论来说,每个元素被抽中的概率应该是p=n/N。但是,如果我们对集合的每个元素都按照固定概率p选择是不是抽中它,那么结果未必那么凑巧抽中n个。所以这个p应该是变化的。假设已经抽中了m个,那么p应该是m的函数。通过计算可得,原数组第t个元素被抽中的概率p=(n-m)/(N-t+1)。t从1开始计数。m是从0开始计数,每抽中一个就加1。这个算法不用遍历原数组的所有元素,抽够了就中止。二. 蓄水池抽样。首先,我们搞一个蓄水池,size=n。然后放水装满。也就是把前n个元素扔这个池子里去。然后,把剩余的这些元素,每个以一定概率把它扔进蓄水池中,随机替换掉池子中一个现有的。(池子中每个元素都是以相等概率被替换掉)蓄水池装满后接下来该处理第n+1个元素,那么显然,它被抽中的概率应该是\( \frac{n}{n+1} \) 。(因为目前是从n+1个元素中抽n个)以此类推,第t个元素被抽空的概率是:\( \frac{n}{t} \)。其中t从1开始计数,蓄水池最开始那n个元素也要被数进去。证明: 第t个元素被扔进池子的概率是\( \frac{n}{t} \)。它被第t+1个元素替换出去的概率是 \( \frac{n}{t+1} * \frac{1}{n} = \frac{1}{t+1} \) 。所以,在经历了第t+1个元素后,它依然留在池子里的概率是 \( \frac{n}{t} * ( 1- \frac{1}{t+1}) = \frac{n}{t+1} \) 。 以此类推,直到第N个元素后,它依然在池子里的概率是\( \frac{n}{N} \)。三. 随机洗牌把输入的这些元素随机打乱(比如用std::random_shuffle()函数。然后取前n个。 把代码写出来仔细看看,它跟蓄水池抽样其实是完全一样的。

uva 10127: Ones

Given any integer 0 <= n <= 10000 not divisible by 2 or 5, some multiple of n is a number which in decimal notation is a sequence of 1's. How many digits are in the smallest such a multiple of n?例如,当n=3时,我们发现3*37=111。而111有3个1,所以输出3。当n=7时,我们发现7*15873=111111,而111111有6个1,所以输出6。 这个问题,最直观的暴力做法是,把n的所有倍数都拿来从小到大试一遍。如果发现某个数的每一位都是1,那么就停。但是这么做会算术溢出。如果我们把问题倒过来,从1、11、111开始,挨个看它们是不是n的倍数,问题就简单多了。令a(0) = 1 , a(i) = a(i-1)*10 +1 那么a(1)=11, a(2)=111, a(3)=1111 ,....另 b(i) = a(i) % n = (a(i-1)10 +1) % n = (a(i-1)%n 10 + 1) % n 则b(i) = (b(i-1) * 10 +1) % n 所以有0<= b(i) < n 。这样就没有算术溢出的问题了。代码如下:intresolve(int n){ if(n==1) return1; int ret=2; for(int i=11;i%n;ret++) i=(i*10+1)%n; return ret; }

Squid As A Secure Proxy

摘要: 这篇文章讲述了一种使用squid“科学上网”的方法。安装Squid:Squid是一个大名鼎鼎老牌软件,用于做HTTP缓存代理。它非常完善的支持HTTP/1.1 proxy协议,所以我的方法就是:让squid以https的方式提供forward proxy service,然后在客户端使用chrome直接访问。首先,我在amazon的ec2上有一个虚拟主机,我要在它上面安装squid。有两种方式通过yum安装二进制包这是最简单直接的方式yum install squid 从源代码安装如果你想从源代码自己编译,那么yum -y install gcc-c++ openssl-devel curl -O -L 'http://www.squid-cache.org/Versions/v3/3.4/squid-3.5.4.tar.bz2' tar -jxvf squid-3.5.4.tar.bz2 cd squid-3.5.4 ./configure --prefix=/usr --sysconfdir=/etc/squid --libdir=/usr/lib64 --with-openssl --enable-auth-basic=DB --enable-auth-ntlm=none --enable-auth-negotiate=none --enable-auth-digest=none --disable-auto-locale --disable-ipv6 --disable-translation --with-logdir=/var/log --with-pidfile=/var/run/squid.pid --with-swapdir=/var/spool/squid --with-default-user=squid --libexecdir=/usr/lib64/squid --enable-http-violations make make install 证书认证:./configure --prefix=/usr --sysconfdir=/etc/squid --libdir=/usr/lib64 --with-openssl --enable-auth-basic=DB --enable-a…

UVA Notes

最近在uva上做了几十个非常简单的题。记录如下369 - Combinations这个就是计算排列组合中的C(N,M)。高中的数学知识了,蛮力计算就可以。但是题目故意迷惑人,真有人按照题目所说的,去计算 N!,然后再除以M!。这就有点2B了。以C(20,2)来说,计算20/1 * 19/2 即可。另外,利用C(N,M)=C(N,N-M),有时也可减少一部分计算量。一个特殊情形C(N,N)=1。11547 - Automatic Answerint x=(int)strtol(line.c\_str(),NULL,10); x=abs(((x*(double)567/9+7492)*235/47-498)/10); int r=x%10; 495 - Fibonacci Freeze因为N不大,所以直接按照递归式计算fib(n)即可,不需要用分治做。但是这里涉及了大整数运算,必须自己实现一套类似于gmp那样的东西。于是我花了将近一周的时间,读openssl的big number相关代码,读gmp的paper。最重要的是这么几个函数:加法、除以单字长的整数、bignumber to decimal string。在实现除法的时候我借助于汇编写的,因为我需要计算一个128位的整数除以64位的整数的结果。除法和加法不同,一旦溢出还会core dump。所以 openssl在做这件事情之前还对这两个数做了normalize,但是我怀疑真的有必要吗? p.s.大数运算中,除法是最最复杂的。算法导论中没有讲这个问题,但是计算机程序设计的艺术中第二卷有。499 - What's The Frequency, Kenneth?出题的人应该是个emacs fans,对vi狠狠吐槽了一番。题目很简单,就是统计26个字母的出现频率,无难点。374 - Big Mod同余群就相当于N的一个有限子群一样。所以\( B^p \mod M = (B \mod M)^p \) 。这个问题就变成了很普通的,求某整数的N次方的问题。最笨的方法,写一个for循环,迭代,那么计算p次方就是O(p)的复杂度。更好的方法是用分治的方法做,代码如下:inlineuint64_tcalc(uint64_t b,uint64_t p,uint64_t m){ uint64_t r=1; wh…

HTTPS Interception In Action

最近我喜欢上了玩iphone游戏,整天琢磨着怎么作弊。比如刷刷排行榜。于是我就先从抓包入手,看它给服务器发了些什么,哪些是我可以改的。首先,我把我的windows7,做成了一个wifi热点。然后让iphone连上去。假设我iphone获得的IP是192.168.137.4,那么网关就是192.168.137.1。这个IP对应我pc上的一个虚拟网卡。用wireshark对这个interface进行抓包即可。很遗憾。这个游戏的所有网络通信全是HTTPS。我用wireshark抓到的全是加密后的数据,看不懂了。于是man-in-the-middle proxy就上场了。HTTPS的身份认证大部分是单向的,client只检查server是否是真的,而server不检查client的身份。所以我们只需要把client欺骗过去就行了。client的检查方法很简单,看server的证书是否是通过一个证书链颁发,而最根上那个证书是一个可信赖的Certificate Authority(CA)。于是,我们只需要在client上植入一个假的CA证书即可。通常来说,只需要修改下系统设置,而不用更改App。首先推荐的是来自微软的fiddler2。网上大多数文章讲到这里就停下来了,因为他们除了会下个软件然后打开运行下,啥都不会。而fiddler2只能解决最初级的问题。我得先解释下什么是proxy。proxy分两种,正向(forward)和反向(reverse)。正向代理是给最终用户用的,填在浏览器、iphone的网络设置里,当你访问任何一个网页的时候,请求先发给代理服务器,然后由这个代理服务器再转出去。反向代理是给网站服务器用的,假如我们有一个网站,它的服务器只有内网IP,但是又希望能从外网访问,那么就找一个有公网IP的服务器,在它上面用nginx、squid、varnish之类的工具反向代理到内网来。反向代理对最终用户是不可见的。Fidder2是一个正向代理,也就是说,需要用户把它的IP和端口号填在iphone的网络设置里(就在填wifi密码的那个界面)。然后当打开浏览器上网的时候,如果浏览器检测到代理设置,那么它发出的HTTP请求的path部分就是一个full url。如本来request应该发送:GET / HTTP/1.1
Host: www.baidu.com因为要使用代理,所以r…

算法:货币兑换问题

这是一个很经典的问题:假如我现在有3种硬币:1分、2分、5分。然后我要用这三种硬币凑成14分钱,有多少种组合方式? 以3分为例,有两种:3个1分的,或者1个2分加1个1分。有人会说,那还可以"1个1分加1个2分"。哦不,这个其实和1个2分加1个1分是一样的,这种不能被重复计数。这个问题该怎么用程序解决呢?如果我们用f(x,n)表示待求解的问题。x代表需要凑成多少分,n代表可用的硬币种类中面值最大的。那么原题就是要求f(14,5)。经观察发现,f(14,5) = f(9,5) + f(14,2)。即,f(x,n) = f(x-n, n) + f(x,prev(n))。 其中prev(n)指硬币种类中,比n略小的那种硬币。即prev(5)=2, prev(2)=1。再加一个边界条件:f(0,n) = 1 对于任意的n >=0f(x,1) = 1 对于任意的x >=0。这个问题就可以递归求解了。f(14,5)=f(14,2)+f(9,2)+f(4,2) = 8 + 5 + 3= 16。实际上这是一个动态规划问题。UVA上有两道类似的题:674 - Coin ChangeSuppose there are 5 types of coins: 50-cent, 25-cent, 10-cent, 5-cent, and 1-cent. We want to make changes with these coins for a given amount of money.For example, if we have 11 cents, then we can make changes with one 10-cent coin and one 1-cent coin, two 5-cent coins and one 1-cent coin, one 5-cent coin and six 1-cent coins, or eleven 1-cent coins. So there are four ways of making changes for 11 cents with the above coins. Note that we count that there is one way of making change for ze…

分治算法的时间复杂度

这周末我把分治算法重新学了一下。假设某问题的输入是一个长度为n的数组,解决这个问题所需花的时间是T(n)假设分治算法总是把原问题分解成q个规模为n/2的子问题,划分和merge所需的时间是f(n)那么 T(n)=qT(n/2)+f(n)\(T(n)=q^2T(\frac{n}{4})+qf(\frac{n}{2})+f(n)\)于是有\( T(n) = q^kT(\frac{n}{2^k})+f(n)+qf(\frac{n}{2})+q^2f(\frac{n}{4})+...+q^{k-1}f(\frac{n}{2^{k-1}}) \)令 \( 2^k = n\) , \(r=\log_2{q}\) 则\(q^k = n^r \)则:\( T(n) = n^rT(1)+f(n)+qf(\frac{n}{2})+q^2f(\frac{n}{4})+...+q^{k-1}f(2) \)下面分析几种特例:f(n)是常数假设f(n)是常值函数,如f(n)=c。则当q大于1:\( T(n) = n^rT(1)+ c\frac{q^k-1}{q-1}=O(n^r) \)当q等于1:\( T(n) = T(1)+ c\log_2{n}=O(\lg n) \) 对应算法:二分查找、单峰数列求最大值。f(n)是一阶线性函数假设f(n)是一阶线性函数,如f(n)=cn,则当q等于1:\( T(n) = T(1)+cn+\frac{cn}{2}+\frac{cn}{4}+...+\frac{cn}{2^{k-1}}=T(1)+2cn=O(n) \)。当q等于2:\( q^{k-1}f(\frac{n}{2^{k-1}}) = 2^{k-1}\frac{cn}{2^{k-1}}=cn \)\( T(n) = nT(1)+ n\log_2{n} =O(n\lg n) \),对应算法:merge sort。当q大于2:\( T(n) = O(n^r) \) 对应算法:大整数乘积。嗯,于是类似的可推出,只要f(n)是多项式,那么原问题就是多项式时间可解的。当输入集是二维或高维时,分析工作就复杂很多。等我遇到对应的问题,再具体分析吧。先列一个:Longest Common Subsequence(LCS)问题。假设两个字符串,长度分别是m和n。它们的LCS的长度已知,求这个序列本身。那么在原来的…

UVA小结

总结一下最近在uva和spoj上做的题目。很少,反正就是挑最简单的开始做。uva上只做了3道题目。100 - The 3n + 1 problem没任何难度的入门题,完全就是适应下如何使用这个系统。按照题目所写的,反复循环即可。102 - Ecological Bin Packing穷举所有可能性即可。struct Check{ constchar* name; unsignedchar pos[9]; }; //B1 G1 C1 B2 G2 C2 B3 G3 C3 conststatic Check checks[]={ {"BCG",{1,0,0,0,0,1,0,1,0}}, {"BGC",{1,0,0,0,1,0,0,0,1}}, {"CBG",{0,0,1,1,0,0,0,1,0}}, {"CGB",{0,0,1,0,1,0,1,0,0}}, {"GBC",{0,1,0,1,0,0,0,0,1}}, {"GCB",{0,1,0,0,0,1,1,0,0}}, {NULL,{0,0,0,0,0,0,0,0,0}} }; 但是我花了0.055秒才完成。112 - Tree Summing先解析成一棵树,然后做二叉树遍历,把所有叶子都找出来,然后从叶子到根回溯一遍。写完,提交,运行时间0.089秒。然后我想,我为什么非得做二叉树遍历呢?我在解析这个二叉树的时候,需要构造Node,那么这个时候,我把所有的leaf Node都放在一个容器(vector或者list)里,到时候直接遍历这个容器不就行了?好吧,改代码,提交。运行时间0.132毫秒,更长了啊!为什么?我发现花了大量的时间在vector的push_back方法里。我并不知道最多会有多少Node,所以就不能给这个vector一次性预留足够的内存。然后我想了一下,给每个Node加了一个next指针。然后用这个ne…

2013-06-22

今天去北京Open Party贡献了一个topic,介绍Flash的RTMFP协议,这是Adobe发明的一种P2P协议,2010年才发布的,非常新,也非常复杂。我准备了一个40-50页的PPT,但遗憾的是对这个topic感兴趣的人并不多,只有12个人举手表示想听,这其中有5-6个都是专程来给我捧场的朋友。最终实际去听的只有7-8个,有一个还睡着了,鼾声微作。全程认真听完的也就3-4个,有一个坐我旁边的非常认真,在不断的做笔记。我当时选这个话题是因为,我上大学是03、04年那会儿在课堂上学的网络知识,而现在又过去了近10年。发生了很多新的变化。Google这样的公司一直在蠢蠢欲动的试图改变internet的基础部件,做一些疯狂的事情。而我们的知识一直停留在10年前,像那些上学时被我们嘲笑的老头子一样。每次在微博上看见有人对Google的GFS、Map-Reduce推崇备至我就想问:“哥!您穿越来吧?”Flash做了一件很激动人心的事情,花4年的时间,设计一套新的传输层协议,替代TCP,并成功的部署到几十亿台电脑上。假如让你重新设计TCP和internet,你会怎么做?由于RTMFP的设计和产生都比较近代,对于一个在大学里受过良好的计算机科学教育的人来说,它真是很难得的研究对象。比如,在我blog中之前提到过一个问题:在不安全的信道上传输数据,有两点很重要:加密和完整性校验。那我是先加密后计算校验值呢,还是先计算校验值再加密呢? 我通过反汇编,发现RTMFP把这两种方式都做了。它给了一个非常标准的答案: AES_CBC_ENC(seq + body) + HMAC。 通过在body前加seq,并采用CBC加密,使得相同的原文不会产生相同的密文。先加密后HMAC,从密码学上来说也是最安全的,在这一点上,它比SSH和SSL做的都好。同时,它又给出了一个不这么安全,但是又更容易实现的方案,并在交换密钥时协商具体如何加密。上面这些,都是你在RFC中看不到,从网上搜不到的。我想拿出来一起分享,讨论。学习网络协议的设计思想。但是遗憾的是,很难找到具有相同技术背景的人。今天现场问了一下,没有一个人具体了解TCP的内部工作原理,slow start 、fast open这些也讨论不起来。比如我想讨论,为什么tcp要用三次握手,再比如我把某些应用层数据放在第一个SYN包就发出去,会有什…

试用gcov

今天学了一下如何用gcov测试test suite的coverage。我最近在练习写一些算法,然后就在想如何能设计好的测试用例快速、全面的把我的算法测一遍。比如拿排序来说,找一个长度为n的数组,让它的每个元素的取值范围都在[1,n]之间,然后把所有的这样的可能性全部列出来,调用我的排序算法,再和std::sort的结果做对比。把数组长度从1到7的,符合上述要求的数组,全测一遍。够吗?对吗? 不一定啊… 比如我在写qsort的时候,只有当数组长度大于7的时候才会打开median3优化。于是,我很需要一个简单的工具告诉我,我现在的test suite的代码覆盖率是多少。那么最古典的工具就是gconv。当编译、链接C/C++代码的时候,加上--coverage ,如CC=/usr/local/bin/clang CXX=/usr/local/bin/clang++ CXXFLAGS=-g3 -nostdinc++ -I/usr/local/lib/c++/v1 -std=c++11 -stdlib=libc++ -Wall -Wextra -fsanitize=address-full -fno-omit-frame-pointer --coverage LDFLAGS=-g3 -fsanitize=address-full -fno-omit-frame-pointer --coverage LIBS=-ltbb\_debug -lc++ -L/usr/local/lib -lglog all: t .cpp.o: $(CXX) $(CXXFLAGS) -c -o $@ $\< t:test.o $(CXX) $(LDFLAGS) -o $@ $^ $(LIBS) 然后执行我的测试程序 ./t就会得到对应的gcda文件。然后调用gcov$ gcov test.cpp
File 'test.cpp'
Lines executed:93.33% of 45
test.cpp:creating 'test.cpp.gcov'....它会生成一个test.cpp.gcov文件。- : 6 : - : 7 : 26: 8: int start = 0; 26: 9: int end = a.size(); 56…