Posts archived in Cool Stuff

12 comments

Borg

Star trek 是基本上属于 Geek 必看的科幻剧了,虽然年代久远了一点,但里面很多词和符号都成了 Geek 文化的一部分。
我甚至怀疑乔布斯老师是按照 Star trek 里面人手一个 PADD 的创意发明 iPad 的。

Startrek 剧集中塑造了一个外星种族,叫做 Borg. 我觉得很有意思,来八卦一下。

首先,Borg 这个种族常常和邪恶帝国挂上等号。如果你去翻 New Hacker’s Dictionary 的 Borg 条目, 他就会告诉你, See also: Evil Empire. 如果你是 geek 网站 slashdot 的常客,你就会发现, 上面每条微软的新闻旁边,都是比尔盖茨同学戴了一个机械状的头盔/帽子, 是的, 这就是隐喻了比尔盖茨的微软是个邪恶帝国。

为什么说 Borg 是邪恶帝国呢? 这要从 Borg 的生存方式说起。 所有的 Borg 成员,都随时听从一个中央命令机构,叫做 Collective (集体). 这个集体, 随时能够和任何一个 Borg 成员通信, 在 Borg 成员里共享一切信息. 每一个 Borg 成员并没有名字,而是以代号相称, 比如第一联合方阵第一分队 9 人组第 7 号(著名的 Seven of nine)。 这些成员也没有任何所谓的个人意志,都是属于 Borg 集体里的一个工蜂而已。

Borg 本身只是一种社会组织方式,蜜蜂和蚂蚁基本上也是这样组织的。 Borg 的邪恶之处在于,他生存的唯一目标,就是不断的同化其他的种族,以达到自身种族的完美。 他们对其他种族的同化显然非其他种族自愿的,于是他们就不断的发动战争,其中就包括对人类的战争。 同时,他们的武器系统还很发达,能够自动适应对手的武器系统,所以基本上同化其他种族好不费力气。 Startrek 剧集放到 Voyager 的时候,他们基本上已经统治了银河系第四象限的绝大多数星球系统了。 一个种族一旦被同化,就彻底变成了 Borg 集体里面的一个零件,所以,Borg 几乎是所有其他种族的敌人。

Borg 同化的方法也很神奇,就是给你注射一种纳米级别的生物芯片,这种生物芯片一旦到了被同化的生物的体内,就开始改造这个生物。 以人类为例,Borg 认为人的视觉系统不够发达,所以同化人类为 Borg 的时候,人就会被添加一个发红光的眼睛部件。 Borg 的这个特征很显著,盖茨大叔的图就是这么回事。

Borg 这种集中的,集体的,一致对外的组织方式,是效率无比之高的。 当然,Borg 也有一个致命的弱点: 他们的技术非要通过同化其他生物才能获得,他们本身的研发技术却不见得怎么样。用句流行的话说就是 “一直在模仿,从来不创新”。 所以假如遇到不能同化的生物,他们就非常郁闷。比如说,Borg 编号为 8472 的生物的免疫系统特别强, Borg 的生化武器完全不起作用,这时候 Borg 就被打得落花流水。 最后还是靠英勇的人类船长和神奇的医生研发的技术才勉强打败了 8472 号生物的一次进攻。

Star trek 中有多次 Borg 的成员被同化后脱离了组织再次变成一个个体的例子。 最显著的就是 Seven of Nine 的去 Borg 过程了。 Seven 是一个人,很小的时候就被同化成 Borg, 一开始是作为合作来到 Voyager 船上的,但是时刻不忘和集体保持联系。因为一次事故,她和集体的连接被切断了,她立即感觉到“我再也听不到集体的声音了,我很孤独”。 的确,Borg 集体的力量和声音是非常有安全感的,一瞬间失去了之后必然会感到很孤独。 船长 Janeway 就说,你不是 Borg, 你首先是一个人,不要感到孤独,我们船上所有的人都是你的朋友。 Seven 最终摆脱了 Borg 集体的影响,成了 Startrek 系列中最性感的角色,哈哈。

最后附送一个和 Borg 有关的好玩的技术八卦。 大家都知道 GoF 的 Design Pattern 里面的 Singleton Pattern, 就是一个类只能有一个实例。 在 C++ 等标准的静态语言上,实现方法是私有化构造函数等等。 在 Python 这种藏不住构造函数又动态的语言中,
实现 Singleton 看上去是比较麻烦的。 不过,有一个叫做 Borg Pattern 的实现,优雅得实现了 Singleton。 如果你了解了 Borg 种族的特点,又知道 Python 的一些基本知识, 你看下面的这个代码肯定会赞叹到笑出来。

class Borg:
    __collective_mind = {}
    def __init__(self):
        self.__dict__ = self.__collective_mind

    # and whatever else you want in your class -- that's all!

Borg Pattern 就这么简单。对于小项目中顺手写一些控制资源访问的 Singleton 来说,这个 Borg Pattern 实在是不能再好了。

一周前我和 Tinyfool 闲聊苹果操作系统,都认为对于开发人员来说,苹果操作系统(Mac OS)是上佳的选择。 Tinyfool 笔头很快,当即就写了一篇长文章, 我则笔头很慢,今天才全部码好。 他的文章的主要切入点在于 Mac 平台作为目标开发平台的优势,而我这篇的切入点主要是 Mac OS 作为一种开发工具的优势。

开发人员的趁手工具
对于开发人员来说,所有的开发工具的最大的用途,就是最大限度的提高开发人员的生产率 (productivity) 和创造力(creativity)。在我们这个时代,使用 GUI (图形界面) 是一个提高生产率的好手段。虽然上一代的那些 UNIX 开发人员的确不需要 GUI。一个屏幕,一个键盘,一个编辑器,在陋巷,人不堪其忧,也不改其乐的黑客比比皆是, 但二十多年过去了, 现如今开发环境发生了巨大的变化。 比如说,相比较于当年程序员使用的基于文本的环境,在 GUI 下格式丰富的文档显得更直观,阅读体验更加好;就算工作中不需要开发任何 GUI 程序,现代开发人员也会使用 GUI 来完成网页图片和文档阅览等等。 因此,即使是最传统的用命令行的开发人员,其实也能沾 GUI 的光。 比如说现在最好的终端程序,都是 X 下模拟的,因为这些模拟的终端的出现,一些复杂的可视化功能可以在这些终端中实现了,比如 Unicode 的显示(rxvt-unicode)等等。

对于开发人员,拥有一组非常好用的,能够最大程度的提高生产率的开发工具乃是一大人生梦想。那么,这套开发工具从何而来呢? 大体来说,这些工具来自于三个方面: 1. 通过系统和单一的应用软件提供的;2. 通过搭配使用各种应用软件 3. 通过定制和改变现有的应用软件。 这三点,对于 UNIX 开发人员是再熟悉不过的了, 无非就是写脚本,走管道而已。 所以,在前 GUI 时代,这一套哲学非常盛行, 开发人员都知道,需要通过安装脚本解析器,写一些的脚本,配置一些环境等等,才能把刚出厂的 UNIX 系统,改造成自己使用起来得心应手的系统。 基本上任何一个使用 UNIX/Linux 系统多年的人,机器里面都有各种各样的“私藏”的脚本。离开了这些脚本,他的效率会大打折扣。

