前一篇文章最后的代码效率很差。由于使用 list 保存临时的计算结果，所有文件内容会同时读入内存，其构建的管道类似下图所示：

list 中的元素是先通过一个过滤器，存起来，再通过下一个过滤器。这样做的坏处是

1. 浪费内存
2. 浪费时间，来回的在临时 list 中进行存取需要时间，另外临时 list 的内存分配，垃圾收集都会增加时间开销

我们希望的管道其实如下：

list 中的每个元素应该一次性通过所有的 filter，只在最后存在一个 list 中。更理想的情况下，一开始的 list 也不应该出现。对于像 Haskell 这样默认使用 lazy evaluation 的语言来说，前面的函数连续调用默认行为就是如此。只有当管道末端需要一个元素时才会从管道头读取一个元素，经过所有过滤器处理以后得到结果，如果没有读取第二个元素，则管道头的其他元素根本不会被处理。

要在程序中使用管道的风格又必须要避免临时数据的产生，然而 python 中没有直接对 lazy evaluation 提供支持，好在 python 有 iterator protocol 和 generator。

先推荐一份幻灯片，David Beazley (“Python essiential reference”, PLY 的作者) 在 PyCon’2008 上报告的幻灯片，强烈推荐！！这篇文章的很多内容都来自或者受这份幻灯片的启发而来。

在上一篇文章里介绍了 Unix 管道的好处，那可不可以在写程序时也使用这样的思想呢？当然可以。看过 SICP 就知道，其实函数式编程中的 map, filter 都可以看作是管道思想的应用。但其实管道的思想不仅可以在函数式语言中使用，只要语言支持定义函数，有能够存放一组数据的数据结构，就可以使用管道的思想。

一个日志处理任务

这里直接以前面推荐的幻灯片里的例子来说明，应用场景如下：

• 某个目录及子目录下有一些 web 服务器的日志文件，日志文件名以 access-log 开头
• 日志格式如下
  

  81.107.39.38 - ... "GET /ply/ply.html HTTP/1.1" 200 97238
  81.107.39.38 - ... "GET /ply HTTP/1.1" 304 -
  

  其中最后一列数字为发送的字节数，若为 ‘-’ 则表示没有发送数据
• 目标是算出总共发送了多少字节的数据，实际上也就是要把日志记录的没一行的最后一列数值加起来

我不直接展示如何用 Unix 管道的风格来处理这个问题，而是先给出一些“不那么好”的代码，指出它们的问题，最后再展示管道风格的代码，并介绍如何使用 generator 来避免效率上的问题。想直接看管道风格的，点这里。

问题并不复杂，几个 for 循环就能搞定：

1
2
3
4
5
6
7
8
9
10

sum = 0
for path, dirlist, filelist in os.walk(top):
    for name in fnmatch.filter(filelist, "access-log*"):
        # 对子目录中的每个日志文件进行处理
        with open(name) as f:
            for line in f:
                if line[-1] == '-':
                    continue
                else:
                    sum += int(line.rsplit(None, 1)[1])

利用 os.walk 这个问题解决起来很方便，由此也可以看出 python 的 for 语句做遍历是多么的方便，不需要额外控制循环次数的变量，省去了设置初始值、更新、判断循环结束条件等工作，相比 C/C++/Java 这样的语言真是太方便了。看起来一切都很美好。然而，设想以后有了新的统计任务，比如：

1. 统计某个特定页面的访问次数
2. 处理另外的一些日志文件，日志文件名字以 error-log 开头

完成这些任务直接拿上面的代码过来改改就可以了，文件名的 pattern 改一下，处理每个文件的代码改一下。其实每次任务的处理中，找到特定名字为特定 pattern 的文件的代码是一样的，直接修改之前的代码其实就引入了重复。如果重复的代码量很大，我们很自然的会注意到。然而 python 的 for 循环实在太方便了，像这里找文件的代码一共就两行，哪怕重写一遍也不会觉得太麻烦。for 循环的方便使得我们会忽略这样简单代码的重复。然而，再怎么方便好用，for 循环无法重用，只有把它放到函数中才能进行重用。 (先考虑下是你会如何避免这里的代码的重复。下面马上出现的代码并不好，是“误导性”的代码，我会在之后再给出“更好”的代码。) 因此，我们把上面代码中不变的部分提取成一个通用的函数，可变的部分以参数的形式传入，得到下面的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

