春夜散记

今天（准确的说应该是昨天吧）从实验室出来已经快12点了，回到青年公寓时，路上已经没有什么人了，和煦的春风吹在身上，感觉是如此的惬意，突然之间，心底的某种东西打断了自己那份匆忙，不自觉的漫步在深夜的“校园”……

头一次发现，青年公寓的夜色也可以如此美丽，躲藏在无数高楼中间的那一小块草坪，在今夜的春风里，散发着迷人的气息，让我有一瞬甚至产生了置身于交大芳花园的错觉，那温爽的风仿佛来自明湖，却又恰如其分的少了那股鱼腥味……

第 一次走到那一小片健身场，也让我想起了大一时，每晚上完自习都会到东区操场边的健身器材处做一下推举。不过这里的健身器材真可谓“男女分明”…… 一边全是单双杠等全靠臂力玩的东西，一边又全是脚踏，手转之类的主要供女生使用的器材。我是历来不会玩单双杠的，再加上现在这体重，估计上去手就折了……

路 边偶尔有人经过，都是行色匆匆的进入各自的宿舍楼，看着他们匆忙的脚步，我突然想，这么美丽的夜晚，难道他们就没想过停下来，享受一下几分钟的宁静。回过 头来，我为自己突然有了这样的想法感到吃惊，进而发现我已经很久很久没有过因为喜欢某个环境而静静的独处于其中了，而这种独处又显得那样的熟悉，细细想 来，年少时候的我似乎经常这样。而进入高中以后，我似乎被我国的教育“成功”的培养成了一名纯粹的理工科学生……之前的许多个夜晚，我也和那些路人一样， 匆匆忙忙的回到宿舍，课业，项目，论文，老板……种种压力下，我们变得很“专注”，专注地抄作业，专注地写代码，专注地编论文，专注得对身边的美视而不 见……

虽然已经过了12点，但几乎还有一半的宿舍亮着灯，我很好奇大家都在做些什么，是在写东西，看论文，还是像我往常一样进行一些临睡前的娱乐……

走 着走着，看到了路边的一只野猫，和交大校园里常见的野猫一样，长得很不起眼。它警惕的望着我，我站着没动，突然好想摸一摸它，我尽量让自己的动作看起来很 友好，慢慢地蹲了下去，可在我的手轻轻的伸出去时，它还是跑了。想起小时候的我是很喜欢小动物的，狗，猫，兔子，鸟，鸡，鹅，喂过的动物也不少，可自从高 中以后，就再也没有接触过这些小生命了……

虽然还没到四月，但这暖暖的春意还是让我想起了一代才女林徽因先生那首著名的诗 (据说清华建筑系的师生提起林徽因都尊称先生，我想，这应该是对一位女性最尊敬的称谓了)--《你是人间的四月天》。林徽因先生是建筑学出身，纯正的工科 血统，却也是一代才女，似乎那个年代各个学科的专家，都有很深的文化底蕴，至少都有着扎实的文学功底，不至于像我们现在，只会写点科技论文，还经常写得词 不达意，现在看来，我国的文理分科教育真的很失败！

就在我有些不舍的走进宿舍楼时，我还在想着原来北京的春夜也很迷人，但嘴里的异样感让我忍不住吐了一口唾沫，看着发黄的唾液，我砸了砸舌，感觉到了那该死的沙子。一想到刚才那么舒适的春风里竟然夹杂着这许多看不见的沙尘，好心情顿时低落了不少……

唉，北京……

附：

你是人间的四月天

我说你是人间的四月天；

笑响点亮了四面风；轻灵

在春的光艳中交舞着变。

你是四月旱天里的云烟，

黄昏吹着风的软，星子在

无意中闪，细雨点洒在花前。

那轻，那娉婷，你是，鲜妍。

百花的冠冕你戴着，你是

天真，庄严，你是夜夜的月圆。

雪化后那片鹅黄，你像；新鲜

初放芽的绿，你是；柔嫩喜悦

水光浮动着你梦期待中白莲。

你是一树一树的花开，是燕

在梁间呢喃，你是爱，是暖，

是希望，你是人间的四月天！

阅读全文...

双信封悖论

自从沉迷于DOTA之后，好久没有更新blog了，先转一个很有趣的问题。

以前在这里看到过一个小故事：


