用C实现的一个简单的线程池

线程池文件有pool.c和pool.h,测试代码在test.c。测试代码比较乱,但应该足够看懂怎么用了。打包下载:pool.tar

pool.h

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <pthread.h>

#define MAX_THREAD 2000

typedef void *(*job_func)(void *);

typedef struct a_job {
    job_func func;
    void *arg;
    void **result;

    struct a_job *next;
} job;

typedef struct {
    pthread_t *workers;
    int total;
    int free;

    job *jobs;
    job *job_end;
    int jobc;

    pthread_mutex_t q_mutex;
    pthread_cond_t  q_cond;

    int init;
    int destroy;
} thread_pool;

int pool_init(int);
int pool_add_job(job_func, void *, void *);
int pool_destroy();
void *routine(void *);

pool.c


#include "pool.h"

static thread_pool *pool;

int
pool_init(int count)
{
    if (count > MAX_THREAD)
        return -1;

    if (pool != NULL)
        return 0;

    pool = (thread_pool *)malloc(sizeof (thread_pool));
    if (pool == NULL)
        return -1;
    memset(pool, 0, sizeof (thread_pool));

    pool->total = pool->free = count;
    pool->init = 1;
    pool->destroy = 0;
    pool->jobc = 0;

    pthread_mutex_init(&pool->q_mutex, NULL);
    pthread_cond_init(&pool->q_cond, NULL);

    pool->workers = (pthread_t *)malloc(sizeof (pthread_t) * count);
    if (pool->workers == NULL)
        return -1;
    memset(pool->workers, 0, sizeof (pthread_t) * count);

    int i;
    for (i = 0; i < count; i ++) {
        pthread_create(pool->workers + i, NULL, routine, NULL);
    }

    return 0;
}

int
pool_destroy()
{
    if (pool == NULL)
        return 0;
    if (pool->destroy == 1)
        return 0;

    pool->destroy = 1;
    pool->init = 0;

    pthread_cond_broadcast(&pool->q_cond);
    int i;
    for (i = 0; i < pool->total; i ++) {
        pthread_join(*(pool->workers + i), NULL);
    }

    free(pool->workers);

    pthread_mutex_destroy(&pool->q_mutex);
    pthread_cond_destroy(&pool->q_cond);

    free(pool);
    pool = NULL;

    return 0;
}

int
pool_add_job(job_func func, void *arg,  void *result)
{
    job *tmp_job = (job *)malloc(sizeof (job));
    if (tmp_job == NULL)
        return -1;
    tmp_job->func = func;
    tmp_job->arg = arg;
    tmp_job->result = result;

    pthread_mutex_lock(&pool->q_mutex);
    if (pool->job_end == NULL) {
        pool->jobs = pool->job_end = tmp_job;
    } else {
        pool->job_end->next = tmp_job;
        pool->job_end = tmp_job;
    }
    pool->jobc ++;
    tmp_job = NULL;
    printf("A job added, number of jobs : %d\n", pool->jobc);
    pthread_mutex_unlock(&pool->q_mutex);

    pthread_cond_signal(&pool->q_cond);

    return 0;
}

void *
routine(void *arg)
{
    pthread_cleanup_push(pthread_mutex_unlock, &pool->q_mutex);

    printf("Thread 0x%x start!\n", pthread_self());

    while (1) {
        pthread_mutex_lock(&pool->q_mutex);
        while (pool->jobc == 0 && pool->destroy != 1)
            pthread_cond_wait(&pool->q_cond, &pool->q_mutex);

        if (pool->destroy == 1) {
            pthread_mutex_unlock(&pool->q_mutex);
            printf("Thread 0x%x exit\n", pthread_self());
            pthread_exit(NULL);
        }

        job *tmp_job = pool->jobs;
        pool->jobs = pool->jobs->next;
        pool->jobc --;
        pthread_mutex_unlock(&pool->q_mutex);

        printf("Job run by thread 0x%x\n", pthread_self());

        if (tmp_job->result != NULL)
            *(tmp_job->result) = (*tmp_job->func)(tmp_job->arg);
        else
            (*tmp_job->func)(tmp_job->arg);
        free(tmp_job);
    }

    pthread_exit(NULL);
    pthread_cleanup_pop(0);
}

test.c


#include "pool.h"

void *
func(void *arg)
{
    int *a = (int *)malloc(sizeof (int));

    *a = *(int *)arg;

    sleep(1);
    return a;
}

int
main(int argc, char **argv)
{
    pool_init(3);

    printf("inited\n");

    int arg = 1;
    void *tmp;
    pool_add_job(func, &arg, &tmp);

    printf("add job finished\n");
//    sleep(5);

    printf("going to destroy\n");
    pool_destroy();

    printf("res is %d\n", *(int *)tmp);

    free(tmp);
    return 0;
}

python虚拟机实现(一)

python并不将py文件编译为机器码来运行,而是由python虚拟机一条条地将py語句解释运行,这也是为什么被称为解释语言的原因之一。但python虚拟机并不直接执行py語句,它执行编译py語句后生成的字节码。本篇简单地讲下编译、运行的过程,涉及到的内容有如何编译、控制流、函数及类的实现等。

0. python的编译

python将py文件编译成为PyCodeObject,再将这个对象写入某文件就成为了pyc文件,文件中包含python的magic number(来说明编译时使用的python版本号)、源文件的mtime(使pyc和py文件保持同步)、编译出的code对象。将对象写入到一个文件似乎听起来不太可能,不过其实很简单,python只写入特定类型的对象,比如要写入一个code对象,python会按一定的顺序将这个对象中的属性一一写入,由于对象是固定的,因而只要记下写入时的顺序就可以从文件中恢复出对象。注意我们这里谈论的并不是python中的序列化。python在写入实际的对象时会写入标识符,即可以标明对象的边界,又可以保持内容信息以在内存中恢复出对象。

python将对象写入文件最后会将调用到两个函数,一个用来写个int,一个用来写入string。对于string来说,为了达到和intern机制一样的目的不重复写string,在写入的时候python还会维持一个dict来保存已经写入的被intern处理后的string,因此当一个string被intern处理过并且出现在之前所说的dict中时,python仅仅会写入该string的索引值,即它是第几个string。当读取文件时,python则会根据每个string的索引值重建一个list,碰到重复的intern的string时就可以根据索引值读出该string的值了。

1. python虚拟机基础

python虚拟机的执行方式就是模仿普通x86可执行文件运行方式,也有栈、帧等概念。除止之外,python还有一个执行环境的问题,考虑print a句话,a肯定指向了一个对象,但是是什么对象呢,这个就由执行环境来确定了,語句可以通过执行环境读写变量的值,在源代码中对这个执行环境的模拟是对它PyFrameObject来完成的,每一个code block都对应一个执行环境,就是一个PyFrameObject,可以认为是一帧。这个struct比较复杂,看下代码:


typedef struct _frame {
    PyObject_VAR_HEAD
    struct _frame *f_back;	/* previous frame, or NULL */
    PyCodeObject *f_code;	/* code segment */
    PyObject *f_builtins;	/* builtin symbol table (PyDictObject) */
    PyObject *f_globals;	/* global symbol table (PyDictObject) */
    PyObject *f_locals;		/* local symbol table (any mapping) */
    PyObject **f_valuestack;	/* points after the last local */
    /* Next free slot in f_valuestack.  Frame creation sets to f_valuestack.
       Frame evaluation usually NULLs it, but a frame that yields sets it
       to the current stack top. */
    PyObject **f_stacktop;
    PyObject *f_trace;		/* Trace function */

    /* If an exception is raised in this frame, the next three are used to
     * record the exception info (if any) originally in the thread state.  See
     * comments before set_exc_info() -- it's not obvious.
     * Invariant:  if _type is NULL, then so are _value and _traceback.
     * Desired invariant:  all three are NULL, or all three are non-NULL.  That
     * one isn't currently true, but "should be".
     */
    PyObject *f_exc_type, *f_exc_value, *f_exc_traceback;

    PyThreadState *f_tstate;

    PyTryBlock f_blockstack[CO_MAXBLOCKS]; /* for try and loop blocks */
    PyObject *f_localsplus[1];	/* locals+stack, dynamically sized */
} PyFrameObject;

许多个PyFrameObject通过f_back连成一串链表,表示了帧与帧之间的先后、调用顺序。python中帧在运行时需要额外的内存,比如a = b + c这段代码,那么需要先请读入b、c,再算a,除此之外还有局部变量等需要保存在栈中,因此最后有一个f_localsplus指向这块多出来的内存,大小则在编译时计算出来保存在f_stacksize中,这块内存具体用来依次保存locals(局部变量)、cellvars、freevars(后两个和闭包的实现有关)、动态栈(f_valuestack指向栈底、起始位置,f_stacktop则维持栈顶)。

