Friday, May 11, 2012

Battleship

Battleship

这是一部纯娱乐电影,剧情不值得推敲。不过总有人能带来相当欢乐的一面。

=========================分 割 线==============================

你们太忽视外星人的感受了。事实是这样的:

爱好和平的G星人有一天收到了地球人发来的电报,G星人感到历史的召唤,决心抓住这一机会,冒险发起接触,但如果派来的战舰过多,恐怕会造成误会,引起星际战争,G星人经过反复权衡,最后派出由一只无武装的主舰和五只超轻型护卫舰组成的使者船队,来地球进行划时代的接触。
但G人没有想到的是,地球周围太空垃圾过多,主舰由于撞到了一个中国废弃卫星而坠毁在香港。舰队大使、舰队总司令、副总司令均死于撞击。太阳能板和自动翻译系统都毁于一旦。舰队陷于无法与地球人沟通并且没有后继能量供应的绝境。
这时候,G星人不得不决定谁来领导这支危机中的舰队。年轻的G星少校(简称GM)被推为总司令,但他非常悲观和焦虑,大家劝他说“你不上,谁上”,GM终于接受了这一职务。
GM上任后,发布了三条命令:
1,地球人如果没有武装或者没有威胁,我们绝不能开火。
2,尽快利用地球的卫星连接银河系云翻译系统,只有这样才有可能消除误会。
3,如果地球人大举进攻,必然会伤亡惨重,因为G星人的力场刀枪不入。这样一来必然酿成星际大战。所以必须阻断地面交通,使用剩下的99.5%能量建立巨型空中力场,尽全力避免和地球人陷入大规模冲突。宁愿让舰队失去防护能力,也要保障抢占卫星任务的完成,确保银河系的和平。
但不幸的是,他们正好遇上地球人的军演,力场障壁内混入了三艘军舰。地球人以武力相威胁,G星人也不得不鸣笛示警,但鸣笛声导致两边发生了摩擦,正当G星人不得不摧毁地球第三艘军舰的时候,GM发现它掉头了,赶紧阻止了投弹手开火。GM希望能借助这一姿态,让地球人明白他们的立场。
他错了。
这场战斗消耗了G星战舰最后的0.5%力场能量。而且误会已经产生,难以收拾,GM不得不拼死一赌,把所有的希望押在控制地球卫星上。
G星人完全没有携带陆战力量,只能集中所有壮汉修理工和科学家,穿上太空行走的防护服,携带一些可以用来防御的太空修理工具,前往小岛控制站。他们遇到了一些持枪向他们射击的地球人,只好把这些地球人的车掀翻。
他们还遇到了一个发型像Moss的geek地球人,偷偷拿走了一个箱子。G星科学家其实很想请他喝茶,但又无法跟他交流,只能友好的拍拍他的箱子,意思是这是你的,请不要害怕,想拿就拿走吧。
地球人抓走了一个G星人,GM派出了营救分队,挖破地球军舰,救走了俘虏,但他因为暴露在地球空气中太久,还是死了。他的弟弟怒发冲冠,大叫“和平个屁,干死地球人”,操起哥哥留下的修理工具,要找地球人算账,连GM也无法阻止他。最后他被一炮轰下,血染太平洋。
G星科学家终于意识到那个被拿走的箱子是什么,追悔莫及,GM赶紧派出最后的护卫舰队,希望阻止地球人破坏发射台,如果发射台被摧毁,一切和平的努力都将白费。但此时,G星舰队已没有防护能量,被地球人的鱼雷和导弹轻易一扫而光。
GM只剩下了最后的指挥舰,对峙脆弱老船密苏里号。GM知道卫星即刻可以拿下,和平就在眼前,于是下达了最后的悲壮命令:对海面投弹威慑,希望对方意识到双方火力的巨大差距,暂时停火。谁知,密苏里号竟抛锚并展开疯狂进攻,指挥舰瞬间便被击沉。
这时候,发射台受到一个疯婆子、一个残疾人和一个geek的自杀性攻击,G星科学家被撞死的撞死,勒死的勒死,都恪守命令,壮烈牺牲。他们坚信,一旦连上云翻译系统,这些代价都是值得的。和平万岁。
这时,一颗炮弹飞过来,发射台报销了。
GM最后放出的三个风火轮也没有阻止地球人的愚蠢行为。他在战机的狂轰滥炸中,黯然神伤,坚毅的嘴角划过了一丝泪水。与指挥舰一起,与G星人追求和平的梦想一起,与银河系实现划时代跨越的机会一起,永远沉入了光荣的太平洋底。

注:Moss是IT Crowd的人物:http://en.wikipedia.org/wiki/The_IT_Crowd

Saturday, December 31, 2011

再见2011

不老歌的好处在于她记录了我过去的一点一滴。虽然很多都是牢骚和调侃,但是回头看过去却也能够体会到当时的心情。这一年我没怎么为自己做过记录,可能因为生活变得平淡思想变得平庸导致了我不再愿意在不老歌上发牢骚做调侃。

曾经有同学问过我,一年之内有哪两个月份是连续两个31天的?我想也没想就说了7月和8月。然后他却得意的告诉我1月和12月也是。当时可能被震住了没想到怎么反驳,但是只有今年的1月和下一年的12月才是连在一起的,并不算是在一年之内。无视答案的荒谬性,没错,最忙的时候往往都是两个31天。整个7月和8月,我每周四早上4点要开一个小时的会,晚上的更是天天有会。本来有一个去美国长期任职的机会,但是各种原因没了下文。12月,老板为了推广她的项目管理方案,连续晚上在家加班。