def generic_process(topdir, filepat, processfunc):
    for path, dirlist, filelist in os.walk(top):
        for name in fnmatch.filter(filelist, filepat):
            with open(name) f:
                processfunc(f)

sum = 0
# 很遗憾，python 对 closure 中的变量不能进行赋值操作，
# 因此这里只能使用全局变量
def add_count(f):
    global sum
    for line in f:
        if line[-1] == '-':
            continue
        else:
            sum += int(line.rsplit(None, 1)[1])

generic_process('logdir', 'access-log*', add_count)

看起来不变和可变的部分分开了，然而 generic_process 的设计并不好。它除了寻找文件以外还调用了日志文件处理函数，因此在其他任务中很可能就无法使用。另外 add_count 的参数必须是 file like object，因此测试时不能简单的直接使用字符串。

管道风格的程序

下面考虑用 Unix 的工具和管道我们会如何完成这个任务：

find logdir -name "access-log*" | \
xargs cat | \
grep '[^-]$' | \
awk '{ total += $NF } END { print total }'

find 根据文件名 pattern 找到文件，cat 把所有文件内容合并输出到 stdout，grep 从 stdin 读入，过滤掉行末为 ‘-’ 的行，awk 提取每行最后一列，将数值相加，最后打印出结果。（省掉 cat 是可以的，但这样一来 grep 就需要直接读文件而不是只从标准输入读。）我们可以在 python 代码中模拟这些工具，Unix 的工具通过文本来传递结果，在 python 中可以使用 list。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

def find(topdir, filepat):
    files = []
    for path, dirlist, filelist in os.walk(top):
        for name in fnmatch.filter(filelist, filepat):
            files.append(name)
    return files

 def cat(files):
    lines = []
    for file in files:
        with open(file) as f:
            for line in f:
                lines.append(line)
    return lines

 def grep(pattern, lines):
    result = []
    import re
    pat = re.compile(pattern)
    for line in lines:
        if pat.search(line):
            result.append(line)
    resurn result

lines = grep('[^-]$', cat(find('logdir', 'access-log*')))
col = (line.rsplit(None, 1)[1] for line in lines)
print sum(int(c) for c in col)

有了 find, cat, grep 这三个函数，只需要连续调用就可以像 Unix 的管道一样将这些函数组合起来。数据在管道中的变化如下图（简洁起见，过滤器直接标在箭头上 ）：

看起来现在的代码行数比最初直接用 for 循环的代码要多，但现在的代码就像 Unix 的那些小工具一样，每一个都更加可能被用到。我们可以把更多常用的 Unix 工具用 Python 来模拟，从而在 Python 代码中以 Unix 管道的风格来编写代码。

不过上面的代码性能很差，多个临时的 list 被创建。解决的办法是用 generator，因为篇幅比较长，具体做法放到下一篇文章中。

Unix 的管道实在是一个好用的东西，利用管道可以很方便的把一些简单的工具结合起来完成一些复杂的任务。这里不想解释什么是 Unix 的管道，也不举具体的例子来展示管道的方便之处，只是想通过一个现实中管道的例子来说明为什么管道是好东西，为下一篇文章写管道的思想在写程序时的应用做准备。

正如其名字暗示的，Unix 的管道其实跟现实生活中的管道非常类似。要注意的是这里讨论的管道不只是为了传送液体（或者气体），还可能对液体进行一些处理。构成管道最主要的东西其实就是一节一节管子/过滤器。液体从管道的一端流入，经过各个过滤器的处理，从另一端流出时可能已经是另外的液体了。流出什么样的液体取决于流入的液体和组成管道的过滤器，很显然决定管道功能的是构成管道的每一个过滤器。现在假设我要进行污水处理，污水里有沙子，还有各种溶解在其中的物质。我可以做一个只含一个过滤器的管道，这个过滤器可以把沙子和溶解物一次性全部过滤掉。

但如果再来一批污水，只含有沙子，那用之前的这个过滤器显然太浪费了；或者，新的污水含有原先污水中没有的溶解物，那只用原先的过滤器是不够的。比较好的做法是用一个过滤器过滤沙子，每种溶解物用一个过滤器（现实中的污水处理当然不可能这么简单，这里只是以此为例子），污水里需要过滤什么就在管道上加上什么过滤器。

