今天谈下技术。介绍一个蛮有趣的数据结构 Ternary Search Tree，我毕设里的关键代码就依赖于这个数据结构。

这个数据结构的思路 1960 年左右就有了，不过其实际使用价值一直被忽略了。Jon Bentley 和 Robert Sedgewick 在 1997 年发表的论文 Fast Algorithms for Sorting and Searching Strings 中利用这个数据结构实现了针对字符串的快速排序和查找算法，网页上除了论文以外还有实现和测试代码。后来他们又专门针对 Ternary Search Tree 发表了一篇文章，Dr. Dobb 上有在线版本。我是在 Robert Sedgewick 的《Algorithms in C, 3rd edition》中 Radix Search Tree 这一章看到这个数据结构的，这本书将 multi-way branching tries 和 TST 放在一起进行介绍，把 TST 作为 multi-way branching tries 的另一种表现形式来看待，另外也将 TST 和 digital search tries 进行了比较。这里只是对这个数据结构进行概述，详细内容还是看作者的论文去。

Ternary Search Tree 的主要应用场景如下：字符串作为 key，每个字符串的长度不定，需要一种支持动态集合操作的数据结构以便能够快速的通过 key 查找到其对应的 value。用 hash table 的话可以做到快速的搜索，但是有两个缺点，一是随着保存的字符串的增多，需要重新构建 hash table 以保证快速的查找，二是 hash table 中不维护 key 之间的顺序关系。使用平衡 Binary Search Tree (BST) 两个问题都能解决，但是查找的速度相对 hash table 变慢了。如果使用 digital search trie 的话查找虽然非常快，但是需要的内存空间太大。

Ternary Search Tree 结合了 BST 和 trie 两者的优点，利用它还可以很容易的实现 partial-match searching, near-neighbor searching 这样的字符串搜索操作。而且 TST 本身非常简单，实现起来也很容易。与 BST 相比，TST 中每个节点存放的不是整个 key，而只是 key 中的一个字符。而对 tries，只需要进行一点小的修改就得到了 TST。（用 trie 描述起来比较方便，如果不知道 tries 的话可以先看下 trie 是什么。）

1. 把 tries 中的每个节点保存的 bit 换成一个字符
2. 和 tries 一样，数据都保存在叶子节点
3. tries 中每个节点最多有两个子节点，TST 有三个，分别称为 left, mid, right

插入 key 的时候，从树根作为当前节点开始（树为空的时候树根为 nil），一个字符一个字符的递归执行下面过程。

1. 如果当前节点为 nil，则创建一个新的节点，将当前字符保存在节点中，将其设置为当前节点。
2. 如果当前字符和当前节点保存的字符都为 ‘\0’，将数据存于当前节点，终止调用。
3. 如果当前字符小于当前节点保存的字符，那么递归将当前字符插入节点的 left 子节点，大于则插入 right 子节点；相等则将下一个字符插入当前节点的 mid 子节点。

搜索的过程和插入类似，把 key 一个字符一个字符的和树中节点保存的字符进行比较，同样从树根开始递归执行。

1. 如果当前节点为 nil，则查找失败。
2. 如果当前字符比节点中的小，递归对 left 子节点查找，依然比较当前字符。
3. 如果当前字符比节点中的大，递归对 right 子节点查找，依然比较当前字符。
4. 如果当前字符与节点中的相等且都为 ‘\0’，则这个节点中就存着 key 对应的 value，终止调用。如果相等但是不是 ‘\0’，则递归对 mid 子节点查找，比较字符为下一个字符。

对 TST 性能的最坏情况分析在 “The Analysis of Hybrid Trie Structures” 这篇论文中，不过这篇论文下不到。对失败的查找，字符比较次数往往远小于其中包含的字符个数。使用 hash table 的话仅计算 hash 值就需要访问 key 中的所有字符（比如这里的 string hashing function），而且得到 hash value 之后还得检查 search key 与实际保存的 key 是否相等。所以 TST 的不成功的搜索比 hash table 更快。