当Python虚拟机开始执行时,它会先进行一些初始化操作,最后进入PyEval_EvalFramEx函数,它的作用是不断读取编译好的字节码,并一条一条执行,类似CPU执行指令的过程。函数内部主要是一个switch结构,根据字节码的不同执行不同的代码。

2. Python运行环境及执行过程

先从整体上看看Python的运行环境。我们知道在操作系统中执行程序离不开两个概念:进程和线程,在Python中也是这样,Python模拟了这两个概念。模拟进程或线程的分别是PyInterpreterState和PyThreadState。可以想象,每个PyThredState都对应着一个帧栈,Python虚拟机在多个线程上切换。

当Python虚拟机开始执行时,它会先进行一些初始化操作,最后进入PyEval_EvalFramEx函数,它的作用是不断读取编译好的字节码,并一条一条执行,类似CPU执行指令的过程。函数内部主要是一个switch结构,根据字节码的不同执行不同的代码。用一张图表示:

3. Python的名字空间

名字空间在Python中是一个非常重要的概念,读写变量值其实就是到某个名字空间中读写与该变量名相对应的对象。如果我们把某个符号和与之关联的对象之间的关系(就是(name, value)这样的关联关系)称为約束的话,那可以认为名字空间的内容就是由一组组約束构成,而增加約束的語句可以被称为赋值語句,函数定义、类定义等都可以被称为是赋值語句。当一个module被加载后,Python会执行相应的代码在这个module的名字空间中建议相应的約束,然后就可以用module.attr这样的語句来访问module的属性。

对于每个module来说,它都有一个顶层的名字空间,可以认为是global名字空间,同时也没有哪个名字空间能够跨module存在。具体到module的某行代码,对它来说还存在local名字空间(比较在函数体或类定义中)、enclosing名字空间(用来实现闭包,其实它不真的存在,但假定有这样一个更好理解)。而Python内置了builtin名字空间。如果要查找某个符号的话,Python会依次查找LEGB。要注意的是Python具有静态作用域,它的意思就是说名字空间这个东西是在你写好py代码后就确定的,而不是由执行的时候确定的。这一部分对于理解Python非常重要,由于篇幅所限之前在是不能详述,建议查看《Python源码剖析》第8.2节。

python内置对象的实现

准备回顾一下python源代码,不过不准备说的太细,尽量勾勒框架,不引用代码。

0. python中对象的概念

python中所有东西都是对象,进一步地,这些对象可以分为类型对象(type)or实例对象,有时一个对象即可以是类型,也可以是实例。所有这些对象中,除了内置的类型对象外,别的都生存于堆上,内置的类型对象则静态分配内存。

每个对象头部都有一个PyObject_HEAD(其实对于某些需要被gc管理的对象,它的头部先为PyGC_Head,再为PyObject_HEAD)。变长对象在HEAD后还有一个ob_size表示变长对象元素个数的多少,非字节数。

类型的信息都在它的type对象里,源码中为struct _typeobject,也就是PyTypeObject。比如实例化一个类型,那会先找它的tp_new(找不到的话在父类找),在tp_new中根据该type的tp_basesize进行分配内存,再调用tp_init进行初始化。对类型的实例做运算,比如相加其实也是找type对象中相应的函数指针。type对象中的信息到后来基本都会在类型的dict中和相应的key对应起来。

1. int的实现

int比较简单,关键在于如何高效地实现。python首先有小整数对象。默认在[-5, 257)。如果超出范围则使用通用的缓冲池,对于大整数则有PyIntBlock,用来作缓冲池。一个block大小大概为1000个字节,去掉头部(8字节),可以存82个整数对象。block之间通过指针相连,首指针为block_list,free_list则维护着一条可以链表,free_list链表的下一项由未用的PyIntObject的ob_type来维持。

一些细节:当无可以用缓冲池可用时python会调用fill_free_list来创建一个新的block,并将其插入block_list,再把free_list指向这个block的objects中的最后一个元素。当某个block中的某个int被释放时,它将自己的ob_type指向free_list,并修改free_list等于它的地址,其实就是一个头部插入,这样把多个block间的objects数组联系起来防止出现内存泄漏。一个值得注意的地方是小整数对象池其实也是生活在block里面,在是整个python环境初始化的时候生成。这里可以看出,为int分配的内存是永远也不会被python释放的,所有的int对象使用的内存大小和同时存在的int数量的最大值有关。

2. string的实现

string复杂一些,它是变长对象。对变长对象内存的管理。每个string对象除了头部外还保存了hash值(ob_shash,避免重复计算,初始-1)、是否已经被intern机制处理过(ob_sstate)、指向实际内存的指针(ob_sval),ob_sval指向的应该是一段ob_size+1长度的内存(为了兼容C,字符串要以'\0'结尾)。在从char *创建string时还是比较直接的,就是检查一些边界情况、初始化hash等,最后逐个拷贝char。python中有一个nullstring指向空字符串,通过intern机制共享,所以不会同时存在多个空字符串。

传统缓冲池。相当于int小整数缓冲池,对单个的char,python也会维持一个缓冲池。创建单个char的string时,如果缓冲池里已有,则直接返回。如果没有,根据char创建string,再对它进行intern,再存入缓冲池。

intern机制。python会维持一个dict,用来保存当前已经被创建的string,如果新创建的string已经在这个dict,也就是已经被intern机制处理过了,那么就会直接返回dict中的值。也就是说一般两个相同的字符串的id是相同的。要注意的是,无论字符串有没有存在于这个dict中,python都会创建一个新要string,原因是因为保存在dict中只能是PyObject,因此肯定要创建一个python对象。intern后的string有两种状态,mortal和immortal,区别在于后者永远不会被gc回收。

要提到的是,创建string时使用的是PyObject_Malloc开头的分配函数,一般来讲它不会每次都从os分配内存,而是从python维持的一个内存池中分配。

3. list的实现

list不仅是变长对象,还是可变对象。在变长头部之外PyListObject还保存了一个PyObject **ob_item指针,一个int allocated。ob_item就是指向实际成员的指针,allocated代表了list当前申请的内存能装多少个PyObject,变长头内的ob_size则代表list中已有多少个PyObject。当创建一个list时,需要指定list的大小(参数size),要申请的内存可以分为两部分,一个是list本身,一个是指向成员变量的指针。如果list缓冲池可用(numfree > 0),那就从缓冲池中给list分配一块内存,否则使用PyObject_GC_NEW来分配空间(和string不同,因为list中的成员可以指向其它python对象,这个函数和python垃圾回收的三色标记法有关)。然后再根据size大小分配一段连续的内存来保存指向各个成员的指针,新创建的list中的ob_size和allocated都为size。

创建list后给list里的某个位置赋值比较简单,就是简单的設定指针而已。添加操作要复杂一些,首先会调整list的大小,使得allocate>=size>=allocate/2。如果该等式已经满足,那么不更改list大小,如果不满足的话通过new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6) + newsize得出新的allocated大小,再通过PyMem_Resize来调整保存成员指针的内存。resize后则使用最简单的策略移动从插入到结尾的成员指针,再设置该位置上的成员。删除成员时实际删除后的也要进行resize操作,和插入时类似。实际删除的操作则由list_ass_slice来实现,它有两种用法,一是更改list中的某一段为特定的值,另一种就是删除list中的某一段。list中每删除一个元素都会造成内存拷贝。一个值得注意的细节是由于从list中删除或是更改的对象需要减少引用计数,但减少引用计数时又会循环调用一些list函数,可能会造成list索引值的破坏,因而函数中得用一个temp数组保留从list中剥离的成员,等删除工作完成,list结构已经确定的情况下再逐一减少其引用。

当list被销毁时,对其成员逐个减少引用,然后检查缓冲区是否已经满,如果没有的话就将该list放入缓冲区,这样下次再创建list的时候就不用为list对象本身再分配对象了。

4. dict的实现

python中的dict是用hash表实现,解决冲突的方法是开放定址法,即二次探测,删除时使用伪删除技术(顺便说下在一致性假设下,如果用k来表示hash表的使用率的话,那么一次成功查找需要的比较次数为1/k * ln(1/(1-k)),插入时的比较次数最多为1/(1-k))。

