标题要长！ 平常都睡到9点多才起床，今天早上3点多居然醒了，然后一直睡不着，起来随便写写。上海的冬天非常冷，还有一点点不适应，买了个电热毯。 刚才一直在想一个事情，在我毕业的时候给一个大学同学介绍了个工作，然后他就辞职去了那。昨天打电话和他聊了一段时间，感觉那边的情况不如预期，公司很多人都渐渐离去。这样心里就有些惭愧，当然我知道并不是我使得他辞职的，他那段时间正好想离职另外换工作。惭愧的原因在于我在这过程中至少当了个”说客”，帮那边公司说了一些好话，因为两边都是熟人，所以这完全不是出于利益目的。同学人很好，也没对我抱怨或者其他不满心情，这更加深了我的内疚感。这算是一个教训吧，永远不要站在自己的立...........继续阅读
来上海有一段时间了，在这段时间里一切都还好。 刚来这边一切都感觉比较新鲜，现在慢慢习惯了。在这边的生活比较规律，每天早上八点四十起来，洗刷完毕，早饭是面包片和同事磨的豆浆。这近两个月早餐都是这样，我觉得挺好的，一点都还没感觉到腻，带黑芝麻或者葡萄干的面包片真的很好吃！每天的九点钟开始出发上班，坐上两路地铁到张江一般整好10点左右。因为比较晚，所以不会赶上地铁的高峰。中午在公司附近的食堂，吃了一个月后觉得有点味觉疲劳了，主要是太清淡，和成都没法比啊。中午还会躺着休息一段，下午的精力才是最好的。公司前辈们都挺好，相处得不错，会耐心教我一些，自己在工作上面还有不少需要自己弄明白的。晚饭在公司吃，我这...........继续阅读
Python2.5的实现中有一个字符串匹配算法，在s中查找p是否存在，s的长度为n，p的长度为m。这个算法符合以下要求：
* 任何情况下都要比brute-force算法快
* O(1)的空间，O(m)的初始化复杂度
* O(n/m)的查找复杂度
* 最坏情况下不能比O(nm)时间复杂度差
* 实现简单，对于实际中的查找大部分表现良好，最坏情况出现概率小
标准的字符串查找算法不满足这些要求，KMP的时间复杂度为O(m+n)(初始化O(m)加第二部分O(n)， Boyer-Moore和其变形要求额外的空间，Python2.5里面增加了这个结合了Boyer-Moore和Sunday的思想的变形实现。来看看这是怎么个神奇的算法，KMP的思想是在每一次不匹配的情况下尽量的向右边移动，所以计算一个Next的移动下标数组。如果不匹配，最理想的情况下是向右边移动多长?应该是m，这样就能尽量减少对比的次数。所以每次比较的时候先比较p的最后一个字符，比如s=”aaaaaaad”，p=”aae”，如果从s的开头查找，只要发现第3个和p的第三个不一样，移动指标，移动多少？如果发现没有e，最长能移动p的长度，就是3。如果最后一个不匹配并且s[i+m]不是p中的字符就移动m，否则移动1。这里有两个问题：
* 如何知道s中的某一个字符是否是p中的一部分?
* 如何尽量移动m而不出现少找的情况?
第一个问题，可以用某个存储空间存下是否有p中的某个字符出现过，方便以后查找。Hash的思想，但是这里字符串查找里面再弄个Hash太无语了吧。一个简单的Bloom-filter，这里是这样实现的。
/*计算mask*/
mlast = m-1;
for (mask = i = 0; i <= mlast; i++) {
mask |= (1 << (p[i] & 0x1F));
}
/*判断s[i]不是p中的一个字符串*/
if(!(mask & (1 << (s[i] & 0x1F))))
printf("s[i] is not in pattern");
else
printf("s[i] is in pattern");
其实我们是要判断一个s中的一个字符串没有出现在p中，取低5位不是可能产生冲突么？产生冲突也没问题，就像一个Hash只要一个元素算出来的Key指定的slot没元素不就能确定这个元素不在里面了么。
第二个问题，有些巧妙。上面那个例子是因为s的最后一个字符没被匹配，所以能移动m的长度。如果这个例子s=”aaacaaaacaa”，p=”aacaa”，第5个位置都为a，最后一个匹配，但是s里面前几个其实不为aacaa，所以需要移动，但是移动多少呢?如果移动p的长度，那从第2个位置开始的aacaa就没被检查到。所以需要一个变量记录在每次最后一个字母匹配的情况下向右移动的合理偏移量，在这里为skip，初始化的时候计算出来，这最偏移量其实是计算的最小偏移量，就是移动skip个位置到第一个s[m-1]的位置。 整个实现既节省空间又速度快，强大。
(更多…)
最近都睡的比较晚，对身体不好啊。写了几行恶趣味的elisp，晚上10点40开始提醒提醒我准备睡觉，如果10点50还没动，我的上下移动键就不能用了，下面会有一条提示：太晚了，该睡觉了。不过这时可以用方向键盘来移动。但过十分钟后快捷键又恢复正常，因为过了11点表示我确实要再待晚点，下个小时40分钟继续提醒，50分锁死快捷键盘。12点过后emacs彻底对我无语了。真是egg hurt… (defun is-late-now() "Check if it is now late, emmm, go to sleep" (let ((hr (nth 2 (decode-time (current-time)))) (minute (nth 1 (decode-time (current-time))))) (and (and (>= hr 22) (>= minute 40) ...........继续阅读
很久没写咯，我已经在上海了，房子刚好弄好。 毕业之前去了青海湖，我和一个同事本来打算三天环青海湖骑行一圈的，第一天骑车148公里，第二天一早就走错了路（环行的居然走错了路），结果骑过了橡皮山，发现是已经骑了20公里左右。幸好在路上等了个回去的卡车，把我们带回黑马河。重新出发，环湖西路的路况非常好，车也很少。继续骑了120公里到达刚察，到刚察之前的最后一段感觉是最累的。第三天早上我刚出门过了个大坡，下来的时候不小心摔了一下，于是最后那一段就没骑了，真是遗憾啊。在西海镇继续住了一晚，221骑吧的店主人很好，看我摔了下巴，晚上给我做粥喝。牦牛肉粥非常好喝，嗯，非常感谢！也非常感谢同行的同事，一路给了我很多鼓励...........继续阅读
最早是在嫣牛博上乱逛，看到一个叫做”推倒柏林墙“的系列几篇文章都挺好玩的。然后在网上找了一个这系列的集合，大概这半个月时不时在看这里的一些文章，从中得到不少新的认知，因此在这里推荐一下。 不像某个小同学如此年纪有如此政治觉悟，本来我是对于政治甚至历史并不怎么感兴趣的，不感兴趣是觉得政治这东西与我相离太远，也参和不上，也不想参和上。一个室友倒是经常看一些历史方面的书籍，对此较有研究，偶尔听他的一些乱侃也别有一些风趣。以前和室友瞎讨论中，对方说某些政权很危险，若干年以后很可能会出现问题，我会嗤之以鼻，看这一副和谐盛世的样子，怎么肯可能。鄙人一直生活在这么一个人为制造出的信息荒漠中，上网翻墙的次数...........继续阅读
