肥康

OO是一种编程范型，而不只是特定语言的特定支持，所以用C来实现也是可行的。最近碰到的一部分代码都是用C实现的面向对象风格，可能是参考了Python里面的实现，Python内部实现的基本对象这块也全是这样的代码。在这里做一个小小的总结。

C语言里面没有语言层面的面向对象支持，那OO中的三个基本要素封装、继承、多态如何实现？C里面最强大的东西是指针，指针中最神奇的是void指针，这是一切的基本。首先来看封装，如何通过实例来调用方法，而对内部数据进行隐藏。完全可以写一些struct，然后写对应的函数来针对这个struct来操作，我们需要更进一步，把数据和方法绑定起来。这样写初看起来并没什么好处，后面会发现，通过函数指针去找对应的函数是多态的关键。

//object.h 
typedef struct _obj{
    char name[MAXLEN];
    int ref_cnt;
    int value;
    void (*destructor) (void* thiz);
    void (*print) (const void* thiz);
    int (*equal) (const void* thiz, const void* other);
}Obj;

//object.c destruct,print,equal定义为static 

Obj* Obj_new(int value)
{
    Obj* o = malloc(sizeof(Obj));
    strcpy(o->name,"baseobj");
    o->ref_cnt    = 1;
    o->value      = value;
    o->destructor = &destruct;
    o->print      = &print;
    o->equal      = &equal;
    assert(o);
    return o;
}

//使用方法 
{
    Obj* first = Obj_new(1);
    Obj* other = Obj_new(2);

    first->print(first);
    other->print(other);
    assert(!first->equal(first,other));
    Obj_drop(first);
    Obj_drop(other);
    return 0;
}

对于继承C当然也没原生的支持，可以在子类的定义中写入父类中的成员变量和成员函数，这里如果父类中定义的时候就是宏，直接拿过来就是。所以把父类的定义重新改写一下，分为DATA类型和TYPE类型，在Python里面就是这样，PyObject和PyVarObject是一切其他对象都包含有的。下面是一个例子People继承Object,Student继承People。

#define PEOPLE_DATA \
    OBJ_DATA \
    int age;\
    char fullname[100];
//OBJ_DATA必须放在子类新的数据成员前面，只有这样才能把子类的指针强制转换成父类指针 或者转化为Object指针 
#define PEOPLE_TYPE \
    OBJ_TYPE \
    void (*sleep)(void* thiz);

typedef struct _People_Type{
    PEOPLE_TYPE
}People_Type;

extern const Object_Type Object_type;
extern const People_Type People_type;

typedef struct _People{
    const People_Type* methods;
    PEOPLE_DATA
}People;

这里sleep为新增加的子类方法，fullname为新增加的成员变量。注释部分为特别注意的，只有在保证内存的里面数据的分布前面部分都是一样的(一个methods指针和obj_data部分)才能进行指针之间的强制转换时候不出问题。例子里面的Student类也是类似的继承People类，这里可以看到sleep这个方法不好弄，因为在People那里申明为static了，这里想复用就麻烦，所以只有再自己写一个(即使实现是一样的)，这也是C++内部帮用户做好的。可以看到通过type里面的函数指针的不同，不同对象相同的方法实现就不同了，因此实现了多态。

最后我们可以写一个基于计数的指针管理，在持有一个指针的时候调用Obj_pick,用完以后执行Obj_drop。

void Obj_pick(const void* thiz)
{
    assert(thiz);
    Object* o = (Object*)thiz;
    o->ref_cnt++;
}

void Obj_drop(const void* thiz)
{
    Object* o = (Object*)thiz;
    const Object_Type* p;
    if( --o->ref_cnt <= 0){
        for( p = o->methods; p; p=p->father){
            if(p->destructor)
                p->destructor(o);
        }
    }
    free(o);
}

按照这种OO的风格的C代码感觉要清晰一些，至少我习惯了。不过还是看个人品位吧，这样的代码风格是我另外一个同事所鄙视的。关于用C实现OO风格，还有一本比较好的书叫做Object-oriented Programming with ANSI-C，感兴趣可以看看。