这样做的好处有几个：

1. 每个过滤器做起来都比较简单，因此每个过滤器的制造成本降低了
2. 过滤器更可能被重复使用
3. 易于处理各种不同的污水，只需要重新组合下过滤器就可以了，而不需要为每种污水设计一个过滤器

Unix 的管道其实就是模仿了现实生活中的管道，只不过流经管道的是数据（多数时候是文本），构成过滤器的是 Unix 下的那些小工具。Unix 中使用管道的好处与污水处理的例子里是类似的

1. 每一个工具只完成一个很简单的任务，因此每个工具都很容易实现
2. 每个工具更有可能被用到，而工具重用的成本几乎为 0
3. 更加灵活（见下面的例子）

有些管道的用法真是让人感叹，比如现在的 Linux 版 QQ 收到消息是没有声音的，有人用 tcpdump, sed, aplay 组合自己山寨了这个功能出来。还有听小百合的 lv 说他用 mplayer,gzip, netcat 等工具做了一个视频监控系统出来。QQ 的那个例子做法如下：

sudo tcpdump -i ppp0 -l udp src port 8000 and ip[0x20]=0x17 | \
    sed -u '/.*$/s//aplay msg.wav/' | sh

前面说过，管道的功能是由过滤器决定的。光由操作系统提供一个构建管道的机制是没有什么大用处的。Unix 管道的强大关键还在于那些小工具的设计。

从一开始，那些小工具的设计就考虑到了通过管道来配合使用（我觉得应该是管道的存在影响了这些工具的设计，而不是反过来，不知道 Unix 的历史是否的确如此），因此这些工具有几个显著的特点

1. 功能简单，有的工具简单到单独看觉得根本就没什么用
2. 以文本作为交互的数据，人能读，程序也能读
3. 功能上尽可能正交，每个工具完成自己的任务，不跟其他工具的功能重复（awk,sed 这样的程序功能上还是有些重复的，当然有时候一件事情能用多种方式完成也是好事。）

软件开发的成本与其复杂度不是线性关系，再加上每个工具都得到了更多的重用，组合起来还可以实现新的功能，考虑到这几点，使用管道可以节省的系统工具开发成本就不是一点点了。当然，光节省成本而不好用那也没意义，但事实是管道很有用。

每个工具都只执行简单的任务也有一点麻烦，一些相对简单的任务也可能需要调用好几个工具，此时可以把常用的命令组合可以存到脚本里。这就相当于把管道存起来，以后直接用这个管道而不用再重新把过滤器搭起来了。另一个方面是用户需要花相对来说比较多的时间来学习这些工具，对于经常要使用电脑的人来说，考虑下学习这些工具以后能得到的收益，花些时间是完全值得的。（对那些偶尔使用的人来说可能就不划算了。）

关于管道和 Unix 的设计哲学，在 Eric S. Raymond 的 “The Art of UNIX Programming” 中有着更多的介绍。（该死的 GFW 把 Raymond 的主页都墙了。）

Unix 管道的好处我们已经看到了，那可不可以在写程序时也使用这样的思想呢？当然可以！下一篇文章我就要谈在程序中如何使用管道的思想。以 Python 为例，介绍 generator，还有为什么 lazy evaluation 也是好东西 :)

10 月份的时候原来的域名过期了，没联系上数字游牧计划的人续费，于是打算自己买域名和虚拟主机。联系了几个同学一起买了个虚拟主机。

在 abcx 的推荐下到 godaddy 买了域名。淘宝上有卖 godaddy 的 e-gift card，这样就不需要能支付美元的信用卡就可以直接从 godaddy 的域名了，很方便。遗憾的是 godaddy 没有 .name 域名的注册，看到 .info 一年才 $0.99，于是就改注了一个 .info 的域名。放弃原来的域名还是有点遗憾，不过为了找一个国外的域名注册商而且要足够方便的话也只好这样了。

主机是麻烦 abcx 买的，购买流程就不清楚了。搞定的时候已经是 12 月，学期的最后一个月，各种作业、老板的任务、准备考试导致没有时间更新博客，只是把数据导了过来。在学校上外网要用代理，ssh 连不了外网，所以到考完试的时候也还是懒得去弄了。

就这样一直拖到昨天回家，终于可以把博客再弄起来了。