GUI 时代传统的丧失

上世纪 80年代的时候,GUI 时代和个人计算机普及的时代降临了。从此,计算机变成了个人电脑,历史上第一次,计算机不是专为开发人员设计,而是为了普通用户设计。普通用户的需求就是完成一个一个的现实问题,软件产业提供的解决办法就是为用户提供一个一个的应用软件,而不是让用户自己一行一行的编程和写脚本,巨大的软件需求瞬间成就了一个巨大的软件产业。 这样的一个间接后果就是,对于普通用户来说,让一台计算机变成能够帮助自己完成任务的“个人计算机”的唯一手段,就是叠床架屋的不断的装各种应用软件。

我们可以用一个简单的例子说明这种使用模式。 我们都知道,安装 Windows 系统的一个经验原则是把操作系统和应用程序分成两个逻辑盘,一个在 C 盘,一个在 D 盘。这个磁盘分区的经验原则不光网吧老板知道,连我大学里面只会点鼠标的那些女同学都知道。为什么有这个奇妙现象呢?其实,这是由 Windows 系统的用户的典型使用模式决定的。 在 Windows 系统上, 应用程序和文档是关键,操作系统只是一个随时可以重装的东西而已,所以干脆两者分开,互不影响。在这样的使用模式引导下,Windows 系统上格盘重装是非常低成本的,只要文档不丢,应用程序不丢就行。这种使用习惯,浪费了多少 geek 男美好的时光为人重装系统,又促成了多少美妙的姻缘 :)。 总之,在 GUI 时代,要解决一个问题,就装一个应用程序。至于应用程序之间的通信,和用非键盘鼠标的方法控制应用程序等等,都不再是要考虑的问题,有这样的需求的人成了非主流,非主流到以致于主流的操作系统和应用软件都不让你这么干了。 操作系统把所有其他的路都封死,就是明摆着告诉你,要想某样功能,请出门买软件。

Smalltalk 的启示


其实 GUI 时代原本不应该是这样的。 我们都知道,GUI 原本是施乐的 Alan Kay 那一帮人做科研做出来的,Bill Gates 和 Steve Jobs 各自到施乐”抄袭” 了一部分过来,于是窗口啊按钮啊就到处都是了。 他们都看到了图形界面和面向对象的形, 看到了图形界面就是把按钮图标等等对象放好,然后鼠标点击拖动等等这些表面的东西。 因为所有的 GUI 界面都是从文字界面起步的,所以所有的 GUI 程序,其实就是原来的可执行程序的包装。 C++ 这个语言的出现也很讨巧,把 C 包装成了一个面向对象的语言,包装对包装, C++ 很讨巧的适应了把可执行程序 GUI 化的趋势, 成了 GUI 时代的主流开发语言。从表面上看,只要运行这些可执行的程序,就能够看到图形界面,就能够用鼠标点击操作他们,可是这些东西的底层,都是一个编译过了的可执行程序,原先 Smalltalk 中的那些运行时环境啊,对象容器啊,都统统不见了,所有的图形界面程序,还是直接运行在计算机的 CPU 上,而不是一个虚拟的面向对象的容器上。而这个面向对象的容器(也叫做“运行时”或者“运行环境”),才是 Smalltalk 的神。 简单的说,Smalltalk 本身具有一个面向对象的运行时,所以即使到了执行的时候,里面所有的对象还是可以互联互通的。 而 C++ 写出来的程序,除了编译之前是面向对象外,只要一编译,就全部变成机器码,和对象就再也没有任何关系了,也就不存在运行时去动态的查看(inspect) 和改变(modify) 这些程序对象的说法。 总之,因为历史的局限,这些 GUI 的平台,都是渐进的照猫画虎的演变的,所以没有一个平台像 Smalltalk 那样细致地考量过对象的互相通信的问题,再加上我们上面说了,反正扩展系统的方法就是引入新的应用软件而已,本身也没有互联互通的需求,所以这种抛弃运行时的,不让对象被外部程序控制的实现方法也无所谓不好。

可是开发人员不是普通用户啊,他们依然要改造计算机成为自己的工具的。在现有的现有工具不能解决问题的时候,要不然自己重新发明轮子,要不然就复用现有的一些工具,或者重新按自己的需求重新配置这些工具。 所以,和一般用户不一样,开发人员需要这些 GUI 的可配置性,也需要这些 GUI 程序之间的互联互通。 用黑话来说,第一个问题关系到 GUI 应用程序的脚本化, 第二个问题关系到 GUI 程序之间的进程间通信。 这两个问题,说起来简单,但都牵扯到 GUI 系统的根本设计问题。 历史在这里开了一个不大不小的玩笑,把这个唯一的机会给了 Mac OS X。其他操作系统,都因为这样那样的原因,在这两个问题上没有很好的解决方案。

进程间通信,苹果的方案

花开两朵,各表一只。我们先说 GUI 程序的进程间通讯的问题。 所谓的进程间通信 (IPC),就是两个程序之间的信息共享。 我们都知道,*nix 的一个强大之处就在于管道,管道是最简单,最廉价也是最常用的 *nix 进程间通信的方法。在 GUI 时代,最常用的 IPC 机制成了剪切板和鼠标拖放操作。这两个操作虽然都很直观,但都要人操作,离开了人,程序根本无法自动完成进程间通信。 而要工作效率的提高,就是要让计算机离开了人的干涉,也能完成这些任务。为了自动化这些任务,操作系统就不能简单的绘制窗口然后万事大吉了,它必须要知道哪些程序在运行,哪个运行的程序可以给哪个程序发消息通信等等,比如说,如果我们想自动的在阅读器里面选择一个词送给字典程序查释义,计算机就需要知道字典程序在运行的时候可以接受一个字符串,但是不可以接受图片。如果我们把字典程序抽象成一个可以提供“查字典”服务的对象的话,毫无疑问,如果想要向字典程序发送字符,必须首先知道字典程序能够接受什么,用什么方式把这个单词发送给字典等等。 所有的这些信息,都必须由操作系统托管才行(不可能每个应用程序里面都要记着字典这个程序能接受字符串不能接受图片,这样每个应用程序都要记下所有其他可能的应用程序的信息,这是一个平方级别的关系,需要开发人员开发一个程序的时候还要兼顾其他所有程序,这显然是不现实的)。用行话来说,必须要有一个统一管理的运行环境,来管理这些程序之间的互相通信问题。 我们上面说了,Smalltalk 的神在于一个统一的面向对象的运行时,使得所有的应用程序能互联互通。 可是所有平台上的 GUI 程序的演化进程都没有走这条路,而是只把外表给模仿走了;有的平台即使想做互联互通,也做得不彻底(比如微软的 OLE,COM 等等)。