忙碌没有什么不好,辛苦也没有什么不好,但是看不到自己的进步却总是那么的无奈,那么的沮丧。

渐渐的,我麻木的觉得我每天的目标就是等着接布置的任务,做任务,交任务。我自己到底想做什么,我的目标在哪里?在我烦恼的同时只能通过重复的任务交接来麻痹自己,让我沉迷于一个忙碌的假相。我认真努力的工作无非就是想把这样的烦恼能够抛在脑后,可是我越是这么做,我越缺乏思考的时间。

我不是一个为了读书而读书的人,我不是一个为了考试而考试的人,我不是一个为了工资而工作的人。我会因为自己很久没读书而懊恼,但是我更懊恼的是我找不出一本能让我坐下来安心看5分钟的书。我会因为考试分数低而难过,但是我更难过的是我找不出为什么要考这个试的原因。我会因为工资低而抱怨,但是更让我抱怨的是我为什么要选择这份工作。

回头再看2011,这一年对我是那么的平淡,那么的容易忘记。

明天就是2012,明天总是那么美好,充满了无限的可能。记住今天的无奈,记住今天的遗憾,在明天,我将会找到我的目标,我将会看到我的希望。

就这样吧,让该来的来,该走的走,总要自己学会长大。

Sunday, December 25, 2011

MoneyBall

不觉得算励志片,因为看完这部电影没有脑门充血,但却印象深刻。

影片一开始就表达了主题:跳出固有思想。棒球球探对球员的评价体系中竟然存在身材和长相这两个指标,Billy Beane(Brad Pitt)就对球探的工作来了一次嘲讽:“It's an unfair game. And you guys are sitting here talking the same old good body nonsense like we are selling jeans. We got to think differently.”(这是一项不公平的比赛,但是你们还坐在这里说些身形好不好的废话,好像我们是卖牛仔裤的。我们要改变想法。)

"Think Different"是Steve Jobs重返苹果后在苹果最困难时期,也就是翻身时候用的标语。成为异类完全没有必要,不过人云亦云缺乏主见真的会让你消失。其实并不是没有独立思考的能力,而是缺乏一点把观点表达出来的勇气。不知道自己的想法是对是错,是好是坏,是否会得到别人的认同是会令人胆怯的。害怕被孤立,毕竟人类的群居性要求我们寻求认同感和归属感。

别再害怕了,鼓起勇气迈出这一步,结果会比现在更差么?

Saturday, December 17, 2011

魔女宅急便

东京电视台重播《天空之城》引爆了推特。试图从硬盘深处找到当年手机的OST的努力以失败告终,不过好歹下载到了Studio Ghibli Songs,其中包含了从《风之谷》到《幽灵公主》的所有主题歌。本以为《伴随着你》(君をのせて)会是我最喜欢的,但是听完才发现《口红的留言》(ルージュの伝言)才是。 第一次看《魔女の宅急便》是上大学的时候,那时经常无所事事游手好闲。所以看完之后对于主人公独自踏上人生的旅途,自己养活自己,自己给自己找活儿干并没有什么特别的感触。但时过境迁,同样的主题,只是我不再是一个无所事事,杞人忧天的大学生了。 影片的开场似乎就是在提醒我,对于一个资质平庸缺乏特长的人来说,养活自己不会是件轻松的事情。而事实是只有通过每天机械式的重复劳动才会有机会找到自己的特长。 第一次接到要自己独立完成任务的兴奋彷徨;在完成这项工作过程中经历源源不断挫折的挫败感;最终以不完美的方式结束这项任务的失落感;这一幕幕和我自己当初是何其相似?工作和生活上困惑的时候,是不是总是会有如面包店老板娘一样的好心人为我指点迷径?那些对别人的好意漠不关心的人,是不是总让自己痛苦无奈?空闲时的寂寞,一个人发呆,难道主人公不是我么?这些虽然只是为了故事高潮而做的铺垫,但是却意外的引起了我的共鸣,让我回忆起了过去的那些痛苦清甜。主人公用自己的方式是教育了我:认真工作,努力劳动,该得到的终究会得到,无非是时间上的早晚。

每个故事都会有一个快乐的结尾。怎么你现在不快乐么?那么别急,故事不是还没结束么?

Saturday, January 29, 2011

First Chance Exception, Second Chance Exception, WinDBG

所有Managed异常的HRESULT都是0xE0434352(无法用Error Lookup找到这个Error Code)。
通常在Event Log或者WinDBG所见到的Managed异常如下:
CLR exception - code e0434352

通常情况下First Chance Exception不是真正能导致程序Crash的异常,通常这个异常可以通过try…catch来捕获。只有当这个异常无法被捕获时才会升级为Second Chance Exception,这个异常会导致Crash。

可以用过WinDBG的命令sxe e0434352来使Debugger在First Chance Exception的时候Break。

image

继续Debug

image

可以看出Thread 4出现了一个System.Exception,还能看出这是一个First Chance Exception。

image

WinDBG报了Second Chance Exception,这导致了程序Crash。

慢慢玩儿,有点意思。

Monday, January 3, 2011

Managed Object Memory Layout