在一个dict中,每个(key,value)对组成一个entry,entry中还另外存储了key的hash值。对每个entry来说有三种状态unused(key,value皆为NULL,初始状态),active(key,value不为NULL,存储了元素),dump(对应于伪删除技术,key=dummy,value=NULL)。dict实际上就是entry的集合,定义如下:

typedef struct _dictobject PyDictObject;
struct _dictobject {
	PyObject_HEAD
	Py_ssize_t ma_fill;  /* # Active + # Dummy */
	Py_ssize_t ma_used;  /* # Active */

	/* The table contains ma_mask + 1 slots, and that's a power of 2.
	 * We store the mask instead of the size because the mask is more
	 * frequently needed.
	 */
	Py_ssize_t ma_mask;

	/* ma_table points to ma_smalltable for small tables, else to
	 * additional malloc'ed memory.  ma_table is never NULL!  This rule
	 * saves repeated runtime null-tests in the workhorse getitem and
	 * setitem calls.
	 */
	PyDictEntry *ma_table;
	PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);
	PyDictEntry ma_smalltable[PyDict_MINSIZE];
};

PyDict_MINSIZE一般被设为8。使用PyDict_New来创建一个新dict时,其实就是分配相应的内存,将ma_fill,ma_used设为0,ma_mask设为7(8-1),ma_table指向ma_smalltable,ma_lookup默认为lookdict_string。在实现dict时python也使用了缓冲池,方法和list基本一样。

ma_lookup这个函数指针确定了散裂函数和冲突发生时的二次散裂函数,在dict中进行搜索有两种方法,lookdict_string和lookdict,后一种是更一般的方法。由于python中dict用的非常广泛,而这些dict中大多数key都是string,因而专门提供了一个搜索方法来进行加速,其实两种方法的本质都是一样的。搜索的具体过程如下:1. 获得探测链中当前应该检测的entry;2. 如果是unused状态,那搜索失败,应该返回一个可用的(可以被设置值)的entry,所以如果freeslot不为空(之前找到了dummy态的entry)就返回freeslot指向的entry,否则返回当前entry;3. 如果entry为dummy态且freeslot未设置,则设置freeslot,继续查找下一个;4. 依次检查当前entry的key和查找的key是否引用相同、值相同,若不是继续查找下一个。需要注意的是,dict使用哪种方法进行查找取决于待查找的key,如果是string的话则利用lookdict_string,和本身已经有的entry中的key无关。

dict的插入和删除基于之前的搜索,很好理解。当插入时先搜索该key,得到一个entry,再根据它的状态来修改它达到插入的上目的。删除操作也类似。需要注意的是插入元素的时候,会检查ma_fill/(ma_mask+1)是否大于2/3,如果装载率的确大于这个值并且有unused或dummy的entry被填充的时候,就会调整dict的大小,新的大小最小为minsize=ma_userd*(ma_used>50000?2:4),显然改变dict大小会造成内存移动,因此这时候可以丢弃dummy的entry。新的dict大小从8开始逐次*2增长,直到大于minsize。接下来就是一些初始化动作,逐个检查entry并插入新的dict等。

开始使用amazon ec2

由于某些众所周知的原因,到我空间22端口的连接总是被timeout,justhost不提供修改端口功能(提供了就出鬼了),实在是不能忍了,决定弄个vps,试了试ec2,本来是准备花钱的,后来发现居然可以免费一年,我就用来fq总是够用了,算是意外之喜。并且新加坡的机房ping值不到200,比以前空间的300多要好多了。

注册很简单,就是要注意填手机号的时候不要加86,我就是因为加了86,最后输pin码时手动改了手机号結果使pin码一直不对。

开始使用前以为会比较复杂,結果发现我想太多了= =…,免费的基本只有用自带的AMI+micro plan+On-Demand Instances。没有什么别的选择机会。这里有个教程可以看看,http://www.giroro.com/amazon-ec2-study-notes-1/,注意登陆的时候的用户名是ec2-user,好囧。。

最后吐槽一下。。AMI是在CentOS的基础上改的,我只很久前用过一段时间的CentOS,各种操作都不会了有木有。就不能来个Debian/Ubuntu or Arch之类的吗。。。我们小用户不用那么高稳定性的。。。

程序员面试题精选100题的答案合集和一些常用算法

最近在为找工作做些准备,做了些题看了些算法,其中有一个程序员面试题精选100题好像是比较有名的(现在还没出满100题),我把自己的答案放上来,如果有人来讨论一下那更好了。我是用的C来做题,有些C++ only的题就跳过了。还有一些别的算法比如RMQ的st解法,kmp等代码都在里面。打包下载地址在这里jingxuan.tar.gz

顺便有几个算法想单独地说一下:

1. O(n)时间求最长回文。主要思路就是从第一个字符开始扫描,记录下以当前字符结尾的最长回文长度。代码如下

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>

int
find(const char *s)
{
    if (!s)
        return -1;

    int lens = strlen(s);

    int i, same = 1, pre = 1, max = 0;
    for (i = 1; i < lens; i ++) {
        int l = 0, s1;
        s1 = i - pre - 1;
        if (s1 >= 0 && *(s + s1) == *(s + i))
            l = pre + 2;

        if (l == 0)
            l = *(s + i - 1) == *(s + i) ? 2 : 1;

        if (*(s + i) == *(s + i - 1))
            same += 1;
        else
            same = 1;

        s1 = l > same ? l : same;
        if (s1 > max)
            max = s1;

        pre = s1;
    }

    return max;
}

int
main(int argc, char **argv)
{
	printf("%d\n", find("aaa"));
	printf("%d\n", find("goooog"));
	printf("%d\n", find("guouyy"));

	return 0;
}

2. 怎么在O(n)的时间,O(1)的空间找出一串数字中两个不同的只出现一次的数字(别的都出现两次)。这题普遍一点的解法是用位数组,不过还可以考虑把整个数组分成两个子数组,每个分别含有一个只出现一次的数字。代码如下


#include <stdio.h>
#include <assert.h>

int n1, n2;

int
find_once(int array[], int length)
{
    assert(length > 0);
    assert(array != NULL);

    int all = 0, pos = 0, i = 0;
    unsigned int tmp;

    for (i = 0; i < length; i ++)
        all ^= array[i];
    assert(all != 0);

    tmp = (unsigned int)all;
    pos = (tmp - (tmp & (tmp - 1)));

    for (i = 0; i < length; i ++) {
        if (array[i] & pos != 0)
            n1 ^= array[i];
        else
            n2 ^= array[i];
    }

    return 0;
}

int
main(int argc, char **argv)
{
    int a[10] = {1, 2, 1, 2, -1, -1, 3, 3, 0, -4};

    find_once(a, 10);
    printf("%d %d", n1, n2);

    return 0;
}

3. 全排列、组合、幂集算法,分重复不重复两种情况(待添加)

4. 后缀数组(待添加)

5. kmp算法(见上一篇博文)

kmp算法及简单应用

kmp算法是模式匹配中的经典算法,在处理很多和字符串的问题时都会用到。不过这个算法虽然实现起来很简单,思路想要描述清楚却不容易,网上有很多资料,但感觉都讲的不太清楚,有些代码都是错误的。为了验证自己已经弄清楚了,决定从头开始介绍这个算法。

假定T为待匹配的文本,P为模式。假定T为ababaabcbab,P为ababaca。我们先从T的第一个字符开始匹配起,粗体表示匹配失败的字符

T a b a b a a b c b a b
P a b a b a c

如果按照朴素的匹配算法,那我们下次应该就从第二个字符开始匹配。那有没有更快一些的方法呢?观察一下P,前两个字符分别和第三、第四个字符相等,也就是说如果我们下次可以从T的第1+2,也就是第三个字符开始匹配起。也就是说假定P[1...q] = T[s + 1...s+q],那么满足P[1...k]=T[ss + 1... ss + k] 的ss最小是多少,其中ss + k = s + q。

进一步地解释,假定匹配在T的第t位和P的第p位失效了,那么我们接下来要继续比较T的第t位和P的(p-x)位,相当于把P往右移了x位。那么如果我们能知道p-x的值,整个匹配过程就很好理解了,t每次增大1,当匹配失效时置p为p-x,继续匹配。

如何知道p-x的值呢?我们先考察一下它的意义,匹配失败并重置p为p-x后我们可以继续比较T的第t位和P的p-x位,这说明在这位之前,t的长为p-x-1的左串等于P的长为p-x-1的前缀。事实上这就是p-x的定义。对于所有的p,记其p-x的值为向量next。那么给定P,对于其中的第i位来说,如果P[i-k+1...i]和P[1...k]相等,且k < i,则next[i] = k。