是好东西,总会发光的。 但是要想让这个好东西被新的操作系统全盘采纳,要想让一个系统能够从底层到上层全部采用统一的运行环境,就要扔掉很多的历史包袱。甩掉这种历史包袱,对于任何操作系统都是不容易的。如果我们回到当年,一定会幻想,要是有个神人,能够不管市场也不管现有平台,从头打造一个没有任何历史包袱的干净整洁的 GUI 系统该多好。 历史就是这么戏剧,还真就安排了一个人,做成了这件事情,这个人,就是那个斯蒂夫乔布斯。

1985 年,乔布斯被苹果扫地出门,成立了 Next 公司, 一心想要做出质量上乘的 GUI 计算机系统。 历史给了乔布斯一个全部从头做的机会。这一次,乔老师和 Next 的开发人员意识到,光照搬 Smalltalk 的形是不行的,要连它的神也拿过来,重头设计进程间通信和 GUI 系统。 在内核层面,他们用了 Mach 这个为 BSD 设计的微内核。 这个操作系统内核就是为了替换已经过时的 UNIX 内核而设计的,其中的一个核心设计哲学就是重新设计进程间通信; 虽然现在基于微内核的操作系统已经不是什么潮流(为此 Linus 和 Tanenbaum 吵了一场著名的架),但在相比较于当时 UNIX 系统的内核(此时 Linux 还没出现的,UNIX 内核只有 BSD, Bell, SUN 等几套),Mach 算是一个高的起点。在这个内核上,Next 公司的工程师开始构建面向对象的基础系统。 这套系统在 Smalltalk 中已经有了蓝图,因此这些工程师以 Smalltalk 为蓝图,先设计了一套基于 C 的语言,也就是 Objective C,照搬了 Smalltalk 的经典的 [对象 消息: 参数] 语法。 (我个人不喜欢 Objective C 这个语言,Smalltalk 是一种纯面向对象的动态类型的语言,Next 公司当年完全有机会用 Smalltalk 语言的,如果用了 Smalltalk,现在的 Cocoa 框架还会更加漂亮,代码更加干净;用 Objective C 这个自创的语言,不知道是不是因为专利的考虑,反正 Objective C 这20年的所有创新,就是在慢慢的更像 Smalltalk 而已,Java 和 Ruby 这几年也是不断的从 Smalltalk 拿东西)。有了内核,有了语言,Next 构建了一个纯的面向对象的运行环境和类库(和 Java 和 .Net 的统一类库想法类似,只不过超前了十几年), 这套类库,在当时叫做 NextStep, 所以所有的类名前面都带有 NS 前缀,无比丑陋。可惜的是,当年这个超越时代的类库太阳春白雪了,话说 Smalltalk 超越了时代 20年,所以90 年代中期的时候, 程序员才想起来当年 Smalltalk 的好,出现了 Java Ruby 等等受  Smalltalk 启发的语言。 乔老师虽然落后了 Smalltalk 5 年,却领先也业界 5-10 年,所以在 1995 年的时候, Windows 95 卖疯了, 乔老师的 NextStep 却没动静,只能把这个类库重新打包当成 Web 类库卖卖,即 WebObjects。这倒是无心插柳,生意不错,因为当时的 Web 开发已经吃尽了没有一个统一的运行环境的苦头(这也是日后 Java 风行的原因)。 我们说,是金子总要发光的,但是前提是要 (1) Next 再等几年,等业界回过神来认识到它的好处,(2) 获得一个主流的操作系统支持,把底层全换成乔老师的东西。 乔老师也知道这两个条件,所以加快了和 SUN 合作的步伐,想要把这套系统放到 SUN 的工作站上。 但是 SUN 本身有很强的底层技术,那段时间又狂推 Java, 所以其实乔老师在 SUN 这条路上胜算不大,况且 SUN 自己内核技术很强,所以肯定要肢解 NextStep 把内核重写,如果不和 SUN 玩,一来Next 这家公司能够多撑 5 年都是问题,二来几乎每家做个人计算机的公司都倒戈微软了,其他做工作站的公司又都有自己很强的底层技术,不可能用乔老师的玩意儿的,所以看起来乔老师和他的阳春白雪好像前景不妙。 可是天无绝人之路,放眼看当年的市场,只有一家公司没有倒戈微软,又没有很强的底层技术,又和乔老师有一些渊源,历史就是这么戏剧,这家公司就是把乔老师扫地出门的苹果。

90年代中期苹果的日子很不好过,个人电脑市场败给了 Wintel 联盟,新兴的市场上成绩也一塌糊涂,投资人也不糊涂,把当年让乔老师扫地出门的 Sculley 也扫地出门了,随后就把乔老师的公司给买了回来,让乔老师复职负责复兴苹果。 所以,上面我们说的两个条件就这样突然的满足了: 第一,他现在是老大了,所以可以彻底的把原来苹果的系统推倒重来,用自己的新家伙;第二,原来 Next 公司的那帮工程师不要担心失业了,现在由苹果负责发工资了,所以,正好可以让这些人着手改造苹果系统,主要的工作就是用自己带过来的新系统取代苹果的旧系统,并且让新系统的图形界面和旧系统保持风格的一致。 这个工作,从1995年 Next 被收购,到 2001 左右的时候才做好,这6年的时间里, 乔老师也顺带让苹果重新盈利了。

2001 年发布的 Mac OS X, 是苹果操作系统的第十代,完全基于了乔老师在 Next 开发出来的那套类库,所以自然的,具有了一个统一的面向对象的运行时。 这个运行时和类库系统,Mac OS X 把它叫做 Cocoa。其实 Mac OS X 刚出来的时候也不怎么好,不过依赖于这套设计精良的底层系统,Mac OS X 的迭代开发周期要比其他操作系统短多了 (仅慢于Linux, 不过 Linux 只有内核部分). 在短短的 8 年里,Mac OS X 就搞出了 7 次大的版本发布。 虽然我们看 Mac OS 好像从 10.0 到 10.6 只是次版本号在进步, 其实每次都是一个 major release, 大致相当于从 Window 95 到 Windows 98 或者 Windows 2000 到 Windows XP 这样级别的升级。 这样的发布却不改主版本号,一方面是从市场上考虑,另一方面也的确说明 OS X 的底层已经处于一个相对稳定的状态。 有很多 Windows 程序员非常推崇 .Net。 是的,.Net 的确是一个非常好的框架,可是想像一下,苹果在1995年的时候就有了一个统一的运行时,加上这么多年所有的程序都在这个统一的框架上开发,如果论在 Mac OS X 这个平台上的经验积累,应该说 Cocoa 社区是比 .Net 社区更加成熟的。

应用程序脚本化