现在有两个人，"酷毙"与"帅呆"，正在花园里一边喝着酒，一边讨论关于精灵的神话。正好有个精灵从此经过，被他们的对话吸引，精灵认为在这个时代，还有人这样仰慕和了解他们值得鼓励，于是便决定给这两个人一点奖赏。于是，他把一笔钱放入两个信封，将信封分给"酷毙"与"帅呆"，出于喜欢恶作剧的个性，精灵透露，这两个信封里金额不同，其中一个是另一个的两倍，但他没有说哪个多哪个少。然后精灵随着一缕轻烟消失无踪。

在精灵消失后，两个人拆开信封，偷看自己拿到的那笔钱，同时心里忖度着，自己到底拿到多的那份？还是少的？" 酷毙"心想：这是笔意外之财，我拿到的数额已经很不错了，如果这是多的那份，"帅呆"就只有我的一半；不过，他也可能很走运，拿到我的两倍。再回顾整个过程，精灵是先把钱装好，密封之后才随机发给我们，因此这是一个对等赌局，两人拿到大份的几率是一半一半。所以也许我应该跟"帅呆"谈个交易，互相交换。既然我赢得一倍金额和损失一半金额的几率都是50%，则仍有期待净利：我的交换期望收入将是现在所有的 1/2*2+1/2*1/2=5/4倍。根据决策原则，"酷毙"认为这对他相当有利，便决定和"帅呆"交换。即使"酷毙"没有拆开信封也可以作出相同决定，因为支票的面额并不影响整个思考逻辑。"帅呆"以同样的方式思考后，也认为与"酷毙"进行交易对自己较有利，于是当"酷毙"一提出交换的建议，"帅呆 "马上欣然允诺。

两人的情况完全一样，都认为自己能遵从一定的逻辑推理规范。那么，有没有可能两人同时都是对的呢？毕竟这是个零和游戏，"酷毙"赢就等于 "帅呆"输，反之亦然，既然不能双赢，就一定有人是错的。但这两人不都是经过缜密逻辑思考了吗？

.....

当时看完之后也只是觉得有趣，也没有再认真去想为什么，时间长了也就忘了，直到今天又在这儿看到了解答。


问题：你有两个信封可以选择，每个信封里有一定数量的钱，已知其中一个信封里的钱是另外一个信封的两倍。你可以选择一个信封，打开之后你能看到其中的钱的数量。现在你可以选择是否更改你的选择。

推断：你应该更改你的选择

1. 假设你打开信封后发现里面钱的数量为A。
2. A是较小的钱数的概率为1/2，为较大的钱数亦为1/2。
3. 如果A是较小的钱数，则另一个信封里钱数为2A；
4. 如果A是较大的钱数，则另一个信封里的钱数为为A/2。
5. 所以另一个信封里的钱数的期望为 E = 2A×1/2+A/2×1/2=5A/4，大于A。
6. 你应该更换你的选择。

想想看，这个问题和推断是不是有点像围城效应？

很显然，上面的推断结果是有问题的。关键在于第二条，如果上面推断中的第二条成立的话，我们假设P(A)为两个钱包里的钱数为（A/2，A）的概率，那么将有P(A)=P(2A)，从而有一个定义在一个无穷集上的均匀分布，这是不可能的。


阅读全文...

最可爱的“老男人”

没想到他们的节目竟然放到零点之后，幸亏没有错过，看到一位网友说的好，这几个“老男人”拯救了09春晚……



阅读全文...

随机抽样算法

前段时间，做移动研究院的项目时，曾经遇到过这样的需求：需要从n条记录中，随机抽取m(n>>m)条数据，因为数据量很大，n可能上亿，所以要求每条记录只能读取一次，也就是说在读入一条数据后，就要马上等概率的判断要不要选择它。

这个需求当时让我大伤脑筋，让我再次感叹，要是早点看到《Programming Pearls》就好了……

我当时想当然的认为一个数被取中的概率是1/n，所以貌似可以直接rand()%n == 0就行了，但是这样的问题在于你无法保证最终取出的正好是m个数。这种做法最终正好取出m个数的概率本身就够小的……

由于当时的需求只要求一个大概的数，不要求十分精确，比如从几千万条中随机取一万条左右，我也就那样糊弄过去了。

