X the Unknown Becoming an “X'' in an equation.

21八/110

慎用 javascript 的 closure

javascript 的对象有一个不足的地方是没有提供公有和私有成员的区分，不过通过 javascript 提供的 closure，弄出私有的效果不算太难，但是使用 closure 却有可能带来效率的降低。我弄了一个简单的测试：

closure_test.js:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

var with_closure = (function() {
    var i = 0;
    var looper = function(loop) {
	var j;
	var start = (new Date()).getTime();
	for (j = 0; j < loop; ++j) {
	    i = i + 1;
	}
	var end = (new Date()).getTime();
 
	return end - start;
    }
 
    return looper;
})();
 
var without_closure = function (loop) {
    var i = 0;
    var j;
    var start = (new Date()).getTime();
    for (j = 0; j < loop; ++j) {
	i = i + 1;
    }
    var end = (new Date()).getTime();
 
    return end - start;
}

在 FF6 中，loop = 50000000的情况下：
With closure: 506 ms
Without closure: 269 ms

在 Chrome 15中，loop = 50000000的情况下：
With closure: 161 ms
Without closure: 78 ms

原因……估计大致是，内层函数需要先搜寻本函数内是否存在关于此变量的约束，如果不存在再去搜寻 closure 中的约束，这样的话自然就会使得变量的搜寻时间变长了。我没研究过 ECMAScript 的标准……不知道上面的猜测是否正确，就算正确也不知道是否是因为实现方式而导致的。

测试结果： closure 确实会带来性能的降低。虽然 closure 并非只是用来实现 javascript 中的私有，但如果仅仅是把 closure 用于实现私有，可能就有点滥用了。

分类: 程序设计 没有评论
23二/090

C++高阶函数（一）

0. 前言

看见了标题不要以为以下的内容是C++的高级话题。这里的``高阶''是与``函数''连在一起作为名词的。高阶函数（high-order functions）有点借用了数学中高阶的概念。当一个函数是以另一个函数作为参数，或者以另一个函数作为返回值的时候（或者两者兼备），就可以称作是高阶函数。举个例说：

typedef int (*int_func)(int);
 
int f(int_func g, int x) {
   return g(x);
}

这里，函数 f 就可以称作是一个高阶函数，因为它以另一个函数（实参 g ）为参数。

高阶函数在函数式编程里面是很普遍，在命令式编程里面可能比较少提到，但对于C++来说，高阶函数已经不是新事物了。很多地方，例如C++的标准库自身，或者C++的巨牛库boost，对在C++中使用高阶函数已经有不同方面的支持。虽然目前还有很多方面我还没有触及到，但为了避免自己没记性忘掉，我还是准备把我不完全的认识先记录下来，日后继续慢慢更新。嗯，期待自己能写出一个系列呢~。

1. 函数的生成

生成函数？

假如现在有一个简单的函数（实际上是函数对象。这里用的是函数的纯抽象概念：只要表现得和函数一样的，都可以叫作``函''。下面的描述，如果不需要严格区分函数和函数对象，那么我一律称作函数），作用是做加法的：

template <class T>
struct x_plus {
   T operator () (T op1, T op2) const {
      return op1+op2;
   }
};

如果有两个int变量x, y，那么

x_plus<int>()(x, y);

得到的结果就是x+y。对于x_plus<int>()来说，它是一个二元函数。

通过把其中一个值变成常量，x_plus<int>()就可以表现像一个一元函数了：

x_plus<int>()(x, 1); //     ---------------     (1)

相当于计算x+1。

函数生成的过程与上面的这个过程是类似的。通过将一个函数的某一个变量绑定为另外一个变量，就可以得到一个新的函数。

然而严格地说，上面的函数调用(1)依旧是二元函数，只不过其中一个参数被固定了。对于一个一元函数，它被期望的调用方式应该是：

_i_am_an_unary_function_(x);

于是，在对于一些需要使用一元函数的场合，x_plus<int>()是无法使用的：

template <class unary_function>
inline int _i_need_an_unary_func (unary_function f, int x) {
   return unary_function(x);
}
 
_i_need_an_unary_func ( x_plus<int>()(x, 1), 10 ); // error

std::bind1st和std::bind2nd

标准库的std::bind1st和std::bind2nd提供了一个解决方案，使得我们可以将x_plus<int>()转化为一个真正的一元函数：

#include<functional>
using namespace std;
 
_i_need_an_unary_func ( bind2nd(x_plus<int>(), 1), 10 ); // ok
_i_need_an_unary_func ( bind2nd(x_plus<int>(), 1), 10 ); // ok

这里的x_plus<>实现于最开始时候定义的有点区别，会在后面说明。

std::bind2nd(x_plus<int>(), 1)和x_plus<int>()(x, 1)的区别在于前者将一个参数绑定到某个已有函数的某个实参上，从而生成一个新的函数，而后者是一个函数调用（而且是不合法的函数调用，这里的 x 会因为未定义而产生编译错误）。所以对于std::bind2nd(x_plus<int>(), 1)，以下的调用是合法的：