求next向量的过程可表示如下,先初始化next[0]为0,假设我们已经知道next[i-1] = k,求next[i]。
1. 如果P[k + 1] = P[i],则next[i] = k + 1
2. 如果P[k + 1] != P[i] 并且 k > 0,则令k = next[k] 直到P[k + 1] = P[i]或 k = 0
3. 第2步得到了新的k,如果P[k + 1] = P[i],那么next[i] = k + 1,否则为k。

完整代码如下:

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>

#define MAX 10000

void
gen_next(char *p, int *next)
{
    int len = strlen(p);

    *next = 0;
    int k = 0;
    int i = 1;

    for (i = 1; i < len; i ++) {
        while (k > 0 && *(p + k) != *(p + i))
            k = *(next + k);
        if (*(p + k) == *(p + i))
            k ++;
        *(next + i) = k;
    }

    // We can set next[0] to -1 to make the code simpler
    // *next = -1;
}

int
find(char *p, char *q)
{
    assert(p && q);

    int *next, lenq = strlen(q), lenp = strlen(p), count = 0;
    next = (int *)malloc(sizeof (int) * lenq);
    if (next == NULL)
        return -1;
    memset(next, 0, sizeof (int) * lenq);

    gen_next(q, next);

    int pi, qi;
    pi = qi = 0;
    while (pi < lenp && qi < lenq) {
        // If next[0] == -1, the while loop can be writen is this way
        //
        // if ((*(p + pi) == *(q + qi) || qi == -1) && pi < lenp && qi < lenq)
        //     pi ++, qi ++;
        // else
        //     qi = *(next + qi);
        while (*(p + pi) == *(q + qi) && pi < lenp && qi < lenq)
            pi ++, qi ++;
        if (qi == lenq) {
            printf("found one match, begins at %d\n", pi - lenq);
            count ++;
            qi = *(next + qi - 1);
            continue;
        }
        if (qi == 0) {
            pi ++;
        }  else {
            qi = *(next + qi);
        }
    }

    return count;
}

int
main(int argc, char **argv)
{
    char s[MAX] = "ababab";
    char p[MAX] = "abab";

    printf("total %d match\n", find(s, p));

    return 0;
}

谈谈grub,mbr等概念

其实grub、mbr这些东西主要是当时本本装arch时看的,现在整理知识发现好些又都记不清了,看来还是有必要记录下来啊。

先来说说grub1。我们知道磁盘的前512个字节叫MBR,那么在系统启动时,BIOS会根据启动顺序选择一个设备执行启动操作,如果刚刚好选择了一块使用grub作为引导程序的磁盘(可能是U盘、硬盘等),那么BIOS会把控制权交给这块磁盘的MBR,由MBR来完成操作系统的加载。加载过程又可以分为两种情况,一是grub处于磁盘的MBR中,另一种是grub被安装在某块分区中,由另一个引导程序来加载grub(被称为chain loader)。

我们先来看看安装于MBR中的grub是如何工作的。grub的启动可以分为三个阶段,stage1,stage1.5,stage2。我们知道MBR只有前446个字节可以被用来安放引导程序,这块空间其实并不大,不可能所有的事情都在这里做完,比如启动时要加载一些配置文件,那我们肯定要有一个读取文件系统的程序,这就是stage1.5了。在安装grub到MBR时,前446个字节其实是安装了stage1,可以使用

sudo dd if=/dev/sda of=mbr bs=512 count=1

来查看一下MBR,然后再用hexdump -C命令和/boot/grub/stage1(不同的系统、安装方法路径可能不同),可以发现前446个字节是一样的。前面说过,stage1的主要作用就是加载stage1.5,而stage1.5就放在MBR后、第一个分区前,这个空间大概有32K,足够实现许多主流文件系统的读取了。加载完stage1.5后再的过程被说过太多次了,读取配置文件等等,我就不再啰嗦了。我们再看看stage1.5这个东西,它放在MBR之后,而这个地方其实是还有可能放其它东西的,不像MBR前446个字节,已经约定俗成放引导程序了,那么当它一部分空间不可用时,grub1就无法正常工作,比如如果磁盘的空间分配比较特别,不符合标准或是磁盘上已经安装了LVM,GPT等。

简单地说来grub2相对于grub1改进之处就在于stage1可以加载一个任意的LBA48地址,因而最终可以完整地加载一个并不在传统位置上的stage1.5,因此可以和LVM,GPT等同时使用。

如果grub是安装在某个分区上启动过程其实也是类似的,只不过这时候需要一个引导程序来讲控制权转交给grub,思考一下用grub启动windows的代码:

set root=(hd0,X)
chainloader +1

其实和别的引导程序加载grub是一样的道理,指定了root分区后再把控制权转交到这个分区上面的引导程序。

最后还想讲讲分区表的错误,在natty出来的时候我也想装个玩玩,个人觉得ubuntu还是个不错的发行版的,上手简单,要折腾的话其实也可以折腾的起来。当时电脑上面已经有了win 7和arch,win7有一个c盘,接下来所以的划了个逻辑分区,d盘是扩展分区。后来装arch的时候就从逻辑分区里又分了两块出来,结果没留意安装时分出来的分区是主分区。于是就出现了主分区在扩展分区中的问题,这下装ubuntu时硬盘的分区完全不能识别了,出来一整块硬盘,后来发现右边的哥们就是因为没注意这个把整个硬盘都格掉了装了个ubuntu,= =||。搜了搜发现这个问题还很常见,http://forum.ubuntu.org.cn/viewtopic.php?f=77&t=194802。如果单单这样还好说,arch的两个主分区在磁盘最尾部,只要强行把分区表的逻辑分区和扩展分区尾调整到主分区之前就好了,但是我又在最后面分了两个分区想装ubuntu的,这下又不能那样调整了,因为如果把逻辑分区放在arch之前,那么主分区就多于四个了。删掉后面的分区是可以的,但是调整arch的主分区就不行,用gparted时说是分区表错误不行,这下可绕回去了,几十G的空间还是舍不得丢在那里不用啊。最后居然是在windows下面用acronis弄好的,它可以移动分区,把arch两个分区移到最末尾,这样未分配的空间可以并入d盘,再调整分区表使扩展分区不要包含主分区就好了。

ps1. linux扩展分区也可以放系统。所以都用扩展分区吧。。
ps2. acronis好像可以把主分区转换成扩展分区,但不好用。arch下好像会出错。
ps3. 修改分区表很危险,一定得先备份啊。

[转]何去何从——仙剑随想

最近刚玩完仙五,颇有感想,可惜自己文笔太差,写不出来。今天在98上看到一篇文章,觉得说的很好。作者为江南狂士@cc98,内网地址:http://www.cc98.org/dispbbs.asp?BoardID=91&id=3717904&page=&replyID=3717904&star=1,以下为正文:

想到哪,就写到哪了。
很乱

题记:《仙剑五》通关之后,说不上惊喜,也说不上失望。毕竟没有太大期望时,就很难说是失望了。之前,曾在一幅《仙剑》的画报上见到一句话:“还记得年少时的梦吗?”不再年少时,梦真的还在吗?

1、
高中才开始接触《仙剑》。
那时偷偷躲在房间里玩,当时只是觉得好玩,却没有感动不感动的说法。而觉得好玩,最主要是没有什么别的游戏。我愚昧憨直、反应迟钝,策略类、动作类的游戏都不喜欢,只有《仙剑》这类回合制的剧情游戏比较适合我。
所以,当提到游戏,我最先想到的就是《仙剑》了。
《仙剑》,陪我走过了最值得怀念的时间。到现在为止,年少的梦,似乎也真的该醒醒了……可是,《仙剑五》将要出来,还忍不住地关注。当时,在黑龙江的牡丹江出差,一看《仙剑五》出来,连出差要做什么也想不起来了,撒腿就跑到电脑城去找游戏了。……罪过罪过,如果老板知道了,估计我会被活活骂死。
《仙剑五》很快通关了。闭上眼睛,回顾一下了历代的《仙剑》,也回顾了一下自己的历程。决定稍稍记录一下:曾经年少。

2、
按理说,春兰秋菊,应是各有风韵,如《仙剑》类的剧情游戏,似乎也很难分出个高低优劣来。但比较,似乎总是人的天性。君不见,至今网上还流传着《金庸小说高手排行榜》之类的帖子,上演着“关公战秦琼”的闹剧。
我本来就很“三俗”,决定也把“三俗”进行到底,给历代的《仙剑》与其副产品排排座次。按照“渐入佳境”的说法,我想还是把我觉得好的作品放在后面。我说话一向刻薄,不把好的留在后面,只怕很容易让自己灰心。