论文的两位作者提供的 C 源代码里给出了迭代的插入和搜索的实现。对插入还作了优化，通过预先分配内存池的办法避免了内存分配成为性能瓶颈。对于数据的保存使用了一点 hack，通过 type cast 直接用叶节点的 mid 指针保存 value。因为 char 默认为 unsigned (至少 gcc 如此)，所以保存 ‘\0’ 的节点的 mid 和 left 肯定不会指向节点（right 节点可能指向树的节点），所以可以利用他们来保存 value。示例代码直接将 key 保存在叶节点中，但实际上 key 保不保存都没关系，除非以后要用到。对示例代码还有一点要说明的是递归版本和迭代版本有一点小差别，递归版本在实现遇到相同的 key 的时候会将新 value 的存入，而迭代的版本则不会。

对于 partial-match search, near-neighbor search 我就不罗嗦了，论文作者肯定比我说的清楚多了。我毕设里面使用的 search 也是标准 search 的一个小变种。我的 TST 中的 key 是文件系统的路径（假设文件系统用 UTF-8 编码，所以树的节点存放 char 就 OK 了），给定一个 search key (path)，如果 TST 中存有 search path 的祖先目录，我希望能够找到与之距离最近的祖先目录。用 TST 来实现这个操作也是非常容易的，有兴趣的可以自己想一下 :–)

TST 也有可以改进的地方。插入过程中，往往到了末尾的字符的时候树种的每一个节点都只有一个 mid 字节点，也就是所谓的 one-way branching，这导致了使用多余的空间，而且对于成功的搜索速度也不一定是最优的。一种改进办法是在接近字符串的尾部使用 multi-way branching 来减少需要的 node，不过怎样确定在什么地方开始 multi-way branching 比较麻烦，而且还要处理多种节点类型的情况。另一种方法是使用 PATRICIA 的思想，在每个节点上再存一个索引，表示其存放的字符是 key 中的第几个字符，比较的时候直接将其与 key 中的特定字符进行比较而不是一个一个的往下比较。这样一来减少了使用的节点，二来对成功的查找，如果保存着的两个 key 之间有几个连续的相同字符就可以跳过这些字符，直接跳到能够区分出这两个不同字符串的字符位置。但这样要求树中也保存 key，在找到节点之后还不要比较一下 search key 和 TST 中保存的 key 是否相同才能决定是否是成功的查找。

发现描述数据结构算法之类的东西还是挺麻烦的，看别人的文章的时候不觉得，自己写的时候就发现难了，也不知道写的能不能让人明白了。欢迎提出建议 :–)

毕设告一段落，可以放心写博客了。这次我也做回标题党，主要内容其实是介绍我昨天看的一本书的 :–)

昨天去图书馆，在音乐的一个书柜上找到这本书，《古典音乐欣赏入门》，作者刘一贯，他在大学里讲授古典音乐欣赏，又很崇拜爱因斯坦，说要像爱因斯坦一样教音乐，书里还有一张爱因斯坦拉小提琴的照片。由此产生兴趣，看过之后才知道爱因斯坦不仅是古典音乐爱好者，他本人还会演奏小提琴（没有记错的话李四光也会拉小提琴），有时还和鲁宾斯坦合作演奏室内乐。铃木镇一的《莫扎特教育风暴》中有一篇文章，《爱因斯坦的小提琴》，此文介绍了铃木本人在德国时在小提琴学习上受到爱因斯坦鼓励，也讲述了爱因斯坦童年学习小提琴的经历。（铃木是日本著名的小提琴教育家。）

爱因斯坦教别人欣赏古典音乐的方法就是让人听录音，从巴赫的作品开始，但是不对作品做什么讲解，就是让人多听，用直觉去感受。（在巴赫逝世 200 周年时代表美国科学界邀请卡萨尔斯到美国举办音乐会的就是爱因斯坦，或许爱因斯坦还是个巴赫迷。）书上摘录了爱因斯坦对科学和艺术关系的一段精彩的评论：

当我们作为自由的人对世界进行观察、探索和赞美的时候，我们就进入了艺术和科学的领域。 如果把见闻感受用逻辑的语言表达出来，所从事的就是科学。如果其表达形式不能被理智接受，而只能凭直觉领悟，所从事的就是艺术。 两者有一个共同之处，就是对于超越个人利害关系事物的热爱和献身精神。

