饭否正式回归。时隔近2年，饭否还是那个饭否，我却不再是过去的我了。
内牛满面和抒情不合适我，上图才有真相：
Friday, November 26, 2010
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初期常见的问题。
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！）但是都只需要知道失去平衡的最小的祖先节点就可以了（这就是回溯插入路径）：
现在的问题是怎么旋转？
先看图:
对这种情况下的x节点做一次向左的旋转。
结果图：
从结果可以看出唯一一个需要变动的字节点就是q，别的节点原来在什么位置现在还在什么位置。一开始听到旋转我马上就晕眩了。现在把图画出来自己研究一下，也就只需要变动一个节点，这样的操作显然不是很困难。但是边界检查很重要。这时有两种情况：
AVL树（平衡树）的定义：
如何才能做到这点呢？
我读的教材所采用的方法是多设一个节点信息叫BF(Balance Factor)作为枚举类型。三个值分别为：LH(Left High)，EH(Equal High)和RH(Right High)并采用递归插入。说实话，作者能写出这么牛的递归并且保证正确相信难倒了不少学生（包括我）。
还有一本经典教材，采取不同的方法解决这个问题：节点增设高度信息。然后对插入路径进行高度平衡。我比较青睐这种做法。
然而这种做法却需要一个额外的节点来表示空节点，否则无法正确处理高度差。所以自然而然想到了null object这个模式。
好了，现在开始解决插入中最麻烦的问题：平衡高度。
一共4中情况（OMG！）但是都只需要知道失去平衡的最小的祖先节点就可以了（这就是回溯插入路径）：
- 受影响的节点从1增加到2，左子树的树高是1。也就是插入的这个左子树的左边。这种情况只要对高度差为2的节点进行一次向右旋转就可以了。
- 受影响的节点从-1增加到-2，右子树的树高是-1。也就是插入这个右子树右边。这种情况需要对高度差为2的节点进行一次向左的旋转。
- 受影响的节点从1增加到2，左子树的树高是-1.也就是插入的是这个左子树的右边。这种情况比较复杂。为了保持中序遍历的正确性（很重要），需要先对这个左子树做一次向左的旋转。然后问题转化为1的情况。
- 受影响的节点从-1增加到-2，右子树树高是1.也就是插入这个右子树的左边。这种情况需要对这个右子树做一次向右的旋转，转化为情况2。
现在的问题是怎么旋转？
先看图:
对这种情况下的x节点做一次向左的旋转。
结果图：
从结果可以看出唯一一个需要变动的字节点就是q，别的节点原来在什么位置现在还在什么位置。一开始听到旋转我马上就晕眩了。现在把图画出来自己研究一下，也就只需要变动一个节点，这样的操作显然不是很困难。但是边界检查很重要。这时有两种情况：
- x的父节点是空。也就是x本身是root，那么把root指向y就可以了。
- 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
写给自己看之二：二叉搜索树的删除操作
删除操作比较搞脑子，需要仔细考虑。
答案很简单：假设这个有两个孩子的节点的后继节点有左子树，那么必然可以在这个左子树中找到一个比该后继更小但是又比原节点大的节点，这样就矛盾了。同理证明前驱没有右子树。（这个结论是MIT里面的一个证明题，国内的教材似乎没有强调这一点，导致我看得很晕乎）。
好了现在再回过头看这算中情况，第一第二种情况下，n最多只有一个子节点。在看情况三，也是只有一个字节点。那么这两个有相同的地方了。
其实这个时候只要能把握住总共只有一个子节点这个问题，就可以比较简单的处理这个问题了。
- 被删除节点n没有孩子。这种情况直接删除就可以。把n.Parent的左或右设成空就可以了。
- 被删除节点n只有一个孩子。需要区分左右，然后穿越就可以了。
- 被删除节点n有两个孩子。最麻烦了，这个情况下有两种策略，也就是用前驱或后继替换这个节点，然后删除这个前驱或后继。不同的教材使用不同的策略，但是普遍都采用替换数据的方法。我也觉得替换链接要考虑的东西太多了，还容易出错，不如直接替换节点。再说，树的建立本身就不是为了频繁的插入和删除，而是为了快速的访问节点。
答案很简单：假设这个有两个孩子的节点的后继节点有左子树，那么必然可以在这个左子树中找到一个比该后继更小但是又比原节点大的节点，这样就矛盾了。同理证明前驱没有右子树。（这个结论是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做铺垫的ArrayList（这个是我蓄意写的泛型版本）：
一点就能看，不想看别点
class MyArrayList< T >
{
private const int INIT_SIZE = 2;
public int Length { get; private set; }
public int Capacity { get; private set; }
private T[] array;
public MyArrayList():this(INIT_SIZE)
{
}
private MyArrayList(int size)
{
array = new T[size];
this.Length = 0;
this.Capacity = size;
}
public T this[int i] {
get
{
if (i < 0 || i > this.Length - 1)
throw new IndexOutOfRangeException();
return this.array[i];
}
}
private void CheckCapcity()
{
if (this.Length >= this.Capacity)
{
if (this.Length == int.MaxValue)
throw new OverflowException();
int i = this.Length - 1;
if (this.Length < int.MaxValue / 2)
{
this.Capacity *= 2;
}
else
{
this.Capacity = int.MaxValue;
}
Debug.Print("Expand to {0}", this.Capacity);
T[] newArray = new T[this.Capacity];
while (i >= 0)
{
newArray[i] = array[i];
i--;
}
this.array = newArray;
GC.Collect();
}
}
public void Add(T t)
{
this.CheckCapcity();
this.array[this.Length++] = t;
}
public T[] ToArray()
{
T[] a = new T[this.Length];
for (int i = 0; i < this.Length; i++)
{
a[i] = this.array[i];
}
return a;
}
public void Remove(int position)
{
if (position < 0 || position >= this.Length)
{
throw new IndexOutOfRangeException();
}
for (int i = position; i < this.Length - 1; i++)
{
this.array[i] = this.array[i + 1];
}
this.Length--;
}
public void Clear()
{
for (int i = 0; i < this.Length; i++)
{
this.array = null;
}
this.Length = 0;
}
}
以下为一个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啦~
Tuesday, June 8, 2010
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的红绸带造型被伞状网格围栏所包裹，巨伞从地底直刺苍穹，在天际无限延伸。登上世博轴，遥望周围矗立的各标志性建筑：中国馆，世博主题馆，世博中心，世博大舞台。一望无垠的大道配合雄伟壮丽的建筑群犹如一曲恢弘壮丽的交响乐，气宇轩昂，慑人心魂。而分布在轴心周围的为来自五湖四海的展馆，它们形态各异，光怪陆离，设计理念和造型超越人类的想象，难以用语言来描述，配合展馆内用抽象，现代等方式对于民族科技文化的诠释，恍惚间犹如时空交错。时而的徘徊在当代废水管道纵横交错的工厂内探索人与自然和谐的意义，时而穿越回16世纪感受麦哲伦发现澳洲大陆的欣喜若狂，时而置身时尚之都米兰欣赏新潮时装，时而塞纳行走河畔浏览法兰西美景，令人流连忘返......
电视中一阵刺耳的报时声把我的思绪又拉回到了现在，央视午间新闻有一回闪亮登场，最近的央视新闻比较千篇一律，前半段为玉树地震，举国人民沉痛哀悼，众志成城，抗震救灾，后半段为世博盛会，举国人民欢欣鼓舞，齐心协力，迎海外宾客。作为一名中华儿女，我自然要与名族“同呼吸共命运”，令自己酝酿好情感融入到新闻报道的氛围中，可我渐渐的陷入疑惑，不断的悲伤和喜悦的情感中来回转换绝非易事，仿佛思维要从大脑中崩裂一般，为此我特地去查了下封尘已久的精神病学教材，才回忆起这类疾病叫做精神分裂①，这令我思索着生活在水深火热中的灾区人民与百年一遇盛会中存在的必然联系，唯一能想到的联系便是资金。近今年我国天灾不断，汶川，玉树地震，雪灾，旱灾，涝灾，每种自然灾害都在无情的光顾着刚从遍体鳞伤中恢复的中华民族，抵抗天灾的拨款都与日俱增，可我们依然倾举国之力举办世博，这是否值得？1851年第一届世博会在伦敦举行，标志着往昔日不落帝国凭借工业革命及遍布全球的殖民地，站在了世界之巅。世博会便是世界顶级科学技术的集中展示。百多年时空轮回，随着信息技术革命席卷全球。信息技术替代工业技术成为了时代的潮流，世博会的意义悄然发生了变化，逐渐由科学技术展沦落为世界土特产及人文艺术展。当世博展示给世界列强当成一种民间行为，我们还未放弃对于世博会孜孜不倦的追求。收入不宽裕的我还资助着一位云南贫困地区的中学生，区区八百元就能令其完成一年的学业，那举办世博千百亿的投资如果注入支援西部，希望工程，灾区重建等建设是否会让中国呈现出勃勃生机？
既然中国已获得世博会的举办权，全国人民勒紧裤带鼎力支持也无可厚非，毕竟世博开启了一扇世界了解中国及中国了解世界的窗口，可在举办世博会的过程中，一些方式实在叫人匪夷所思，世博会的吉祥物“海宝”②，世博会歌曲“2010世博欢迎您”③。皆为抄袭之作。这实乃令国外友人贻笑大方。回顾过去，我国几代领导人都把解放思想，实事求是当做治国的方针。抄袭行为显然犯了未能实事求是的错误。放眼当今社会，学术造假，技术剽窃蔚然成风，正所谓上梁不正下梁歪，若抄袭之风堂而皇之荣登大雅之堂，后果不堪设想。世博开幕前上海人民每家每户都欣喜了得到了世博的门票，上海人口高居1600万，这又是一笔巨大的投资。虽然我不明白这种刷新参观率数字的行为对于提高综合国力拉动GDP有何影响，或许只是来年政府工作报告中一串华丽的数字。可我深刻这笔不小经费对必然抗震救灾举足轻重，否则国家不会一次次的呼吁广大市民伸出援手，若在个人娱乐与救死扶伤中作出一个抉择，我想有良知的市民必然会作出正确的抉择，把这笔经费捐献到祖国最需要的地方，可事到如今我们连抉择的机会都没有~~。
古人云“居庙堂之高，则忧其民，处江湖之远，则忧其君”④，庙堂之高，我乃一届庶民，无可企及。处江湖之远，温总理的话语又在耳边回响“将来要创造条件给人民向政府提意见”，那本人现在的疑虑也乃不合时宜的庸人自扰。世博尚未开幕，零零总总，已在脑海烙下了印记，凝望海宝，聆听群星在山寨歌曲中声嘶力竭的高喊，顿感五味陈杂，由衷发出一声叹息。
PS：以上文章纯属转载，不代表本人观点，谢绝跨省
②
③
④岳阳楼记 范仲淹
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倍。
总结：
归并排序是用空间换时间，而插入排序是用时间换空间。
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#):
public static void sort(int[] array)
{
if (array.Length == 2)
{
if (array[0] > array[1])
{
Utility.swap(ref array[0], ref array[1]);
}
return;
}
if (array.Length == 1)
return;
int iMid = array.Length / 2;
int[] first = getArray(array, 0, iMid);
sort(first);
int[] second = getArray(array, iMid, array.Length);
sort(second);
int i = 0, j = 0, k = 0;
for (; j < first.Length && k < second.Length; i++)
{
if (first[j] < second[k])
{
array[i] = first[j];
j++;
}
else
{
array[i] = second[k];
k++;
}
}
if (j != first.Length)
{
for (; j < first.Length; j++, i++)
array[i] = first[j];
}
else
{
for (; k < second.Length; k++, i++)
array[i] = second[k];
}
}
Insertion Sort(C#):
public static void sort(int[] array)
{
int size = array.Length;
for (int i = 1; i < size; i++)
{
for (int j = 0; j < i; j++)
{
if (array[i] < array[j])
{
int v = array[i];
for (int k = i; k > j; k--)
{
array[k] = array[k - 1];
}
array[j] = v;
}
}
}
}
C#结果:
归并排序（merge sort）： 00:00:00.0960054
插入排序（insertion sort）： 00:00:49.5428337
Merge Sort(C++):
template < class T >
void mergeSort(T array[], int const size){
if(size == 2){
if(array[0] > array[1]){
T tmp = array[0];
array[0] = array[1];
array[1] = tmp;
}
return;
}
if(size == 1){
return;
}
int mid = size / 2;
int first_size = mid;
T* first = getArray< T >(array, 0, mid);
mergeSort(first, first_size);
int second_size = size - mid;
T* second = getArray< T >(array, mid, size);
mergeSort(second, second_size);
int i = 0, j = 0, k = 0;
for(; j < first_size && k < second_size;){
if(first[j] < second[k]){
array[i++] = first[j++];
} else {
array[i++] = second[k++];
}
}
while(j != first_size){
array[i++] = first[j++];
}
while(k != second_size){
array[i++] = second[k++];
}
delete [] first;
delete [] second;
}Insertion Sort(C++):
void insertionSort(int array[], int size){
if(array == 0 || size == 0)
return;
for(int i = 1; i < size; i++){
for(int j = 0; j < i; j++){
if(array[i] < array[j]){
int v = array[i];
for(int k = i; k > j; k--){
array[k] = array[k-1];
}
array[j] = v;
}
}
}
}
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
Wednesday, January 13, 2010
Google, Awesome!
今天在推特上看到了这么一条：
Facebook的原罪是它能让人认识想认识的人，Twitter的原罪是它能让人说出想说的话，Google的原罪是它能让人找到想找到的东西，Youtube的原罪是它能让人看到想看到的东西……所以它们都被干掉了……Google在中国转折点应该是从“高野”这个担心同学“身心健康”的“大学生”开始的。在此之前Google已经在搜索内容中滤去了大量的政治敏感信息，这个工作需要大量的手工劳动。之后的岁月就是伴随着饭否，twitter,facebook,blogger等等群众喜闻乐见的网站的"Time Out"和"connection reset"了。在此期间我朝各大媒体的主要位置赫然刊登了“谷歌涉黄”的新闻，大家都在怪罪牛顿发现了万有引力导致飞机坠毁。但是这一轮的媒体攻击和早年的FLG不同，FLG传播再广也没到一个家喻户晓的程度，不过谷歌是。本来是想杀鸡儆猴，没想到搬起石头砸了自己的脚。“高野”不仅没有成为“先进个人”，反倒成了CCAV下流手段的证据。随着李开复的离去，Google中国也失去了重要的旗帜和有分量的话语权。之后又传出了Google和中国作协的版权纠纷。Google依然在我朝各级机关不断骚扰中坚强的活着，那是因为Google认为中国的市场还没有到放弃的地步。 但是，根据A new approach to China里的描述，有第三方长期攻击Gmail企图窃取邮件信息。这应该是触犯了Google的底线。回想当年Google宁愿每天交罚款也不愿遵守在Patriot Act的名义下上交用户个人信息可以看出，Google对自己的理念看得比什么都重。 在推特上又发现了一条：
@kisafran 努力学习，到春暖花开的地方去，翅膀硬了以后再回来。RT @klx1204: 我爱我的祖国，我爱这个生我养我的国度，我依旧坚信共产主义必将实现，但我仍然要移民，因为我不想我的子孙生活在一个闭关锁国与世隔绝的地方。Google好样的，这样的地方不合适你！
Subscribe to:
Posts (Atom)
