Archive for the ‘未分类’ Category

快排时间复杂度退化到 O(n2) 的问题

由 chys 发表于 2012 年 02 月 04 日

算法书上都会讲：在输入已经有序等特定情况下，快速排序 (quicksort) (最简单的实现) 的时间复杂度会退化到 O(n2)。书上通常建议用 “随机化” 或 “三取中” 的方法选 pivot，并声称这样的算法这样对于非故意构造的真实数据，基本上总是会有一个满意的 O(nlogn) 运行时间。

可惜，事情没这么简单。

不需要故意构造，只要用一个常量数组 (不是常量也行，只要数组中包括比较多的相等元素，比如仅由很小的正整数组成的较长的数组)，不算 pivot 怎么选，大部分教材上的实现都照样退化至 O(n2)。

问题不难发现：这时的问题不在 pivot 的选择，而在 partition 这一步，多数教材上的 partition 代码在区间中有大量元素与 pivot 相等时都会把这些元素分到 pivot 的同一边。

要改进也不难，以《算法导论》上的 partition 代码为例 (比多数国内教材中所用的版本简洁)，改进前：

	while (q != hi) {
		// Loop invariant: *[lo ... p) <= pivot <= *[p, q)
		if (*q < pivot)
			std::swap(*p++, *q);
		++q;
	}

改进后：

	while (q != hi) {
		if (*q < pivot)
			std::swap(*p++, *q);
		++q;

		if (q == hi)
			break;
		if (*q <= pivot)
			std::swap(*p++, *q);
		++q;
	}

其实就是把 “小于” 的判断改成 “小于” 与 “小于等于” 交替，这样与 pivot 相等的元素会被大致平均地分到 pivot 两边。

之所以写这篇博文，就是因为昨天实际碰到了这个问题——对一组真实数据，我自己写的快排 (使用 “三取中” 法选 pivot) 花的时间是 std::sort 的十万倍。做上述改进后即变回到与 std::sort 相当。

这样的改进只是减少了对现实中的真实数据退化的可能性，仍然可以故意构造出 O(n2) 的情况。有更好 (也更复杂) 的解决方案，比如 SGI STL 中用的 introsort，它是一种快速排序与堆排序 (heapsort) 的混合算法，对真实数据的速度与 quicksort 相似，同时最坏情况下的时间复杂度为 O(nlogn)。

标签:

Gmail 的邮件编码

由 chys 发表于 2011 年 11 月 30 日

我一直以为 Gmail 发邮件是始终用 UTF-8 的，刚才无聊翻了一下跟一个台湾人往复的几封邮件的源码，发现不是那么简单。他发过来的是清一色的 UTF-8，我给他的一会儿是 UTF-8，一会儿是 GB2312 (名为 2312，其实是 GBK)，一会儿是 Big5。

这才知道原来 Gmail 是可以设置邮件编码的：

但是什么是 “default encoding” 呢，比较了若干邮件的编码，Gmail 所说的 “default encoding” 似乎是似乎是根据文字内容猜测邮件的语言，然后选择这种语言最常用的编码 (不成功时 fallback 到 UTF-8)。今天跟我发邮件的是台湾人，他写繁体字，我写简化字，Gmail 很郁闷，它不知道该用 UTF-8 还是 GB 还是 Big5 合适了，这一封是 GB 与 Big5 混合的：

标签: , ,

Passing of the great minds

由 chys 发表于 2011 年 10 月 13 日

最近十天，在我比较关注的领域里，有三位比较有影响的人登上了方舟：

  1. Steve Jobs (1955.02.24 – 2011.10.05)，苹果公司联合创始人及前 CEO。
  2. Dennis Ritchie (1941.09.08 – 2011.10.08/09)，Unix 之父 (之一)，C 语言之父 (之一)。
  3. Bob Galvin (1922.10.09 – 2011.10.11)，摩托罗拉前 CEO，“手机之父”。


[左为 Jobs，照片版权属于 Matthew Yohe，按 CC-BY-SA 3.0 许可；右为 Ritchie，照片属于公有领域]

在全球悼念乔布斯的高峰时段，我写过一句话 (大意)：

相比乔布斯，我更希望 Vint Cerf 将来能有这样的待遇，不过看来是不可能了。

写完以后觉得不太适合，又删了。一来这有诅咒 Cerf 老先生[注]之嫌；二来这又掉进技术人员常见的技术至上的思维怪圈。