3、
历代《仙剑》中,口碑最差的,可能是《仙剑二》。
说起来,我觉得,这事还真是有冤。虽然,比起其他《仙剑》的其他作品,也的确存在差距。但如果不是放在《仙剑》的名下(特别是,放在已在经典的《仙剑一》之后),估计也不会被骂得那么难听。
一般来说,小说男主角的第一个条件就是长得好!想想也是,反正都是想象出来的,为什么想象一个好点的?借用夙莘大姐的话来说:天下男子长得大多不堪入目,做个英俊的,看着也舒心!
可是,王小虎长得……只能抱怨一下美工。
须知,在纸上的时候,男主角是可以长得砢碜点,比如《天龙八部》的虚竹、《大人物》的杨凡。但是,一旦上了电视、电影,还不是一样要找樊少皇、高虎、吴京那些帅哥去演?如果给人的第一印象不好,势必就要难要接受。
同理,苏媚、沈七七,包括小萝莉忆如,是吧?形象都成这样了,多数玩家不买帐,也是理所当然。
除了形象,再看看故事的构架和叙事,似乎也都只是平平——只有一个很普通的故事罢了。有印象的桥段不多:江都离宫,苏媚与仙霞派子弟的针锋相对;云梦泽,苏媚失踪后,李忆如的祈祷;邪雾林,王小虎一人对抗天下英雄;禁咒空间,苏媚破阵……这几处都可算是差强人意了。
最后,峨眉山下,王小虎和七七说要去找苏媚,而身后有一只小狐狸静静地看他们离开……这个结局倒是保持了《仙剑》“余韵不绝,绕梁三日”的风格。
《仙剑二》多处不善,据说与公司内务有一定的关系。这点似乎在剧情上也有所表现。按理说,续作虽然续前之作,但作品的构思却应当另起炉灶的。比如说,《神雕侠侣》之于《射雕英雄传》。而《仙剑二》则不然,几乎处处都要和《仙剑一》拉上关系,殊不知,这样不但无法提升《仙剑二》的水平,反而很容易坏了《仙剑一》的招牌。而且,很多情节处理得也未必妥当。比如说,李逍遥接任蜀山派掌门,这个多少让人觉得费解。李逍遥,毁了锁妖塔,虽然说是情有可原,但这事毕竟不妥。蜀山也是名门大派,独孤剑圣一世英雄,门下难道连一个像样的弟子都没有吗?……倒是,《仙剑五》的安排合理,让李逍遥当了蜀山的长老。
此外,还有一处值得一说。禁咒空间中,苏媚看见的那首诗:
“看朱成碧思纷纷,憔悴支离为忆君。
不信比来长下泪,开箱验取石榴裙。”
这是武则天的《如意娘》。历代文人,对武则天似乎都颇有成见,对此诗的评价就有些争议,但诗倒是的确不错。但历来都说这诗是武则天怀念她的小白脸的,而且是写的也分离之后的思绪(多少有点怨妇的感觉),所以,放在这里是否贴切,怕是值得深思了。

3、
《仙剑三外传——问情篇》,这个我唯一只玩过一遍的《仙剑》,虽然我一向有炒冷饭的习惯。倒不是说故事真有那么不堪入目,只是《问路篇》的迷宫,实在令人望而生畏。
过于强大的迷宫,把原本还算紧凑的剧情切割得支离破碎。等出了迷宫,常常都想不起要做什么来了。《仙剑》这种剧情类游戏的玩家,事实上,只怕也没有几个人会很喜欢迷宫。过份专注于迷宫,只怕是一个误区。像《仙剑四》的迷宫机巧精致,又如《绝代双骄二》的迷宫简捷明了,也许会让玩家舒服很多。
而如《仙剑三》《仙剑五》,又或《古剑》,迷宫都显得有些冗余了。《仙剑一》的迷宫也很复杂,但报怨声却不多,那里因为在那个时候,游戏少,大家有时间不知该做什么,所以迷宫复杂些也不妨。但现在嘛,处处声色犬马的,要玩家把心思放在迷宫,怕是有点强人所难了。
从剧情上来说,《问情篇》也略显单薄,先是地脉,再是里蜀山的燎日,好像也真的没太多内容。这样的安排,剧情就显得太过平实了。
一般来说,实用性的文章,需要写得简洁明了;而文艺性的文章却需要多用曲折之笔,这样的文章才会显得峰回路转、仪态万方。而这就是常说的“文似看山不喜平”。《仙剑》的剧情,该如何写作?我想也就不用多说了。金庸的小说,剧情一般都非常厚实,但行文还不免要弄些玄虚;古龙的小说,看似变幻莫测,细细想来,内容常常却不多,这就是行文的妙处了。
《问情篇》,也可以看出一些主创人员求新求变的尝试。比如说,温慧。按着武侠小说的习惯,铜锤之类兵器总该是莽夫型武将用的,但温慧就是用了。而且,温慧本人,天生神力(这话好像形容《鹿鼎记》中鳌拜的)、性格粗豪,也和寻常的女主角颇有区别。但这样的尝试,是否会成功,就很难说了。
我很欣赏求新求变,但不太认同作品的标新立异。人们的审美观念的形成,是一个积淀的过程。一定的事物会很自然让人产生一些特定的联想,如梅高兰幽、松劲竹韵,这些都已是自在人心的观念。文艺作品如果要尝试突破这些观念,就需要很慎重。
温慧的出现,……这样说吧,喜欢温慧的男生,会有多少呢?温慧是第一女主角,不是路人甲,这样的安排,是否需要好好考虑呢?
《问情篇》的剧情也并非乏善可陈。个人认为,里面最出彩的部分是南宫煌和两位父亲之间的父子之情。南宫煌数次回家,和养父的对话,总觉得让人觉得特别温馨;而赤炎对南宫煌谈论自己的过往时,对于现在家庭的那份感情,也实在令人动容。
偶尔也听人谈论,赤炎心中,爱的到底是蕙卿(相国小姐)还是丝缎?事实上,这重要吗?在柴米油盐中,爱情很容易就可以被折磨得面目全非。对于更多的人来说,爱情只不过是年少时做的一个梦,留下的只是美好的回忆罢了。

4、
《仙剑一》,让我说些什么好呢?
的卜!就是的卜!
的卜,是我们家乡的一种特产小吃。在我们的方言里,“的卜”还有一个意思,就是“掐一下”或者“捏一下”。的卜,刚拿出来,硬硬的。如果冷藏下,就更脆了。放进嘴里,过一会儿就变软了,甜甜的、糯糯的。
在我很小的时候,在街上就可以卖到。偶尔吃一点,觉得特别好吃。后来,就一直没见到过。偶尔想起来,总觉得有点遗憾:那么好吃的东西,怎么就没有了呢?一两年前,终于又看见店里有的卜出售了,包装得很精致。很开心,连忙去买了几盒,但却再吃不出原来那个味了。
《仙剑一》,在有些人心里,几乎成了一个不可超越的经典。但,到底是《仙剑一》真的不可超越呢?还是仅是心中的那个记忆不可超越?
关于这个问题,我想肯定有些聪明人不愿意去知道确切的答案。但很可惜,《仙剑五》的出现,已经给出了答案。商业社会中,也许可以真的可以满足人提出的各种要求,却常常很难满足人心底的愿望。就像“的卜”一样,可以再次尝到相同的滋味,也再找不回相同的感觉。
《仙剑一》本身的故事其实很简单,但很符合很多人幻想的情节:不情愿地施舍了一壶酒给了一个道士,却学到了几乎无敌的剑法(如果比武招亲,还能认为是林月如放水,那接下林天南的七诀剑气却是真功夫了);跑到一个荒岛,并遇上正在洗澡的漂亮姑娘,然后……然后,还不断地遇到新的漂亮姑娘……
先被逼着娶一个绝世佳人(还很有钱的样子),不想拜堂还可以撒腿就跑(不要说是为了找灵儿。真要留在林家入赘,也未必受得了),那个姑娘还死心塌地跟上你了;在神木林,强吻了一个异族的可爱小萝莉(认错人了?你去打听打听,有哪个男人会故意认错漂亮姑娘的?说认错人的,只是为了搭讪),那个小萝莉居然还粘上你了……有清纯少女(灵儿)、红粉佳人(月如)、还有小萝莉(阿奴),偶尔还可以遇到御姐调情(姬三娘)……
这么些事,上哪找去?
每个人心中都有幻想过艳遇,现在却有人把艳遇很形象生动具体地呈现给你了……然后,告诉你:那个走狗屎桃花运的,就是你!
这样的《仙剑一》,能不招人喜欢吗?
《仙剑一》改编成电视剧,结果很多玩家都说失去《仙剑》的味儿,然后挖苦几句导演编剧。事实上,导演编剧真的很冤,因为《仙剑一》的剧情只适合用于游戏,供人幻想,而根本就不适合改编为电视剧。《仙剑一》的剧情太过简单粗糙,硬伤也不少。比如说:剑圣既然认识圣姑,还将李逍遥一行人送到圣姑处养伤,那对于苗族(大理一带,应是白族比较多,而非苗族;如果说苗疆什么,主要应集中湘西一边,而不是云南大理)的女娲崇拜也应该有了解才是,怎么可能硬认灵儿是妖?玉佛珠既是达摩大师手持的佛珠,剑圣又如何认为这是妖魔所化,非要毁去?……
当然,这些都不重要。重要的是,在那个游戏市场相对空白的时代,有一款如诗如梦的游戏,给很多人的少年时代,留下了动人的回忆。
有一位颇有灵气的才女,以《小桥流水》的曲调,填了词,题为《仙剑旧谣》,倒似很能说明玩家对《仙剑一》的情怀。词写得很好,也抄录一下:

小舟轻疾 沙棠逐浪碧海摇[1]
小径通幽 洞天远红雨飘[2]
小石旁 瑶池解佩仙缘巧[3]
小潭边 曾惹蝶翩仙子扰

偶尔还会想起 最初那座岛
桃木的剑 绿叶的妖
野花儿轻描 心中一段谣
我对涟漪唱起 无人知晓

桥送行舟 柳枝轻飘羁旅迢
桥渡晨钟 寒山远清风摇[4]
桥上望 姑苏繁华春光好
桥下叹 引凤台高佳人杳[5]

你是否还记得 那片青石道
锈铁的剑 生涩的招
繁星点点 心中一段谣
我对夜色唱起 无人知晓

流霜未散 白沙堤上纤草凋
流年已醉 银杏熟金鲤跳
流得尽 十里荒村泪光绕
流不尽 相思坛上相思调

依然害怕回到 黑水白河郊
染血的剑 糯米的糕
西风淡扫 心中一段谣
我对桐叶唱起 无人再知晓

水色微茫 浮生梦远咫尺遥
(一去故土 十里坡遥)
水长成恨 转头空皆寂寥
(湘江水逝 难解寂寥)
水潺潺 春绿江南芳华笑
水悠悠 月影波荡渐缥缈

总是忘不了 年少意气豪
青春的剑 红尘不归鞘
侠情不老 心中一段谣
清歌唱道不悔 流水小桥
注:[1]沙棠:李白《江上吟》:木兰之枻沙棠舟。
[2]红雨:李贺《将进酒》:桃花乱落如红雨。
[3]解佩:刘向《列仙传•江妃二女》:江妃二女者,不知何所人也。出游於江汉之湄,逢郑交甫,见而悦之。……遂手解佩与交甫。至今,襄阳仍有“解佩渚”。
[4]寒山:张继《枫桥夜泊》:姑苏城外寒山寺,夜半钟声到客船。
[5]引凤台:刘向《列向仙•萧史》秦穆公有女,字弄玉,善吹箫。穆公为作凤台。弄玉与其夫萧史,居于其上,不下数年。后,乘龙凤升仙而去。

5、
有人说《仙剑》到现为止,已不再是一个游戏,而形成一种文化了。那么,这种文化的形成,我想应该起源于《仙剑三》。
在经历了《仙剑二》的失望后,《仙剑三》的出现,实在有些叫人眼前一亮。开场动画,就是感心动耳、回肠荡气。然后,在《玉满堂》的音乐下,男女主角闪亮登场……
与前期的作品相比,《仙剑三》倒真是显得有些奇峰崛起——无论是对游戏的全局掌控,还是对各处细节的设定,都显得游刃有余。
《仙剑三》在技术上存在不足,这点也不必讳言,但主创人员却尽可能地做到了扬长避短。游戏中的人物,基本连脸上的五官都不全,但由于做成了Q版的造型,也就不觉得那么刺眼了。配上一些合理动作,这些Q版人物倒显得颇有生气。特别在雪见结局,一个字的对白都没有,但却让人能准确明白到事情的过程。原本轻柔妩媚的《还魂草》,变得如此回肠荡气,更使剧情感人肺腑……
也是从《仙剑三》开始,主角和重要配角的名字,开始体系化,而不再是零散的名字。这点,虽然在后来的游戏也带来了一定的弊端,但当时也为《仙剑三》增色不少。除去名字,《仙剑三》的各处细节处理也非常严谨,基本也做到了有据可查,比如说:地名与当地的风俗特产等,这些一眼就可以看出是经过考据求证的。又比如说:挂在墙上的对联等,也多写得颇有意味。……从这些细节,也可隐约看出创作者的良苦用心。
《仙剑三》附带了不少诗词,算是一大特点。这些诗词,有些写得甚好,有些却只是一般。不过,想想《三国》《水浒》那样的巨著,所附的诗词也未必尽善尽美,似乎也不应在这点作过分苛求。
这些诗词,无疑在一定程度上刺激了玩家填词作诗的兴致。说《仙剑》成为了一种文化,很大程度就是来于玩家的诗文歌赋。由于缺乏专业的文学修养,在遣辞用字似乎也未必能让中文系那帮村学究满意,但有些作品所体现出来的灵气,却只怕要让不少迂腐的穷酸撞墙了。
说只是一定程度,那是因为,真正刺激动玩家填词是音乐。而这,似乎也从《仙剑三》才开始大规模流行的。《仙剑一》《仙剑二》的音乐,动听的也有不少,《蝶恋》《水龙吟》等也都可称经典。但,毕竟数目不是很多,而且也很多背景音乐一旦从游戏取出来单独听时,却总是欠缺了什么。而《仙剑三》和以后的作品,大多数本身就是非常悦耳的曲调,并且都安上非常高雅的名目,如《青玉案》、《水柔声》、《玉水明沙》、《行云织梦》等等。在这样的环境,玩家若想袖手作壁上观,怕是做不到了……
《仙剑三》本身的主题也选得很妙——轮回。
《仙剑一》的主题是宿命,坦白说,表现得并不好。倒是被唾骂的电视剧表现还凑合,李逍遥在“回梦游仙”时拼命要改变,但却改不了。这就是宿命。——当然,那句“地球是圆的”真的有点雷人。而《仙剑二》的主题是宽恕,这个主题定得点浅,所以,如果想表现得好,也更难。
轮回,这个主题,其实和“宿命”有点相似,都是对不可捉摸的命运的一种感叹。而在《仙剑三》中,轮回的主题,似乎更多地表现成了宿命。龙葵,守候千年的执念,最终还是随着铸剑炉的火焰化成烟尘;夕瑶,只是想着和喜欢的人一起,却只能以神树之实化成的替身代替自己完成这个实在平凡的心愿;紫萱,为了天长地久,几乎是不择手段,到头来却也只是镜花水月;重楼,对紫萱的爱慕至极,却只是说道“相见不如不见……我知道她平安就好”……念之人断肠!
《仙剑三》堪称经典的桥段极多,而相应的人物也更见饱满。霹雳堂,雪见劝景天逃走的场景,实在让人感动;而无极阁前,雪见两次殒命,则更是催人泪下!雪见,当然有雪见的缺点,用景天的话,就是“小心眼”。关于这个,我倒想借用龙幽的那句话:“说文了,那叫关心则乱;说白了,那叫喝醋。”但对着自己喜欢的人,谁真的做到淡定?美玉微瑕,却更见真质!
《仙剑三》中最突出的人物,该是重楼。《大众软件》在仙三外传的攻略上,曾如此形容重楼:无敌的酷哥,超人气的偶像!我一个朋友,并不怎么迷《仙剑》,但见到重楼惊为天人,硬是把QQ头像改成了重楼。但,我总觉得重楼在《仙剑三》的设定中,其实本来应该没打算这样潇洒(重楼的潇洒,简直就到了得瑟的地步)。至少,我相信是重楼本来该有两个唱对手戏的搭档:一位是没有正面出场的飞蓬,一位是徐长卿。
飞蓬,没有正面出场,但从重楼和夕瑶的态度来看,飞蓬应该也非常潇洒。只是由于没有正面出现,所以容易被忽视。而徐长卿,我觉得更多的是编剧做得不够。紫萱,何许人物?一个能让紫萱倾心三世的人物,岂同凡俗可比?但在游戏,更多却是看到徐长卿的固执。相比起来,倒是电视剧中的那位略带痴气的白豆腐可爱多了(电视剧中的清微掌门,也比游戏中那个老古董可爱)。神魔之井中,重楼对徐长卿的斥责,实在大快人心!
可能是主创人员也觉得没有好好表现徐长卿,有点歉疚,所以在《仙三外传》中出现的徐长卿就显得顺眼多了。当然了,在重楼面前,好像还是有点虚了。实在没办法,重楼太霸气了!
但成也重楼,败也重楼。重楼一个劲地抢戏,结果重楼的人气一度是《仙剑》中最高的人物,这叫景天情何以堪啊?不过,没关系,小紫英的出现,很快就结束了这个局面;而现在,龙幽的出现,也许会抢一点小紫英的风头……这就叫江山代有人才出!