其实，如果你够聪明的话，应该已经看出了我的错误，没错，从n个数中选m个数，对于某一个具体的数k，其概率不是1/n而是m/n，我们做一下简单的组合运算就知道了：这个概率等于C(n-1,m-1)/C(n,m)，化简之后就是m/n。

如此一来，第一个数被选中的概率是m/n；第二个数的选取概率依赖于第一个数的选取情况，如果第一个数被选中后，意味着问题转化为从n-1个数中选m-1个数，否则转化为取m个数；一般地，对于某个数k，如果之前已经选择了s(s < m)个数，那么k被选中的概率就应该是(m-s)/(n-s)。

这样，我们就可以得到如下代码：

void sample(int m,int n)
{
    for(int i = 0; i < n && m; i++)
    {
        if((rand()%(n-i)) < m)
        {
            cout << d[i] << endl;
            m--;
        }
    }
}

接下来，我们可以看出，这段巧妙的代码正好取够m个数，不多也不少，不多是因为当取到m个数后,变量m变为0，循环结束；不少是因为每当n减小到与m相等时，必然会选择。
.....

阅读全文...

我的第一个Python程序

看Python好几天了，一直都是看，还没有写过，今天想试着写写《简明Python教程》中第十章的题目，但是不知道Windows下如何调用WinRAR，看了网友andelf写的这个程序之后，对其做了一下修改，写成函数的形式，让它看起来更像传统意义上的“程序”。其实也就是想多动手写写，理论联系实践嘛，呵呵。

然后将待备份文件改为列表传入，更符合原题意：

import os
import time

def backup(srcfileList,terfile):
    for srcf in srcfileList:
        tername = terfile + "\\" + time.strftime('%Y%m%d%H%M%S') + ".rar"
        order = r"C:\Progra~1\WinRAR\Rar.exe a "+"%s %s"%(tername,srcf)
        if os.system(order) == 0:
            print srcf + " has been backuped as " + tername
        else:
            print "Failed to backup " + srcf
        time.sleep(1)
if __name__ == "__main__":
    srcfileList = [r"C:\test1",r"C:\test2"]
    terfile = r"D:\test"
    backup(srcfileList,terfile)

os.system('PAUSE');

其中，C:\Progra~1\…… 其实就是C:\Program Files\……，这种目录是在纯DOS下看到的,纯DOS使用8+3文件格式,也就是说文件名最多不超过8个字符,扩展名最多不超过3个字符,长文件名就采用第7个字符为~，第8个字符为前面字符相等的文件间的相对序号。WinRaR命令的更多内容可以在命令行下键入C:\Progra~1\WinRAR\Rar.exe --help查看。

代码中，之所以要在一次备份之后，让程序sleep 1秒，是因为原题要求用系统时间作为备份文件名，但我没找到怎么取到毫秒级的时间，就只能采用这种折中方案了……

.....

阅读全文...

同样是排序，C++的sort咋就那么强大呢

今天看《Programming Pearls》看到快排那一章了，看着Jon Bentley从最基本的实现方式一步一步的优化出好几个巧妙的实现方法，还是很过瘾的。

不过，最后他给出了一个表格，列出了他的四种实现方式以及C里的qsort，C++里的sort之间的对比，不出所料，qsort是最慢的，而出乎我意料的是，sort竟然是最快的！

在Jon的几种方法的递进过程中，还涉及到了如何处理已经有序的数据，记得10月份的时候，我用MapReduce做实验室的项目，还遇到过这个问题，就是因为map之后的key值都是有序的，所以排序时超栈了，我在这篇日志中有详细描述。

其实这个问题解决起来也不难，Jon采用的办法是每次随机的选取枢值。我就很疑惑，这么简单的解决办法，为什么MapReduce里的排序就不采用呢？

后来想看看sort有没有解决这个问题，又写了个小程序测试了一下，对一个1000000的整型数组进行排序：

当数据为随机生成的整数时，大概需要900ms左右。
当数据为严格升序的整数时，大概需要150ms左右。
当数据为严格降序的整数时，大概需要200ms左右。

看来，sort也很完美的解决了这个问题。

既然sort这么强大，我忍不住进其内部想一探究竟，但是面对一大堆的模板，最终还是望而却步了……

总之，sort很强大，要善加利用……
阅读全文...