可怜我在南大浦口待了四年，没有见过计算机系的老教授徐家福先生（唉，孙钟秀先生也没有见过），今天在复旦因徐先生来讲座而得见！

讲座题目是“量子程序设计语言初探”，跟语言相关的东西我都有兴趣，更何况我也想见见徐先生真人。原来还在纠结要不要跷课去听徐先生讲座，结果睡过上课时间，于是有了名不正言不顺跷课去听讲座的理由。而施伯乐老师把原先上课的学生都叫来听讲座了，于是我这次跷课就算是得到了施老师的支持 :)

第一眼见到徐先生还是有点吓到了。虽然知道徐先生 1925 年 11 月生到现在已经是 82 岁高龄，但见到的时候还是担心他的身体状况还能不能给我们做讲座。先生开始讲座时才知道他刚去了 5 天东北，有点感冒，所以喉咙不是很好。这下自然更是担心了。

不过正式开始讲座以后发现这些担心其实还是多余的。先生虽然年级大，但是思路清晰，上来就说明今天讲座的内容，讲多少时间，然后就照着开始的介绍一路讲下来，讲完一段就进行回顾，不会有听着听着不知道讲到哪里的情况。大学里多数老师如果能像徐先生一样上课的话就是学生的福气了。徐先生解释问题简明扼要，定义的阐述也是精确到位，经常援引名家原话典故。没有记错的话他在 45 年去中央大学读书之前在复旦学英语（所以也算是复旦的校友），徐先生的英文不错，讲座时经常提醒我们有些容易读错重音的单词的发音。讲座唯一不足的还是徐先生的声音不够大，当然讲座教室没有准备扩音器实在失败。可能是为了考虑到坐后排的同学听不清，徐先生讲座时前后走动，虽然声音不太大，但是至少教室前半部分的人应该都能听到先生说话。80 多岁高龄的教授讲座依然不坐着，光这一点就令人感动了。

从徐先生身上能够看到什么是治学严谨，而如此高龄仍然做科研更是难得。徐先生说他也是在五年前才开始涉及量子程序设计语言领域，为此专门学了一年的量子力学。实在是佩服徐先生在 77 岁还去学一门没有接触过的学科的精神，我自己是对现在要学一点生物方面的东西就已经叫苦叫累还有点不太情愿，对比之下自然是很惭愧。

讲座中徐先生提到的一点有点令人无奈。中科大做量子计算机有了一点成果了，徐先生去看时发现他们的计算机要进行新的计算时要手工调整输入设备（类似最初使用打卡机编程的计算机），于是问他们能不能把这一步自动化。做这项工作的博士研究生说理论上可行，没有实际做一方面是因为没有大量经费支持，另一方面他们的主要任务不在这里，而是在把量子算法在量子计算机上实现出来，这样才能发出论文。徐先生对此的评论是做研究不应该是为了发论文，而应该是为了是对自然、社会做探索，等研究工作做好了，论文自然就出来了。话是没错，但现在的体制逼得人为论文而战，水文、没有意义的所谓研究工作大量存在。徐先生现在的身份恐怕是难以体会到发论文的压力了，他做研究是可以完全为了对自然、社会做探索，然而他如果还带学生的话，他的学生还是要为论文而战的。

（想起了钟扬老师讲过的 Bardeen, Cooper, Schrieffer 的故事。Bardeen 56 年第一次得了诺贝尔奖后找学生，给每个学生几个问题随便他选哪个做。Schrieffer 拿到这些题目后给他的老师看，他老师说这些题目随便哪个做出来差不多都能得诺贝尔奖。他原先不建议 Schrieffer 做 Bardeen 的学生，因为做那样的问题很可能读了几年之后没有出结果最后都毕不了业。（话说 Bardeen 第一个诺贝尔奖工程性质比较浓，他一直想搞个理论方面的东西再来证明下自己，他可以不管学生能不能毕业。）在知道 Schrieffer 当时还只是 26 岁的时候老师才让他还是去 Bardeen 那里试试吧，说大不了就是浪费这几年时间，反正你还年轻。好在 Schrieffer 也是够聪明的人，57 年开始做 Bardeen 学生以后真的解决了一个问题，结果 72 年的时候他们三人同时获得了诺贝尔物理学奖。做牛人的学生，自己不够了得就得有毕不了业的觉悟；要是自己也够牛，那样大家都好。）

