Posts Tagged ‘coding’

快排时间复杂度退化到 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 混合的：

标签: , ,

Terminology

由 chys 发表于 2011 年 05 月 01 日

德国人 Rudolf Bayer 在 1972 年发明了一种数据结构，将它称为 “对称二叉 B-树” (symmetric binary B-tree)，这个名称相当无聊，尤其是当有一大堆名称类似的 “B+树” “B*-树” “Bx-树” 什么时，别人除非对它非常感兴趣，时间一长很容易忘记或者混淆。

1978 年，希腊人 Γκίμπας 和美国人 Sedgewick 给 “对称二叉 B-树” 改了一个名字：“红黑树” (red-black tree)。这个名字就比较抢眼了，大概还能让人联想到《红与黑》，容易给人留下印象。

当然，Bayer 本人也不是完全不知道怎样抓人眼球的，他虽然没用 “红黑树” 这个名字，但是从一开始就是用 “红” “黑” 两种颜色而不是用 0/1 来区分两种结点。这与物理学家让夸克有味道和颜色的做法简直如出一辙。

红黑树后来的应用很广泛* 了，不好说它的名字为它的应用作了多少贡献，我想大概还是加速了这个过程的。

* 例如：红黑树是 C++ STL 中 std::set 和 std::map 的标准实现。

标签: ,

神物一件

由 chys 发表于 2011 年 01 月 16 日

可惜照得太模糊了。

好怀念 12.5 年前没有电脑，手写学习 C 语言的场景。

标签:

CSS is awesome

由 chys 发表于 2009 年 04 月 16 日

又发现 WordPress 的这个 theme 的一个 bug——如果将中文字体设为微软雅黑，顶上的标题和搜索栏的位置就会乱套。用 FireBug 查了好一阵终于发现原因：改字体后，导航栏几个浮动元素高度变得差了一两个像素，就让标题的定位差得老远。在导航栏下面插了一个空 div，属性 clear:both，就 OK 了。

CSS is awesome…

CSS is awesome
(via 1 2)

标签: , ,

C、Python 与民煮

由 chys 发表于 2009 年 03 月 22 日

受水木社区 adoal 网友言论启发，得如下类比：

  • C 语言（以及它的衍生品 C++、Java 等）是民主政!府的典范：

    它的人/民（程序员）除了丰衣足食（程序可以完成功能）以外，还拥有广泛的人/权与自|由（将代码按个人意愿任意排版和缩进的自由）。因此它的人民组成了很多不同的政/党（不同的编码风格），相互之间常常明争暗斗，浪费大量口水和资源（例如产生了专门将代码格式化成不同风格的程序：indent 和 astyle等）。

  • 而 Python 从诞生那一天开始就是一个卑|鄙的毒^豺者：

    政/府（Python 设计者）规定它的所有人~民（程序员）要穿同样的衣服吃同样的饭（严格规定程序的缩进风格，程序员没有风格上的自由度），持.不,同:政;见’者受到严厉镇压（程序无法运行）。因此避免了很多口水，人_民将全部精力放在核心建设上，思想统一，效率高上。

  • 毒~豺政!府向民,主政_府转变是大势所趋——FORTRAN 77 到 FORTRAN 90/95 的进化就是一个典型例子。但是，作为新兴的民~煮政!权，FORTRAN 90/95 统|治下的人/民拥有的自由与老牌民!主国家 C 语言相比，仍然相当有限。

还是伪基百科一语中的，鞭辟入里：所谓民煮，就是被煮的人可以选择被什么样的厨师煮。

ps. 请勿试图从本文内容推测作者对德先生的看法，您有可能得到相反的结论。

pps. 好像灌得有点多了，用阅读器的童鞋们不好意思干扰了你们视线。

标签: ,