冬天无题

上周是Thanksgiving Day,刚好第二天也是师妹的生日,因此在心中想到很多要感谢师妹的东西。当然感恩节还要感谢父母和很多朋友。以前不知道感恩节是十一月第四个星期四,也不知道来源。现在知道了,原来是为了五月花号终于到了美国。那时他们在那里经过一个寒冷的冬天后,受到当地人的照顾,吃火鸡,所以现在的美国传统也吃火鸡,其实我也想试试。

turkey

最近一边学C语言,发现了几个UNIX好用的小程序,Linux上一般也找到。一个是wc,其实我觉得名字还是很抽象的,意思是WordCount,可以把input算出总字符数、单词数和行数,挺好用。另外一个是sort,它把input的行按字母顺序排好再重新显示。最近我按照书上的例子,把上面两个程序的基本功能实现了,挺好玩,用到了quick sort算法。

CiscoTeam最近准备招新了,估计宣传的事情会忙起来,不知道这次的新的成员都有哪些呢。

网络二三事

上个星期见到一个网站叫Imagery,是一个图片搜索的网站。试用了一下,看看跟Google还有百度的有什么区别。然后看看搜索结果,那个准,简直无话说。而且搜出来的基本就可以用作素材了。而且这个网站还有一个很专业的功能,就是即时编辑,如果你点了一张图片,就会出现在下方,可以裁减或编辑以后再下载,非常方便。不过目前这个功能只在FireFox上有效。网站的地址在这里

Imagery

另外介绍一个很好玩的叫RescueTime。顾名思义,网站的目的就是帮我们重新规划,节省时间。具体来说,是使用电脑的时间。如果要用这个功能,首先从网站上下载一个客户端,客户端在监视你的电脑行为,而且计时比较准,因为如果外出不动鼠标很久也不会计算在内。然后客户端每隔30分钟左右把数据上传到网站,所以只要登录自己的账户就可以看到自己用电脑的统计情况了。

Rescue time

不过客户端监视不知道有没有危险,如果登录网上银行之类的,就先关了它吧。

OSPF的邻居全相连

以前在CCNA看OSPF的时候,总是不算很清楚它邻居建立起来七个状态之间的关系。主要是细节的地方没有搞清楚,看得越多反而越混乱。后来做完实验,觉得大部分地方开始明晰了,但还是有些地方若隐若现,那时候最搞不清楚的是建立邻居全相连(Full Adjacency)关系的七个状态和五种包到底关系怎样。这次看了CCNP之后总算清楚了。

原来这五种包分别是Hello,DBD,LSR,LSU,LSAck。似乎是五种独立的包,实际上它们的header都是一样格式的,其实可以统一叫做OSPF包,OSPF包的header有一个字段叫type,当它等于“1,2,3,4,5”,就分别是这五种包的其中一种了。OSPF包是直接封装在IP包里的,也就是说,OSPF包既不利用TCP,也不利用UDP。这也就好理解为什么会特别有LSAck包了。

知道了这五种包,要理解建立全相连的过程细节也变得容易了。第一阶段,是Hello协议建立two-way关系,利用hello包就可以了,主要是检查大家参数是不是一致,如果发现对方发过来hello包的邻居列表包含自己,随即宣布自己和他进入two-way关系。

第二阶段就是由two-way阶段进化到full adjacency,利用的协议是Exchange交换协议。能不能进化,主要看的是网络类型,如果是点到点,是可以的。但如果是广播型多路网,自己只有和DR和BDR之间才能进化。进化的细节是这样的,首先用DBD(只有简单描述的信息)确定主从关系。然后主方首先发送DBD,从方也发DBD,大家看看有没有自己缺的链路状态,有就发LSR问详细信息,然后用LSU回答。反复沟通,直到大家数据库一致了,就完成进化了。

整个过程也是这样,应该没有说得太抽象吧,可能没有解释一些专业术语,稍微查查就知道了。因为这个过程的目的就是同步数据库,因此这个过程有时也叫同步数据库过程。更好玩的是,最近学了一条命令,是“debug ip ospf packet”,这条命令会把收到的OSPF包的头部信息显示出来,但是用的是缩写形式。

OSPF debug

然而,最近在CCNP里找到这些缩写的解释表,现在我可以实际地感受书上说的整个进化的过程了。

Crayon Physics

这个游戏有人译作蜡笔物理学,是一个非常有创意的游戏。在看到介绍和图片的时候,就已经对它很有好感。

这个游戏的玩法很简单,就是画一些形状出来,使小球撞上星星。但是这个游戏却很有创意,把物理学和游戏结合在一起。目前来说,游戏还很简单,因为只能识别矩形,或者偶然一些小闭合图形也行。但就算这么简单,也已经有很大的发挥空间。基本上我觉得每一关过关的方法都有很多种。

Crayon Physics

游戏的下载地址在这里。这个游戏做得最好的应该是重力,感觉上很符合日常生活规律。目前,这个游戏的开发还是在初始阶段,如果将来可以识别越来越多的形状,一定更有挑战性,很期待,加油!

Binary Search

这是一个很著名的算法,就是二分搜索,一般可以在算法和数据结构中都能见到这个名字的存在。今天讲这个话题是因为前几个星期看C语言的时候,又再次看到这个算法,想起以前在数据结构学的知识,觉得这个算法真是大有文章,比较好玩。

二分搜索的思想很简单,在一个已经排好序的数列里找一个数,那么每次找中间那个比一比,如果要找的数比中间大,那么要找的数肯定在原来数列的后半部分了,反之亦然。按照这个思想做下去,一般很快就能找到那个数。现实中也有这样的例子,比如猜数字的游戏,一般也喜欢猜中间那个,然后就可以在几个回合之内猜到数字。

刚才是通俗的说法,一般来说,算法中的二分搜索要求如果原来数列有,则返回序号或指针,如果该数不存在,则返回不存在。刚才的通俗说法还有一个地方没说清楚,就是那个“比一比”。现实中,我们可以一眼可以看出大还是小,但在计算机中,要知道A是大于、等于还是小于B,要比较两次。下面给出其中一种解法的部分代码。
while (low <= high) {
mid = (low + high) / 2;
if (x < v[mid])
high = mid - 1;
else if (x > v[mid])
low = mid + 1;
else
return mid;
}
return -1;

这是一种正确的写法,可见在while循环内就完成搜索的过程。这个版本叫做Recognizing Equality,就是每次二分的时候如果刚好和中间的数相等,就直接结束。这是最容易理解的一种写法。

还有一种写法,没那么直接,叫Forgetful Version,就是每次不去特意比较中间的数,让循环一直下去,因为最后范围会收敛到只有一个数,所以也能完成任务,代码如下。
while (low < high) {
mid = (low + high) / 2;
if (x < v[mid])
high = mid;
else
low = mid + 1;
}
if (v[low] == x)
return low;
else
return -1;

这种写法的好处是每个循环里只需要比较一次,但是不是比较的次数是不是一定比第一种少呢,这不一定,因为第一种写法可以提前结束,第二种写法一定要收敛到范围只有一个数才结束循环。那到底哪种写法比较次数少呢?解答这个问题前,最好先搞清楚影响这两种写法的关键因素是不是比较的次数,书上说是的,到底是不是可以想一想汇编。

哪种写法的比较次数少,有一种分析方法叫比较树,把每次的比较用圆圈标出,下图是第二种写法的比较树(部分)。同样道理可以画出第一种写法的比较树。

Binary Search

可以数出来,当数列长度是10的时候,第二种解法的比较次数无论是存在还是不存在的树,都是4.4次。但是第一种解法的成功搜索的比较次数要4.8次,假如该数不存在,平均要比较7.1次。

不过虽然第一种写法每个循环要比较两次,但是两次比较其实有关联的,都是和同一个数比较,因此两次比较加起来的时间和只比第二种写法的一次比较的时间稍多一点,完全不是我们所想象的两倍时间,因此可能第一种写法的效率还是比第二种高。

但是,第一种写法有一个最致命的弱点,就是处理有相同的数的时候,比如“1,2,2,2,5”五个数,我现在搜索2,算法找到中间那个,发现相等,没有继续比较,所以返回的序号是2(假设从0开始)。这样就要命了,也就是说算法无法确定返回的是哪一个,这就很难做到通用性。相反第二种,它把大于等于归为右半部分,于是有相同的数的时候总是可以返回第一个,或者如果把把等于归为左半部分,就总能返回相同数中的最后一个。因此,大部分通用算法的写法,比如C+=的STL,应该也是用第二种的。我个人也喜欢第二种写法。

秋天无题

这个星期虽然也获得很多新的信息,但是还是以无题写一写杂事好了。

首先是今天终于获得一本英文版的《Computer Networks》,作者是著名的Andrew S. Tanenbaum。这本书是计算机网络的经典书籍,说它为这方面书籍的经典第一位也不为过。可能也是这一阵子真的很喜欢经典书,《The C Programming Language》已经看完第三章了,有空的时候就在网上搜索。后来得知网络书中有两本比较经典的,一本就是我一开始说的那本,电子版也拿到了,后来想了想,好像某个同学的教材正是这本,那我连打印都不用,实在太好了,万分感谢那位同学。

Computer Networks

另一本经典书是《Internetwork with TCP/IP》,作者是Douglas E.Comer。这两本书并不冲突,后者基本是围绕TCP/IP讲了几乎所有的技术,不过可惜的是我到现在还找不到那本书的电子版。好在,这本书在中国有影印版,估计到时会买来看的。

说说这个星期的互联网趣事吧,谈谈我不熟悉的微软,但是好奇使我决定注册了live.cn。从此,我有一个全新的Live ID,以后估计也是会用上MSN的,而且我又多了一个5GB的邮箱。

Live CN

之所以无题,确实是有点心烦的事。工作上遇到一点阻力,希望汲取教训和经验,而这件事也可以快点变顺利。

iGoogle的新主题

iGoogle在昨天新增加了五款主题,在别的地方还看到说好像要把一段JavaScript粘贴上去,我迫不及待地尝试,发现根本什么都不需要做,在主题选择的最前面已经多了五款主题了。之前看到截图很漂亮,换了一个太阳系的主题,一来是感觉很cool,二来是因为以前的主题都是按时间变化的,但过一天之后还是一样的。

而这一款主题是按天变化的,昨天看到的是太阳,今天看到的是木星,下面的截图就是今天的。还有几款主题好像也很好玩,以后有机会逐个试试。

iGoogle

今天Google还给了一个好东西我,就是终于把我的Google拼音升级了,升级到1.0.23.40,之前一直没有自动升级觉得郁闷,看来自动升级真的是一个很长的周期,不过其实输入法的升级与否可能影响不大。

今天顺便介绍一个好玩的游戏,是一个要求质量平衡的游戏,或者就叫做称重。游戏的玩法很简单,用鼠标点下去可以生成一个球,点得越久,质量越大,目标是和右边尽量相等。游戏地址在这里

mass attack

前面几关比较容易,后面要求的精确程度越来越高,我觉得还是很难玩的,有兴趣的可以挑战自己。