Sunday, June 20, 2010

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

二叉搜索树的遍历是可以采用非递归方式的,其实所有的递归都可以写成循环的方式,就是简单和复杂,看得懂和看不懂之间的区别。
先看一段代码(本以为看了代码就能理解怎么写这么个循环遍历):
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)。