最近闲暇时间用C++写了个小Demo，一个小小的篮球模拟。在学校的时候看过《人工智能编程精粹》，里面有个足球模拟，看起来还比较逼真。我这个篮球模拟是比较类似的，主要好玩的地方是在于状态机。图形方面做得很简单，还是用OpenGL来实现的，另外用了一个库glui，这个东西很好，把GUI方面琐碎的事情就简化了。整个效果图如下，这可是湖人对火箭噢。 调试状态机是个很有趣的过程，每一个球队有自己的状态机，分为进攻状态、防守状态、准备发球状态，每个球员也有自己的状态机，如下图所示。这里使用的是状态模式，把复杂的转移逻辑分散到各个状态节点，这正是状态模式的精华啊。现在这个还只是个粗糙的版本，虽然看得出来有那么点意思，规则都出...........继续阅读
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]的位置。 整个实现既节省空间又速度快，强大。
(更多…)
最近在看memcached的源代码，边看边随手记录了一下。 assoc.c: 记录一个item是否存在于缓存中，这里使用了power 2扩展，primary_hashtable,和old_hashtable分别存新申请的hashtable和旧的hashtable。这里起了个线程来做拷贝的工作，当需要扩展hashtable的时候就触发assoc_expand函数，但是这个函数做的工作是备份primary_hashtable，即old_hashtable=primary_hashtable；然后申请新的空间，标识expanding为true，如果申请空间失败则交换回来。通过条件信号量，assoc_maintenance_thread把old_hashtable的数据逐步拷贝到新的hashtable中，当拷贝完了后释放old_hashtable的空间。耗时的操作用另外一个线程逐步来处理，不过查询和插入都要注意是否...........继续阅读
内存泄漏 上一次以为内存泄露查完了，发现服务器跑了比较长时间后又占用太多内存。刚好这段时间加了一些新的模块，又该查查了。整个服务器模块分的还行，但是中间经过几个人一起写，所以看起来就麻烦了。要解决问题还是必须找到泄露的代码段。在C/C++中，只要用了指针这东西，很多逻辑上的问题也会产生内存泄露。在线下用上次封装malloc和free的方法测试，找不到产生内存泄露的样例，grep了一下没有用原来的malloc之类的东西啊，那就应该是测试数量太少的问题。没法，从线上的log中导入一些天的访问记录，其中包含了一天的访问url。试着用Python写个小程序把一天中所有的url依次往线下的服务器发送，这应该有几万条数据了。Python中这相关的库...........继续阅读
cflow cflow是个比较古老的程序(好像比我老一岁)，主要是用来打印C程序的函数调用关系，通过函数调用关系能大概看一下程序的流程。最近看了一下这个程序的代码，主要分为两个小程序组成。首先是prcc.c这个程序，作用是读源文件，提取出函数名称，然后生成一个函数列表。第一列是调用函数，第二列是被调用的函数名称(如果是函数声明则这两列相同)。第二个程序prcg.c是读取函数关系，里面建起一个有向无环图。根据这个图加上缩进打印出函数调用轮廓，这里有一个例子。最后是一个脚本cflow.sh，其核心代码就是。 prcc demo.c | prcg 这是典型的通过管道把小程序组起来的例子。 life is short , use Python 闲着的时候在这个程序上做了些小工作。既...........继续阅读
以前写的一些程序运行一段时间后占用的内存越来越多，估计是内存泄露了。服务端的程序要长时间的运行，内存泄露是个很严重的问题。于是再检查程序，很崩溃的是还有另外一个模块不是自己写的，看起来很麻烦。看了半小时后发现一些问题，但是还是不能保证是否完全解决了。同事让我用以前他们写的一些函数，对应的为MALLOC和FREE。仔细看了一下觉得很不错，其实就是把malloc和free函数封装了一下，用来记录申请空间的文件和代码位置，使用方法就是用MALLOC和FREE替代原来的函数。主要的数据结构是： typedef struct { long pcode; //指针 char filename[128]; //申请空间的源文件名称 int line; ...........继续阅读