bind2nd(x_plus<int>(), 1)(10); // ok, equivalent to function call: x_plus<int>()(10, 1)

std::bind1st和std::bind2nd是类似的，区别在于绑定参数的位置不一样：

bind1st(x_plus<int>(), 1)(10); // => x_plus<int>()(1, 10)
bind2nd(x_plus<int>(), 1)(10); // => x_plus<int>()(10, 1)

因为std::bind1st和std::bind2nd的实现是类似的，我只考虑实现其中一个的基本原理：

bind1st返回的可以是普通函数指针或者函数对象，然而对于返回普通函数指针，实现起来似乎不怎么方便>*<，所以一般都是返回函数对象：

template <class F, class A1>
struct x_bind1st_c {
   x_bind1st_c(const F& _f, A1 _a1) : f(_f), a1(_a1) { }
 
   return_type? operator () (argument_type? a2) const {
      return f(a1, a2);
   }
private:
   F f;
   A1 a1;
};

上面的实现还未完整，但不妨先进行分析。通过x_bind1st_c< x_plus<int>, int >(x_plus<int>(), 1)，就可以产生一个函数对象func。函数对象里面已经定义了operator()(...)的成员，所以可以通过func(x)的方式来调用这个函数对象，达到预期的效果。

实现中还有部分地方没有明确：operator()(...)的返回类型是什么？实参a2的类型又是什么？或许可以假定为与A1相同，但这毕竟没有普适性：要求一个函数的返回值与实参类型相同、所有实参的类型都一样，这样的要求显然不合理。函数需要返回什么值，实参接受什么类型，是被绑定的函数决定的，如此考虑的话，直接从被绑定函数中获取是最好的方法。为了这样，需要对x_plus<>的定义稍微修改一下：

21
22
23
24
25
26
27
28
29
30

template <class T>
struct x_plus {
   typedef T return_type;
   typedef T arg1_type;
   typedef T arg2_type;
 
   T operator () (T op1, T op2) const {
      return op1+op2;
   }
};

然后……重新写一次完整的x_bind1st_c的定义吧：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

template <class F>
struct x_bind1st_c {
   typedef typename F::return_type return_type;
   typedef typename F::arg1_type arg1_type;
   typedef typename F::arg2_type arg2_type;
 
   x_bind1st_c(const F& _f, arg1_type _a1) : f(_f), a1(_a1) { }
 
   return_type operator () (arg2_type a2) const {
      return f(a1, a2);
   }
private:
   F f;
   arg1_type a1;
};

x_bind1st_c是一个类模板，使用的时候必须显式指定模板的参数。可以利用函数模板的自动推导简化使用：

16
17
18
19
20

template <class F>
inline x_bind1st_c<F>
x_bind1st(F f, typename F::arg1_type a1) {
   return x_bind1st_c<F>(f, a1);
}

x_bind1st就这样完成了。（我并没有看过标准库的实现，所以我不保证这就是std::bind1st的实现方式。事实上我觉得标准库应该比我上面简单的实现考虑得更多，比如const和volatile关键字的修饰。不过我觉得基本原理应该是这样的。）

x_bind1st（算是简化+删节版的std::bind1st吧，所以下面把两者合在一起统称bind1st/bind2nd）的实现同时也提示了几点：

1、只能用在接受两个参数的函数对象上。

所以对于非二元的函数对象，无法使用bind1st/bind2nd；而且对于普通的函数，因为缺少return_type、arg1_type和arg2_type的定义，所以也不能直接使用；相同的情况存在于类成员函数指针中，不过成员函数指针的情况有点特殊，下面将会提及。

为了让bind1st/bind2nd可以为普通的函数绑定，标准库定义了一个ptr_fun，用来包装普通函数，使得bind1st/bind2nd可以用在普通函数上；对于类成员函数指针，标准库也定义了mem_fun/mem_fun_ref来包装，使得bind1st/bind2nd可以用在成员函数指针上：

int func1(int op1, int op2) {
   return op1+op2;
}
 
struct X {
   int func2(int op) {
      return op;
   }
};
 
std::bind2nd(std::ptr_fuc(func1), 10)(20);
std::bind1st(std::mem_fun(&X::func2), &x)(10);

成员函数X::func2只接受一个参数似乎和之前的说明矛盾。其实这是因为成员函数需要接受一个额外的参数（this指针的由来）。除去这个额外参数以后，就只能再接收一个了。

2、被绑定的参数只能是兼容于被绑定函数的可接收参数的类型（即存在隐式转换）。

简单的说就是你不能这样调用bind1st/bind2nd来实现生成类似于f(x)=(10+x)+x的函数：

std::bind1st(
   x_plus<int>(),
   std::bind1st(x_plus<int>(), 10)
)(20);

原因很简单，因为经过bind1st/bind2nd后得到的是一个函数。除非原来的函数接受的就是函数类型的参数，否则，由于不存在隐式转换，这样的调用将产生错误。

* 或许可以考虑一下返回的是一个函数指针。但如果返回的是一个函数指针，那么这个函数的定义至少应该类似于：