讲座结束的时候连着问了徐先生几个关于函数式设计语言的问题，也算是跟徐先生讲过话了。在南大时留下的遗憾，今天算是弥补了一个 :)

介绍

有了 rebuild_db，你可以基本上像使用普通 mp3 播放器一样来使用 shuffle，不再需要 iTunes 那样臃肿的程序。需要注意的它只适用于 1/2 代的 shuffle，是否支持 3 代我没有测试过。可以用于其他 iPod 的类似程序叫 reTune，不过 sourceforge 上的页面貌似挂了。

rebuild_db 说白了就是用一个 Python 程序扫描 shuffle 中的 mp3 文件，然后更新 shuffle 的数据库使得 shuffle 可以找到并播放这些文件。

安装

到这里下载，解压后把 rebuild_db.py 文件拷贝到 shuffle 根目录下就 OK 了。当然你的系统上得有 Python 才能用该程序。

shuffle 的初始化还是只能用 iTunes，这里是我的 2 代 shuffle 初始化后 iPod_Control 的备份，没有 iTunes 而数据库坏了的人可以拿去试试看，下载以后解压到 shuffle 根目录就应该可以了。

添加音乐

想要向 shuffle 添加音乐时只需比普通 mp3 播放器多一步：

1. 把音乐文件直接拷贝到 shuffle 的任意位置。
2. 在 shuffle 根目录下运行 rebuild_db.py 程序。
3. 解除挂载并且 eject 设备。

建立数据库时程序对文件名的排列不是简单的字典序，对数字的话会根据其数值大小进行排序，这样就避免了 10 出现在 2 之前的情况了。

另外 rebuild_db.py 可以使用一些参数。我觉得重要的有 -r 重新命名文件，这样可以避免中文文件名可能造成的问题。（不过我的文件名都是英文的，所以不知道是不是中文一定会出问题。）

后记

以下可以略过，很多无关紧要而且杂乱的小事而已。

写这个软件的作者不知道是怎么知道 shuffle 的数据库格式的，看了下 iTunes 目录下的文件都是二进制的。

以前给 shuffle 导 mp3 都是用 amarok。amarok 有两个缺点，一是启动慢，而是同步文件多的时候非常慢，不仅传文件慢，刷新数据库也慢。所以上次尝试了下 gtkpod。gtkpod 实在有点糟糕，UI 不好还不去说它，关键是同步的时候总是莫名的死掉，最后 shuffle 的数据库坏了，没法用了。我没 Windows 机器，就算有也懒得装 iTunes，所以想搜搜在 Linux 下修复 shuffle 的办法。修复的办法没有找到，搜到了 rebuild_db，而数据库是找了实验室的本科生 DD 修复的。然后对修复后的 iPod_Control 作了个备份，以后再坏就不用麻烦别人了。

最近败了个拜亚动力的 DT231 Galactic 耳机，最初的动机是实验室的机器 Think Center 的耳机接口在机箱后面，买长线耳机才行，二来是 shuffle 原配耳塞的橡胶老化了，被我扯掉了，第三是硬凑上来的，冬天当耳罩用。

看网上 N 多人说该耳机灵敏度低，用 mp3 难推。我现在就接在 shuffle 上用，音量稍微开大点就成了，没觉得有什么推不动的。要说推不好么我就不知道了，反正听协奏曲什么的气势比原配的耳塞大多了。第一次花这么多钱买一个耳机，对我来说总体效果也不错，银子没有白花。

很想去听 Hilary Hahn 10.19 上海演奏会，可惜复旦的票务西施 MM 没有弄到 90 元的学生票，280 的我可消受不起。省下的 90 块钱打算买 CD 去了。听了这么多音乐，总该多支持下唱片产业了。

很奇怪，本科毕业以后到现在没有多少话题冒出来让我想写东西。

暑假开始时看 Algorithms，书很有趣，讲解清晰，强烈推荐以这本书作为算法的入门教材。这本书让我对算法产生了兴趣，做习题的时候觉得有些收获，但这些收获太小，肯定不值得写出来。