汇总学到的知识才是对上一年最好的总结。
CLR中的Object的Memory Layout是由一个4 byte的Syncblk,一个4 byte的TypeHandle以及之后的Instance Fields之类组成的。TypeHandle中又包含了重要的MethodTable和EEClass数据结构,这两个数据结构的实例对一个Type来说都只有一个。
通过Windbg来观察这个Object,首先找到这个Object的reference:
windbg
然后dd 0x0184274 - 0x4,ObjetRef实际上是指向TypeHandle而非Syncblck,所以需要减4。
windbg
这里可以看出Syncblk的值是08000001,TypeHandle是00233090,之后的三个是instance的值,分别是10,5,10。
TypeHandle是一个指向MethodTable的指针。
再一次通过Windbg来看这个指针的内容:
windbg
通过观察可以发现示意图似乎不准确,可能实现细节改过了。00232c5c才是一个指向EEClass的指针,002312a8是一个指向Module的指针。之后似乎又有4个连续的指针地址:594f6a90 -> 595674c0,这四个其实是4个method。看过Raw memory之后再用过sos来看看这个MethodTable
windbg
又见到了594f6a90这个地址,先看看这个的MSIL:
windbg
似乎是一个ToString(),再来看看sos:
windbg
两者一致。继续用sos来观察这个EEClass和Module两个数据结构。
windbg
windbg
这只是所有Managed Object中的一小部分,很多内容还有待挖掘。

Friday, November 26, 2010

归来的饭否

饭否正式回归。时隔近2年,饭否还是那个饭否,我却不再是过去的我了。

内牛满面和抒情不合适我,上图才有真相:

饭否

Saturday, October 9, 2010

对和平奖的亵渎?

外交部发言人马朝旭在回应刘晓波获奖时说:“刘晓波是因触犯中国法律而被中国司法机关判处徒刑的罪犯,其所作所为与诺贝尔和平奖的宗旨背道而驰。诺委会把和平奖授予这样一个人,完全违背了该奖项的宗旨,也是对和平奖的亵渎。”

中国的法律是对和平的尊重么?

Sunday, August 15, 2010

全国哀悼日

2010年8月15日(GMT+8)是全国哀悼舟曲泥石流遇难者日。这边厢我朝大小衙门需要下半旗;子民须停止一切娱乐活动并且要举行默哀仪式。那边厢SB会依然热情款待着全世界来朝的人民,明天还是一年一度的七夕节。
又一次形式主义的宣传,再一次抓住次要矛盾忽略主要矛盾。这所谓的“天灾”哪一次不是人祸?这边救灾还在进行那边就忙着大肆宣传“英雄”的“杰出”事迹,再深究祸事就似是对“不识大体,不顾大局”。我真的很不明白到底是生活在一个身边都是“英雄”的险恶地方好,还是生活在一个身边都是“常人”的安全地方好。随着时间的流逝,追究事件原因的声音也在变小,终究会到大家都麻木的时候。鲁迅的讽刺现在依然适用,而且对应得是那么得贴切。衙门就好似阿Q,别人欺侮阿Q,阿Q则欺侮比自己更弱小的小尼姑。

Thursday, July 15, 2010

Windbg学习笔记之一:构建环境

Debug是每一个合格的开发人员都必备的技能。(我惭愧了,我不合格)
Windbg是Windows平台上功能极度全面的Debug工具,此乃居家旅行,杀人越货之必备产品。
在学习如何使用Windbg之前,首先要有个实验的环境,但是安装Windbg,并且使Windbg正常工作不是件容易事。通过这几天的研究,我将列举出安装Windbg和使用Windbg初期常见的问题。

问题一:哪里下载?
回答: https://www.microsoft.com/whdc/DevTools/Debugging/default.mspx上面的链接通常是一个web installer,但是也提供了ISO下载。这套工具中包括了kd,ntsd, cdb,和万能的Windbg,当然也包含了很多其他常见的工具。

问题二:装完之后怎么用?
回答:Windbg自然是用来Debug的,但是它也可以用来观察系统是如何运作的。要让Windbg正常的工作起来,还是有一定难度的,首先要做的一件事情就是把symbol path设定好。
什么是symbol path?编译原理中提到的符号表就是编译器用来找符号对应地址时候用的,同时在debug的时候,符号也能够用来帮助我们定位变量和函数的具体位置。如今的软件动辄几个GB,为了不增加最终用户磁盘空间的压力,所以把符号表和其他相关的信息存储到了另一个文件上(通常是dbg或pdb文件)。这样就确保最终编译出来的文件又小又快。
Windbg有很多中设定symbol path的方法,这里只需要介绍两种。
方法一:_NT_SYMBOL_PATH
把_NT_SYMBOL_PATH添加到环境变量中去,如_NT_SYMBOL_PATH=SRV*d:\symbols\7600*http://msdl.microsoft.com/download/symbols
其中d:\symbols\7600是缓存,而http://msdl.microsoft.com/download/symbols是符号的下载地址。这里需要注意的是一定要使用管理员权限去打开debugger,否则无法读出环境变量。 方法二:.sympath
在任意个一个debugger中的命令行中键入:.sympath SRV*d:\symbols\7600*http://msdl.microsoft.com/download/symbols 也能达到同样的效果。
直接通过下载符号可以保证符号是正确的,但是这也造成了不小的负担,所以可以先下载已有的符号当缓存用:http://www.microsoft.com/whdc/devtools/debugging/symbolpkg.mspx但是这个缓存通常不是最新的,这也就是设定网络路径的好处了。
通过使用命令:!sym noisy可以使debugger把查询符号的位置和是否匹配的结果列出来。这样可以马上知道什么原因无法找到符号。比如ntdll.dll时常更新,7600里面的版本号和新的ntdll不匹配会导致无法找到符号。