想起了 Knuth 对科学和艺术的评论，当我们能够将原先只能靠直觉感受的事物用逻辑语言（数学）描述的时候，科学就得到了进步。牛人们对科学和艺术的见解真是精辟，听来让人激动！

作者说像爱因斯坦一样教古典音乐其实就是要让学生多听，而不多做讲解，靠直觉去感受。作曲家的表达媒介就是音乐。有一种音乐体裁叫无词曲，李斯特对它的解释是文字不能表达他想表达的东西，为了避免听众被误导干脆就去掉文字。音乐和其他艺术相比最大特点是它是与时间紧密相关的，乐谱描述的是从音乐开始到结束这段时间内每一个时间点上应该发出什么样的声音，这构成了旋律，它是音乐的灵魂。而古典音乐的一个特点是耐听，一首曲子听过很多遍都不会厌。作者觉得有时候自己喜欢一首曲子部分是因为熟悉，所以通过多听记住一首曲子的旋律，慢慢的就会喜欢上它。听古典音乐的时候遇到自己不喜欢的曲子先跳过好了，没有关系，没必要觉得自己不喜欢是因为听不懂。那些说自己懂一首曲子的人往往是过分自信自己对音乐理解的人。

作为“非专业”入门级古典爱好者，作者的这些看法我挺赞同的。我觉得对理解音乐有意义的解说可能只有作品的创作背景，通过这些背景可以了解作曲家创作时的心情，从而推测出他想在音乐中表达的感情。我觉得即使忽略这些也没关系，自己喜欢就行了，当然这些背景当成八卦来看也挺有意思的。比如有些求爱的曲子之类是为谁创作的，创作以后作曲家有没有把 MM 追到:–) 更何况有些幻想曲、或者炫技的曲子就是灵感来了而做的，也没有什么创作背景可谈，作曲家自己都可能不一定说的清想表达什么。书里面介绍了一些作曲家和演奏家的生平，其中有一些东西可以当八卦来看。

仅仅靠听当然也有不足，比如只靠听的话很可能永远都明白不了作品名字前的什么 A 小调之类的东西是什么意思。（曲式，体裁之类的东西靠听到还是能够自己领悟出来的。）因此书中还介绍了一些乐理方面的基础知识，而这些乐理知识也可以认为是描述音乐的逻辑的语言，使得我们可以系统化的去理解古典音乐。学乐理最好的方法很可能是先去学下钢琴，小时候学电子琴的时候老师跟我讲过一些乐理方面的东西，可惜差不多都忘了。这本书上给了一个钢琴键盘图，通过它来讲解还是很清楚的。书中介绍了音程、音数、度数的概念，它们之间的区别和联系，音程与听觉协和度的关系。还有用五度相生、十二平均律来选择基本音级，调式等基础乐理知识。这些描述都是用的“逻辑的语言”，不少乐理方面的东西在我看来像是数学小游戏。（之前看到 Solidot 上说微软在开发自动生成伴奏的软件，开发这东西的人应该需要不少乐理方面的东西，比如和弦和声什么的。要是我也能去的话就好了，想必那里会有一堆古典音乐的 CD，还可以假借研究之名欣赏古典音乐，妙哉！）

乐理方面只说一个魔鬼音程吧，其实更有意思的是五度相生和十二平均律，但描述起来比较复杂，有兴趣的人可以自己搜下，或者等我以后再写 :–) 魔鬼音程东西跟 sqrt(2) 有关。音程指的是先后或同时发出的两个音之间的结合，表示音高的差别，但是注意决定协和程度的不是音高的差，而是两个音频率的比值，因此音程描述的是音高的比值。完全协和两个音的频率比值是 1:2 （也就是八度的差别），次之的是 2:3。小整数比值的音程听起来会比较协和。钢琴上最不协和（也许听起来并不是最不协和的，但很可能是最难唱准的）的音程的音高比值无法用整数描述，是 1:sqrt(2)，也被称为魔鬼音程。看来人们天生还是喜欢整数更多一些啊。