上面的代码在这里下载：https://github.com/chenyukang/ooc。

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]的位置。 整个实现既节省空间又速度快，强大。
Read the rest of this entry »

最近都睡的比较晚，对身体不好啊。写了几行恶趣味的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)
              (message "prepare sleep now...."))
         (>= minute 50))))

(defun my-next-line()
  (interactive)
  (if (is-late-now)
      (message "late now, go to sleep ... baby!")
    (next-line)))

(defun my-prev-line()
  (interactive)
  (if (is-late-now)
      (message "late now, go to sleep ... baby!")
    (previous-line)))

(global-set-key (kbd "C-n") 'my-next-line)
(global-set-key (kbd "C-p") 'my-prev-line)

这样写不好看，更好的办法是用defadvice，那就不用重新绑定C-n和C-p了，defadvice可以直接在运行next-line和previous-line之前检查一下。

(defadvice previous-line (before check-is-later)
  (if (is-late-now)
      (progn
        (message "late now")
        (sleep-for 1)))) ;;just sleep 1 second

(ad-activate 'previous-line)

这样后只要执行previous-line这个函数之前都会执行我这个defadvice定义的代码，但是这样连方向键也不能移动了，因为向上这个按钮是绑定的previous-line这个函数。

很久没写咯，我已经在上海了，房子刚好弄好。

毕业之前去了青海湖，我和一个同事本来打算三天环青海湖骑行一圈的，第一天骑车148公里，第二天一早就走错了路（环行的居然走错了路），结果骑过了橡皮山，发现是已经骑了20公里左右。幸好在路上等了个回去的卡车，把我们带回黑马河。重新出发，环湖西路的路况非常好，车也很少。继续骑了120公里到达刚察，到刚察之前的最后一段感觉是最累的。第三天早上我刚出门过了个大坡，下来的时候不小心摔了一下，于是最后那一段就没骑了，真是遗憾啊。在西海镇继续住了一晚，221骑吧的店主人很好，看我摔了下巴，晚上给我做粥喝。牦牛肉粥非常好喝，嗯，非常感谢！也非常感谢同行的同事，一路给了我很多鼓励和帮助。青海一行虽然有些意外，但是也还是觉得挺不错的，那边人和风景都可以。

更多照片在豆瓣上面，照得不好，实景更漂亮，如果七月份去会更好。在从青海回成都的火车上，躺在铺上看《瓦尔登湖》，以前总没好好静下心来看完这本书，那天慢慢翻着有些入味了。“你们要尽可能长久地生活得自由，生活得并不执着才好。执迷于一座田园，和关在县政府的监狱之中，简直没有分别。” 如何生活得简单、自由，是我所难于学会的。

从青海回成都后，在学校办了一些手续，然后直接到上海了。国庆看有没有时间再回家一趟吧。在成都，走之前还和不少朋友没有聚，先记下吧，我觉得我会回成都的:)

在上海待了已经有几天了，说不上适应不适应，至少还没融入，只是一个旁观者。至少楼比成都高多了，交通比较方便也稍微有点贵。房子基本没找，有同事的一个二室一厅的，租下来就行了吧，认识的人住在一起也好些。工作上面还在适应，不少东西要好好学习一下噢。新的开始，努力一把。

最近在看一本书《Land OF Lisp》，看了大部分。离前一次看Lisp方面的书刚好三年，用Emacs也有四年了，这期间接触的多是简单的Elisp。总得来说，Lisp的书看起来是比较有趣的，这本也不错，稍微比《Practical Lisp》简单。竟然有个第6.5章，Lambda这么重要，怎么说也要占一章！第八章实现了一个小游戏。Wumpus(Hunt the wumpus)是个古老的游戏，那个年代还没有绚丽画面，只有文字界面。这里游戏的规则是：

1. 地图为一个无向图，玩家控制一个人物在图中行走，目的是寻找潜伏在节点中的一个怪兽。其中要边走边推理，得出怪兽在哪个节点。

2. 还有其他角色，有的节点隐藏着超级蝙蝠，它能把你扔到图的任何位置。节点之间的边可能有警察。

3. 如果你推测出怪兽的位置，向那里射箭，如果射中则胜利，否则输掉。如果你不小心从有警察的边通过了，也死掉。

4. 在怪兽的附近两个距离范围内，会有血气。如果一个点的某条边有警察，这个点会有光晕。

说起来复杂，来看副图。有点像挖地雷那种小游戏。有？符号的为没访问过的点，*为当前点，从14到15遇到警察死掉了。

上周末玩了好几个小时，还挺难胜，主要还是图比较大，游戏一开是整个地图是已经生成了的，要偷懒可以看看。

来看看如何用Lisp代码来实现这个程序，程序比较短。首先是如何生成图，需要生成一个随机的连通图。设定节点数目和边的数目，以编号代表节点。random-node:随机地选一个节点。edge-pair:连接两个点表示边。make-edge-list: 重复N次，生成N条边的集合。这个随机图可能不是连通的，下面的代码找出孤立的点集，用一些边连接起来这些孤立的点集，随机图产生完成。第二步向某些点之间加警察，随机的。这其中用了各种mapcar和Lambda，这样的效果使得Lisp程序看起来全是括号。mapcar的意思就是我要在这个列表上面所有的元素上都执行这个Lambda函数。visited列表保存已经访问过的节点，know-city-nodes更新(不是纯函数式编程的风格)，know-city-edges根据访问的节点，生成已知的路径，当前已知的用dot画出来。graphviz是个好东西，最近也在学习用这个来画一些流程图，效果挺好的。

乱说说Common Lisp，看了一些这方面的资料，这语言不管有多少牛逼人士簇拥(最近Paul Grahamd的书被翻译了)，使用的人还是太少还是有一定的历史原因，早期的实现效率是一个问题，而当实现和硬件都不错了的时候C/C++已经成大局了。另一个很重要的原因是，文档不是很好，我想找个处理图片方面的库，见到一个README文件跟救命稻草似的，打开一看”Do you really need DOCS?”。Lisp的哲学是语言不能给太多限制，甚至做到代码就是数据、数据就是代码，你可以轻而地为语言添加特性，你还可以用宏来写出生成代码的代码。Lisp给了程序员最大的自由来挑战语言的限制，所以会出现如此多种的方言。好的一面是面对特定的问题或许能得到优美而高效率的解决方法，而这个代码对于另外一个程序员来说太难读懂(特别是夹杂了宏的代码)，继而难于流传。这里有篇经典的Lisp:Good news,Bad news，作者为早期用Lisp作为开发语言开公司的。

以后看看Hashkell吧，这个比较有前途。

我是豆瓣FM的忠实用户，用这个东西已经有一年多了吧，累计收听了不少歌曲(316首喜欢的,45首不再播放的,7352首播放过)。通过这个东西发现不少符合自己口味的音乐。这316首是我喜欢的类型，所以想把这个列表弄下来，然后把这些歌曲下载到电脑上。

看了一下豆瓣是有自己开放的API的，不过还是够麻烦的。于是折腾了一个Python程序，输入你的豆瓣用户名和密码，模拟登录豆瓣并记录cookie，自动地到FM的页面去取下这个音乐列表。这个程序在处理HTML文件的时候有点笨拙，正则表达式不够强嗄。需要另一个库python-beautifulsoup。

通过歌曲名，自动下载这个应该是已经有人做了的，于是发现这个getsong.py，是通过Baidu音乐自动下载的，使用了一下速度和成功率都不错，于是在这个上面做了一些修改，直接从上面的程序生成的列表中取歌曲名字，下载下来。如果网速可以一般能在500k左右的下载速度，挺不错的。这个程序有可能会抛出一些异常，我没做仔细的检查，如果一首歌下载不下来就pass掉。

上面的程序都放在GitHub上了，Git/GitHub可个是真好东西。
需要的朋友们从这个地址弄下代码:https://github.com/chenyukang/fmmusic

使用方法：

1 修改fm_get_music.py，在里面填入自己的豆瓣用户名和密码。
2 运行这个程序，会在当前目录生成一个歌曲列表：songlist.txt。
3 运行getsong.py程序， python getsong.py -x，就是通过songlist.txt逐个通过百度搜索自动下载，存在当前目录。