光有进程间通信的系统还不能算是一个完全成熟的 GUI 系统,因为进程间通信依然是相对底层,而 GUI 上的应用软件是层出不穷的,不可能任何问题都跑到底层用进程间通信解决;所以,要想让 GUI 系统进化到易用和易于定制的水平,就需要开放对 GUI 程序的脚本控制。只有 GUI 程序能被外部控制了,才能真正的达到搭配使用 GUI 系统的效果。 其实,一旦有了一个统一的运行时,只要开发应用软件的时候统一设计一下脚本接口,用脚本控制 GUI 程序应该不难。 比如说,微软的 Office 系列套件, 就完全可以用 VBScript 去控制。 可惜的是,没有一个系统能够实现全系统的控制。 要实现全系统的控制,不仅仅要这个系统能够提供底层的支持,更重要的是要能说服所有的开发人员,或者说让所有的开发人员养成开放脚本接口的好习惯。 从技术上来说,这不是太大的问题,只要开发人员按照统一的脚本通信协议,实现特定的接口就行了,可是,如果一个平台上开发 GUI 的方法太多,开发人员只选自己喜欢的来,这种标准就不可能统一。 比如说 Linux 上 KDE 和 Gnome 都有自己的脚本化系统,可是开发人员有的用 KDE, 有的用 Gnome, 有的干脆两者都不用,这就谈不成有一致的接口。 一个平台要想有一致的脚本控制接口,除非 (1). 这个平台上就一种 GUI 开发方法,自古华山路一条,要不不做,做出来的东西就只能是标准的接口; (2). 这个平台上大部分的,主流的应用软件,都实现了这个脚本接口,这样因为这些程序的拉动,其他 GUI 程序想要融入这个平台上现有的应用软件的圈子相互通信,那也就必须要实现这个接口。 在 2000 年的时候,又只有一家公司能够同时满足这两个要求,就是苹果。 微软部分做到地了这两条,基本上用 VBA 统一了 Office 的控制,但是跳出 Office,微软的 OLE 对象模型几乎没有任何用武之地,与之捆绑密切的 VBA 自然无人问津。 不过据一些在金融行业工作的朋友说, VBA 能够大大提高 M$ Office 的生产率。

GUI 脚本化不是一夜之功,特别是我们说要做出统一的脚本接口,能兼顾各种程序的需求,这就完全不是一两年的时间能够搞定的,总需要很多年的技术积累和设计取舍后才能收敛到一个相对稳定成熟的系统, 而苹果,居然很神奇在十几年前就有这方面的经验,苹果再次怎么这么幸运呢?

在 80 年代后期的时候,苹果机上有一个非常超越时代的软件,叫做 Hypercard。 这个软件我曾经在上一代苹果上玩过,具体的思想就是你可以存储一张一张的“卡片”,这些卡片上面可以放置多媒体的声音,图像文字和其他对象,基本上就和现在网页一回事,唯一的区别就是这些卡片都存在本机。 在没有 Powerpoint 这类软件之前,这个 Hypercard 的软件可以用来做课件,做幻灯片演示等等,是个极其强大的工具。 为了让用户可以定制这个卡片,这个程序提供了一套非常强大的编程系统,叫做 Hypertalk。 因为这种编程语言是给普通人而不是程序员用的,所以你会感觉根本不是编程,而是写英语。这套东西,虽然本质上也是从 Smalltalk 学来的,但是用英语语法的方法编程的确是一个全新的思路,苹果把这个给普通人编程的语言发扬光大了,用更加贴近自然语言的方法重写了语言和文档,模仿 Hypertalk 系统,发布了一个跨系统的脚本控制语言,叫做 Applescript。这个语言就和自然语言没什么区别,比方说, 获取窗口的大小不再是
window.getSize()
而是
get size of window

显示第 22 段的 第一个单词不再是
print(paragraph[22].getWordByIndex[0])
而是
print the first word of paragraph 22

更狠的是,你还能用法语和日语写。 80年代后期的时候和整个 90年代初期,苹果基本上已经被 PC 机逼到墙角了,只剩下出版行业,设计行业等等专业的行业因为应用软件和图形处理能力的关系,依旧在守着苹果机。 两个行业的用户都需要自动化的 GUI 控制,但是编程都不怎么样,于是,这些应用软件的开发商也主动掺合加入 Applescript 旗下。 在90年代乔老师没有加入前,苹果自己把 Finder 全部脚本化,出版业的 QuarkXPress 和 Filemaker 也都完全脚本化,等乔老师入主苹果后,基于 Cocoa 的新技术,苹果一口气在 Mac OS X 上推出了 Safari, iTunes, iPhotos 等等软件,一股脑儿的全部脚本化了。 在别的公司都可望而不可求的历史机遇,又是被苹果给抓住了,一股脑儿全部塞进了 Mac OS X。这下,所有的第三方开发的工具,如 Firefox, Adium 这些,其实本来都不是苹果开发的,也没有太强的苹果渊源,但是 Firefox 要读 Safari 书签吧,哈,那就用 Applescript 吧,所以, Firefox 也逼着脚本化了(这个在其他平台上都不存在的事情)。 Adium 也是,这个聊天软件想要把 iTunes 正在播放的歌曲当成状态信息,好呀, Applescript,所以,也被带着脚本化了,而在 Linux 上的对应产品 pidgin 就没有这么脚本化。 所以,苹果平台已经成了一个惯性,你不想脚本化,就不带你玩,看你还脚本化不?

结语

我们都知道, UNIX 时代的主要哲学是提供给开发人员一组小巧精美且可以任意搭配使用的小工具,也就是所谓的 Software Tools, 然后任由开发人员由此出发,自己搭建自己的工具,打造自己的瑞士军刀。而开发人员所用的操作系统的目的,要不就是提供这样的一组开发工具,要不就是为这样的开发工具提供一个便利的平台,使得这样的工具变为可能。如果说 UNIX 是命令行时代的一个易于改造成 “自己的操作系统” 的操作系统的话, Mac OS X 就是 GUI 时代的这样的一个操作系统。 即使是从应用软件的层面看, Mac OS X 的底子好,更加容易出精品软件,所以即使仅使用应用软件,开发人员也应当优先考虑 Mac OS X。

附A: 相对正确的 Mac OS X 使用习惯

0. 一定要装 Quicksilver 或者用“服务”,否则就是把苹果当 Windows 用。
1. 在苹果计算机上,因为有服务和 Quicksilver 这样的工具,90% 的程序间的拷贝粘帖都是可以避免的。
2. 剩下的 10% 的程序内的拷贝粘帖,如果用一个好的编辑器的话,又可以省略掉 90%。

附B: 为什么 Linux 系统在这个方面还不够好

第一, Linux 上的 GUI 子系统,其实不是 Linux 的一部分,而是 X 和上面的 KDE 以及 Gnome
等等。 这几年,这些系统终于开始统一管理一个面向对象的运行环境了。可是这两个系统都是用C++ 所写,所以免不了费很大的力气才有了运行时信息,绕了一个大弯路,如果一开始这两个系统就用 Smalltalk 之类的有运行时的语言编写,至少现在应该有能和 Cocoa 抗衡的框架。

第二, 这几年 X 也认识到了在脚本化控制上面的不足,所以几年前做桌面的 Redhat 提出了 DBus 标准。 可惜的是不是每个程序都开放了 Dbus 接口,所以和苹果比起来,还有比较长的路要走。

在以前的文章中我介绍过囚徒困境,并且介绍了 Tit for Tat 策略,这种策略可以在多轮囚徒困境中不至于受益太差。那么,假如囚徒困境的游戏只有一轮呢? 有什么好的方法可以达到左上角那个双赢状态而不是左下角那个对两者都不是最优的状态呢?

囚徒困境是一个纯博弈论的模型,这个模型里面的赋值就直接决定了想要最大化自己利益的局中人必然会陷入困境,这是模型无法避免的。 所以想要跳出这个困境,只能靠博弈论之外的手段。 所幸的是,我们人类早就发现了这两种方法,并且都在实践中尝试过了这样两种方法。 第一种方法可以看成是直接的斩草除根法,即直接剥夺两个局中人选择“不合作”这个选项的自由,让他们都只有一个合作的选项。 这种政治学方法的优缺点在此我们不做讨论,我们关心的是第二种方法,一种经济学的方法–通过改变游戏受益矩阵,在新的游戏中,让局中人偏好合作。 在宏观经济的实践中,第二种的一般实现方法则是通过道德和法律手段对选择不合作的进行惩罚,对选择合作的实施奖励,以期改变整个收益矩阵,让这个收益矩阵不再满足囚徒困境的条件。 因为道德手段不确定太多,我们只考虑现代社会的最普遍手段,即法律手段。 具体来说,就是让局中人构建合同,并通过合同法等立法手段保护这个合同的实行,从而改变收益矩阵。

从博弈论的角度理解合同的话,通过订立合同,规定合同和法律效力,调控局中人不合作所获得的收益,使得局中人不再偏好”不守约定”选项。 具体的做法也很简单,估计聪明的各位早就想到了:

假定双方都选择合作则收益为 a, 而甲方合作,乙方背叛的时候,甲的收益是 b, 而乙的收益是 c。 按照我们的囚徒困境假设,背叛的收益 c 要大于合作的收益 a, 这样乙才会偏好背叛。 现在我们假设甲乙事先签订一个合同,规定背叛的一方要向合作(没有背叛)的一方支付损失。 我们假设这个值为 r。 显然的,现在乙背叛之后的收益就变成了 c-r, 而 甲合作的收益就是 b+r。 对于乙来说,我们的目的是要让他偏好合作,所以我们一定要让 a 大于等于 c-r。 最极限的情况就是 a = c-r, 于是, r = c-a。 这样, 乙的收益变成了 a, 而甲的收益变成了 b+c-a, 乙即使背叛也占不到好处,而甲也收到了合作的回报。

当然我这里说的是一个简化的模型。 不同的司法实践可能会取不同的 r 值,但是法的精神都是一样的,法律本身不限制你的选择,只是通过合理的奖励和惩罚,让理性的人自然的做出符合自己利益的选择。

从经济学角度来说,人类社会的运行中必然会有这样那样的博弈,尤其是市场经济发达的现代社会,可以说博弈无处不在, 而避免如囚徒困境这样的博弈情景也是社会效率所必须的。 如果单纯地剥夺局中人的选择权,通过”下一盘很大的棋”的方式去掉博弈选项,逃避囚徒困境, 那么局中人就可能不能完成充分博弈,利益得不到最大化。 而事实也证明, 这种方法在实践中效率不够高,因为人类社会运行这盘旗完全复杂到任何人都不能全盘掌控, 而且很容易就造成哈耶克说的”通向奴役之路”。 而法律为我们提供了另一种截然不同的思路,即仍然保持博弈,但调控收益矩阵,这样,仍然保证了合同双方的博弈选择自由。 在合同法和自由的关系的阐述上, 西方学者马克思韦伯曾经说过一段著名的话: “规范合同双方的那些法律的发展,以及在规范的框架下允许自由意志的法律的充分发展,往往被视为个人自由发展的标志[1]“。  通过对囚徒困境的解决方法和韦伯的这句话,应该不难理解为什么市场经济发达的国家恰好就法律制度健全,且恰好有较多的个人自由。

—-

[1] 这个自由具体来说叫做 Freedom of Contract, 有兴趣的读者可以阅读  “Max Weber on Law in Economy and Society”

以前我在博客里说过我用 Gtalk 控制我家的空调,这样我在回家之前就可以先开空调, 到家的时候正好家里凉爽起来了。 这个技术很简单, 只需要弄一个所谓的 X10 设备就行了。 我的朋友 Bao Sheng 做了一个视频, 有兴趣的可以看看他的演示和讲解。

X10 是一种非常方便的协议, 所有的控制信号都通过家中的电源线传播, 所以设备一插到插座上, 就可以被控制,不需要另外布线, 即插即用,对于我这种租房的人来说非常方便。 X10 设备有很多控制的方式。 有一种 X10 设备, 可以连接在计算机上, 然后计算机就可以发送指令控制其他X10设备。 计算机和X10 之间的接口是串口,所以如果你觉得不爽,用单片机和一个 MAX232 芯片就可以控制了,不需要庞大的计算机。

如果家中的电灯等不是插在插座上,而是通过墙上开关控制,你只需要将家中原有的电灯开关换成支持 X10 的电灯开关就行了。这种 X10 的电灯开关, 和普通墙上开关大小一样,功能一样, 但在 eBay 上的售价比在 Home Depot 买的普通开关还便宜,所以完全可以把家中开关全部换掉。这样就可以用计算机控制家中原有的电灯。

空调, 电饭锅, 风扇, 电视机等电器都可以如此控制。 至于我说的网络控制,就更加简单了, Gtalk 协议都是公开的,只需要写个客户端挂机监听就行了。 如果想玩这套东西的, 我这里有源代码。 X10 还有无线射频接口, 所以可以在车上控制车库的门或者门口的灯, 在家也可以躺在床上一键关灯,都是无线接口能干的事情,这里面的技术,和电动车锁的原理是一样的,你甚至可以把家里面的锁换成车上那种,一有人撬,立即杀猪似的发出警报。

控制电器有很多应用, 比如看电影的时候,能够达到一键打开电视和DVD以及关掉大灯的效果。早晨也可以通过控制灯慢慢亮起来让人自然醒来。至于控制空调,电饭锅这些,都是完全看需要看想象力了。

以上这些玩意,属于第一代智能家庭,我家基本上都部署了。 我现在考虑把我们家往二代智能家庭进化, 具体来说要能做到以下几点, 有些技术细节我没想好, 所以写出来请各位读者大牛出主意。

1. 在计算机上可视化控制一切电器

这个不难,只要写一个 GUI 客户端就行了。 如果想做得比较好玩一点,可以像  Second Life 一样, 把家中做成一个虚拟现实系统, 人走到哪个房间, 哪个房间灯自动点亮。 这个需要一个人的定位机制, 而且人身上的传感器要很小, 便于携带。 这个目前还没想好怎么弄。 大家帮我出出主意? 虚拟现实有什么好的软件? 是不是在门口装个摄像头做一下 Motion Detection 比较好?

2. 语音控制

我想语音控制所有的家电。 我看到别人 hack 了一个无线对讲机,让这个对讲机的信号送到计算机里面,但是随身放一个对讲机好像太庞大了,目前正在考虑弄一个蓝牙耳机,这个蓝牙耳机和计算机连接起来,做语音识别,然后发送信号到家电。 计算机端的语音识别软件很多的,应该很好弄。

3. 大脑直接控制和其他控制

BCI 技术还不成熟, 不过带一两个传感器的检测眼球运动的东西早就有了,如果要控制的东西不复杂,可以使用 Ocz Nia,  如果要复杂一点, 可以使用 Emotiv. 唯一的不好就是要带个帽子到处走,倒没有一个随身的车钥匙大小的遥控器方便。 自从有了 WII, 我们可以 Hack 一个 WII Remote, 然后在家挥一下 WII Remote, 就可以让灯亮起来。 要是 WII Remote 再小一点,或者自己买一个加速传感器和位置传感器粘在筷子上, 就很有魔棒的感觉了,到时候对着灯一点,灯就亮了, 哈里波特保证拜你为师 :)

4. 传感器通信

我家现在卧室的门上面都装了一个红外发射器(垃圾堆上捡了个电视遥控器,用了里面的红外发光二极管)和一个接收器,人进入屋子的时候会切断红外线一次,我就自动打开屋子里的灯,本来是贴在地上的, 可是我们家的猫老是走来走去,干扰系统,所以我不得不放在半人高的地方,可是这些器件总是要拖很长的线才能把信号送回去,我现在放半人高的地方,线拖下来, 猫就老在我接出去的线上面蹭痒,搞得系统三天两头挂掉。 各位知道有没有什么便宜的无线协议,能够把这些小器件之间的无线通信问题解决? 市面上的 WIFI 传感器都要大几十美元一个,不够便宜,这些小器件走 X10 也不行,我家没那么多插口, 而且我还得投资 TTL 到 X10 的接口。 蓝牙和WIFI 模块都太贵,RF 技术我是白痴,而且也不知道怎么做一个不互相干扰的系统,各位有高人指点指点?

5. 微型化计算机

我最近找了一些不带风扇的,可以跑 Linux 的作为家庭媒体存储中心和控制中心的计算机, 我的要求是体积要小,耗能要低,可以放在客厅或者锁在锁在壁橱里面。 其实一个几十块钱的二手计算机就可以干这些事情了,但是噪音太大,长得难看,实在不适合放在客厅。

还有就是接口,至少要支持一些 USB 口,这样我外面才能接其他的外设。 我找了一顿没找到什么好的。 各位有什么建议? 我目前找到的包括 WD My Book World Edition, 中科梦龙盒子(太贵), Foxboard, 和 Marvell Plug Computer. 或者自己 DIY 一个 ATOM 芯片的机器, 或者买一个 ARM 开发版, 或者 Hack 一个  20 块钱的二手 TiVo. 我现在还在这些技术之间纠结,想要找性价比最好的。

同时我还想搞一块很节能的液晶面板,带触摸的,算是家庭控制中枢,可以看到所有的灯和传感器的工作情况,就是不知道有便宜的小触摸面板没有?

我的目标是建立一个智能的,让我安居乐业的家。 各位读着还有什么奇妙的想法?

前几篇我已经提到了完全用命令行工作的妙处。 我提到了聊天用的 Freetalk, 查邮件用的 Mutt 等等。这篇完结篇中,我把以前没提到的零零碎碎的完全基于命令行/键盘的用法写出来.

在苹果下, 我用的 Launcher 自然是 Quicksilver. 在 Linux 下, 我一般是直接用命令行. 偶尔用用 GNOME Go, 不过基本上还是用命令行.

窗口管理器上, 我现在用的是 awesome windows manager. 这个窗口管理器支持多屏幕的纯键盘操作, 我强烈建议天天只用 Firefox 和一个编辑器一个命令行的程序员们尝试一下这个窗口管理器。 这个窗口管理器还有一个好处,就是所有的窗口控件都可以脚本化,所以,可以随意在状态栏加时间状态啊,按钮啊, 等等。 而且这些按钮啊,状态阿,都是可以在运行时用脚本修改的。比如你可以定时让状态栏闪动,只需要在 cron 脚本里面写一条就行了, 让控制闪动的脚本按时运行。

现在我聊天还是用 Freetalk. Freetalk 有一个非常好的特征,就是可以任意的加插件。 我写了一个插件,让我在工作的时候,除了爸妈,未婚妻或老板给我发消息触发一个“滴”,其他消息一概不响。这样非常集中精力。 有时候不得不上 MSN, 我就用 centerim 和 centerim-utf8 (后者支持汉字), 不过我极少用,一个主要原因就是我不知道怎么写插件。 这些不让我 hack 的软件基本上都不是太顺手的。

除了写程序和发邮件聊天,剩下的就是上网了。 自然,我上网是 Firefox。 我用了一个叫做 vimperator 的插件,可以纯键盘的用 vim 的方式控制 Firefox. 这个插件可配置性极强,基本上日常用到的翻页,开关标签和搜索,都可以一键完成。 如果您是 vim 的超级粉丝,这个插件肯定让你觉得上网冲浪从来没这么爽过。 以前我常常用 ubiquity, 不过现在鼠标被我拔了,所以”选中一段文字”这样的操作我基本不用,所以 ubiquity 用的相对少了。

还有就是看 pdf 了,我要推荐一个中国人开发的软件,叫做 apvlv。 这个软件可以让你用vim 的方式看 pdf. 比如光标往下走,直接按 j 就行了, 非常方便。 我现在看 pdf 基本上就用这个了, 每次文件另存为的时候只要 :w, 实在是大大提高效率。

最后,我在文本字符下面也发现了一个类似于 awesome 的咚咚, 叫做 screenwm. 这个软件, 可以让你横着或者竖着切分屏幕成任意的组合, 在每一个小单元里面,相当于运行着一个 GNU Screen 窗口。 所以,在我的宽屏上,我的左边是 vim, 右上面是 mutt/gtalk/todo, 右下面是 shell, 工作起来不要反复切窗口, 非常舒服。

如果您有什么完全用键盘工作提高效率的妙招,不妨留言告诉我 :)

我们都知道, 著名的 SETI 项目, 是用 NASA 高分辨率的射电望远镜收集宇宙各个角度的电磁信息, 然后通过分布式的计算, 寻找外星人. 其实呢, 我们完全可以发挥山寨精神, 用您的手机, 笔记本电脑, 或者任何电子设备, 去检测有没有外星人的存在. 怎么检测呢, 我来一一道来.

首先, 我们说原理. 我们这个宇宙中存在着一种无处不在的辐射, 叫做宇宙背景辐射. 这种辐射, 是一种微弱的电磁波, 一般科学家认为是大爆炸的遗迹. 这种微弱的电磁波, 一般情况下对电子设备和人, 都是没什么影响的, 因为这些电磁波太弱了.

可是, 假如有外星人, 并且外星人发展到了和人类文明相当的地步, 那么外星人就会发射电磁信号寻找宇宙中的同类. 这时候, 我们接受到的电磁信号, 就会有一个方向稍微强一点. 我们可以放大这个信号, 这样, 各个方向的电磁波信号就有显著的差异. 这时候, 如果我们自己做一个土制的天线大锅, 就像这位土制无线网一样, 然后把电子芯片放在大锅的焦点, 可以想像, 这个电子芯片就会收到很多的电磁干扰. 通过一系列的理论计算, 我们可以得出, 国产 MTK 平台的塑料外壳的山寨机, 正好能够抵御宇宙背景辐射. 但是在一米直径的增强天线的聚焦下, 对于超过0.001 mW 的电磁信号, 就会产生比较明显的反应, 比如死机, 蓝屏, 或者重启.

基于这个, 我们可以这个做: 自制一个山寨版的大锅(可以在五金商店购买大锅, 不过为了环保, 可以自己用纸糊制, 内侧贴锡箔), 然后买一个山寨机 (极其重要: 一定不能买有 CE 认证的手机, 因为那些手机是屏蔽了电磁辐射的), 然后, 把您的手机开着, 抓着这口大锅做 360度旋转, 如果您的手机在旋转到某个方向的时候突然蓝屏了, 恭喜您, 您定位到外星人了.

那么, 感兴趣的朋友要问了, BP 机行不行呢. 当然行, 其实不光 BP 机可以, 任何电子器件都可以. 但是考虑到微波炉和冰箱等电子期间没有蓝屏功能, 也不便于旋转, 所以没有手机方便. 国产山寨手机价格便宜量又足, 本人强烈推荐.

注意: 检测时注意远离无线基站和高压电线, 防止干扰. 北半球南半球用户只能检测一半星空, 所以检测不到外星人也不要沮丧. 另外, 月黑风高之时, 正是没有其他恒星干扰之时, 检测效果俱佳.

那么, 有的宅男宅男和程序员朋友要问了: 有没有在家就可以检测外星人的办法哩. 当然有啦, 这里奉送一个 C 程序片段:

volatile int x = 0;
volatile int y = 0;
while (1) if (x != y) {
printf(”检测到外星人啦\n”);
y = x;
}

快掏出您心爱的手机, 检测外星人吧.

上篇我们说到 Tit for Tat 的策略有一个极大的漏洞, 是什么样的漏洞呢? 我们不妨先用通俗的例子理解一下.

假如现实生活中有两个人 A 和 B, 都是认为自己非常理智, 而且严格执行”以牙还牙”策略的人遇到了一起, 会发生什么样的事情呢? 我们按照他们初始的策略, 分三种情况讨论.

1. 假如 A 某次不小心招惹了一下 B (执行了被 B 解读为 D 的策略), 按照 B 的策略, 必然会在下一轮执行 D 策略 (报复). 而 A 对 B 初始是执行 C 策略 (合作) 的. 在 B 报复之后, A 下一轮就会采用报复. 而相反的, B 在本轮看到 A 合作之后, 下一轮就会报复. 如此往返. 不难看出, A 和 B 会陷入彼此报复的怪圈当中, 用大白话说, 就是所谓的冤冤相报何时了.  更加糟糕的是, 博弈的双方都认为自己是完全理智而且愿意合作的, 但是就是因为正好彼此差了一步, 因此从A的角度看B, A 会认为 B 是一个完全不懂得合作的蠢货 (A 提出合作的时候B正好报复). B 看 A 也一样. 现实生活中我们也能发现这种例子, 比如两个性格很强的人遇到了, 在某件事情上不投合, 结果成了一辈子的仇人, 还互相认为对方是傻X. 此时, 双方都得不到期望的最大受益.

2. 如果一开始双方都采用 D 策略, 则可以遇见, 这样的 D 策略将持续下去, 没有一方会主动的让步, 因为先让步的一方必然吃亏. 现实中, 我们也能观察到这样的事情, 即博弈双方仇怨越积越深, 最后到了不可化解的地步. 此时, 双方都陷入了囚徒困境.

3. 如果博弈的双方一开始都采取 C(合作)策略. 那么, 博弈双方则能够永远的友好合作下去, 获得最大的受益. 此时, 双方获取的受益都最大化了.

从上面的分析我们可以看到, 在多轮囚徒困境的情况下, 如果有多个 Tit-for-Tat 策略参与, 那么每个的受益, 极端的依赖于初始状态的设定. 在数学和计算机科学中, 这样的系统, 叫做”初值敏感系统”. 一般认为, “初值敏感系统”是非常不好的系统, 原因在于缺乏”鲁棒性”. 这里我走一下题, 解释一下初值敏感系统和鲁棒性这两个概念.

大家都知道有一个叫做”蝴蝶效应”的东西, 大体是说, 一只蝴蝶在巴西扇动翅膀,有可能会在美国的德克萨斯引起一场龙卷风. 原因在于, 这只蝴蝶翅膀扇动的气流, 引起的一个小小的搅动, 可能会在系统中被各种各样的因素放大, 最后演变成一个非常显著的效应. 中国也有一句古话, 叫做差之毫厘, 谬以千里, 说的都是, 初始的微小变化, 都能引起最后结果的显著不同. 我们这里的初值敏感系统, 和蝴蝶效应也是类似的, 能从小的摄动引发出显著的后果的. 比如大家都知道, 在”一只馒头引发的血案”中, A 在很不经意的情况下, 对B 采用了 D 策略(抢了馒头), B 由此产生了报复, 搞得 A 国破家亡.

显然, 面对这样的系统, 人类即使有模型, 也是很难预测未来的, 因为初值条件在测量上的一点点微小的误差, 都能造成预测的结果的巨大不同. 为了表征这个特性, 我们把”不对初值敏感”的特性成为鲁棒性 (Robustness). (这个鲁棒, 您可以直接理解为山东大棒, 结实, 抗得住外界的一些摄动).