我开始欣赏古典音乐也是到了大学，作者是从 25 岁开始，看到这里也就不觉得自己起步晚了。小时候看过中央电视台的一期节目，介绍了小提琴和三种名琴的历史，那期节目里放了不少维瓦尔第的四季的录音，有吕思清用一把名琴演奏的版本。对这期节目印象很深。从此喜欢上维瓦尔第的四季，也逐渐喜欢上了小提琴和古典，或许也是这期节目让我在大学里产生兴趣并鼓起勇气去学小提琴。喜欢古典导致的一点遗憾是现在从来不听流行音乐了，每次有人拉我去 K歌都只能沉默，最多只能唱几首高中时会唱的。

作者推荐欣赏古典从一些简单的小品开始，他最喜欢的是卡萨尔斯的巴赫大提琴小品，另外他还推荐莫扎特的一些小品。作者自己收藏有上千张的 CD，书中推荐了非常之多的古典名作，我就准备拿着上面的曲目单子来扫盲了。（巴赫的大提琴组曲多亏了卡萨尔斯才被世人认识，也使得大提琴作为独奏乐器得到了重视。他 13 岁看到这部作品，25 岁第一次登台演奏其中的一首作品，到 35 岁才给整部作品作了录音。卡本人还有不少传奇的故事。）除了维瓦尔第以外，我听古典音乐也是从巴赫和莫扎特开始的，不过是直接从听协奏曲开始的。贝多芬的作品要到一定的时候才会喜欢吧，并不适合入门。欣赏古典是一条漫长而有趣的道路，我只是刚踏上愉快的旅程而已，所以对于推荐什么没有什么好说的。

爱因斯坦认为对音乐的欣赏没有影响他的科学研究，反而是帮助了他，甚至于在他的自传中写到：“我一生的事业得益于童年时期的音乐训练。”我童年时也有过一点音乐训练，很遗憾的是父亲恨铁不成钢的方式使我一直疲于应付甚至抵触，最终没有坚持下去。但即使这样，还是要感谢父母让我能够在小时候接触到乐器，小时候的经历对我现在学习小提琴还是有帮助的。看到爱因斯坦的故事以后，我更加希望能够坚持把小提琴练下去，争取早日可以拉出动听的旋律来 :–)

最后贴几个视频。第一个是前几天在土豆上看到的罗斯特罗波维奇演奏的巴赫无伴奏大提琴组曲中的前奏曲，给人很静谧的感觉。第二个是 Hilary Hahn（美女！）的访谈，其中有 Bach 的 A 小调小提琴协奏曲第一乐章的录音。第三个是穆特演奏的莫扎特降 B 小调第一小提琴协奏曲，分了好多段，我觉得不错，贴一个第一乐章的。（不过莫扎特的五首小提琴协奏曲里最受欢迎的貌似是第三协奏曲。穆特阿姨当年也挺漂亮的。）

最早在 youtube 的 MIT sketching 这个视频上看到过这种东西，利用这种程序，你可以利用计算机画出一些东西，比如小车，链条，弹簧之类的，随意放置在不同的位置，然后它可以自动演示在有重力等作用你所画的物体将如何运动。slodit 上之前有提到过一个这样的游戏，Crayon Physics Deluxe，不过可惜的是只有 Windows 版的。

这次 solidot 提到的 Phun 是瑞典的一个学生开发的类似的程序，同时提供 Linux, Mac(即将推出) 和 Windows 版本。试了下，蛮有意思的。

最近让我堕落的源头就是这部电视剧了—-《交响情人梦》。以前同学在看的时候因为觉得里面的小提琴演奏的动作比较假，就没有注意它。在复旦的时候有同学觉得这部电视剧不错，正好最近我也需要些娱乐的东西，于是就决定看这部电视剧了。没有让我失望，反倒是如果坚持最初的偏见而不看这部电视剧会是不小的损失。

总得来说属于搞笑类的电视剧，看起来很轻松。没有太多的注意剧情，因为音乐吸引了我多数的注意力。包含很多的古典名曲，莫扎特、贝多芬、肖邦、舒伯特、舒曼、勃拉姆斯等人的作品都有涉及，有不少作曲家我以前没有怎么听说过。作品的形式也很全，奏鸣曲、协奏曲、交响曲都有了。豆瓣上有电视剧中出现的所有曲子的列表，全听下来可不是件容易的事。