暑假快结束的时候觉得无聊，就开始学 Haskell，觉得这是我见过最为优雅的语言。是的，虽然没有 Lisp 的 read/eval 这样令人赞叹的东西，但 Haskell 更加符合 lambda 演算，所以更为 consistent。个人觉得 Common Lisp 很多地方看起来很丑陋，而且为了利用现有的类库总是需要付出不少努力；而 Scheme 虽然更优雅，但太多的实现真让人无法适从。我没有怎么写过 Lisp 宏，没有很好的理解它，因此使用 s-expression 带来的最大好处我没体会到，反倒是觉得 Lisp 没有语法带来的是相对糟糕的可读性和冗长的代码，至少与 Haskell/Python/Ruby 相比。我觉得使用语法来简化代码，提高可读性是很重要的，Lisp 或许在这方面有最大的潜力，因为你可以针对特定问题构建特定的宏，但前提是你必须知道如何构造这些宏。花更多的时间或许可以获得这样的能力，但对 Lisp 现有实现和可以使用的类库的失望让我放弃了，特别在看到 Haskell 之后。HaskellWiki 上有 project euler 的解答代码，很多次看到别人写的简洁优雅的代码时激动的想写篇题目为 The beauty of Haskell 的文章，却发现自己没法写出那样的代码，也还没有水平能够写出对得起这样题目的文章，于是作罢。（Haskell 也可以写出丑陋的代码，但是用 Haskell 写丑陋的代码会非常痛苦，而且看到别人优雅的代码会刺激你也想写出漂亮的代码来，可惜我的脑子还没转过来，写个简单的程序还要想好久才能开始编码。）

开学以后比较忙，自己想做的事很多又只能停下来。研究方向定为生物信息学，得自学生物方面的一些知识，上数据挖掘和模式识别的时候发现要补习线代和概率统计（大四就想重学这两门课，可惜太懒），还要不少论文要看。估计以后只有零碎的时间能写文章，也不知道会不会像本科时经常遇到有意思的东西。

不过还是要坚持把博客写下去。最初写博客好像写了不少 Linux tips 之类的文章，这个写起来比较快，而且最近因为经常在宿舍登录实验室的机器，还有使用校园网的资源，学到了一些东西，所以最近准备写一些积累到的小 tips。The beauty of Haskell 会作为长期的目标。其他写什么就到时候看了，总之要努力成为一个好的 blogger。

CLRS 上对 Red-Black Tree (RBT) 的介绍简直是一团乱麻，代码又乱，解释又罗嗦，我完全没有实现它的兴趣……

不得不佩服 Robert Sedgewick 啊，他在 Algorithms in C 里先介绍 2-3-4 Tree，把 RBT 作为 2-3-4 Tree 的一种表示方式来介绍 RBT，这样就清楚多了。当然，Sedgewick 本来就是 Red-Black Tree 的发明者之一，他能够讲清楚也就不奇怪了。除了解释清楚以外，Sedgewick 使用递归实现，因此代码很简洁，看起来很舒服。

不过即使如此，Red-Black Tree 还是很复杂，所以即使看了 Sedgewick 的代码以后还是没有自己实现的冲动。好在 Sedgewick 已经考虑过这个问题，其结果就是 Left-Leaning Red-Black Tree。（这份幻灯片做得非常好！Apple 的 Keynote 貌似不错啊。）LLRBT 跟 RBT 的不同之处在于 2-3-4 Tree 的 3-node 在 LLRBT 中只有一种表示方式，因此 LLRBT 减少了 RBT 的插入/删除需要处理的情况数量，从而大大减小了复杂度。RBT 的 Java 迭代实现要用 150 行代码，而递归实现需要 46 行代码，LLRBT 递归则只需要 33 行。删除需要的代码行数也大大减小了，实现难度当然也大大降低了。

我用 Common Lisp 试着实现了 LLRBT，确实很简单。不过我还在想怎样才能迭代实现 LLRBT，找到了 FreeBSD 用头文件实现的 LLRBT，被彻底雷到了，这宏用的太牛了！

Update: 其实 LLRBT 是在好几个月前看到的，最近才想到写出来。FreeBSD 中 LLRBT 实现的作者 Jason Evans 写过一篇文章 ”Left-leaning red-black trees are hard to implement“，不过他写文章时候使用的算法中 4-node 对应 RBT 中向左倾斜的 3 个节点，可能因此比较难以实现。Sedgewick 在后来的幻灯片中更新了算法，4-node 变为平衡的三个节点。Evans 还比较了 LLRBT 和其他树实现的性能，在文章的注释中也提到了他将算法改为迭代所采用的办法。

