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

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好样的,这样的地方不合适你!

Thursday, December 31, 2009

2009的最后一天

09年的最后一天是这么开始的: 8:46:18系统出现了我报道的备案,始干活。于闲时对战《吉米多维奇》,败得心灰意冷。 午后,港汇门口之低音喇叭不断炮击,攻击范围之大使人难以置信。竟使吾身中数炮于高层。黄昏时刻,当“不明真相”群众于港汇,胡乱溜达耳。子曰:冷啊...,猛曰:极是。 晚上,挑灯夜战《吉米多维奇》,独感寡不敌众。唯有屡败屡战,身经百战,才能弥补我儿时曾吹过的牛B。 谨以此帖作为09年告别自勉制作。

Wednesday, December 30, 2009

[转贴] 《我哥在光腚》

墙外(墙内一切都很河蟹): 歌词(猛击)

Wednesday, December 23, 2009

What's NORMAL?

House.S03E04 Lines in the Sand中一段House对社会的辛辣讽刺: Wilson: Hope is all those parents have going for them. House: No, hope is what's making them miserable. What they should do is get a cocker spaniel. A dog would look them in the eye, wag his tail when he's happy, lick their face, show them love. (有希望才有失望) Cameron: Is it so wrong for them to want to have a normal child? It's normal to want to be normal. Lines in the Sand House: Spoken like a true circle queen. See skinny socially privileged white people get to draw this neat little circle, and everyone inside the circle is normal, anyone outside the circle should be beaten, broken and reset so they can be brought into the circle. Failing that, they should be institutionalized or worse, pitied. (“主流”人喜欢给人分类,和自己一样的人就正常,和自己不一样的人就要“帮助”。如果不能成功“改造”,就会给关起来或者,更糟,被怜悯。) Cameron: So it's wrong to feel sorry for this little boy? Lines in the Sand House: Why would you feel sorry for someone who gets to opt out of the inane courteous formalities which are utterly meaningless, insincere and therefore degrading? This kid doesn't have to pretend to be interested in your back pain or your excretions or your grandma's itchy place. Can you imagine how liberating it would be to live a life free of all the mind-numbing social niceties? I don't pity this kid, I envy him. (为什么要可怜一个能够可以选择不生活在繁文缛节里的人?他不必装着去关心别人。你能想象这样的生活有多自由么?我一点也不可怜这个孩子,我羡慕他。) 其中更有一段父母对子女成长的期望与现实落差描述极为精辟: When a baby is born, it's perfect; little fingers, little toes, plump, perfect, pink, and brimming with unbridled potential. Then it's downhill, some hills steeper than others. Parents get off on their kid's accomplishments. They'll annoy you with trophy rooms and report cards. Hell they'll even show you a purple cow and tell you what a keen eye for color their kid has. (刚出生的孩子最完美,渐渐的孩子就不想你想象的那么好了。孩子开始烦你,开始给你添乱。)