看过以后也长了不少音乐方面的知识，比如管弦乐团小提琴首席的重要性，指挥究的作用等等。有些作品出现时会通过某个角色来介绍作曲家和创作背景，演奏时有时会加上一些解说，这样对乐曲会有更好的理解。以前听古典音乐的范围很狭窄，基本只听小提琴协奏曲，而且只局限于莫扎特，维瓦尔第，巴赫这几位作曲家的作品，看这部电视剧的时候喜欢上了不少钢琴曲，比如肖邦的幻想即兴曲，莫扎特的双钢琴奏鸣曲，拉赫曼尼诺夫的第二钢琴协奏曲。我都有点后悔还是应该学钢琴了，钢琴不愧是乐器之王，独奏都能有管弦乐队的气势。小提琴在独奏上还是比不上钢琴，而我这种半路出家的又不可能进乐队去。现在对交响乐也渐渐能够接受了。这部电视剧里面还有很多我喜欢的曲子，有不少都是以前没有听过的。日本有推出这部电视剧中古典音乐合集的 CD，可惜国内没有，只好做不道德的事情了……这两天 iPod 几乎一直随身带着，不少曲子听多了以后轮流在脑中出现，感觉很幸福。

非常推荐这部电视剧，相信很多人看过以后都会开始喜欢上甚至迷上古典的，至少也会对古典产生兴趣 :–)

还是从我在 Ruby 和 Python 上的经历说起吧。

大二暑假的时候学了 Ruby，但是到现在为止只用 Ruby 做过文本处理，还有一次做 Linux 网络编程作业的时候用 Ruby 实现了一个服务器的原型，还稍微尝试过一下 RoR，不过因为我对 Web 开发没什么兴趣，所以是浅尝辄止而已。平时自己机器上能够用到的 Ruby 程序也只有 deplate 而已。

今年寒假的时候开始考虑毕设的事情，考虑实现语言的时候也曾考虑过 Ruby。但是我要用的 dazuko 的 Ruby 绑定可能存在内存泄漏的问题，引起内存泄漏的原因应该在 Ruby 的实现上。考虑到 Python 的实现更成熟，对于要求稳定的系统程序来说可能更为合适而开始考虑 Python。于是开始看 Dive Into Python，被这本书吸引而继续学下去。我之前的介绍过这本书，很欣赏它。

最经开始更多的实际使用 Python 了，很自然的会想把它跟 Ruby 做些比较。因为我对 Ruby 和 Python 的语法和特性的了解只是一般而已，所以对语法的比较我说不出太多的东西。在我看来语法上来看它们相似的地方多于不同的地方，在它们中进行切换是很方便的。我很喜欢 Ruby 的 block 语法，但 Python 有 list comprehension 和 generator，很多 block 的用法都可以用它们来完成，所以我并不会在使用 Python 的时候非常的渴望 Python 也有 block 语法（仅有的时候是文件打开完成任务以后自动关闭这种地方，Python 里还没有很好的解决）。就语言本身来说我更喜欢 Ruby，个人觉得用 Ruby 写程序更为舒服，而且通常完成同样任务的 Ruby 程序也比 Python 更短。但是 Python 的优秀的社区使我选择 Python 而不是 Ruby。

在 Python 和 Ruby 中我只想选一个，用它来完成一些 quick and dirty 的任务，我希望一切越简单越好，最好就是别人已经帮我完成了，直接拿来用就可以。随着越来越多的使用 Python，看到 Python 社区所完成的工作，我觉得 Python 才是这一任务更好的选择。Guido 在一次访谈中说：

对于杀手锏应用（killer application），我个人并不十分迷信。如果你太看重杀手锏应用的话，实际上你可能会把焦点放错地方，或者你可能太专注于某一个方面。

以前对这话觉得不屑，觉得是酸葡萄心里而已，现在越来越觉得 Guido 是对的。Python 现在已经进入很多领域，在科研领域，已经出现像 NumPy, SciPy 这样优秀的软件。我也看到生物信息学研究者写的用 Python 编程来处理生物信息学问题的文章。在图形处理方面也有了优秀的软件，如 PIL。而 NASA, Google 等组织也在大量使用 Python。而在 Web 开发框架上，Python 有不止一个，另外还有像 twisted 这样高层的互联网应用程序开发框架。实现上 CPython 比 CRuby 也要成熟，两者都有许多实现，以前很看好 Rubinius，但现在我知道了 PyPy，如果 Rubinius 能够使得 Ruby 在性能上有很大的提升，那 PyPy 肯定也能，事实上 PyPy 现在应该比 Rubinius 更成熟。而我现在自己常用的 VCS 工具 Mercurial 就是用 Python 实现的。