很久没有更新博客了。做毕设的时候是没时间，做完以后是没了动力。六月马上就要过去了，再不写点这个月就没有文章了。

这次就偷个懒，发一份去年在 Linux 程序设计课上做演讲时所做的幻灯片吧，点这里下载。内容是关于 Unicode 和国际化的。制作这份幻灯片时参考了 Tim Bray 的几篇文章，UTF-8/UTF-16 的 RFC 文档，还有 Arnold Robbins 的 ”Linux Programming by Exmaple“。主要内容有：

• 国际化的相关概念
• 字符集、字符集编码、语言等概念的澄清
• 使用标准 C 的 wchar_t 和 locale 来解决国际化问题
• Unicode 的历史，一些基本概念。如 Unicode 和 ISO 10646 的关系，Unicode 的划分。
• UTF-16, UTF-8 的编码方法，各自优点和缺点
• gettext 的使用

最早开始接触编码的问题是自己写文本编辑器的时候，为了支持中文才去了解这方面的知识。这份幻灯片准备的还是蛮用心的，花了一个多星期的时间。准备这份幻灯片的时候对编码之类的问题算是搞的比较清楚了，自己写的文本编辑器支持 UTF-8 编码了，后来碰到数据库链接、网页乱码之类的问题都可以猜出问题大概出在什么地方，看别人的解决办法也不会觉得不明不白。Unicode 的知识对于写程序来说还是很重要的，可惜老师不会讲这种东西（或许有些老师自己也不是很明白），只好自己花时间去弄明白了。希望这份幻灯片能给希望了解 Unicode 和国际化的人提供一些帮助。请原谅，幻灯片里中英混杂比较厉害。

PS：

毕业快一个星期了，不过最近还在南京待着。出去转了几个学校，除了南农以外，其他从中央大学分出去的学校都去逛了一下。南师的随园很不错，不过还是更喜欢金陵大学的北大楼。看过东南以后觉得当初南大把中央大学的四牌楼校区留给工学院，文理学院搬去金陵大学也不是太遗憾。不知当初设计出金陵大学北大楼的是何许人也，实在是佩服！唯一的遗憾是北大楼后面现在出现了两座高楼，大煞风景，真是可惜！

南大、东南、南师的老校区进校门都是非常相似的，都是两排高大的梧桐树，南林、河海的校区也有不少的梧桐。要说我对这几个学校校园环境的喜欢程度，南大为首，南师其次，东南和南林（学校里有不少漂亮的树林）并列第三，河海虽然为末，但也不错。

论文准备了两个星期，修改了好几次，今天终于答辩了。

记得去年查师兄答辩时穿的是红色 T 恤，今天我也特意选了红色的 T 恤，不过答辩的房间是 625 而不是 614。回想去年答辩时自己只是听众，而今天自己要作为答辩人，不由感慨时间过得真是快。

8:30 答辩开始。毕设是关于访问控制机制里的安全模型的设计和实现，这种东西 10 几分钟要想讲清没那么容易，而我为答辩做的准备也不是太充分，讲的时候感觉有点乱。感觉讲的有点挫，演示虽然很顺利，但是因为毕设的主要工作是在内核里，能看到的效果也就是 root 用户的权限被限制了，还有我们的访问控制机制确实是生效了。答辩的老师对访问控制之类的东西可能也不是很熟，没有问我什么太技术性的问题，问到的问题都轻松回答了。没想到就这么结束了，比我想像的要失败一些……

同时答辩的同学全部答辩结束以后老师讨论结果。等待的时候有那么一点点担心因为答辩时失败的表现而出岔子，不过公布结果时论文被刘嘉老师表扬为是这两年里本科一辩论文中他看到的最好的，听到这个称赞还是很开心的，不过也有点心虚。刘老师欠我的一件 IBM 的纪念 T 恤就此也不打算去追着要了，说不定他也记得这事，所以就故意表扬我一下，让我不再追究。

本科学业到今天就结束了，距离离校还有 20 多天。想起来下个星期还有一次小提琴课，这样算的话学业也还没有结束。然而总还是会要离开的，要好好珍惜最后这段日子了。