R bind1st(A2 a2) {
   return &func_to_be_bound(a1_bound, a2);
}

返回值、参数a1和a2的类型先不作考虑。

为了记录func_to_be_bound，bind1st必须定义为一个函数模板。这样的话就要求函数的参数列表中须新增用来接受func_to_be_bound的形参。这样的话又会破环bind1st的接口：

template <class f>
R bind1st(A2 a2, f func_to_be_bound);

另一个可能的形式是这样：

template <class F, F f>
R bind1st(A2 a2) {
   retrun f(a1, a2);
}

这种形式中 f 是一个非类型的模板参数。如果 F 是一个指针类型的话， f 就是一个指针，也能算是整型的非模板参数，所以这样的形式是接受的。问题在于调用须以这样的形式进行：

bind1st(a2_arg);

和之前的bind1st的用法差别甚大。或许可以尝试写一个辅助函数来简化：

template <class F>
R bind1st_aux(F f) {
   return &(bind1st<F, f>);
}

然而这种方式实际使用中会产生编译错误，因为模板的实例化参数使用了函数参数。函数参数的值是在运行期才能决定的，而模板则要求在编译期完成实例化。

而且上面那样的函数模板无法接受非整型的函数对象作为模板参数，除非把函数对象定义为全局变量，并将函数对象的地址作为参数传入。局部变量因为储存在栈区，地址取决于栈的使用状况，故只能在运行期判明，不能用作模板参数（我认为理论上静态变量也是可以的，因为都是储存在静态区，地址是可以在编译期决定的。不过在gcc 3.4.5上只有使用全局对象时编译才能通过）。

暂时能想到的用普通函数指针来实现会存在的问题就这些，似乎对于普通函数指针来说限制是比较多的。如果哪位有用普通函数指针的不错的实现的话，请告诉我吧！

另外，这不知道算不算是函数对象比普通函数要灵活的一个例子呢？

>back<

分类: C++, 程序设计 没有评论
7二/090

WinMain->main

我想基本上每一个有Windows GUI编程经历的人都知道：对于一般的Win32 Console程序（就是一般的C/C++程序），程序的入口是main；对于一般的 Win32 GUI程序，程序的入口是WinMain。

对于main不一定就是一般C/C++程序的入口，看过不少相关的评论也算是知道的，main仅仅是一个标准规定的符号；对于GUI程序，如果用前面的情况类比，那么WinMain也不一定就是入口。只不过……你想象过用main来换掉WinMain吗？

我是没有想过的，虽然这说的通，main怎么说都是标准的定义，WinMain不过是微软自己定的，但main没有WinMain定义的参数。再说进入WinMain之前的“初始化”也可能和进入main之前的不一样。

不过经过今晚，尽管无法断言初始化的工作是否一样（十有八九不一样），但是用main来代替WinMain，应该是行得通的。WinMain的四个参数中，第二个一般用不上，第三个和main的第二个差不多，第四个是可以显式指定的，剩下的第一个，可以通过GetModuleHandle(NULL)来获得，结果：

int main () {
 
HINSTANCE hInst = GetModuleHandle(NULL);
 
/*
 
...
 
*/
 
}

然后编译，链接，记得链接上GUI程序所必需的核心库。然后运行，得到的结果和用WinMain写的看上去是一样的，除了多了个黑色底的console window。

分类: 程序设计 没有评论
27九/086

认识迷宫

之前的某篇post上，我提起过我学习过了如何生成迷宫。乘今晚终于把迷宫游戏重新写了一次，来总结一下吧。

至于重新写的目的，皆因想顺便练习巩固一下学习过的设计模式的使用，不过我如今写的这个迷宫还是比较微型的，用到的不多。

来个截图先：

迷宫游戏的截图

迷宫游戏的截图

原理

话说我第一次接触如何生成一个迷宫应该是在初中的时候，因为我记得那个时候我才在我住的地方可以买到电脑报的报摊。看守报摊的是一对老夫妻了，不知道他们现在过得可好？

回到主题。我已经记得不清楚了，好像那时候上面的方法是有一个专门的数组，然后0代表通路1代表是墙的，接下来的就真的不知道了，因为那个时候我还看不懂。完全把迷宫写在一个数组里面应该算不上生成的方法吧，只是表示的方法，因为生成迷宫的是人脑不是电脑。

勉强算得上是方法的，应该是依靠填充0和1的随机数到一个二维的数组，0代表通路1代表墙，然后再图形化出来。不过这样的算法其实很囧，生成出来的能不能叫迷宫……我不知道了。

我不懂定义什么叫迷宫，不过我玩过的迷宫，一般都是只有一条路的，从起点到终点只有唯一一条路径，当然这不是绝对的，不过这种迷宫有一个附带的好处就是，你在迷宫走过的正确路径，可以构成唯一的一幅图画。我想这样的迷宫大家应该都玩过很多的啦。

其实可以让条件更严格：迷宫中任意一点都有且只有一条通往另一点的路径。

考虑一下这样的迷宫其实是什么？任意两点之间都有通路，而且通路唯一，也就是不会构成回路——没错，那就是树。