从使用的广泛程度来说 Python 目前远超过 Ruby，记得 2008 年 1 月的程序设计语言使用广泛度统计中 Python 排名首次超过 Perl，而 Ruby 的排名反而下降了。不知道是因为 Python 有大量优秀的软件导致大量的使用，还是因为大量的使用导致有如此多优秀的软件，但现在的社区已经使得这两个方面可以互相促进，形成一个良性循环了。如果 Python 社区的注意力都集中在 Web 开发上，或许它可以出一个类似 RoR 的 killer application，但它就不会产生如此之多不同领域的优秀软件，也会使得 Python 的使用达不到如此广泛的程度。在我看来这是得不偿失的。

即使我不喜欢 Python 中一些 Guido 强加给我的限制，但是只要它能够让我把那些 quick and dirty work 以最快的速度最小的精力做完，我就不在乎，而那些限制在构建大型软件上可能反而能够带来好处。如果哪天 Ruby 能够像 Python 社区这样成熟，提供更多的优秀的软件，那我在解决个人的 quick and dirty work 时就会选择使用 Ruby。但是现在，我选 Python。

我仍然会花时间去学 Common Lisp，但 CL 现在不擅长跟 OS 和其他基础设施交互，所以我不会用它来完成日常的工作。我目前只打算想把它作为一个研究性质的语言，满足我对程序设计语言本身的兴趣。一方面，SLIME 提供的交互式的开发环境更加合适探索性的任务（ipython 虽然不错，但是跟 SLIME 和 CL 提供的环境比起来还是差了点）；另一方面，正因为有许多工作在 Common Lisp 中还没有完成，我可以尝试自己来研究解决，在其中得到锻炼。我也希望在真正领悟 Common Lisp 的时候我能够成为一个更好的程序员。

语言的选择并不是至关重要的，但是我希望能够使用一个使得编程更加有趣的语言。以前在语言上花了太多的时间，现在决定把语言逐渐固定下来，把注意力放到更加重要的问题上，为我以后的研究做准备。

PS: 现在在浦口每天的时间都可以自己支配，太爽了 :–)

不过想看的书太多了宏观经济学（微观已经看完了），算法导论，线性代数，Ansi Common Lisp，还要每天在毕设上投入一点时间（现在还在准备阶段），再加上要利用本科最后这个学期好好练小提琴，有点安排不过来了。为了集中精力，有些书看了一点又要停下来了。

最近回到浦口真开心，爱死浦口的食堂了 :–) 我现在的日子跟查师兄去年的比真是太舒服了，这两天有点堕落，明天起要鞭策自己努力了。

以前在用 Common Lisp 做计算方法的作业的时候就觉得 Common Lisp 的 prefix notation 对数学表达式不够友好。最近打算用 Common Lisp 实现些算法，再次遇到了这个问题。好在已经有人做了将 infix notation 转成 prefix notation 的工作，所以我就可以用现成的了。

CMU 的 AI repository 里有一个 INFIX: Infix reader macro for Common Lisp，实现了一个 reader macro，用它就可以在 Common Lisp 里面使用 infix notation 了，不过需要把表达式用 #I() 括起来。

代码注释里面有一些例子，也有使用说明，看看就能用了。这里举几个简单的例子：

1
2
3
4

#I(1 + 2) ; 3
#I(2^^2 + 4) ; 8
#I(1 == 2) ; 判断, 得到 nil
#I(1

有了这个 read macro 数学表达式的输入就简单多了，布尔表达式也可以用类似 C 的语法来写，不用再做人肉 infix –> prefix 转换器了。

除此以外，它还提供了函数调用数组访问的特殊语法，而且用 = 号做赋值，同样是用了类似 C 的语法。

1
2
3
4

(defparameter v (vector 0 1 2 3))
#I(v[1]) ; 1
#I(v[0+1] = -1) ; 现在 vec 中的第二个元素值为 -1
#I(random(5)) ; 调用函数 random