Ritchie 去世的消息今天公布以后，在程序员的圈子里掀起悼念的热潮，一点不逊前一阵子悼念 Jobs 的盛况。然而，在悼念 Ritchie 的过程中，总是有顺带贬低 Jobs 的声音。也难怪，对于这个圈子的很多人，包括我，Ritchie 的逝去更能触动内心，毕竟 (按网上有人的话说) “他赐予我们饭碗”。

也许还有更深的观念上的原因。把商人看作不做 “实事” 的投机分子的思想在中国由来已久。同时请复习马克思主义政治经济学：工业商品的价值是由产业工人的劳动创造的，产业资本家、商业资本家和以及商业资本家的雇佣劳动者都不创造价值。这些思想加上我们屁股决定脑袋的放大，难免得出 Jobs 什么都不算的结论。

其实，Jobs 当年也何尝不是试图通过技术上的先进来取得成功，Apple Lisa 和 NeXT 都是技术先进而失败的例子。

我没兴趣论证商业的地位，那是一个意识形态问题，这个问题也不属于我的专业。只是，对伟人们，不管哪个领域的，还是少去比较谁更伟大，更多心存敬畏吧。敬畏不是放弃自己的努力，相反使人奋进——没有比战胜自己的偶像更让人兴奋的事。哈！

[注] Vint Cerf，美国计算机科学家，与 Bob Kahn 共享 “Internet 之父” 的称号。

标签:

接上一篇

由 chys 发表于 2011 年 10 月 08 日

上一篇扯了一下现在的初一英语课本。这一篇扯一下语文 (江苏教育出版社、凤凰出版传媒集团)：

从头到尾随便翻了一遍，只有一课给我留下了印象。这一课有两篇文章，第一篇是蒲松龄的《狼》，最后两句：

禽兽之变诈几何哉？止增笑尔。

第二篇是毕淑敏的《母狼的智慧》，开篇第一句：

“仅次于人聪明的动物是狼。”

编者的意图很明显。在我的印象中，我从小到大用过的教材里，第一次编者有意把这种对同一事物作不同解读的文章放在一起的还是高中《论雷峰塔的倒掉》，课文后面附了《再论雷峰塔的倒掉》。

对了，为什么我会没事去翻初一的课本呢？因为某老师的小孩在上初一，周末和假期经常坐在我旁边的旁边的旁边的位置上做作业，有时候也就把课本、作业本之类留在这里没带回去。

标签:

随手翻了翻初中课本

由 chys 发表于 2011 年 09 月 04 日

今天无事发现一本现在的七年级英语课本（人教版），随手翻了翻，想看看跟我们当年的有什么区别。其实也没什么好写的，不过鉴于很久没更新了，凑个数。

1) 全面采用美式拼写：math, color, favorite。我们原来是到高一才有一个单元介绍了美式英语。 (现在这样子，是要以后再用一单元介绍 British English 吗？其实我看国际组织之类多数好像还是倾向于英式拼写的。)

2) 全面采用美式用法，参见下图中日期的说法，未使用定冠词。

3) 英美读音不同的词，同时标注 General American (美) 和 Received Pronunciation (英)，美音在前，英音在后。

英音的 /ɒ/ (过去常用 [ɔ] 表示这个音) 在美音中标为长音 /ɑ:/，如 not 为 /nɑ:t/，这似乎有点少见。

4) 似乎没有贯穿始终的人物了，这一代人以后不会再有类似 Li Lei 和 Han Meimei 这样的回忆。

最后，图中的这两个日期是故意的吗？

无题

由 chys 发表于 2011 年 05 月 15 日

昨天，有同学说今天下午来找我，我随手回道：“好啊，你出差吗？”

答曰：“明天再细说，到了联系你。”

顿感情况不单纯。

今天一聊，果然。

坦率地说我并不为他的决定感到惊讶，虽然还是有些出乎意料。

说不惊讶，因为他以前（N 年前，N⩾6）也表达过类似意向；再说经过某牛鬼蛇神辈出的大学的熏陶，已经 “difficult to be shocked by anything”（引用某系友的话）；再说我自己也干过让人多少有些吃惊的事情。

说出乎意料，因为我原本还是以为他在这个让无数人羡慕的职位上待几年以后，原来的理想也会渐渐被现实冲淡，但是我错了。

当然了，别人羡慕归别人羡慕，子非鱼。反正，上天保佑勇敢的人儿吧。

定律：一个人在 SNS/IM 上突然变得特别活跃或突然消失，一定是有原因的，没有无缘无故的改变。

这个定律今天再次得到了验证。

写完了回头一看，OMG，我写东西啥时候开始成这种风格了。

标签: