新春快乐, 祝福各位读者, 做生意的炒股的统统遇牛市,想牛逼的统统成为牛人乃至牛魔王; 当然, 买饮料别含牛奶, 买票别遇黄牛, 追求心上人别对牛弹琴. 

各位读者身体健康, 阖家幸福.

好吧, 我承认我是标题党. 其实真实的标题是: _ 书评_. 此处 girl, 除非特指, 均指美国 MM.

这书很薄, 也没有数学推导和定理证明, 几周前在书店学校花了半个小时就从前到后看完了(最后很邪恶的没买).  第一眼看到这个标题的时候, 我好奇死了. 该是怎样一个牛逼的风月高手, 才能写出<怎样和女生说话> 这样的书? 想想当年的是纽约时报的记者潜心两年, 潜入史上最隐秘的组织”搭讪俱乐部”, 获得无数一手资料之后才写出来的. 这本”怎样和女生说话”, 想必应该是 布拉德.彼特 这样的风月高手写出来的吧? 或者, 即使不是风月高手, 也是心理学家或者带着博士帽的”女性文化研究”专家吧?

背面一看, 靠, 原来是个9岁的小孩子写的. 用我们苏北话说, 太牛X了!  我问我自己, 假如我有一个小孩, 9岁, 要写本<怎样和女生说话> 的书, 我会让他出版么? 不会, 因为我小孩子懂什么, 还不是过家家? 可是小孩子写的, 恰恰是最简单最朴素的真理. 比如: “如果你对一个女孩说 Hi, 她也对你说 Hi, 这就是一个好的开始”, 一语道破搭讪的所有诀窍. 不少人肯定不服气, 说, 九岁的小孩子的朴素道理也是朴素道理罢了, 难道”和女生约会的时候穿得要好看一点” 以及 “不要惹太漂亮的” 这个道理成年人不懂? 怎么要小孩子来教育?

错了, 全错了. 原生态的著作, 如不加奶粉的三聚氰胺 (错了, 是不加三聚氰胺的奶粉) 保证喝下去顺畅. 加了三聚氰胺的, 小仪器一检查, 哼, 蛋白质含量很高嘛, 咦, 怎么肾结石了?  原因在于, <把妹达人> 这样的书, 理论性太强, 看上去充满营养, 其实实践性太弱, 消而不化. 看得时候自信满满, 仿佛立即成了把妹达人, 做的时候如同小学生, 连“做原来的自己”都做不到了, 最后就领一张好人卡 (或者一张猥琐男卡), 或者想搞点技巧搞成了怪蜀黍. 每逢此时, 一个穿越千年的老和尚的声音就在你耳边响起 “施主, 易筋经可不能强练, 轻则走火入魔, 武功全废; 重则经脉错乱, 神智不清.” 因此, 读那些书, 从来都是故事穿肠过, 没啥心中留. 而读读原生态的书, 看看在九岁的小男孩的眼里, 怎样和九岁的小女孩说话, 说不定别有一番启发呢.  况且从数学意义上说, 女大十八变, 模九还是零, 所以, 用对付九岁的技巧对付十八岁的, 从理论上来说是等价的.

这书还有个特点, 叫做语言直白, 直指人心, 堪称当代追美国MM的坛经. 比如说吧, 这位小师傅说: “Life is hard, move on! Or sometimes it just doesn’t work out. I had a crush on a girl in preschool. Then my family had to move, so I had to let her wash out of my mind.” (人生苦短, 即时行乐. 如沉迷过去, 将不得解脱. 我曾在幼儿园的时候有意中人一枚, 因搬家之故, 不得不学太上忘情).   唉, 这样的境界, 该多少痴男怨女学习啊. 如果我们把幼儿园换成什么兰香桂坊的, 那就是”寒蝉凄切, 对长亭晚”的婉约. 把第一句换成”人生得意须尽欢”, 就是李白同学的境界. 多高妙的境界啊, 试想, 没这么直指人心的纯朴小句子, 哪能直接触及到成年人内心的小波澜?

书店里面类似于怎样和女孩说话, 怎样赚大钱等等的真理到处都是, 这是一个人生精华泛滥的年代. 所以我想, 一本书改变一生之类的说法有点扯淡, 也不必指望, 不妨先学习小师傅一下, 装备一下发现真理的”纯真眼神”, 从最朴素的大道理入手. 等朴素的大道理知道了, 熟稔了, 学会观察得到结论了, 说不定, 很快就可以和一个美国 MM 约会了.

忘了说, 这位小师傅叫做 Alec Greven. 让我们紧密团结在以小师傅为首的团伙周围, 高举“怎样和女生说话” 的红宝书, 人人行动起来, 装备起来, 勇敢的和美国MM约会吧.

附纽约时报书评: http://www.time.com/time/arts/article/0,8599,1865128,00.html

上篇我们说到 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.

1. [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.

1. 设栈的输入序列是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分)】

1. 一个栈的输入序列为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分)】

1. 设一个栈的输入序列是 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分)】

1. 某堆栈的输入序列为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 是大宝藏,　这废话就无须多说了.