Monday, June 21, 2010

写给自己看之三:AVL树的插入

当初没有学会,考试似乎也不考,所以没放在心上。但是心血来潮一下,搞了一下这个东西。
AVL树(平衡树)的定义:
  • 每个节点左子树的高度和右子树的高度差的绝对值小于2.即:| h(left[x]) - h(right[x]) | < 2。
  • 这样做的好处就是把二叉树的树高严格控制在log(N)上。从而杜绝成为链表的情况。
    如何才能做到这点呢?
    我读的教材所采用的方法是多设一个节点信息叫BF(Balance Factor)作为枚举类型。三个值分别为:LH(Left High),EH(Equal High)和RH(Right High)并采用递归插入。说实话,作者能写出这么牛的递归并且保证正确相信难倒了不少学生(包括我)。
    还有一本经典教材,采取不同的方法解决这个问题:节点增设高度信息。然后对插入路径进行高度平衡。我比较青睐这种做法。
    然而这种做法却需要一个额外的节点来表示空节点,否则无法正确处理高度差。所以自然而然想到了null object这个模式。
    好了,现在开始解决插入中最麻烦的问题:平衡高度。
    一共4中情况(OMG!)但是都只需要知道失去平衡的最小的祖先节点就可以了(这就是回溯插入路径):
    1. 受影响的节点从1增加到2,左子树的树高是1。也就是插入的这个左子树的左边。这种情况只要对高度差为2的节点进行一次向右旋转就可以了。
    2. 受影响的节点从-1增加到-2,右子树的树高是-1。也就是插入这个右子树右边。这种情况需要对高度差为2的节点进行一次向左的旋转。
    3. 受影响的节点从1增加到2,左子树的树高是-1.也就是插入的是这个左子树的右边。这种情况比较复杂。为了保持中序遍历的正确性(很重要),需要先对这个左子树做一次向左的旋转。然后问题转化为1的情况。
    4. 受影响的节点从-1增加到-2,右子树树高是1.也就是插入这个右子树的左边。这种情况需要对这个右子树做一次向右的旋转,转化为情况2。
    晕了么?我是晕了。但是通过画图就知道是怎么回事了。还有就是看教材上的图片,教材上的图应该能解释一下问题。还有一点非常好的地方就是不存在别的情况(教材上说了就那么4种,再多就是不正常的了)。
    现在的问题是怎么旋转?
    先看图:
    Before rotation
    对这种情况下的x节点做一次向左的旋转。
    结果图:
    After rotation
    从结果可以看出唯一一个需要变动的字节点就是q,别的节点原来在什么位置现在还在什么位置。一开始听到旋转我马上就晕眩了。现在把图画出来自己研究一下,也就只需要变动一个节点,这样的操作显然不是很困难。但是边界检查很重要。这时有两种情况:
    1. x的父节点是空。也就是x本身是root,那么把root指向y就可以了。
    2. q是个空节点。这是不需要对q的parent节点进行操作。
    左旋转的代码:
    private void Rotate_to_Left(Node x)
    {
        Node y = x.RChild;
        Node z = x.Parent;
        Node q = y.LChild;
    
        if (z == NULL_NODE)
        {
            this.root = y;
        }
        else
        {
            if (z.LChild == x)
            {
                z.LChild = y;
            }
            else
            {
                z.RChild = y;
            }
        }
        y.Parent = z;
    
        y.LChild = x;
        x.Parent = y;
    
        x.RChild = q;
        if (q != NULL_NODE)
        {
            q.Parent = x;
        }
    }
    
    右旋转也一样只有一个子节点需要改变,代码如下:
        private void Rotate_to_Right(Node x)
        {
            Node y = x.LChild;
            Node z = x.Parent;
            Node q = y.RChild;
    
            if (z == NULL_NODE)
            {
                this.root = y;
            }
            else
            {
                if (z.LChild == x)
                {
                    z.LChild = y;
                }
                else
                {
                    z.RChild = y;
                }
            }
            y.Parent = z;
    
            y.RChild = x;
            x.Parent = y;
    
            x.LChild = q;
            if (q != NULL_NODE)
            {
                q.Parent = x;
            };
        }
    
    接着的关键问题就是如何计算节点的高度了,问题不难,但是注意我有一个null object: NULL_NODE。这个节点没有父,左,右和高度信息。
        public int Height
        {
            get
            {
                if (this == NULL_NODE)
                {
                    return 0;
                }
    
                List< Node > nodes = new List< Node >() { this };
                List< List < Node > > height = new List< List< Node > >() { nodes };
    
                while (true)
                {
                    nodes = new List< Node >();
                    foreach (Node n in height[height.Count - 1])
                    {
                        if (n.LChild != NULL_NODE)
                        {
                            nodes.Add(n.LChild);
                        }
                        if(n.RChild != NULL_NODE)
                        {
                            nodes.Add(n.RChild);
                        }
                    }
    
                    if (nodes.Count != 0)
                    {
                        height.Add(nodes);
                    }
                    else
                    {
                        break;
                    }
                }
    
                return height.Count;
            }
        }
    
    下面处理如何使这颗树回复平衡:
        private void balance(Node x)
        {
            int balance_factor = x.LChild.Height - x.RChild.Height;
            //There are 4 cases:
            //1. balance factor increased form 1 to 2; do a roatation toward right can address the problem
            //2. balance factor increased from -1 to -2; do a rotation toward left can address the problem
    
            if (balance_factor == 2)
            {
                if (x.LChild.LChild.Height < x.LChild.RChild.Height)
                {
                    this.Rotate_to_Left(x.LChild);
                }
                this.Rotate_to_Right(x);
            }
    
            if (balance_factor == -2)
            {
                if (x.RChild.LChild.Height > x.RChild.RChild.Height)
                {
                    this.Rotate_to_Right(x.RChild);
                }
                this.Rotate_to_Left(x);
            }
        }
    
    和二叉搜索树插入唯一不同的一点就是在插入结束的时候回溯到根节点:
        public void Add(Node n)
        {
            Node p = this.root;
            Node q = NULL_NODE;
    
            if (p == NULL_NODE)
            {
                this.root = n;
            }
            else
            {
                while (p != NULL_NODE)
                {
                    q = p;
                    if (n.Key > p.Key)
                    {
                        p = p.RChild;
                    }
                    else
                    {
                        p = p.LChild;
                    }
                }
    
                if (n.Key > q.Key)
                {
                    q.RChild = n;
                }
                else
                {
                    q.LChild = n;
                }
                n.Parent = q;
            }
            n = n.Parent;
            while (n != NULL_NODE)
            {
                balance(n);
                n = n.Parent;
            }
        }
    

    Sunday, June 20, 2010

    写给自己看之二:二叉搜索树的删除操作

    删除操作比较搞脑子,需要仔细考虑。
    1. 被删除节点n没有孩子。这种情况直接删除就可以。把n.Parent的左或右设成空就可以了。
    2. 被删除节点n只有一个孩子。需要区分左右,然后穿越就可以了。
    3. 被删除节点n有两个孩子。最麻烦了,这个情况下有两种策略,也就是用前驱或后继替换这个节点,然后删除这个前驱或后继。不同的教材使用不同的策略,但是普遍都采用替换数据的方法。我也觉得替换链接要考虑的东西太多了,还容易出错,不如直接替换节点。再说,树的建立本身就不是为了频繁的插入和删除,而是为了快速的访问节点。
    好了,看完这三种情况我发毛了。这么多情况怎么实现?一个一个实现的话会累死的。找来MIT的书看之后发觉其中的确有奥妙。MIT的书强调一点:一个有两个孩子的节点的后继节点不可能有左孩子,同理前驱没有右孩子。这是为什么呢?
    答案很简单:假设这个有两个孩子的节点的后继节点有左子树,那么必然可以在这个左子树中找到一个比该后继更小但是又比原节点大的节点,这样就矛盾了。同理证明前驱没有右子树。(这个结论是MIT里面的一个证明题,国内的教材似乎没有强调这一点,导致我看得很晕乎)。
    好了现在再回过头看这算中情况,第一第二种情况下,n最多只有一个子节点。在看情况三,也是只有一个字节点。那么这两个有相同的地方了。
    其实这个时候只要能把握住总共只有一个子节点这个问题,就可以比较简单的处理这个问题了。
        Node p, child;
        //This block set p as the node to be deleted.
        if (n.LChild == null || n.RChild == null)
        {
            p = n;
        }
        else
        {
            p = Successor(n);
        }
    
        //In all 3 cases, there will be at most one child for n
        if (p.LChild != null)
        {
            child = p.LChild;
        }
        else
        {
            child = p.RChild;
        }
    
        //Set the parent of the child
        if (child != null)
        {
            child.Parent = p.Parent;
        }
    
        //Is the node to be deleted a root?
        if (p.Parent == null)
        {
            this.root = child;
        }
        else
        {
            if (p.Parent.LChild == p)
            {
                p.Parent.LChild = child;
            }
            else
            {
                p.Parent.RChild = child;
            }
        }
    
        //If the node to be deleted is not the paramter,
        //this means an extra content replacement needs to be made.
        if (p != n)
        {
            n.Key = p.Key;
        }
    
    

    写给自己看之一:非递归遍历二叉搜索树(栈)

    二叉搜索树的遍历是可以采用非递归方式的,其实所有的递归都可以写成循环的方式,就是简单和复杂,看得懂和看不懂之间的区别。
    先看一段代码(本以为看了代码就能理解怎么写这么个循环遍历):
    Status InOrderTraverse(BiTree T, Status ( *Visit)(TElemType e)){
     InitStack(S); p = T;
     while(p || !StackEmpty(S)){
      if (p) { Push(S, p); p = p->lchild; }
      else {
       Pop(S, p);
       if(!Visit(p->data)) return ERROR;
       p = p->rchild;
      }
     }
     return OK
    }
    
    应该是一段很简洁高效的C/C++代码,但是看得我瞬间晕倒。我根本没看懂是怎么回事情。
    再回头想一想什么才算利用栈写循环遍历呢?
    首先,作为中序遍历,必然总要走所有的左子树。
        Stack< Node > stack = new Stack< Node >();
    
        Node n = this.root;
    
        while (n != null)
        {
            stack.Push(n);
            n = n.LChild;
        }
    
    这一步必然是这样的。 其次,当栈找完所有的左子树的时候,就要打印出该节点的值(这个没问题)。这个时候其实相当于在访问中间节点,因为如果把空的左节点看成非空,那么其实就是打印一个空值,也就是说正真的打印其实是中节点。那么此时只需要遍历该节点的右子树就可以了。
        while (stack.Count != 0)
        {
            n = stack.Pop();
            _visit(n);
            stack.Push(n);
        }
    
    但是,光这段代码不可能继续去遍历这颗右子树啊!怎么办?这个时候看看原来的C/C++代码,有点感觉了。只要把这两个循环结合在一起就可以解决这个问题。灵感来自最后那句stack.Push,只要重新复制n就解决了,不过这其实是一个揣测的操作,我是一点理论根据也没有,就算对了,我感觉依然没有完全搞懂的样子。
        while (n != null || stack.Count != 0)
        {
            if (n != null)
            {
                stack.Push(n);
                n = n.LChild;
            }
            else
            {
                n = stack.Pop();
                _visit(n);
                n = n.RChild;
            }
        }
    

    Wednesday, June 9, 2010

    ArrayList和Hashtable

    最近看数据结构的时候在想为什么.Net的Hashtable的key和value都是object,而且没有泛型的版本。直道自己动手练习,才发觉其中奥妙。没有泛型的原因简而言之就是用泛型的话Collision就不好处理了。(不好处理不等于不能处理,就是处理起来明显太麻烦了。)
    为Hashtable做铺垫的ArrayList(这个是我蓄意写的泛型版本):
    一点就能看,不想看别点
    以下为一个Hashtable:
        class MyHashtable
        {
            private MyArrayList< object > keys;
            private ValueChain[] values;
    
            private class ValueChain
            {
                public object Value { get; set; }
                public object Key { get; set; }
                public ValueChain next;
    
                public ValueChain(object key, object value)
                {
                    this.Key = key;
                    this.Value = value;
                    this.next = null;
                }
            }
    
            //Apparently this is way too samll, it can ensure that Collision happens.
            private const int SIZE = 4;
            private MyHashtable(int size)
            {
                this.keys = new MyArrayList< object >();
                this.values = new ValueChain[size];
            }
    
            public object[] Keys
            {
                get
                {
                    return this.keys.ToArray();
                }
            }
    
            public object[] Values
            {
                get
                {
                    MyArrayList< object > values = new MyArrayList< object >();
                    foreach (object k in this.Keys)
                    {
                        values.Add(this[k]);
                    }
                    return values.ToArray();
                }
            }
    
            public object this[object k]
            {
                get
                {
                    int h = hash(k);
                    if (this.values[h] == null)
                    {
                        throw new IndexOutOfRangeException();
                    }
                    else
                    {
                        ValueChain p = this.values[h];
                        while (p != null)
                        {
                            if (p.Key == k)
                                return p.Value;
                            p = p.next;
                        }
                        throw new IndexOutOfRangeException();
                    }
                }
                set
                {
                    this.Add(k, value);
                }
            }
    
            public MyHashtable()
                : this(SIZE)
            {
    
            }
    
            public void Add(object key, object value)
            {
                int h = hash(key);
                ValueChain  v = new ValueChain(key, value);
                if (values[h] == null)
                {
                    values[h] = v;
                    keys.Add(key);
                }
                else
                {
                    ValueChain p = values[h];
                    ValueChain q = null;
                    while (p != null)
                    {
                        if (p.Key == key)
                        {
                            p.Value = value;
                            return;
                        }
                        q = p;
                        p = p.next;
                    }
                    q.next = v;
                    keys.Add(key);
                    Debug.Print("Collision: {0}", key);
                }
            }
    
            private int hash(object key)
            {
                //Obviously, this is a dumb idea.
                return Math.Abs(key.GetHashCode()) % SIZE;
            }
        }
    
    很明显的一点就是在比较Key的时候泛型就不管用了,这个时候要么用IComparable和IComparer两个接口,要么就用object一了百了。显然图省事就是object啦~

    Sunday, May 9, 2010

    Google code jam: Qualification Round

    又到了一年一度的code jam,过去从来没有参加过,因为从来不认为我天资聪颖到可以玩code jam。但是万事总有一个开头,今年我就参加了。获得名次的话,从来没想过,或者说in my dreams。
    资格赛(Qualification Round):3个题目,给我的感觉是难度依次递增。其中最为阴险的是最后一题(我被秒杀了)。
    第一题:Snapper Chain。简单题。小输入:9739/11496,大输入:8169/9676。N位2进制外加模(mod)运算。33分获得的相对轻松。
    第二题:Fair Warning。小输入:3372/4419 ,大输入:2500/3042。整体难度最大(几乎没什么人做,相对而言),但是没有阴招(这点非常好)。感觉这题目在考验参赛者数学功力,并且顺带考察了参赛者对编程语言的了解程度。本题的第一个挑战在于数学,更细一点就是初等数论中关于最大公约数(Greatest Common Divisor,简称gcd,不要想歪了)的理解。我的解法就是最常用的递归欧几里德算法(Euclidean algorithm)(其实还有别的算法,更好更快,但是我自己没实现过,也就不用了)。第二个难点在于计算机对于数字的编码方式。几乎我所了解的所有强类型语言(Strongly typed programming language)对于一个10进制数的表达方式最多用两个机器字(Machine Word)。也就是说32位机器上最大的数字也就是用64位表示,再大就要溢出了(Overflow)。所以为了不自己写一个大数结构(自己写的话,加减乘数都太烦了),我就选择了Python(版本号2.5.4,GAE也就支持到2.5)。Python最大的好处就是不限制数的长短,只要内存够用就行了。这题目困扰了将近一天时间,解答出来已经是code jam时间23:13:14了。累计错了5次,很囧。我随便浏览解出这题的人的名单里面没有人超过4次的。
    第三题,Theme Park。小输入:8274/8745,大输入:3108/7845。题目很简单,陷阱很可怕。这是一个计数问题,可怕的地方在于如果采用简单的循环方式解题的话,不可能处理那个大的输入文件,我就给这道题目秒杀了。
    最后得分:76。和大牛们不能比,我也就享受这个解题过程中给我带来的困扰罢了。对,是困扰。我自知天资愚笨,所以只好勤加练习。和跑步一样,我羡慕那些天生就能跑得飞快,跑得时间超长并且不吃力的人,但是我自己一跑就知道自己慢并且非常吃力。我也知道自己再怎么努力也追不上那些天生体力好并且快的人。可是我知道这个世界不仅仅需要牛顿、爱因斯坦和比尔盖茨。

    Monday, April 26, 2010

    [转贴] 一声叹息——世博试运行有感

    周日慵懒的上午,当我睁开惺忪的双眼,用遥控器打开的电视机,“2010世博欢迎您”那熟悉的旋律又一次回响在耳际。拾起床头世博试运行的门票,恍惚间觉得卡片上“海宝”正用一种诡异的眼神凝望着我,充满疑惑又略显嘲讽。我的思绪一下被拉回到2天前。
    乍暖还寒,如织的游人,热情的志愿者,精心编排的宣传海报布满申城的大街小巷,空气中仿佛弥漫着世博的气味。终于在一个风和日丽的上午,我有幸与教务处的几位老师一起成为这一盛会的第一批见证者。刚入大门,映入眼帘的便是位于世博轴顶端的主题雕塑,象征2010的红绸带造型被伞状网格围栏所包裹,巨伞从地底直刺苍穹,在天际无限延伸。登上世博轴,遥望周围矗立的各标志性建筑:中国馆,世博主题馆,世博中心,世博大舞台。一望无垠的大道配合雄伟壮丽的建筑群犹如一曲恢弘壮丽的交响乐,气宇轩昂,慑人心魂。而分布在轴心周围的为来自五湖四海的展馆,它们形态各异,光怪陆离,设计理念和造型超越人类的想象,难以用语言来描述,配合展馆内用抽象,现代等方式对于民族科技文化的诠释,恍惚间犹如时空交错。时而的徘徊在当代废水管道纵横交错的工厂内探索人与自然和谐的意义,时而穿越回16世纪感受麦哲伦发现澳洲大陆的欣喜若狂,时而置身时尚之都米兰欣赏新潮时装,时而塞纳行走河畔浏览法兰西美景,令人流连忘返......
    电视中一阵刺耳的报时声把我的思绪又拉回到了现在,央视午间新闻有一回闪亮登场,最近的央视新闻比较千篇一律,前半段为玉树地震,举国人民沉痛哀悼,众志成城,抗震救灾,后半段为世博盛会,举国人民欢欣鼓舞,齐心协力,迎海外宾客。作为一名中华儿女,我自然要与名族“同呼吸共命运”,令自己酝酿好情感融入到新闻报道的氛围中,可我渐渐的陷入疑惑,不断的悲伤和喜悦的情感中来回转换绝非易事,仿佛思维要从大脑中崩裂一般,为此我特地去查了下封尘已久的精神病学教材,才回忆起这类疾病叫做精神分裂①,这令我思索着生活在水深火热中的灾区人民与百年一遇盛会中存在的必然联系,唯一能想到的联系便是资金。近今年我国天灾不断,汶川,玉树地震,雪灾,旱灾,涝灾,每种自然灾害都在无情的光顾着刚从遍体鳞伤中恢复的中华民族,抵抗天灾的拨款都与日俱增,可我们依然倾举国之力举办世博,这是否值得?1851年第一届世博会在伦敦举行,标志着往昔日不落帝国凭借工业革命及遍布全球的殖民地,站在了世界之巅。世博会便是世界顶级科学技术的集中展示。百多年时空轮回,随着信息技术革命席卷全球。信息技术替代工业技术成为了时代的潮流,世博会的意义悄然发生了变化,逐渐由科学技术展沦落为世界土特产及人文艺术展。当世博展示给世界列强当成一种民间行为,我们还未放弃对于世博会孜孜不倦的追求。收入不宽裕的我还资助着一位云南贫困地区的中学生,区区八百元就能令其完成一年的学业,那举办世博千百亿的投资如果注入支援西部,希望工程,灾区重建等建设是否会让中国呈现出勃勃生机?
    既然中国已获得世博会的举办权,全国人民勒紧裤带鼎力支持也无可厚非,毕竟世博开启了一扇世界了解中国及中国了解世界的窗口,可在举办世博会的过程中,一些方式实在叫人匪夷所思,世博会的吉祥物“海宝”②,世博会歌曲“2010世博欢迎您”③。皆为抄袭之作。这实乃令国外友人贻笑大方。回顾过去,我国几代领导人都把解放思想,实事求是当做治国的方针。抄袭行为显然犯了未能实事求是的错误。放眼当今社会,学术造假,技术剽窃蔚然成风,正所谓上梁不正下梁歪,若抄袭之风堂而皇之荣登大雅之堂,后果不堪设想。世博开幕前上海人民每家每户都欣喜了得到了世博的门票,上海人口高居1600万,这又是一笔巨大的投资。虽然我不明白这种刷新参观率数字的行为对于提高综合国力拉动GDP有何影响,或许只是来年政府工作报告中一串华丽的数字。可我深刻这笔不小经费对必然抗震救灾举足轻重,否则国家不会一次次的呼吁广大市民伸出援手,若在个人娱乐与救死扶伤中作出一个抉择,我想有良知的市民必然会作出正确的抉择,把这笔经费捐献到祖国最需要的地方,可事到如今我们连抉择的机会都没有~~。
    古人云“居庙堂之高,则忧其民,处江湖之远,则忧其君”④,庙堂之高,我乃一届庶民,无可企及。处江湖之远,温总理的话语又在耳边回响“将来要创造条件给人民向政府提意见”,那本人现在的疑虑也乃不合时宜的庸人自扰。世博尚未开幕,零零总总,已在脑海烙下了印记,凝望海宝,聆听群星在山寨歌曲中声嘶力竭的高喊,顿感五味陈杂,由衷发出一声叹息。
    PS:以上文章纯属转载,不代表本人观点,谢绝跨省
    ①精神病学第5版 第四章 精神分裂的诊断标准 人民卫生出版社出版,主编 郝伟
    ②
    ③
     
    ④岳阳楼记 范仲淹

    Original

    Saturday, February 27, 2010

    排序:插入排序和归并排序比较

    排序算法的可以用两种不同的标准分类:
    1. 存储空间
    2. 稳定(stable)

    所谓存储空间指的是算法需要的外部空间是不是一个常数。当需要的外部存储空间是常数时,这个排序就是原地排序(in place sort)。反之就不是。计算机科学就是一个时间和空间的妥协,可以用空间换时间,也可以用时间换空间。 所谓稳定,就是相等元素的相对位置不变。例子: 1,3,1,6中两个1的相对位置必须保持一致。

    插入排序(Insertion Sort)是算法导论(Introduction to Algorithm)介绍的第一个排序算法,它的优点是算法简洁,实现(implementation)方便,稳定(相同元素的相对位置保持不变),而且是原地排序。缺点是时间复杂度为n2,也就是慢。
    归并排序(Merge Sort)则是介绍的第二个算法,优点是快,时间复杂度是nlg(n),并且稳定。缺点是递归,比插入排序复杂,不是原地排序。

    插入排序的算法表述:
    把n维数组分成前后两个部分,视前半部分为已排序的(sorted),后半部分为未排序的(unsorted)。
    每次循环取出未排序部分(unsorted)的第一个元素,逐个比较它和已排序部分(sorted)的大小,并且插入到已排序部分(sorted)。

    归并排序是一种“分治”(Divide and conquer)算法:把问题(problem)分成若干的小的问题逐个解决。
    “分治”算法的三个步骤:
    1. 分解(devide): 将原问题分解为一系列子问题。
    2. 解决(conquer): 递归地解答各个子问题,若子问题够小,可直接求解。
    3. 合并(combine): 将子问题的结果合并成原问题的解。
    对于归并排序来说就是:
    1. 将n个元素分解为n/2个子序列。
    2. 再用归并算法递归解决这两个字序列的问题。
    3. 合并两个已排完序的序列。
    抽象的数学证明很难给人一个具象的感受,所以需要实验来感受一下。
    实验环境:
    CPU: Intel Core2 Duo T6400 @ 2.0GHZ
    语言: C#(.NET 3.5 SP1) / C++(gcc 3.4.5)

    实验数据:
    0至100000之间的90000个随机数。

    MergeSort(C#):

    Insertion Sort(C#):

    C#结果:
    归并排序(merge sort): 00:00:00.0960054
    插入排序(insertion sort): 00:00:49.5428337

    Merge Sort(C++):

    Insertion Sort(C++):

    C++结果(毫秒):
    归并排序(merge sort): 78
    插入排序(insertion sort): 5273

    从实验结果来说,当数据量很大的时候,归并排序的性能(performance)远好于插入排序。
    实验同时也表明对于一个好的算法其性能表现比较一致,C#和C++在归并排序的测评上表现相近。但是对一个相对较差的算法来说,更高级的语言似乎会放大这个差距,C++和C#相差10倍。

    总结:
    归并排序是用空间换时间,而插入排序是用时间换空间。

    Saturday, February 6, 2010

    我的坐标

    这个测试结果如下:
    政治立场坐标 0.8 文化立场坐标 0.8 经济立场坐标 0.4 结果说明: 政治观念坐标,负值为左,即威权主义 (Authoritarianism),正值为右,即自由主义 (Libertarianism)。 社会文化观念坐标,负值为保守与复古派 (Conservatism),正值为自由与激进派 (Liberalism)。 经济观念坐标,负值为左,即集体主义与福利主义 (Welfarism, Collectivism),正值为右,即新自由主义(Neoliberalism)。 三个维度的最大区间均为 [-2,2]。
    测试表明我是提倡自由主义和激进的右派(Rightist)。

    Wednesday, January 27, 2010