我比较喜欢用这种语法来访问数组元素，比用 aref 看起来更清楚些，还能少打些字。

如果想知道这个 read macro 在背后究竟做了什么的话可以在 #I() 之前加个单引号。

1

'#I(v[0+1] = -1) ; (SETF (AREF VEC (+ 0 1)) 1)

跟 Python, Ruby 这样的语言比起来 Common Lisp 的程序代码并不是很紧凑，因为有很多长的函数名，一些常用的操作也没有特殊的语法来支持。只使用 prefix notation 的好处就是可以方便的使用宏，更容易的进行元编程，也使得程序员可以自己定义语法，这里的 infix read macro 就是一个例子。

Paul Graham 在他的 Lisp 方言 Arc 中就希望能够使 Lisp 的代码更紧凑，更短，添加一些语法来简化某些操作。通常来说程序中的 bug 数量与程序的长短成正比，与使用的语言无关，如果能写出来的程序更短那么错误应该也会更少。不知道以后 Arc 的发展会如何，不过现在就已经有一个对 Lisp 语法做出许多改动的基于 Common Lisp 的语言，Qi。Qi 的作者正准备大幅改进语法，推出 Qi II，等出来了再去看看，到时候看是否可以把它和 Common Lisp 混合使用。

最近有人留言问我数字游牧计划的信息，所以决定专门介绍下。

首先你可以到数字游牧计划的主页来看看他们自己的介绍。数字游牧计划为 blogger 提供 blog 空间，使用的主机来自国外，域名也在国外注册。数字游牧计划不是虚拟主机提供商，而是向国外的虚拟主机提供商购买空间，然后再转给国内用户使用（目的不是盈利）。自己购买国外空间的话一来麻烦，二来比较贵，数字游牧计划通过多人共享一台虚拟主机降低费用，而且有人帮你负责主机的维护。没记错的话国内个人 blog 是要备案的，用数字游牧计划的话就不用做这事了。

我现在的博客域名和空间都是通过数字游牧计划来购买的。文件通过 ftp 上传，mysql 数据库用 phpmyadmin 访问。我只有安装和升级 wordpress 的时候会用 ftp 来传下文件，phpmyadmin 只在安装的时候用过。因为服务器在国外，所以有些人访问起来可能会比较慢。购买的时候把要注册的域名（子域名可以以后随便加）告诉数字游牧计划的负责人，通过支付宝支付，过几天就有自己的空间了。除了刚开始的安装和升级、平时的备份以外，没有做过任何的维护。（geek 一下，Linux 用户可以用 ping 来查我的博客服务器的 ip 地址，然后用 whois 来查这个 ip 就会知道服务器是 Dream Host 提供的。）

如果你有兴趣使用数字游牧计划提供的服务的话，可以在这里申请加入社区，申请时最好留下博客地址等信息。加入以后可以查看更多关于数字游牧计划的信息。

大年初一浏览了下《货币战争》这本书。

这本书凸显了金融系统的巨大力量。从德国 Rothschild 家族的发家历史开始，讲述美国总统与银行家斗争希望获得政府发行货币的权力的历史，介绍了美联储的成立，再介绍了一战时银行家们如何利用战争发财，国际金融体系从金本位到依赖美元的变化过程，日本 90 年代的经济衰退等等事件。讲述了金融系统如何一步一步扩大自己的力量范围，然后利用自己的力量来控制世界。最后提及了中国应该如何应对国际金融市场的变化，如何应对已经开始进入的外国金融企业。

对于不是学金融的我来说，书里面的许多东西都很陌生。有些东西确实让我涨了见识。最有意思的一点是西方英美等国的货币发行权属于银行，政府向银行发行国债作为银行发行的货币的储备金。（可能不能称为储备金，我的理解是金本位下货币的发行是以黄金储备作为基础的。使用国家债券的话就是用一种纸币作为另外一种纸币的基础。以后要看些这方面的书来理清这些知识了。）因此政府每年需要向货币发行银行支付国债的利息，实际上也就是纳税人每年都得向银行变相纳税。更要命的是政府还不能还清国债，否则就没有作为流通货币基础的债券了，因此这些货币发行银行可以稳当的每年从政府收取很多的利息，政府很难把这些银行甩开。