迷宫可以用树的结构表示这一点其实可以用来解释右手规则（或者左手规则）：这所谓的规则其实只是人工地遍历树罢了，迷宫的入口是树的根，出口是树结构中的某一个结点，所以是绝对可以从入口找到出口的。

所以怎样构建迷宫其实就是怎样去构建一棵树。那么有什么方法呢？

最直接的方法就是数据结构书经常有代码例子的直接生成啦，不过我感觉这个方法其实……跟人工生成没太大区别，你觉得呢？

间接生成树的方法就是从一个图中得出，比如说遍历，或者是最小生成树。图是现成的，一个3x3的迷宫完全可以看成是一个由9个顶点构成、每两个相邻的顶点之间就存在边的无向图。然后喜欢深度遍历还是Prim算法还是其他的就是你的选择了。

知道了以上的基本原理，生成一个迷宫就不是难事了。下面的没有什么原理上的东西了，只是我实现的具体细节。

分类: 程序设计, 设计模式 继续阅读
20八/084

Abstract Factory和Factory Method的区别

不得不说这两个囧模式看到我现在都还是不能很确认自己是不是真的了解它们之间的区别了。主要原因估计是Abstract Factory一般通过Factory Method来实现的原因。

（下文中，首字母大写正体的表示一个模式，如Abstract Factory，指的是Abstract Factory这个模式；首字母大写粗斜体的表示一个类，如Factory表示一个Factory的类；小写字母的表示一个对象，如factory表示某个类的一个实例，一个对象；其他的可以通过上下文区分其含义。）

经过多番钻牛角尖和刨书的结果，它们两个的区别，我认为还是比较基本的一点：虽然均属创建型模式，但是Abstract Factory是对象型而Factory Method是类型的（强烈BS一下中译版把这么重要的区别给弄没了）。

更具体一点来说，Abstract Factory把一系列的对象的创建留给了一个factory对象去创建。这里面包含了一个动态的概念：你可以动态地决定你的factory的将创建一堆什么东西（通过选择不同的Concrete Factory）。

而Factory Method则是一个静态的概念，它把一个对象的创建推迟到了子类，我们知道这在C++里面可以通过虚拟函数来实现。之所以说是静态的是因为，Factory Method里面的Product，在你进行类设计的阶段时就已经被固定为是经过Creator通过某个操作来创建的。为了创建一个Product的对象，你必须要通过Creator的这个操作进行。

尽管用什么Creator的子类对象来创建哪个Product的子类对象还是动态的，但是这不是Factory Method关心的范围。这也是因为Factory Method是类创建型模式所决定的：它关心的是Creator和Product两个类（包括子类）之间的关系：Creator负责了Product的创建，而这种创建将依赖于在Creator上面定义的一个操作（也就是一个factory method，``because it is resposible for "manufacturing" an object''）实现。这其实定义了一个Creator(Factory)->Product的关系。

而Abstract Factory之所以显得和Factory Method很接近——Abstract Factory指定了许多的操作，然后再在Concrete Factory里面定义好这些操作，负责创建对应的Concrete Product——是因为Abstract Factory通过Factory Method来实现的原因（所以，Abstract Factory里面的那些操作都可以称为是factory method）。

但Abstract Factory并非只能通过Factory Method来实现。如果说通过Factory Method来实现Abstract Factory使得Abstract Factory定义的类间和类层次结构与Factory Method很接近的话，通过Prototype来实现的Abstract Factory将可以把这个结构坎掉一大半，让Abstract Factory与Factory Method不再相似，只剩下一堆操作。这堆操作只起到接口的作用，并没有定义像Factory Method中那样的关系：尽管对象还是经由Abstract Factory这些操作产生，但本质上已经不再是Factory->Product的关系了（Prototype模式里面通过拷贝对象原型来产生新的对象，是一种prototype->product的关系。注意字体）。

然而根本不用管是否Factory->Product，因为Abstract Factory关心的只是，提供接口，隐藏内部细节，使得可以通过不同的factory object用相同的接口来产生不同系列的产品对象（其实就是不管如何都是显示为一个factory->product的关系。注意字体）。

这也是为何Abstract Factory定位为一个对象创建型的模式的原因吧。

分类: 设计模式 4 评论
27三/083

javascript里面的this