6、
如果说《仙剑三》是创造了一个奇迹的话(毕竟,一个游戏能到这种地步,真的可说是奇迹了),那么,《仙剑四》简直就是一个神话!
我一直在想,《仙剑四》之后,《仙剑》到底该怎么做?
一种文化发展到极致,就会出现一个突出的特征:对于自身反思和解构。而在《仙剑四》中,这点已经非常明显了。《仙剑》的主题,原本应是寻仙;而《仙剑四》却自始自终都在反思和解构寻仙。原先的是非善恶,几乎都开始模糊和淡化。柳梦璃是妖,但却出尘如仙;琼华派道貌岸然,但其所作所为却实在令人不齿;梭椤树仙的选择,很难说是对是错;欧阳明珠对于厉江流,更是爱恨难分;琴姬伤心于秦逸之死,显得极是悔恨,但如果可以重来,却又很可能会做出相同的抉择……
《仙剑四》似乎只想讲一些故事,却不对这些故事多作评判,只是留给玩家自己去琢磨。比起《仙剑一》,李逍遥一开始就对灵儿图谋不轨(少装清纯,别说什么看见人家姑娘洗澡是不小心,那满脸的笑意,足以说明一切!还偷人家姑娘的衣服,……TMD,我这那么流氓都没干过这事),《仙剑四》的感情故事则显得清纯了许多,似乎一直在友情的圈子打转,只是到最后才开始显出爱情的征兆。
小野人很幸福,两个女主角都对他颇有情意。可是,小野人,到底是喜欢梦璃多一些,还是喜欢纱纱多一些?这可真是个问题。我觉得可能是喜欢梦璃更多一些,按我的经历,对着自己真正很喜欢的女孩子,的确很容易紧张。背地里是患得患失,疑神疑鬼;当面见着了,却只会不知所云胡说八道。一般,这样的感情很难有结果,因为自己根本就不知道该去怎么样经营,甚至都不知道该开始。这样的感情,只适合留作怀念。迫于客观环境的中止,如梦璃这样的,也许反而一件好事。而对着只是有好感的女孩子,表现一般会好很多,至少会正常些。
而纱纱,从一开始总觉得纱纱就是蹦蹦跳跳没什么心事的,只是偶尔透露出来的那一丝忧郁着实让人心疼。不过,还没等心疼结束,纱纱自己就又开心起来了。但渐渐深入,才很惊讶地发现原来这个貌似开朗的女孩竟背着这么重的包袱!开朗之中的那份柔情,更是让人感动。封神陵的心愿,固是让人潸然泪下;而树屋中的告白,更是教人肝肠寸断。被爱,固然幸福,但却也是可以压得人透不过气来的重担。但,重压之下的幸福,也许才是真正的幸福。
相比于小野人,小紫英则显得有点委屈。小紫英的人气据说是《仙剑》中最高的。想想也是,像小紫英那样的人,谁会不喜欢呢?但问题是,两个女角眼睛都只盯着小野人。小紫英也很有意思,好像对两个女主角都颇有情意,但好像又是什么都没有。潜伏得真够深啊!只是在冥河上,与韩北旷对话流露出来的那份悲伤,让人看看心都有些酸酸的。而幻暝界中,小紫英对表现出来的那么正气和刚强,则让人不觉得重复夙莘姐姐的感叹:小紫英已经是一个好男人了!
梦璃,是很特殊的女主角。整个《仙剑》系列中,梦璃怕是最不爱说话的女主角,更多的时候,只是嫣然一笑。“巧笑倩兮,美目盼兮”,这两句诗,似乎本来就是为梦璃而作的。梦璃和小紫英,有些地方倒是很相似:对自己的感情都很克制,对自己的选择也都很执着。梦璃,很能干,以制香之技福泽一方,但却又温润如玉,丝毫不露锋芒。梦璃,很善良,上善若水,似乎是对梦璃最好的评语。梦璃,也很坚强,也很痴情,……
《仙四》中,四位主角固然光彩鉴人,而如玄宵、云天青、夙瑶,包括那位萍踪一现的夙莘姐姐,也都各有特色。
玄宵,无可否认,是一个极具人格魅力的人。只是,最后与九天玄女的那场,我觉得,似乎和很多人想得不一样。有点像什么呢?就是《拳打镇关西》中,鲁提辖的那句:你要死硬到底,洒家没准还饶了你;你求饶,洒家偏不饶你!于是,镇关西悲剧了,因为求饶遇上了鲁提辖;玄宵更悲剧,因为遇上九天玄女。《孙子兵法》说“先知者,不可验于度”,这话还真TMD有道理!
夙瑶,原本应是真正的望舒剑宿主,因为这个女人在很多方面,倒真和玄宵倒真是一路的。不过,无论是心胸气度,还是资质才识,就不是一个层面了。夙瑶,好强但软弱、固执而狭隘。这四点,无论哪点,都领导决策者的死穴。夙瑶,居然全占了,也真算是一朵奇葩。
云天青,也许是我见过最完美的一个形象。我说不出云天青的优点在哪,但也说不出他的缺点在哪。他的大多数特点,都能在别人身上见到。率性正直?司徒钟不正是这样?善良宽容,古灵精怪?江小鱼在这点更加突出啊!痴情却又淡泊,胡逸之表现也很不错(胡逸之是《鹿鼎记》中的一个路人甲)……但混成一体,却是一个独一无二的云天青。
……
《仙剑四》可圈可点的人和事太多了,就算是铁泽居的刘铁山的那份单相思都能令人感叹良久。
音乐的烘云托月,使《仙剑四》自然更上层楼。《沧浪剑赋》(官方好像写“苍浪”,可能弄错了。“沧浪之水清兮,可以濯吾缨”,这应是“沧浪”二字的出处)、《行云织梦》、《君莫思归》、……当然包括最重要的《回梦游仙》,都已成为不朽的经典!
说不尽《回梦游仙》,唱不尽的《回梦游仙》!