美国宪法中规定政府拥有发行货币的权力，这样就可以避免向货币发行银行支付利息。书中说美国总统的数次遇刺都与银行家为了取得美国货币发行权相关，而且最后银行家们成功了，美联储就是他们胜利的产物。中国的货币是由政府直接发行的（严格来说是人民银行吧？），这样做其实是好的，千万不要去与国际接轨。

对我来说这本书还是很有意思的，书中体现出经济对政治的巨大影响力，甚至可以说经济控制了政治，而且是几个金融巨头控制了整个金融体系从而控制了政治。它对许多事件的解释都站在了这一个单一的角度来看。学金融的同学跟我说这本书的有些观点不是很好，所以也不能全信。不过对我来说，看看这本书还是有好处的，至少激发了我对资本市场的兴趣，多知道了一些资本市场上的名词。

第一次看到这个程序的演示是在去年 10 月 29 日的微软亚洲研究院参与举办的 “21世纪的计算” 学术研讨会上。（其实不能称作研讨，应该是研究成果的展示，图灵奖得主的研究成果我们短时间内是理解不了，怎么跟他讨论。）虽然我很少用微软的产品，但是这个研究院产的程序还是很赞的，确实是很牛！对的对子非常工整，也有一定的意义。

不过被王三表狠狠的恶搞了一把，有的对子很搞笑。这个程序不弱智，其实没有社会责任感。应该是它的算法恰好使它体现出社会责任感来了。我不认为设计算法的人偷偷的把他的社会责任感放在算法中，当然，如果他这么做，真是相当的高明，因为没人会针对这些对出来的对联去审查算法设计者，即使有，他也可以很轻松的赖帐。

昨天用 python 写 insertion sort 练练手，在用 for 循环的时候遇到了一点小问题。

Dive Into Python 这本书的确不适合初学程序设计的人，我看完第 6 章都没有看到 python 中的 while 语句，所以最初我用了两个 for 循环来实现，xrange 也是我看别人的程序的加上查文档才知道怎么用的。对有经验的人来说这样也没什么不好，python 的语言和类库参考都不错，直接查也很方便。

最初的实现出错了，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13

def insertion_sort(list):
    for i in xrange(1, len(list)):
        key = list[i]
        for j in xrange(i - 1, -1, -1):
            if key

随便试了几个就错了，很奇怪为什么会出错。后来才意识到使用 for 遍历的是一个列表，如果没有 break，遍历完之后 j 是列表中的最后一个元素 0，而不是 -1。如果因为列表遍历完成而非 break 中断循环，则最后应该执行 list[0] = key，但实际执行的是 list[1] = key。

这样就有个问题，如何判断 for 循环是正常遍历结束还是被 break 中断的？在 C 中写 for (j = i - 1; j > -1; j--) 最后循环结束的时候 j 为 -1，所以检查 j 的值就可以了。但在 python 里面，j 最小只可能到 0，循环结束时 j 为 0 可能是因为 key >= list[j] 而 break，也可能因为 0 是最后一个元素而终止循环，所以通过检查 j 的值是没法做到的。（因为 python 中 for 的作用是遍历列表等容器，所以不能让 for 与 C 中有相同的行为。）

查了下语言参考，发现 for 语句可以跟一个 else 块，觉得有点奇怪，还没有见过哪个语言有这样的语法的。文档说 else 后面的块在循环条件为假时执行一次，但如果 for 后面的块中因为 break 导致循环结束则这个块不执行。一开始觉得这个 else 没什么用，除非死循环，否则条件总是会变为假，那直接把代码放在 for 外面不就可以了。后来想到这个特性正好可以用来判断循环终止的原因，用个条件变量即可，在 else 代码中改变这个条件变量，然后在后面的代码中检查条件变量的值即可。

最后的代码如下：

1
2
3
4
5
6
7
8
9
10
11

def insertion_sort(list):
    for i in xrange(1, len(list)):
        key = list[i]
        outbound = False
        for j in xrange(i - 1, -1, -1):
            if key

当然用一个 while 循环就可以不用这么麻烦了，不过我就是想知道用 for 该怎么解决这个问题。

PS:
wordpress 有没有什么贴代码用的插件？