聪明的读者要说了, 即使系统不鲁棒, 我们能不能设计好初值, 使得系统沿着最好的方向演化呢? 答案是不能. 因为任何一个客户端拥有的上传和下载的带宽都是有限的, 有限的资源必然会导致资源的竞争, 从而导致必然某些请求不能满足. 在这种情况下, D 策略是不可避免的. 况且, 网络情况复杂多变, 即使双方都有意采取 C 策略, 很可能因为网络的复杂性, 双发获得的受益不对等, 从而引发一方采取 D 策略. 所以, 如果 Tit for Tat 这种初值敏感策略放到 P2P 客户端中, 结果是不可想像的, 因为这时候每个客户端都是碰不得的刺猬, 一旦在某个时间点某个节点出现了差错, 很可能整个系统都陷入”冤冤相报”的死结, 让整个网络没法完成文件的传输, 反而忙着互相报复和自我保护.

从上面的分析我们看出, 靠精心设计初值来维护这个系统是不现实的, 我们需要设计的, 是一个好的策略, 使得不管初值怎么变, 系统中每个个体依然能够获得较大的收益.  那么, 怎样设计这个鲁棒的系统呢? 我们从极端的两个例子开始, 一种是不管别人怎么出牌, 永远合作的; 另一种是或者不管别人怎么策略, 永远背叛的. 这两个都很鲁棒, 都很”彪悍”. 但是毫无疑问, 效用不见得最大化.

从这两个极端的例子表现不怎么好来看, 我们的确应该要根据对手的策略选择自己的策略, 同时又不能非常的依赖于对手的策略(否则就初值敏感了). 那么, 最简单的方法就是: 我们以一定的概率去执行以牙还牙, 但是也允许以一定的概率不管上次选什么, 这次和对手选择合作(跳出怪圈). 这样, 因为随机性的引入, 对初值的依赖就随着时间的流逝越来越小了.

在多个人的环境中, 我们的确愿意和对手选择随机合作, 但是因为资源的限制, D 是不可避免的. 但是我们不会让 D 永远下去, 我们每轮和随机的对手选择一次随机的合作, 这样就不会被怪圈所左右. 这个就是 bt 协议跳出冤冤相报的精髓. 一旦知道了这个, 本文思想就差不多介绍完了. 下面就是程序员的编码工作了. 下面的内容完全是基于 Bram Cohen (bt 协议创始人) 的经典论文 “Incentives Build Robustness in BitTorrent” ( http://www.bittorrent.org/bittorrentecon.pdf ) 里面的内容展开的. 我只介绍和博弈论有关的部分. 读英文更加习惯的读者直接看原论文比读下面的文章更加好.

首先说点背景知识, bt 把文件看成一块一块的, 并且用一定的排序算法决定现在能够下载哪一块. 其次, bt 协议同时和多个机器之间建立 TCP 连接, 但是采用堵塞的方法控制传输. 因为建立连接代价比较大, 所以 bt 协议维持连接不变, 在其上采用 choking (堵塞) 的方法来执行 D 策略, 采用 un-choking 的方法 来执行 C 策略, 而不是每次都重新建立和取消连接. IP 协议在这方面有天然的优势.

每次, BT 协议选择 k (通常为7, 限速的情况下为2, 3, 或 4) 个其他的客户端来执行 C 策略(即给上传). 在上一轮中给出最多下载的那些节点, 在本轮将被执行 C 策略(注意到有的节点上一轮并没有给上传, 即从C 到 D). 同时, 为了避免其他的更加好的节点被忽视, 每 m 轮, BT 客户端选择一个随机的 choke 了的节点执行 C 策略 (即从 D 到 C. 同时, 因为资源限制, 必然有一个被 choke 了, 即从 C 到 D).

那么, 什么时候执行 D 呢? 在 BT 协议中, 假如连续 n 轮, 都没有从一个节点收到任何下载, 在 bt 术语中, 这个叫做 snubbed. 这时候, 则该节点认为自己被那个结点执行D策略了. 作为报复, 自己也停止对该节点的上传(即以牙还牙, 从 C 到 D. ). 除非等到下次随机的选到了那个节点(再次到 C ).

这就是 bt 的协议关于博弈论的全部. 其中, 一轮持续时间在现在的实现中是 10 秒. m 为 3, n 为 6. 目前暂不清楚 Bram Cohen 是否通过实验得到这些参数, 有兴趣的读者可以自己查阅 bt 源代码, 改一下, 看看哪个更加好. 同时, 因为其他客户端采用的是 Tit for Tat, 想把自己的客户端改成 吸血bt 是不可行的, 也占不到别人便宜.

PS: 有兴趣的读者可阅读 bt 源代码中的 Choker.py. BT 源代码用 Python 写成, 比较好懂.

我考研的那会儿, 研究北大计算机系历年考研的试题, 发现几乎每年都会很常规的问一道选择题 给定进栈序列是 123456, 问选项中哪个是不可能的出栈序列的题目. 我觉得这个题超级简单, 标准解法应该满天飞, 可是就昨天, 还有一个刚考了研的哥们给我发信问这道题的“快速解法”. 我想想也是, 北大出的那本离散数学的教材上, 的确是没有讲怎么去算, 我也没有翻过其他的国内教材, 不知道哪本教材覆盖到了. 不过当时和我一起考研的同学, 看了很多参考书, 似乎也都不知道这个方法, 我还讲给他们听过. (如果哪位读者知道国内哪本教材讲到一下的方法的,可以提醒我一下)

方法不是我的, 是TAoCP 的. 我就直接抄书了. 参见 TAOCP 第一卷 2.2.1 习题 5.

5. [M28] Show that it is possible to obtain the permutation p_1 p_2 \cdots p_n from 1 2 \cdots n using a stack if and only if there are no indices  i< j < k such that  p_j < p_k < p_i .

下面是随便拷贝的网上的几条考研题 (http://www.vipkaoyan.com/dl-149-4039-0-8587.html)
瞬间可以看出答案分别为:

D, B, D, D.

7. 设栈的输入序列是1,2,3,4,则( )不可能是其出栈序列。

A. 1,2,4,3, B. 2,1,3,4, C. 1,4,3,2,

D. 4,3,1,2, E. 3,2,1,4,
【中科院计算所2000一、10(2分)】

8. 一个栈的输入序列为1 2 3 4 5,则下列序列中不可能是栈的输出序列的是( )。

A. 2 3 4 1 5     B. 5 4 1 3 2        C. 2 3 1 4 5        D. 1 5 4 3 2

【南开大学 2000 一、1】【山东大学 2001 二、4 (1分)】【北京理工大学 2000 一、2(2分)】

9. 设一个栈的输入序列是 1,2,3,4,5,则下列序列中,是栈的合法输出序列的是( )。

A. 5 1 2 3 4    B. 4 5 1 3 2     C. 4 3 1 2 5     D. 3 2 1 5 4

【合肥工业大学 2001 一、1(2分)】

10. 某堆栈的输入序列为a, b,c ,d,下面的四个序列中,不可能是它的输出序列的是( )。

A. a, c, b, d    B. b, c, d, a        C. c, d, b, a        D. d, c, a, b

【北京航空航天大学 2000 一、3(2分)】【北京邮电大学 1999 一、3(2分)】

TAoCP 是大宝藏, 这废话就无须多说了.