昨天的思考中遇到了this的问题。ECMA-262中，this是在执行上下文(Execution Contexts）中被首次提及的，所以或许我应该先了解一下什么是执行上下文。

执行上下文？

Excution Contexts（我简称EC吧），当程序的控制流进入一段ECMAScript可执行代码时，就会进入一个EC。活动EC在逻辑上会形成一个栈，栈顶EC就是当前运行的EC。

ECMAScript可执行代码？

ECMA-262中定义了三类这样的可执行代码：

  • 全局代码：用C的概念类比的话，就是main函数里面的所有语句。javascript程序的源代码，除了函数体以外，都可以看成是全局代码。

    我好像一直在混淆javascript和ECMAScript的概念了？其实ECMAScript可以认为是javascript和jscript的泛化，是一个标准化的规范。虽然我不知道javascript是不是完全兼容于ECMA的规范，不过ECMA中定义的大部分概念，对javascript应该都是适用的。

  • eval代码：eval，但凡解释性语言基本都有的东西。当然apply也是。eval/apply可谓亲密无间的伙伴，不过在这里它不是主角。eval代码就是应用到内建的eval函数的那些字符串。性质类似于全局代码。
  • 函数代码：全局代码里面并没有包括函数体的源代码，函数体的源代码属于函数代码的一部分。当然，函数体的源代码中如果包含嵌套的函数体，嵌套的那部分则是属于另一段的函数代码的。上一篇文章里面说过函数也可以通过new Function来创建，所以new Function的最后一个参数，也就是函数体，也会被看作是一段函数代码。

我猜想EC的并非以一种对象实现的。ECMA-262里面从头到尾都没有提起过所谓execution context object，甚至连context object的概念也没有看见。会有不少对象和引用附加在一个EC上，大概可以把EC理解成一个小型集合吧。

那么this到底和EC有什么关系？
this是EC上附加的一个……引用。this的值与调用者（主要对函数而言）和被执行的代码有关，并且值在进入EC的时候就已经定下来了。this是不可修改的。

this是跟可执行代码类型有关的：

  • 对于全局代码，this引用到全局对象。

    什么是全局对象？

    全局对象是javascript的一类原生对象Global Object，在进入EC之前就已经被创建。它有几个特点：

    • 不能通过new constructor构造。
    • 不能用作函数调用。
    • Global Object的类型以及prototype是跟具体的javascript的实现细节相关的。

    javascript提供的内建值（NaN，Infinity和undefined）、内建函数（eval，parseInt等）以及其他原生对象的构造函数（Object，Function等）都是Global Object的提供的属性。可以向Global Object中添加各种其他的属性。

    Global Object处于作用域链的最高层。至于什么是作用域链……再说吧，现在已经离题很远了。

    根据这些，现在可以猜想到的一点就是，在javascript里面这样的调用：

    eval("alert('hello');");

    其实是等价于下面这样的伪代码：

    global_object.eval("alert('hello');");

    回到this。因为对于全局代码，this引用到了全局对象，所以在全局代码里面使用this，跟没使用效果是一样的orz：

    this.a="hello";
    this.alert(a===this.a);

  • eval代码

    当进入的是eval代码的EC时，上一个EC，被称作调用上下文。eval代码里面的this，与调用上下文里面的this是一样的。如果没有调用上下文，那么eval代码会做与全局代码一样的处理。

    function test() {
    eval("this.a = 'hello';");
    alert(a);
    }
    test();

    不过实际上，这里的this用了跟没有用也是一样的。

  • 函数代码

    this的值由调用者提供。当调用者不是对象时，this将引用到全局对象上。

看到这里，虽然还没弄清楚到底调用者怎样提供this的值，不过可以猜想，如果调用者是对象的话，那么this将会引用到调用者自身。这就可以解释为什么new constructor的时候，this是指向实例化的对象了。如果作为普通函数调用，按照之前对全局代码得出的结论，应该跟global_object.a_function的调用是一样的。这样想的话，调用者就是全局对象了。

那样的话，总算明白了普通函数里面的this有什么意思了……

function test_class () {
this.v1 = '1';
}

/* new constructor方式调用，function code的
调用者为新实例化的对象，this引用到这个对象上。*/
alert((new test_class()).v1);

alert(v1); // 调用失败，v1未定义
test_class(); // 普通函数调用，this为全局对象
alert(v1); // 经过上面的调用，全局对象里面有了v1的定义

不过让ECMA-262里面提到的一点我不太明白：eval代码可能会没有调用上下文。那会是什么样的情况呢？是指eval语句是第一句的情况吗？还是说只有eval一句的情况呢？

说到这里仍然是有很多不明不白，唯一清晰了的就是this在普通函数里面有什么含意……嘛既然标题是关于this的，我也不去想先了。留给后一篇post吧。

分类: 程序设计 3 评论
26三/082

Javascript中prototype的菜鸟级思考

进入主题之前不得不承认，一直以来我都把javascript看成是java的缩水版，同一个公司出品。我一直不太喜欢java那笨重的身体，于是，javascript就也被我放进了不喜欢的PL的队列里面，javascript在我脑子里面大概都有4、5年没有更新过了。直到上个月着手为xtheukn做些小修小改的时候开始，我对javascript的理解才有了质的变化。

虽然挺想认真地再学一下这个有趣又强大的小玩意，不过时间是最大的问题啊……所以下面写的东西，可能会很肤浅也很多错误……

今天特意认真的看了看有关javascript的prototype部分，算是把之前不太懂的弄懂了一点了吧。

不过，大概还是停留在很低的水平上……

什么是prototype？

或许是我搜索能力问题，也或许是我脑子不太灵活的问题，自己在网上搜了不少关于prototype的讲解，但看了又看还是不太懂。后来找到了ECMA-262，仔细读了读，总算明白了什么是prototype了。

按照ECMA-262的定义，prototype是一个对象。利用prototype，可以在ECMAScript（javascript和jscript的泛化）中实现继承，它被构造函数（constructor）所持用的，可以通过constructor.prototype引用。

那么什么是构造函数？

构造函数其实跟普通的函数，单从函数的定义上面来说，可以说是完全一样的。唯一区分构造函数和普通函数的，大概就只有new操作符了。当new操作符作用在一个函数的时候，将会产生一个对象，然后在这个对象上调用这个函数，初始化这个对象里面的成员。

function BaseClass () {
this.var1 = 'Base';
}
var baseobj = new BaseClass();

然后baseobj.var1就会包含值'Base'了。javascript里面的所有对象，都可以通过new constructor(...)来实例化。

假如没有了new，那么对BaseClass的调用就是普通的函数调用，这时的baseobj就不是一个BaseClass的对象了，而仅仅是BaseClass这个函数的返回值。

当然，这样的话，对this的理解就不能停留在C++的层面上了。有空再慢慢看看这个this的含义吧。

在函数定义好以后它就持有一个prototype对象的引用，也就是constructor.prototype。这很正常，因为函数在javascript也是一个对象，到prototype对象的引用其实就是这个函数对象上的一个成员变量。constructor代表一个具体的构造函数名，比如说在上面的代码片段，constructor对应了BaseClass，引用BaseClass的prototype对象应通过BaseClass.prototype来引用。

函数对象

把函数也作为一种对象在解释语言里面很常见。在javascript里面，函数对象（Function Object）是一种原生的对象，也可以通过new constructor来实例化：

var func = new Function("v1", "v2", "return v1+v2;");

上面的语句定义了一个函数func，等价于：

function func(v1, v2) {
return v1+v2;
}

而当一个对象被成功实例化以后，它就会隐式的引用到构造函数持有的prototype对象上面。一个对象总会有一个隐式引用的prototype对象。

如果BaseClass的对象baseobj要引用一个变量var1，那么首先当然会去查找当前的baseobj对象上面有没有这个var1变量，如果有，取其值；如果没有，则通过这个隐式的引用回溯到BaseClass的prototype对象上面继续查找。很容易可以想到，如果在这个prototype对象上找不到var1，那么，因为这个prototype对象也是一个对象，它也有隐式引用的prototype对象，所以将会继续回溯到BaseClass.prototype对象所引用的prototype对象上继续进行查找，直到找到为止，否则就返回undefined。这种prototype之间的引用也称为prototype链。

需要记住的是prototype只能通过constructor.prototype来进行显式的引用，被构造函数实例化的对象只有隐式的引用，没办法显式的访问，所以类似BaseClass.prototype.prototype这样的调用是会失败的，除非BaseClass.prototype引用到的是一个函数对象。不过似乎构筑这种情况没什么实用性可言。

通过prototype链，javascript就可以实现继承了：

1 function BaseClass() {
2 this.var1 = 'Base';
3 }
4 function DerivedClass() {
5 this.var2 = 'Derived';
6 }
7 DerivedClass.prototype = new BaseClass();
8 var derobj = new DerivedClass();

这里关键的一句是第7行的语句。它把DerivedClass.prototype引用到一个BaseClass的实例（方便起见，记为baseobj）上面了。于是当第8行语句实例化一个DerivedClass的对象derobj时，derobj就会有一个对baseobj产生隐式引用，当在derobj访问一个不存在的变量时，就会通过隐式引用回溯到baseobj里查找。继承就是通过这样的方式实现了。

当然，因为baseobj是被DerivedClass所持有的，所以所有DerivedClass实例化的实例，都会隐式引用到同一个对象上面，也就是说，当baseobj有所变动，DerivedClass的所有实例都会受到影响。

需要注意的是哪些对象之间存在引用，是何种引用。假设存在构造函数CF，CF持有的prototype对象CFp，以及CF实例化的两个对象CF1和CF2：

  1. CF1和CF2是CF实例化而得到的，所以CF1和CF2对CFp存在隐式的引用。
  2. CFp是一个对象，假设构造它的构造函数是CFpCF，被实例化时CFpCF持有的prototype对象是CFpCFp，那么CFp对CFpCFp就存在隐式的引用。
  3. CF是一个函数，函数也是对象，也是通过某个构造函数实例化而得的，假设为CFCF，那么CF对CFCF也存在隐式引用。
  4. 最后，CF是一个构造函数，所以它有一个对CFp的显式引用。

从上面可见，CF1、CF2和CF之间是没有引用被引用关系的。也就是说，CF1、CF2对CFp的引用，是不受CF干预的。也就是说当CF.prototype改变了以后，CF1和CF2对CFp的引用是不会变的。

会产生循环引用吗？

我曾经考虑过这样的语句序列：

function func1() {}
function func2() {}
func1.prototype = new func2();
func2.prototype = new func1();
var v1 = new func2();
alert(v1.vv1);

看上去好像当v1检索vv1变量的时候：v1中不存在vv1变量，到func2.prototype找-->到func1.prototype找-->到func2.prototype找-->...，似乎会变成一个循环。

定义一个函数（也就是创建一个函数对象）的过程中有以下几个重要的动作：

  1. 创建一个原生的Function对象F
  2. 创建一个原生的Object对象O
  3. F.prototype <- O
  4. 返回F

实际的过程比上面列出复杂得多，不过已经足可见一个构造函数持有的prototype对象，是在定义的时候就已经引用到一个Object对象了。

然后看看func1.prototype = new func2()时发生了什么：

  1. 一个func2的实例F2被创建，根据当前func2的prototype是引用到一个Object对象O上面的，所以F2也是引用到这个O上面。
  2. func1.prototype <- F2

前面提到，constructor和实例化的对象之间是没有引用关系的， constructor.prototype的改变并不会影响已经实例化的对象所引用的对象，所以，F2此时仍然指向Object对象O上。 然后当下一句被执行的时候，func1.prototype已经被改变而指向F2，所以new func1所创建的对象F1会指向F2，而func2.prototype指向func1.prototype已经改变以后再实例化的F1。 然后v1被实例化，指向func2.prototype即F1。

然后看看实际的回溯路径： v1-->F1-->F2-->O

并没有构成循环。

想到这里算了。好像写了不少没用的东西了……不过就体谅一下我这等菜鸟吧。如果你发现有错的，请务必告诉我。

然后又一天被我这样花掉了，sigh……

分类: 程序设计 2 评论
21九/060

The Game of Life

介绍

与其说是game，其实它更像是一个simulation，在1970年由英国数学家J. H. Conway提出的。The Game of Life的规则很简单：假设有一个无边界的矩形网格（我更喜欢把它称作宇宙，或者universe），这个矩形网格中的每个单元可被一个有机体占据（同样地，我更爱细胞这个词，或者cell）。被占据的单元称为活的（alive），未占据的单元称为死的（dead）。哪一个单元是活的要根据其周围活的邻居单元（neighbor）的数目而一代代（generation）地发生变化，规则如下：

  1. 给定单元的邻居是与它在垂直、水平或对角方向上相接的8个单元。
  2. 如果一个单元是活的，但没有邻居单元是活的，或者仅有一个邻居单元是活的，则在下一代，此单元就会因孤独而死亡。
  3. 如果一个单元是活的，且有4个或4个以上的邻居单元也是活的，则在下一代，此单元会因为拥塞而死亡。
  4. 一个活的单元，如果具有2个或3个或的邻居单元，则此单元在下一代仍是活的。
  5. 如果一个单元是死的，则在下一代，如果它不多不少刚好有3个邻居单元是活的，则此单元变成活的。所有其他死的单元在下一代仍是死的。
  6. 所有的出生和死亡都刚好在同一时间发生，因此正在死亡的单元有助于另一个单元的出生，但它不能通过减少阻塞而组织其他单元的死亡；正在出生的单元也不能保护或杀死上一代中活着的单元。

以上是我从我第一次看到The Game of Life的书——Data structures and Program Design In C++——里面节选出来的，除了括号里面的字，因为我比较喜欢那样的称呼^_^。

第（6）点可能有点怪怪的，举个例子说。假如下面的©代表一个alive的cell，◎、①代表一个dead的cell，那么对于以下这样的情况，◎的位置的cell因为刚好有3个neighbors，将会变活。但这不会影响到旁边的标记为①的cell的生死，①位置的cell只有2个neighbors，没办法继续存活。

◎①
©©©

就是这么简单的6条规则（我承认我的那本书上写得有点长气），但这么简单的几条规则确可以变化出相当复杂的过程。不同的初始宇宙配置（就是第一代宇宙的模样），演变下去规模可以变得十分庞大复杂，也可能慢慢的变得稳定，有的甚至灭绝（全部细胞都挂了――b）。

在The Game of Life发明后不久，Martin Gardner就在Scientific American的专栏里面对它进行了讨论，很多人为之着迷。

没有理由的感叹一下，The Game of Life，会不会就是我们的现实生活的一个写照呢？在我们活着的这样的复杂不堪的世界里面，说不定只有几条十分简单的规则在不停运转着。

只是我们还没有发现（或者说没完全发现）The Game of Our Life的规则而已。

当上帝的助手——实现The Game of Life

Conway给我们定下了6条规则而把宇宙交给了我们。我第一次实现The Game of Life（好长……后面简称tgol好了）是在C++上，大约是2年前的事情了吧。最近无意中在emacs里面再次发现了它的身影，又正逢我在学习python，正好拿来练习练习。

于是好几个版本的tgol（在我编写的时候，tgol被我称做Life Game）诞生了，限界不限界的都有，到今天成功进化到了1.3.2版（其实我不太会定版本号――b，下载的链接可以在文章末尾找到），学到的还是不少的。

* 有界还是无界？

在Conway设定的tgol里面的universe本来是无界的。由于边界的原因，有界的结果跟无界的有时是大相径庭的。主要原因在于有界的宇宙，细胞一旦到边界了就无法继续发展，因而边界外也不会产生活细胞对边界内的universe进行干涉。

绝对不会是最有效，但绝对是最简单的实现有界tgol的算法就是一个矩形数组（在python里面就是list的嵌套），然后从最开始遍历到最后。对于边界的cell可以加入额外的监视哨消除特殊性，然后就没什么好说的了。

而对于无界tgol，用这样的算法实现会相对复杂一点。我们或许可以申请一个相当大的数组去表达我们的宇宙，但我们并没办法阻止细胞们的增长，再大的数组也可能容不下我们的细胞。而且随着数组的增长，遍历整个数组的时间会变得越来越长。第一版的tgol就是用这样的算法实现的，结果前100多200代耗时还忍受得了，200代之后就变得蜗牛一样了。

这似乎是个解决的办法：随时缩少数组的规模。这对于某些增大了然后又缩小的细胞社会（society）似乎是有效的。缩少数组的规模并非意味限制宇宙的大小，很简单的例子是，用一个100×100的数组去表示一个只有1个细胞的宇宙，很明显是小题大做，一个3×3的数组就足够了，10000次遍历和9次遍历差别可是很大的哦^_^。

然而事实上这种做法没什么效果，首先是，细胞社会不会一直缩小下去，很可能过两三代以后又开始变大了，虽然确实缩小了遍历次数，然而对于整个运行来说，显得苍白无力；其次是，有些society会一直膨胀不缩小，在我发布的1.3.2版里面的”five block”就是很典型的例子。

对于用数组存储universe的这条路径，我还构思过一个方法，然而没有用来实现：只对需要计算的cell进行计算。所谓的“需要计算的cell”，就是存在变活或变死可能性的cell。很明显一个没有neighbor的dead cell是不可能变活的，存在变化的只有仍然alive的cell以及它们的邻居。为了用这种方法，必须对这些需要计算的细胞进行额外的记录（不然还是得从头遍历一次来确认）。在一次计算结束后，剔除无法存活的细胞，对剩下的细胞继续进行计算，这样遍历的次数就会大大的降低了。

这跟稀疏矩阵十分相似。

* 三元组还是十字链表？

作为稀疏矩阵的两种常用实现方法，我认为三元组比较直观，十字链表比较灵活。

而应用在tgol又是怎样的情况呢？

为了索引某个位置的细胞是否存活，查找是必须的。在理想的情况里面，对于三元组，一次索引就意味着平均要花上０.5(number_of_cells+1)次的比较。相比起来，十字链表需要的次数要少一些：假设细胞们很整齐的排成m×n，那么要索引到一个细胞平均起来需要0.5(m+n+2)次（行平均次数＋列平均次数）比较。如果进一步假设m=n=sqrt(number_of_cells)，平均就要花上(sqrt(number_of_cells)+1)次的比较。

而要决定一个细胞存亡的命运，必须进行9次索引操作（8次用于邻居，1次用于自身），合起来一共是9×number_of_cells次索引。

看得出用十字链表效率上是比较高的，主要原因应该是出于十字链表本身可按行按列遍历。当然换来的是空间上的损耗，不过从性能提升的角度来看，那些损耗是“物超所值”的。

* Cross List? Hash table?

哈希表的使用完全归功于我的tgol启蒙书——还是开头我说的那本。实际上，v1.3.2的实现就是用哈希表而不是十字链表实现的。事实上我没用十字链表实现过tgol，因为在我想到十字链表实现法之后的不久我就再次拜读了启蒙书去了，并发现hash table的效率似乎更优于cross list。

Hash table以其O(1)的时间复杂度著名，主要原因在于它在实现上还是一个数组，要访问hash table里面的元素就跟访问数组一样——直接定位，即使有冲突的问题存在，但无论是顺序hash table还是链式hash table都有一个有效的解决方法（我个人更欣赏链式的）。

那么选择hash table的原因就很明显了：O(1)的时间复杂度。这意味着，对于每个细胞，很多情况下1次查找就可以索引出结果了。尽管hash table中的冲突现象难以消除，但对于一个合理大小的hash table配合一个合理的hash函数来说，冲突是比较少的。

这样效率上的优势就很明显了，hash table的实现，可以把索引需要的查找次数控制在次低（仅仅从指定cell的查找次数方面评价，正牌的数组绝对是大哥，随机索引一次完成。而对于有一定规模的数据，hash table的冲突是很难避免的，而解决冲突必定会引入更多次的索引）。

---

回头一看发现自己已经写了2千多字了……希望自己写的不是些无用的废话吧。

刚刚回看自己的tgol代码，发现有些小细节还可以改进，代码就先不公开贴上来了，等我再写好点先……由于1.3.2里面用到了windows的API的关系，拙作暂时只能运行在windows系统上，可以在这里下载用py2exe发布好的win32-binary。1.3.2还只是windows console下的字符版，以后有时间，或许会利用python再写一个gui版吧。

感谢Conway的The Game of Life给我带来的欢乐。

分类: 程序设计 没有评论

近期文章

最新评论

  • 正在加载...

分类目录

标签

功能