7、
《仙剑四》之后,仙侠类的剧情到底该怎么做?
因为《仙剑四》似乎是很不厚道地把路都堵上了,若要在同一题材上作出新的突破,以我的智商,是真的想不出来了(所以,我现在还只能一个穷酸酒鬼)。
但这时《古剑奇谭》出来了。关于大宇公司内部的人事变更,外人无权置喙。只是,《古剑》上所传承的,我觉得还是《仙剑》的精神。所以我个人(注意这个词,只是我个人。只要我个人愿意,我想就算我把猫叫成狗也不犯法)也愿意把《古剑》作为《仙剑》的分流。分流,没有比较的意思。只是就如《仙剑三》所说的那样,神树也不知怎么了,本来是结一个果的,现在却结了两个!
《古剑》出来,颇具争议。不过,有争议,总比没有人理要好些。像我这个穷酸酒鬼,天天还想被争议呢,但没人要理我。
客观说,《古剑》的宏观构架非常出色,比起让我开始时觉得不可超越的《仙剑四》也未必逊色太多。这可能与主创人员精于历史有关。因为精于历史,所以,对于作品的内涵和构架也自然会更加重视,而且设计得也更高明(我认为历史是没有规律的。只不过,大家都喜欢规律,要不然没有安全感,所以历史学家就满足了一下大家)。
《仙剑四》的主题就是对于寻仙(更确切地说,是人的执念)的解构与反思。所以,如果再以寻仙为题,就很难超出《仙剑四》的范畴。所以,《古剑》很明智避开了这点,选择了对人性进行深入挖掘——特别在宿命已定的情况下,人到底该怎么生存?其实,类似的事,已经有人做过了,而且做得更好——加缪的《西西弗斯的神话》。只不过,这类哲学书,不太好读,所以,也没什么人读。当然,这些内在素质,对于编剧来说,就比较重要了,可惜,好像只有我一个半瓶醋才会这样觉得。
而且,《古剑》之前所预设完整的世界观,对于游戏的构建,也实在是功不可没。
我相信,《古剑》是先有设想好的主题,才开始在这个大架构上展开创作具体内容,而不是常见的先有故事再挖掘内涵。
这样,故事自然很容易就做到“体大精深”。但问题在于,执行编剧的那位仁兄,真的有能力体会出这个构架的其中三味吗?即使能体会出,能有能力表现得好吗?这个要求,还真不低。《古剑》的编剧,文采很足。但问题是,一个好的编剧(或者作家),最重要的素质根本就不是文采,而是对于人性的深刻认识。——不仅要把握的剧中每个人物的心态,还要把握玩家的在看这些对白时的心态。否则,注定找骂!
国内历来就最缺编剧,不仅是游戏,也包括电影、电视。事实上,《仙剑》《古剑》的编剧已经比很多电视剧的编剧好很多了。只不过,游戏编剧所面对的都是思想最活跃的这些人,不是菜市场上扫地、卖菜的老太太。这些人的嘴,一个个都挑得不得了……
依稀记得,周孝正先生谈到中国大学教育时说:“教育本身没问题,有问题的那是社会。教育问题,其实只是社会问题的一个体现。”先生这话,若是在这里套用一下,倒也适当。
常有人说,《古剑》的情节拖沓。但事实上,《古剑》的剧情环环相扣,非常紧凑,只是对话常常写得不得要领,所以才现得拖沓。
而且,玩家的很多心态有些犯贱,要吊点着这些人的胃口才好。怎么说呢?如果对白写得比较含糊,自然有些好事之徒会天天想着去挖掘。这时,善良的编剧会想:算了,真麻烦,还不如我直接告诉你得了……这时,有麻烦就该是编剧了。
举个例子,《古剑》刚开始时那两个官差大爷的对话,大家都骂真拖沓。但,如果编剧把这些对话不要放主线里。只是让那两个人杵在那。我想,会有无数的玩家兴高采烈地这些对话看完,然后,在网上不停讨论……
这招数,是有点下流。但没办法,很多人就硬是吃一套。你不给他吧,他天天惦着;你真要给了吧,他又不当回事。就像看泳装的模特,大家都想把遮着那几点扒出来看看。可是,作为一个资深老流氓,我告诉你:你要觉得这些色狼,真喜欢看那几点就错了。那些色狼只是喜欢扒这个过程……
除了这点,《古剑》还犯了一个创作的忌讳,就是过于强求。我不是说,要主创人员一个个都弄得从大悲寺里出来似的(虽然,我很尊重大悲寺的师父们,但我本人却不想当和尚,因为和尚不能酗酒),只是说有些事,是不可直接强求。注意我的用词:不可直接强求。
打个比方说,如要把盆里的水弄出来,直接猴急地用手抓,只是自找麻烦。把盆的角度侧一侧,水自然就流出来了。这就是道家所说的“无为而无不为”。把盆的角度侧一侧,这就是一个造势的过程。
凡事,不要直接强求。先注意蓄势,然后顺势而为。很多看似不可能的事,就可能比较轻松的做到。要体现方兰生的鸡婆性格,其实根本不用让他在主线上折腾。让他把该说的说完,就可以让他一边凉快去——反正,自有鸡婆的玩家会去招他说话的。再比如说,要体现尹酒鬼的才识,也不一定非要让他在雷霆之海中指语,让平时在醉话多说几句聪明点的怪话就好了。再比如,要给少恭的坏做伏笔,又何必非要让他多出一些很无谓的情节呢,多注意一下细节就好了……
而人物的刻画上,编剧的短板真是体现得淋漓尽致。尹千觞、红玉、少恭、秋桐,这四个都人精中的人精。结果呢,尹千觞,整一个不知所云;红玉,不像从天上来到人间,倒像是从天上人间出来的;少恭,怎么看怎么像岳不群;秋桐,基本就被无视了……而事实上,尹千觞,心中实有难言之隐,应该是浮华之中暗藏沉痛,这点倒是可以对比一下《仙剑五》的一贫道人,而不该是一味嬉闹;红玉,经历千年,应是老于世故但却执念深藏,而不该卖弄风骚;少恭,应该是温润如玉中自然带出丧心病狂,而不是分成两段,成了伪君子;秋桐,应该是处处冷眼旁观、玉蕴珠藏,而不是表现像个路人甲……
关于少恭,我想到一个不是很适当的例子,但应该可以说明一些问题。就是主父偃说的:“臣结发游学四十馀年,身不得遂,亲不以为子,昆弟不收,宾客弃我,我阸日久矣。且丈夫生不五鼎食,死即五鼎烹耳。吾日暮途远,故倒行暴施之。”
对于《古剑》的不足,倒真是说不了不少。不过,换我上场,也不见得就能做得更好。这就是常说的“看人挑担不吃力,自己挑担压断脊”。但《古剑》的构思,我是非常认同的,而且,我坚持认为,只有这样,才能出真正的精品。
只是希望,《古剑》不要因为过于关注市场而失去市场……

8、
《仙剑五》,可让我怎么说啊?
的卜!
《仙剑五》,可以说是对于《仙剑一》的回归。
不再关注太复杂的世界观,也不再关注什么内涵不内涵、文化不文化,只是一个游戏。好看、好玩,大家喜欢就好!——我猜,这就是主创人员的初衷。
这个想法,倒是很务实。
主创人员在细节的设定上,功力不凡。很多细节处理很微妙,处处勾起玩家心底对于是《仙剑一》的美好回忆。可是,积淀在心灵深处的回忆,我觉得,最好不要去多搅比较好,多搅就混了。
至于《仙剑五》……
昔日,谢灵运的诗,有很多传世佳句,如“池塘生青草,园柳变鸣禽”等。但整篇都被公认为是好诗,好像不多。我只是随口说说,没别的意思。可能是写乱了。
啊,《幽梦影》中有一句话,很有趣啊:“园亭之妙,在邱壑布置,不在雕绘琐屑。往往见人家园子屋脊墙头,雕砖镂瓦,非不穷极工巧,然未久即坏,坏后极难修葺,是何如朴素之为佳乎?”
不过,我书读得少、酒喝得多,也不知道是什么意思,看见就正好写上来了……反正,我只是也只图个华丽好看,就写上来了。
……
一贫道长喜欢酒,我也喜欢;一贫道长早年是个花花公子,我早年是流氓,我喜欢一贫道长。就像龙少喜欢小姜那种……
所以,《仙剑五》是个好游戏!

使用chrome原生代理api的代理管理插件

今天在台球室等桌的时候上GR,突然发现了这文章,http://www.chromi.org/archives/12679。真是大囧啊。。。我前两天就在改proxy switchy!的代码,想使它支持chrome原生代理,界面什么的都保持不变。到今天看到这文章的时候主要功能是已经完成了,不过还有点bug。。试了试这个扩展。。估计作者和我思路一模一样。。看来我的第一个chrome插件是夭折了。。。@@。最后附上插件链接。http://code.google.com/p/switchyplus/。囧囧囧囧!!!

Windows下chrome+proxy switchy!使用独立代理自动翻墙

本来如果chrome使用和firefox一样的独立代理设置的话,这种文章完全没有必要出现,无奈windows下面chrome使用的是ie的代理,而ie的代理又非常地乱,使得设置下来各种bug,比如有可能每次在线更新地址pac都会被清空,因而要把pac更新一次,再设为只读,比如有时候明明auto-switch模式,设置也正确但流量全是不走代理等等。今天折腾了一小时发现了一个比较完美的方法。

chrome在四月份发布的API中有独立代理设置的API,但proxy switchy!这种插件肯定是不会使用这种实验性质的api的,那有没有办法让它们共存呢?网上找了挺久后发现是有方法的,配置好后proxy switchy!负责更新需要翻墙的list,然后使用独立代理配置浏览器进行翻墙。

首先配置proxy switchy!,online rule list我找了一个新的list,内容取自autoproxy,但修复过兼容性,地址在这里 。然后随便切换成auto-switch模式上下网,就会在proxy switchy!的配置文件夹下面生成SwitchyAuto.pac,这就是后续步骤需要的东西了,proxy switchy!的作用就是提供这个pac文件。

这里可以下到google 提供的使用独立代理设置的examples。在extensions界面里打开developer mode,安装这个插件,完成后配置代理,使用之前的pac脚本,大功告成。