自从11月4日 Obama 赢得大选之后, 我看国内媒体对美国政治的关注就明显降低了. 其实对于我们这些民间人士来说, 认识美国民主制度的核心和稳定的根基, 不在于大选日那天的隆重和获胜演讲的煽情, 而在于大选之后的一系列操作. 我举几个例子说明:

1. 新总统就职之日, 是旧总统下台之时. 这个权力交接如何才能平滑呢? 权力交接究竟是像某些国家一样领导人生病了都藏着噎着, 或者等上代领导人把亲信都插好了等下代阿斗上代, 是任何一个国家, 任何一个组织必然面临的问题. 我们可以从美国的权力交接, 体会一个良好的制度是怎么避免人亡政息的. 最受爱国青年讨厌的 CNN, 每天都有叫做 “Transition of Power” 的节目, 整天关心闲得蛋疼的问题, 比如中东局势怎么收场, 经济怎么继续救市. 依我看,这时候要大面积歌颂这八年的伟大发展成就, 宣传小布什的光辉思想才是.  你说整天扯什么这个提名的部长和前任的区别, 那个部长和总统的打篮球关系有啥伟大的? 这些对于对小布什这样的国家领导人落井下石且不弘扬主旋律的反动媒体啊, 大家给狠狠的记住他们的名字.  

2. 总统不是想指定一个内阁, 就能制定一个内阁的. 这些提名的人, 都要经过国会的听证. 在美国的观众可以观看美国国会的免费24小时频道C-SPAN, 看看这些明天就要当部长, 首席大法官的人, 是怎么在国会被听证的. 因为国会要保证总统指定的人过关, 所以会把若干年前的丑闻揭出来, 一一质问. 看看那个架势, 完全就是审问犯人似滴. 比如今年一早首席大法官的提名者 Eric Holder, 在国会被揭出貌似若干年前和什么违法的事情有关(我没注意听), 就看见这哥们辩解得满头大汗. 没办法, 国会听证的那帮人都是老爷, 他们不满意你, 把你否决掉, 总统还得重提名. (这个事情就发生过, 详情可读林达的<近距离看美国>). 天朝观众可关心国会是怎样把好端端的部长候选人问出一身冷汗的. 哼, 这些作威作福的大资产阶级的代言人, 你们也有今天, 在无产阶级发出的质问面前发抖吧.  

3.  本来总统啊, 内阁这些人啊, 大多都是参议员. 所以, 他们到行政分支上班之后, 相应的职位就要别人替代. 花钱买官的事情到处有, 比如伊利诺伊周州长, 就号称能把奥巴马空下来的名额卖给别人, 大家竞标吧. 结果, 被联邦政府(准确的说是被牛逼的FBI )抓住了, 结果州议会现在弹劾着这哥们呢. 用中国话说, 相当于一个省长吧, 公布价钱, 卖一个官位, 被联邦的纪检发现了, 罚了4500 块钱(联邦政府还没权双规他, 因为他是伊利诺伊人民选出来的). 然后, 到了省里面, 人民不高兴了, 要弹劾他. 这哥们脸皮还厚, 就不辞职, 等着被罢免. 估计最后以省人大罢免他为结果.  跟踪这个事情, 就会理解为啥联邦政府只能罚钱, 不能发红头文件也不能双规; 州政府才能罢免, 但不辞职还不能强迫辞职 等一系列的美国社会的运行方式. 如果您就把他当成一个普通的贪官现行案, 这些小细节是注意不到的. 而在最近的媒体放大镜下, 这些细节就很明显的体现出和天朝的不同了. 当然, 我泱泱大国, 诚信为本, 卖官卖成这个鸟样的事情, 我们是从来没有滴. 

4. 1月20日乃是奥大叔的登基大典, 到时候各路媒体都会报道. 一般来说, 总统的就职演说, 基本上是未来几年的一个蓝图, 像美国这样被我党称为扛着普世价值的黑旗做世界城管的国家的大佬的讲话, 值得我们这些小摊贩关注. 这个大佬未来四年的动作, 和他任命的内阁的人是息息相关的, 所以, 从现在到1月20号, 天天任命, 天天有新闻, 而且每天的新闻, 都可以在未来四年找到注脚. 各种对政策牛逼冲天的预测, 也会趁这几天放出来. 比如古巴的卡斯特罗老先生就预测了, 说米国要股价下跌, 继续好战, 等等, 咱们看看这些大仙的预测不是蛮好玩的么. (说到预测, 卡老师上次预测奥巴马不会当选, 结果预测不成功, 害得古巴人民赌钱输给了美国不少, 浪费了好多GDP. 朝鲜金主席就比较靠谱, 比如他预测朝鲜就能够变成发达国家, 结果自己第二天就病倒了. 金老师这个能力我还是很佩服的, 我就不能预测自己第二天干啥. 这次这么好的机会, 金主席老不出镜预测, 实在有点小失望).

总之, 想更多的了解美国的方方面面各位读者, 从今天到20号, 是能学到最多知识的时候. 上面说了不少玩笑话, 最后这句绝对是真话.