寻找发帖“水王”

编程之美第2.3题————寻找发帖“水王”

题目描述:

Tango是微软亚洲研究院的一个试验项目。研究院的员工和实习生们都很喜欢在Tango上面交流灌水。传说,Tango有一大“水王”,他不但喜欢发贴,还会回复其他ID发的每个帖子。坊间风闻该“水王”发帖数目超过了帖子总数的一半。如果你有一个当前论坛上所有帖子(包括回帖)的列表,其中帖子作者的ID也在表中,你能快速找出这个传说中的Tango水王吗?

首先,我们可以假设有这样一个数据结构来表示帖子

[cpp]
type struct post
{
char* title;
char* content;
int uid;
}post_t;
[/cpp]

题目告诉我们已知所有帖子的列表,也就是说我们知道了所有帖子的链表 post_t* post_list,或者是所有帖子的数组post_array[num]。然后让我们找到出现次数最多的uid是多少,并且该uid一定超过了总和的一半。为了叙述方便,下面用数组举例。最容易就想到的方法,就是遍历整个数组,记录每一个uid出现的次数,然后再比较一下,求出最大的。

其实,这个问题就可以等价于:求数组中出现次数大于一半的那个数

解法一

对数组排序,然后遍历排好序的数组,统计各ID出现的次数,找到超过一半的那个即可。代码如下:

[cpp]
int Find (int* post, int len)
{
sort(post, post + len);

int num = 1;
for(int i = 0; i < len; i++)
{
if(post[i] == post[i + 1])
num++;
else
num = 1;
if(num > len / 2)
return post[i];
}
return 0;
}
[/cpp]

这里先调用了一下sort函数排序,也可以换成自己的排序函数。

因为采用了排序,复杂度有所提升,于是书中提出了第二种解法,我觉得是比较巧妙的。

解法二

由于x出现的次数大于总数的一半,所以如果每次删除两个不同的值,不管是否有x,在剩下的数中,x的次数依然会大于总数的一半。

于是,算法可以这样设计

[cpp]
int Find2 (int* post, int len)
{
int x;
int times = 0;
for(int i = 0; i < len; i++)
{
if(times == 0)
{
x = post[i];
times = 1;
}
else
{
if(x == post[i])
times++;
else
times–;
}
}
return x;
}
[/cpp]

该算法不用排序,很巧妙的通过向前移动达到了“删除”的目的,自己真的没想到:)。

越来越觉得优美的代码就是美了,简洁明了,而又功能强大。

扩展问题:

随着Tango的发展,管理员发现,“超级水王”没有了。统计结果表明,有3个发帖很多的ID,他们的发帖数目都超过了帖子总数目N的1/4。你能从发帖ID列表中快速找出他们的ID吗?

解法x

这个思路就是一样的了,设a,b,c三人的发帖数都超过了 1/4,那么把4个不同id删除以后,并不影响剩余数组中a,b,c三人的发帖数都超过1/4这个结果。示意图如下所示。

QQ图片20130721232439

把数组分为四个四个数字一组的来看。由于a的发帖数超过了1/4,所以,平均下来,在每一个分组里都有一个a,并且至少在某一组中有大于一个的a,假如分组1中的四个数字都不相同,我们删除分组1,如果a不在分组1里面,那么在剩余的2~n组中,a出现的次数显然会继续大于1/4;如果a在分组1里面,那么在剩余2~n组中,平均下来,a还是会至少在每一个分组出现一次。所以只要分组1中4个数字不相同(主要是保证没有两个a),那么删除分组1,并不改变a在剩余数组中出现次数依然大于1/4的事实。同理b,c。

代码如下:

[cpp]
void Findx(int* post, int len)
{
int a, b, c;
int ta = 0;
int tb = 0;
int tc = 0;

for(int i = 0; i < len; i++)
{
if(ta == 0)
{
a = post[i];
ta++;
}
else if(a == post[i])
ta++;
else if(tb == 0)
{
b = post[i];
tb++;
}
else if(b == post[i])
tb++;
else if(tc == 0)
{
c = post[i];
tc++;
}
else if(c == post[i])
tc++;
else
{
ta–;
tb–;
tc–;
}
}

cout << "a: " << a << "\t";
cout << "b: " << b << "\t";
cout << "c: " << c << "\t";
}
[/cpp]

Enjoy!

求二进制数中1的个数

编程之美第2.1题————求二进制数中1的个数

题目描述:对于一个字节(8bit)的无符号整形变量,求其中的二进制表示中“1”的个数,要求算法的执行效率尽可能的高。

书中由浅入深地给出了几种解法。

解法一

也是最容易想到的,因为对于无符号整数,若采取对2取余操作,结果只有两种,奇数余1,偶数余0,而奇数的二进制最后一位为1,偶数的二进制最后一位为0。这样我们就可以通过奇偶判断来得到结果,以二进制数1011和1100举例:

1011 对2取余,余数为1,二进制末尾为1,即含有一个1

1100 对2取余,余数为0,二进制末尾为0,即含有一个0

不管这个二进制数的高位有多少个0或者多少个1,对2取余的操作只与最低位相关。所以,如果能够把所有的位都作为最低位,对2取余一次,然后将结果相加,即可得到该题答案。而二进制数中,右移操作,就相当于除以2,所以有了以下解法。

[c]
unsigned int Count (unsigned int x)
{
unsigned int num = 0; // the result
while(x) // end of loop when x is 0
{
if(x % 2 == 1) // to judge whether the last bit is ‘1’
{
num++;
}
x = x / 2; // same as x >> 1
}
return num;
}
[/c]

当然你要是觉得除法耗费时间,可以把x = x / 2改成 x >> 1,本质上是一样的。

解法二

既然提到了右移,就能想到,右移的时候会把最后一位移丢,那我们只要在每一次移动的时候,判断一下最后一位是否为1,然后重复该步骤直到将所有位都移除。用1011举例:
1011,最后一位是1,结果加1,右移一位,变成0101

0101,最后一位是1,结果加1,右移一位,变成0010,

0010,最后一位是0,结果不加,右移一位,变成0001,

0001,最后移位是1,结果加1,右移一位,变成0000,所有位都已移除,结束算法。

而判断最后一位是否为1,可以用&操作,x & 0x1 即可。

算法如下:

[cpp]
unsigned int Count2 (unsigned int x)
{
unsigned int num = 0; // the result
while(x) // end the loop when x is 0
{
// x & 0x01 will be 0 if the last bit is ‘0’, otherwise ‘1’
num = num + (x & 0x01);
x = x >> 1; // right shift 1 bit
}
return num;
}
[/cpp]

可以看到,上述两种解法对每一位都进行了比较运算,时间复杂度都为O(log2x),出于降低时间复杂度的角度,书中又给出了第三种解法,让复杂度只与二进制数中‘1’的个数相关。

解法三

该解法确实好玩儿,让我有一种“让广大码农飞,让搞算法的死”的感觉,很巧妙。还是先举一个例子来阐述原理:对于无符号一个二进制数x,与 x – 1 采取&操作会消除x最低位的1,假设x为1010,0000:

x – 1 的二进制为 1001,1111,与x进行&以后得1000,0000,最低位的1没有了,让x = 1000,0000

x – 1 的二进制位 0111,1111,与x进行&作以后得0000,0000,最低位的1没有了,x 为0,结束算法

算法一共就执行了两次,即‘1’的个数。不管‘1’之后有多少个0,x & (x – 1) 总是会消除最低位的1,这就是该算法的巧妙之处了。代码如下。

[cpp]
unsigned int Count3 (unsigned int x)
{
unsigned int num = 0;
while(x)
{
x = x & (x – 1);
num++
}
return num;
}
[/cpp]

算法把时间复杂度降到了O(n),n为二进制中‘1’的个数。应该算是很不错了,关键是很巧妙,灰常好玩儿有木有。

书中还给出了查表法,因为题目是八位的二进制,那么一共也才256个数,完全可以开一个256大小的数组,将结果存起来,如255的二进制为1111,1111,让result[255] = 8,同理把其他所有数的结果都存一遍,以后需要的时候直接返回result[x]就可以了。只是如果不是八位的,变成了32位,那查表这种空间换时间的方法就很不划算了。

后来查阅网上一些题解的时候,发现很多大牛对此题书中解法的提出了质疑。比如解法三,虽然理论上一次地址计算就可以解决,但实际上这里用到一个访存操作,且第一次访存的时候很有可能那个数组不在cache里,这样一个cache miss导致的后果可能就是耗去几十甚至上百个时钟周期(因为要访问内存)。而对于这种数据规模给定,而且很小的情况下,耗去几十甚至上百个时钟周期是很慢的。所以对于这种“小操作”,这个算法的性能其实是很差的。

然后我看到了另外一个巧妙的解法,有点像二分,个人灰常喜欢。

解法X

怎么说呢,先举个例子,比如整数212的二进制1101,0100,一共有4个‘1’对吧。而正好又是8位大小,有没有一种“对折对折再对折”的冲动,有木有?

于是算法可以这样描述:

先把相邻的‘1’的个数算出来,同样二进制的形势保存起来

QQ图片20130720202159

那么现在 10,01,01,00分别代表了1101,0100中相邻两位中‘1’的个数。而且由于是计算的相邻两位,所以‘1’的个数最多为2,所以用两位足够表示。

现在的问题变成了,如何继续处理第一步得到的结果1001,0100呢,对于1001,0100,

第8位,第7位联合起来,即10,表示了原二进制数(1101,0100)中第8位与第7位所含‘1’的个数。

第6位,第5位联合起来,即01,表示了原二进制数(1101,0100)中第6位与第5位所含‘1’的个数。

第4位,第3位联合起来,即01,表示了原二进制数(1101,0100)中第4位与第3位所含‘1’的个数。

第2位,第1位联合起来,即01,表示了原二进制数(1101,0100)中第2位与第1位所含‘1’的个数。

现在我们就需要把新得到的二进制串1001,0100的

8、7联合位与6、5联合位相加,即把10和01相加,代表原第8,7,6,5位的‘1’的个数

(因为8、7联合起来才表示原第8位和原第7位一共有多少个‘1’,这里不能再次分开计算他们了,应该把他们当成一个整体。同理6、5位,也当成一个整体来看待)

4、3联合位与2、1联合位相加,即把01和01相加,代表原第4,3,2,1位的‘1’的个数

QQ图片20130720225843

后面就类似啦,把0011与0001相加,代表原第8,7,6,5,4,3,2,1位的‘1’的个数

QQ图片20130720230443

就得到最后的结果了,结果为4。

好了,现在剩下的问题就是怎么样让相邻的位相加,怎么样让相邻两位的相加,怎么样让相邻四位的相加。

拿相邻两位的相加举例,

(x & 0x55) + (x >> 1  & 0x55)

因为0x55展开成二进制就是0101,0101,观察1的位置,奇数位为1,偶数位为0,这样和x进行与操作的结果就是保留了x的奇数位。然后x右移一位以后,再与0x55进行与操作,对x>>1来说是保留了奇数位,但相对于原来的x则是保留了偶数位。最后将两式相加,就得到了x的二进制中,相邻两位的‘1’的个数。

同理因为0x33展开成二进制是0011,0011,所以相邻二位的相加则为

(x & 0x33) + (x >> 2 &  0x33)

因为0x0f展开成二进制是0000,1111,所以相邻四位的相加则为

(x & 0x0f) + (x >> 4 &  0x0f)

所以算法如下:

[cpp]
unsigned int CountX (unsigned int x)
{
x = (x & 0x55) + (x >> 1 & 0x55);
x = (x & 0x33) + (x >> 2 & 0x33);
x = (x & 0x0f) + (x >> 4 & 0x0f);
return x;
}
[/cpp]

优美的代码总是很简洁,这个算法估计只要十几行指令吧,速度应该是很不错了,至于网上其他更好的算法,写得让我半天看不懂哈哈~~感觉太复杂了也就失去了美。

最后,POJ的相关题目有Problem2453

原题链接:http://poj.org/problem?id=2453

解题报告:http://keping.me/poj2453/

That’s all,

Enjoy!

读《怀才纳贿的“二皇帝”和珅》

001

                                               和珅(1750~1799,清朝人,钮祜禄氏),权臣,豪商,巨贪。

读这本书并不是因为什么“读史可以明智”,还达不到那个境界。“以史为鉴”倒还是不错的。

读这本书是因为最近开始对历史有些感兴趣,恰巧在书店转的时候,又被它诙谐的语言,文学的形式所吸引,离开的时候也就带上了。从来没见过一本史书可以这样写,让人读起来毫不费力,有一些像小说。

本书从和珅出生,到求学,到考公务员(是的,原书写的就是考公务员),再到后来的官场沉浮,一直写到乾隆驾崩以后势力的迅速没落,最后上吊自杀。全方位、多角度地展示了一个真实的和珅,一个有血有肉的和珅。

此前,接触和珅最多的则是从电视上——《铁齿铜牙纪晓岚》,一部饱受争议的电视剧,最大的争议点当然还是不符合历史。其实大可不必纠结,电视剧本来就是用来消遣的,君不见广大抗日神剧中,八路军小战士手撕日寇么,难道这也要去算一算作用力与反作用力?

再说和珅,王刚先生之所以把和珅演的惟妙惟肖、脍炙人口,不是因为多像历史的和珅,而是因为多像剧本。试问,你见过哪个电视剧的反面能演到如此让人又爱又恨看不到又想的程度么?王刚的和珅,走的是“戏饰和珅”的感觉。结合剧本的语境词境意境,将和珅一角色表达的生动活泼惟妙惟肖。

只是,和珅真不是一个大胖子啊,王刚先生。

据广大史书记载,和珅是一个美男子,而在不是以肥为美的大清,我觉得,和珅应该不会是一个胖子。

回到书中,给我印象最深的,除了和珅的干女婿刘国泰借银填仓那一段(因为最近发生的黑龙江火龙烧仓事件,实在是很难让人不起联想),就是和珅对夫妻、兄弟、朋友之前感情的珍视了,他也有他善良的一面。不过好像上天并不眷顾他们家,在各自前途最光明的时候,都相继死去,以致最后的描写的和中堂都有点让人惋惜的感觉。

如果你还没读过这本书,也碰巧想了解一下中国史上第一贪的话,可以试着读一读。走近和坤跌宕起伏、颇具戏剧色彩的人生,无疑也能让你对人性、对历史有更多的体会。

2013-7-17 于 北京

MySQL 插入错误

MySQL insert error。。。。。。。。

 

一条简单的SQL语句,竟然插入错误:

INSERT INTO USER (id, describe) VALUES (‘David’, ‘diudiu’);

咋一看确实没错啊,瞅半天才发现,是由于table中有字段名是MySQL的保留字。这里就是‘describe’,报错也就理所当然了。

解决办法:
在关键字的地方加上反引号”`”,就是键盘1旁边的那个字符。

MySQL就是通过添加反引号来区别保留字。

上述修改为

INSERT INTO USER (id, `describe`) VALUES (‘David’, ‘diudiu’);

即可。

 

 

Linux 下 C++ 连接 Mysql

——国外有一篇博客写得挺好,有一些小错误,改正以后翻译过来,发这里了。

C++是一个效率非常高的编程语言

Linux 是一个类Unix操作系统,它促进了开源软件社区的发展,并且用这些开源软件就几乎足以构建一个复杂精妙的企业系统。

MySQL是一个流行的多线程、多用户的数据库管理系统,全球有超过1000万的安装量。

 

这篇文章将演示如何在Linux下用C++连接MySQL。

首先我们需要将所需要的头文件和库全部包含进来

#include <stdio.h>

#include <mysql.h>

然后我们来定义一下main函数

int main()

{

// code 

return 0;

};

然后我们定义一下需要用到的变量,你应该将这些写到main函数里去。

MYSQL_RES *result;

MYSQL_ROW row;

MYSQL *connection, mysql;

int state;

既然要使用MySQL数据库,我们首先就得连上它,使用下面的代码即可:

mysql_init(&mysql);

connection = mysql_real_connect(&mysql,host,usr,pswd,database,0,0,0);

其中

host – 数据库所在主机的名字,比如 “localhost” 或者 “192.168.250.100”

usr – 连接数据库时使用的用户名

pswd – 连接数据库时使用的密码

database – 数据库的名称

如果有错误发生,如用户名/密码不匹配,我们可以通过以下代码获取到错误信息:

if (connection == NULL)

{

printf(“%s\n”, mysql_error(&mysql));

return 1;

}

如果没有错误,那么证明我们连接好了,现在我们来执行一个简单的查询语句,其中mytable指的是你指定的数据库中的一张表名:

state = mysql_query(connection, “SELECT * FROM mytable”);

if (state !=0)

{

printf(“%s\n”, mysql_error(connection));

return 1;

}

如果成功执行,我们可以使用一个变量来存储查询结果:

result = mysql_store_result(connection);

使用mysql_num_rows函数,我们可以得到查询结果的条数:

printf(“Rows:%lld\n”,mysql_num_rows(result));

使用mysql_fetch_rowwhile循环中处理每一条查询结果:

while ( ( row=mysql_fetch_row(result)) != NULL )

{

printf(” %s, %s\n”, (row[0] ? row[0] : “NULL”), (row[1] ? row[1] : “NULL” ));

}

最后,别忘了释放内存:

mysql_free_result(result);

mysql_close(connection);

IMPORTANT!!! How to make this code under Linux?

重要!!!!在Linux中怎样编译上面的代码呢?

g++ test.cpp -I/usr/local/mysql/include /usr/local/mysql/lib/libmysqlclient.so

路径有可能不同,修改为自己的即可。

/usr/local/mysql/include 中含有mysql.h等头文件

/usr/local/mysql/lib/libmysqlclient.so 这个动态链接库也是需要的

Enjoy!

 

 

Paper things

在线考试系统功能需求以及数据库定义

由于是技术说明文档,就不再叙述背景以及国内外现状等。

在线考试系统模块需要实现的功能在这里分传统题目考试、程序题目在线判定(Online Judgement)两大部分叙述。

一:传统题目部分

对于题库:

1. 能够添加多种题型(单选、多选、判断、填空、简单等)

2. 能够添加多种题目分类(如“计算机基础“,“管理“),并支持子类父类(如”C语言” 属于 “计算机基础”)

3. 对于每一种题型,能够添加试题

4. 对于每一道试题,有正确率统计,便于出题的时候进行难度判断

5. 对于每一道试题,能够指定属于哪一分类

6. 对于每一道试题,除了设置答案以外,还需有答案解析,便于实现以后某些功能需求(如某些考生看不懂答案)。

对于试卷:

1. 能够设置试卷的名称、分类等(分类参考题库模块的分类)

2. 能够直接从题库里提取试题,组成试卷

3. 组卷选题过程中支持重复性检测,以及难度提示(根据题库中题目的正确率等作为参考)

4. 支持相同题型不同分数(即可根据难度设置分数,参考高考理综考试)

5. 能够查询某一时间段里出的试卷(如今年期末考试出题想参考1999年的试卷)

对于考卷:

1. 能够将试卷的题目乱序以后组成考卷

2. 维护考卷的基本信息

3. 记录考卷中每一道题的正误(题库中题目的正确率来源于此)

4. 支持缓冲。由于对于每一次考试,有多少考生参加就有多少张考卷,如果对每一道题都访问数据库,会由于频繁反问造成系统效率不高,所以需要提供缓冲机制。

5. 支持到时间收卷

对于考生:

1. 维护考生的基本信息

2. 考生作为与外界系统的主要接口,将其他系统的用户与在线考试系统联系起来,所以在该系统中,考生参加考试一律只使用考生编号。

总体草图

QQ图片20130626102929

对于数据库:

1.  由于在该系统中会涉及到较多的事务处理,所以讲数据库引擎采取ENGINE = InnoDB模式

2.  数据库表如下图所示。

QQ图片20130730221759

QQ图片20130730221827

具体每个字段代表什么,以及具体的SQL创建语句已经在“数据库创建语句.sql”里详细列出,这里给出对于某些数据库表的解释:

question_type是什么表?

题型表。如单选题、多选题、判断题、填空题、简答题等。

category是什么表?

类型表。该表包含了指向自身的id,用以实现子类型与父类型的关系。

question是什么表?

题目表。包含题型id,内容id,分类id,出现次数,正确的次数

为什么question表中要单独设置frequency(出现次数)和correct(正确次数)?

为了统计题目的实时正确率,为出题的时候提供难度判断。如果采取直接储存正确率的方式,每当该题目出现在考卷中一次,则需要重新统计该值,工作量巨大。

question表中content_id指什么?

题目具体内容编号,即type_xxx表的id号。

题目具体内容表type_xxx中,都具有describe, analysis以及answer字段,为何不把它们提取出来写到question表中?

为了保持question表的整洁,特别是在需要做一些统计(如题型正确率统计、某一类型出题率等)以及其他操作的时候,只用很少的字段即可完成需求。所以question表里存的都是各相关表的索引ID。基于同样的原因,由于question表里已经有了content_id,为了减少数据的冗余,把具体内容全部移到了type_xxx表中。再者,由于不同题型的试题所需的答案的长度不同(如,判断题只需要1个字符,简单题可能需要500个等),也应该把该字段放到各自的内容表里去。

paper、paper_content、exam_content、exam各是什么表,之间有什么关系?

这四张表主要是用来实现试卷与考卷功能的。

paper为试卷表,paper_content为试卷内容表,exam为考卷表,exam_content为考卷内容表。

paper表主要维护了试卷的基本信息,paper_content表中主要是试卷包含的试题以及该试题在该考卷中的分数设置。

exam表主要维护了考卷的基本信息,包括该考卷属于哪一套试卷,该考卷的考生id,该考卷的开始以及结束时间。exam_content则包含了考卷中具体的题目、该题目出现在考卷中的位置信息及考生的答案。

examinee是什么表?

考生表。其中id代表考生的id。uid代表用户id,是与外部系统对接的时候,外部系统的用户id。

二. 程序题目在线判定

以C语言程序设计课程举例。某老师开设了C语言课程,布置作业后,学生提交C语言程序。老师希望有系统能够自动判定学生提交的程序,并反馈结果(如编译错误,运行通过所有数据,运行超时,使用内存超出题目设定值等)。流程图如下:

online judge

流程解释:

  1. 学生提交程序到系统
  2. 系统进行编译,如果出错则返回错误信息,如果正确进入第3步
  3. 运行程序,并从数据输入文件中输入数据
  4. 运行时候,如果运行错误、超时、超过题目设定的内存使用量则返回错误信息,如果运行正确则得到输出数据并进入第5步
  5. 将学生程序产生的输出数据与标准输出数据对比,反馈结果(Accept或者Wrong Answer)
  6. 结束。

PHP调用C/C++动态链接库

摘要

有时候,单纯依靠 PHP “本身”是不行的。尽管普通用户很少遇到这种情况,但一些专业性的应用则经常需要将 PHP 的性能发挥到极致(这里的性能是指速度或功能)。由于受到 PHP 语言本身的限制,同时还可能不得不把庞大的库文件包含到每个脚本当中。因此,某些新功能并不是总能被顺利实现,所以我们必须另外寻找一些方法来克服 PHP 的这些缺点。

了解到了这一点,我们就到了应该接触一下 PHP 的心脏并探究一下它的内核——可以编译成 PHP 并让之工作的 C 代码——的时候了。

概述:

PHP调用动态链接库几个必要步骤为:

1. C/C++编写动态链接库,编译打包成.so文件

2. 初始化一个新的PHP扩展

3. 配置、编写PHP扩展内容,在扩展中使用C/C++调用.so

4. 编译并添加PHP扩展

5. 在PHP应用中直接调用PHP扩展里暴露出来的API

为了从能运行的最简单的例子开始,所以下面的叙述可能不会严格按照上面列的步骤来写,也有可能会重复穿插着写。但总体顺序是一致的。

一. C/C++编写动态链接库,编译打包成.so文件

如果还不会用C++调用自己写的.so库,请参考我的这篇文章:

http://keping.me/cpp_invoke_so/

文中从什么是Name Mangling开始,到如何用调用一个包含简单函数的so库,再到如何从so中加载类,都有详细叙述,并附有可运行示例代码。

二. 初始化PHP扩展

本文中,我们将创建一个叫“vehicle”的PHP扩展,其中包含一个“Car”类。

将要创建的扩展会涉及到以下文件需要修改,这些文件将会出现在vehicle目录下。后面会一一叙述这些文件是怎么来的,现在只是大致了解一下。

  • car.h —— 包含了C++写的类,即Car的定义
  • car.cc —— Car类的具体实现
  • php_vehicle.h —— 包含了PHP创建扩展所需要的一些头文件,外部变量定义等。
  • vehicle.cc —— 扩展的主要源码文件,这里面会调用到Car类
  • config.m4 —— PHP扩展的配置文件

1. 需要PHP源码包

如果你不是通过源码包方式安装的PHP,而是通过apt-get install 安装的,那么首先确保你安装了 php-devel 包,然后需要下载php源代码,然后可以跳到第2步。

如果想从源码包编译安装PHP,可以参考我写的另外一篇文章《Linux(Ubuntu12.10)搭建PHP开发环境(源码包方式)》,有详细的每一步的介绍。地址为:

http://keping.me/linux-php-dev-by-source-style/

安装完成以后,跳到第2步。

2. 制作PHP外部扩展

去到PHP源码包目录的ext目录下,我的在

/usr/local/src/php-5.3.22/ext

然后输入命令

sudo ./ext_skel –extname=vehicle

该命令会在ext目录下新建一个vehicle目录,并创建新模块“vehicle”目前所需的所有文件,包括

config.m4, php_vehicle.h, vehicle.php, CREDITS等。

还会列出应该执行哪些后续步骤来使用新的扩展,具体如下图所示。

Selection_190

图中我一共使用了三个命令

$ pwd 显示我的php源码包的ext目录所在位置

$ sudo ./ext_skel –extname=vehicle 前面已解释

$ ls 列出了执行上一条命令以后,在vehicle目录下,为我们创建的文件及目录。

如上图所示,在它的指导步骤1~8中,大致了解到我们需要编译config.m4文件,然后需要运行配置,然后需要使用make命令编译等。现在不用知道具体都干些什么,接下来会分别叙述。

三. 配置、搭建最基本的PHP扩展骨架

1. 配置PHP构建系统——编写config.m4

首先我们需要明确的是,为了在PHP扩展中使用C++,那么必须通知PHP构建系统使用C++编译器

通过在config.m4 文件中添加宏PHP_REQUIRE_CXX()来实现。

使用C++的过程中,肯定会用到C++的一些库,至少需要标准库(libstdc++ 大多系统都是这样的)

通过在config.m4 文件中添加宏PHP_ADD_LIBRARY()来实现。

将下面的代码添加到config.m4中

PHP_ARG_ENABLE(vehicle,
    [Whether to enable the "vehicle" extension],
    [  --enable-vehicle      Enable "vehicle" extension support])

if test $PHP_VEHICLE != "no"; then
    PHP_REQUIRE_CXX()
    PHP_SUBST(VEHICLE_SHARED_LIBADD)
    PHP_ADD_LIBRARY(stdc++, 1, VEHICLE_SHARED_LIBADD)
    PHP_NEW_EXTENSION(vehicle, vehicle.cc car.cc, $ext_shared)
fi

即去掉config.m4文件中某些行前面的注释符号“dnl”,然后添加我们需要的配置。如果还不清楚,可以参考我的配置文件,内容如下图

Selection_191

这里的宏PHP_SUBST()是标准autoconf的AC_SUBST()宏的php修改版, 它在将扩展构建为共享模块时需要。

PHP_NEW_EXTENSION宏中,第一个参数代表模块的名称;第二个参数是需要编译的文件,用空格隔开;第三个参数跟宏PHP_SUBST()是一样的。

2. 编写头文件php_vehicle.h

该头文件应该包含以下内容,其中PHP_VEHICLE_EXTNAME “vehicle” 代表该扩展的名称,PHP_VEHICLE_EXTVER则代表版本号,这些都会在php_info()中显示出来。

#ifndef PHP_VEHICLE_H
#define PHP_VEHICLE_H

#define PHP_VEHICLE_EXTNAME  "vehicle"
#define PHP_VEHICLE_EXTVER   "1.0"

#ifdef HAVE_CONFIG_H
#include "config.h"
#endif 

extern "C" {
#include "php.h"
}

extern zend_module_entry vehicle_module_entry;
#define phpext_vehicle_ptr &vehicle_module_entry;

PHP_MINIT_FUNCTION(vehicle);
PHP_MSUTDOWN_FUNCTION(vehicle);
PHP_RINIT_FUNCTION(vehicle);
PHP_RSHUTDOWN_FUNCTION(vehicle);
PHP_MINFO_FUNCTION(vehicle);

#endif /* PHP_VEHICLE_H */

我的php_vehicle.h文件内容如下图所示。

Selection_193

要理解PHP_MINIT_FUNCTION()函数,就需要了解PHP的启动步骤。大体就是

  • 当我们启动Apache的时候,它就启动PHP的解释器
  • PHP会调用每一个扩展的MINIT函数,可以通过查看php.ini文件来看哪些扩展模块是激活的
  • MINIT就是Module Initialization,即模块初始化方法的简称,在每一个模块初始化方法里,会定义并初始化一系列在以后的页面请求中需要用到的函数、类、变量等。
  • 一个典型的MINIT方法框架如下所示

[php]
PHP_MINIT_FUNCTION(extension_name) {

/* Initialize functions, classes etc */

}
[/php]

以上是PHP启动的第一步。为了先跑通整个流程,这里就不在一一叙述每一个方法以及宏的作用了。

3. 编写需要编译的文件(vehicle.cc、car.cc)

使扩展能够运行的最基本的vehicle.cc框架应该包含以下内容

#include "php_vehicle.h"

PHP_MINIT_FUNCTION(vehicle)
{
    return SUCCESS;
}

zend_module_entry vehicle_module_entry = {
#if ZEND_MODULE_API_NO >= 20010901
    STANDARD_MODULE_HEADER,
#endif
    PHP_VEHICLE_EXTNAME,
    NULL,                  /* Functions */
    PHP_MINIT(vehicle),
    NULL,                  /* MSHUTDOWN */
    NULL,                  /* RINIT */
    NULL,                  /* RSHUTDOWN */
    NULL,                  /* MINFO */
#if ZEND_MODULE_API_NO >= 20010901
    PHP_VEHICLE_EXTVER,
#endif
    STANDARD_MODULE_PROPERTIES
};

#ifdef COMPILE_DL_VEHICLE
extern "C" {
ZEND_GET_MODULE(vehicle)
}
#endif

我的vehicle.cc文件如下图所示

Selection_197

有了这个文件,我们还不能能创建最基本的PHP扩展,因为前面我们在配置文件config.m4中指定了需要编译的还有car.cc文件,所以必须给出,即使现在里面什么也没有。

所以还需要新建一个car.cc文件,暂时让它空着。

4. 配置、编译、安装

在当前文件目录(即/usr/local/src/php-5.3.22/ext/vehicle)下执行命令

$ sudo /usr/local/php/bin/phpize

$ sudo ./configure –enable-vehicle –with-php-config=/usr/local/php/bin/php-config

如下图所示

Selection_195

然后执行make & make install 命令

$ sudo make

$sudo make install

Selection_196

安装完成以后,会看到在

/usr/local/php/lib/php/extensions/no-debug-zts-20090626/

目录下有一个新生成的so文件,名为vehicle.so,将库该文件的路径添加到php.ini配置文件中,如下图所示。

Selection_199

即添加这句话

“extension=”/usr/local/php/lib/php/extensions/no-debug-zts-20090626/vehicle.so”

然后重启你的apache,在phpinfo()中就可以看到已经成功启动扩展vehicle了,如下图所示。

Selection_200

至此,最基本的框架已经搭起来了。接下来要做的工作就是如何使用PHP调用C/C++编写的so文件。先从简单的直接调用开始

四. 编写具体的PHP扩展内容

1.  编写car.h头文件

把头文件与源码文件分开是一个不错的习惯,特别是在别人不想知道你的具体实现的时候。这里我们也采取这种方式。

#ifndef VEHICLE_CAR_H
#define VEHICLE_CAR_H

// A very simple car class
class Car {
public:
    Car(int maxGear);
    void shift(int gear);
    void accelerate();
    void brake();
    int getCurrentSpeed();
    int getCurrentGear();
private:
    int maxGear;
    int currentGear;
    int speed;
};

#endif /* VEHICLE_CAR_H */

如上代码所示,我们先定义一个Car类,然后定义几个public的方法以及私有成员变量。然后在car.cc中实现它

#include "car.h"

Car::Car(int maxGear) {
    this->maxGear = maxGear;
    this->currentGear = 1;
    this->speed = 0;
}

void Car::shift(int gear) {
    if (gear < 1 || gear > maxGear) {
        return;
    }
    currentGear = gear;
}

void Car::accelerate() {
    speed += (5 * this->getCurrentGear());
}

void Car::brake() {
    speed -= (5 * this->getCurrentGear());
}

int Car::getCurrentSpeed() {
    return speed;
}

int Car::getCurrentGear() {
    return currentGear;
}

现在我们已经定义好了Car类,那么如何使其暴露给PHP用户空间,让PHP能够调用这些方法呢。

首先你需要定义一个包含有function_entry 表的PHP类来调用Car,这个function_entry 表里就包含了每一个你想暴露给PHP的C++方法。这里所指的这个PHP类就是前面提到的vehicle.cc。更新一下vehicle.cc的内容,如下所示。

#include "php_vehicle.h"

zend_class_entry *car_ce;

PHP_METHOD(Car, __construct)
{
}
PHP_METHOD(Car, p_shift)
{
}
PHP_METHOD(Car, p_accelerate)
{
}
PHP_METHOD(Car, p_brake)
{
}
PHP_METHOD(Car, p_getCurrentSpeed)
{
}
PHP_METHOD(Car, p_getCurrentGear)
{
}

function_entry car_methods[] = {
    PHP_ME(Car,  __construct,     NULL, ZEND_ACC_PUBLIC | ZEND_ACC_CTOR)
    PHP_ME(Car,  p_shift,           NULL, ZEND_ACC_PUBLIC)
    PHP_ME(Car,  p_accelerate,      NULL, ZEND_ACC_PUBLIC)
    PHP_ME(Car,  p_brake,           NULL, ZEND_ACC_PUBLIC)
    PHP_ME(Car,  p_getCurrentSpeed, NULL, ZEND_ACC_PUBLIC)
    PHP_ME(Car,  p_getCurrentGear,  NULL, ZEND_ACC_PUBLIC)
    {NULL, NULL, NULL}
};

PHP_MINIT_FUNCTION(vehicle)
{
    zend_class_entry ce;
    INIT_CLASS_ENTRY(ce, "Car", car_methods);
    car_ce = zend_register_internal_class(&ce TSRMLS_CC);
    return SUCCESS;
}

zend_module_entry vehicle_module_entry = {
#if ZEND_MODULE_API_NO >= 20010901
    STANDARD_MODULE_HEADER,
#endif
    PHP_VEHICLE_EXTNAME,
    NULL,        /* Functions */
    PHP_MINIT(vehicle),        /* MINIT */
    NULL,        /* MSHUTDOWN */
    NULL,        /* RINIT */
    NULL,        /* RSHUTDOWN */
    NULL,        /* MINFO */
#if ZEND_MODULE_API_NO >= 20010901
    PHP_VEHICLE_EXTVER,
#endif
    STANDARD_MODULE_PROPERTIES
};

#ifdef COMPILE_DL_VEHICLE
extern "C" {
ZEND_GET_MODULE(vehicle)
}
#endif

可以看到在PHP_METHOD中的函数名称与Car.cc类里写的函数名称并不需要一样,你可以定义任意自己觉得合适的函数名,为了表示方便,我这里一律添加前缀”p_”。这里每一个函数都还没有具体实现。

前面提到的function_entry表在上诉代码中可以看到由很多PHP_ME组成,每一个都代表了想要暴露给PHP用户空间的方法,最后一定以{NULL,NULL,NULL}表示结束。

现在我们已经有了C++的类,也有了PHP类,那么如何把两者联系起来呢?

首先你需要做的是定义一个zend_object_hander。然后定义一个结构,该结构包含了这个hander和C++的类。在PHP5中一个object其实就是一个hander,可以如下定义。

zend_object_handlers car_object_handlers;

struct car_object {
    zend_object std;
    Car *car;
};

该结构就会把C++的对象与zend的对象联系起来,然后你需要把下列代码添加到你的vehicle.cc文件中去,在PHP_METHOD方法之前。

void car_free_storage(void *object TSRMLS_DC)
{
    car_object *obj = (car_object *)object;
    delete obj->car; 

    zend_hash_destroy(obj->std.properties);
    FREE_HASHTABLE(obj->std.properties);

    efree(obj);
}

zend_object_value car_create_handler(zend_class_entry *type TSRMLS_DC)
{
    zval *tmp;
    zend_object_value retval;

    car_object *obj = (car_object *)emalloc(sizeof(car_object));
    memset(obj, 0, sizeof(car_object));
    obj->std.ce = type;

    ALLOC_HASHTABLE(obj->std.properties);
    zend_hash_init(obj->std.properties, 0, NULL, ZVAL_PTR_DTOR, 0);
    zend_hash_copy(obj->std.properties, &type->default_properties,
        (copy_ctor_func_t)zval_add_ref, (void *)&tmp, sizeof(zval *));

    retval.handle = zend_objects_store_put(obj, NULL,
        car_free_storage, NULL TSRMLS_CC);
    retval.handlers = &car_object_handlers;

    return retval;
}

然后更新一下PHP_MINIT_FUNCTION,这个函数前面提到过,就是PHP的扩展的模块初始化函数,如下所示:

PHP_MINIT_FUNCTION(vehicle)
{
    zend_class_entry ce;
    INIT_CLASS_ENTRY(ce, "Car", car_methods);
    car_ce = zend_register_internal_class(&ce TSRMLS_CC);
    car_ce->create_object = car_create_handler;
    memcpy(&car_object_handlers,
        zend_get_std_object_handlers(), sizeof(zend_object_handlers));
    car_object_handlers.clone_obj = NULL;
    return SUCCESS;
}

可能这里对“TSRMLS_DC”这个宏比较疑惑,它其实是 “ , void ***tsrm_ls”

然后编写一下构造函数

PHP_METHOD(Car, __construct)
{
    long maxGear;
    Car *car = NULL;
    zval *object = getThis();

    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "l", &maxGear) == FAILURE) {
        RETURN_NULL();
    }

    car = new Car(maxGear);
    car_object *obj = (car_object *)zend_object_store_get_object(object TSRMLS_CC);
    obj->car = car;
}

接着实现一下前面定义好的,但没有写内容的PHP_METHOD函数。为了演示的简洁,我们就实现两个函数。

PHP_METHOD(Car, p_accelerate)
{
    Car *car;
    car_object *obj = (car_object *)zend_object_store_get_object(
        getThis() TSRMLS_CC);
    car = obj->car;
    if (car != NULL) {
        car->accelerate();
    }
}

PHP_METHOD(Car, p_getCurrentSpeed)
{
    Car *car;
    car_object *obj = (car_object *)zend_object_store_get_object(
        getThis() TSRMLS_CC);
    car = obj->car;
    if (car != NULL) {
        RETURN_LONG(car->getCurrentSpeed());
    }
    RETURN_NULL();
}

记得添加所需要的头文件car.h。

然后重新 make & make install 吧,做完以后重启Apache服务器。

五. 在PHP脚本中调用扩展暴露出来的方法

编写一个PHP脚本,去测试是否成功。测试代码如下

[php]

<?php
// create a 5 gear car
$car = new Car(5);
print $car->p_getCurrentSpeed(); // prints ‘0’
$car->p_accelerate();
print $car->p_getCurrentSpeed(); // prints ‘5’
?>

[/php]

运行结果如果是0 和 5就说明成功了。

自此一个简单的PHP调用C++类已经实现了。

六. 在扩展中调用C/C++写的so库

假设现在我们有一个冒泡排序的.so库文件,现在我们想在PHP扩展中调用这个库文件里的函数

[cpp]
extern "C" void bubble_sort(int *arr, int len)
{
int tmp;

for(int i = 0; i < len – 1; i++)
for(int j = i + 1; j < len; j++)
{
if(arr[i] > arr[j])
{
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
}
[/cpp]

1. 更新car.h文件以及car.cc文件,添加调用so的代码,如下图所示。

Selection_201

car.cc 中代码如下图所示。

Selection_202

2. 更新vehicle.cc文件

在function_entry car_methods添加

PHP_ME(Car, p_bubble_sort_so, NULL, ZEND_ACC_PUBLIC)

然后添加一个PHP_METHOD(Car, p_bubble_sort_so),代码如下

[php]
PHP_METHOD(Car, p_bubble_sort_so)
{
zval *arr;
zval *len;
if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "zz", &arr, &len) == FAILURE)
{
return;
}
switch (Z_TYPE_P(arr)) {
case IS_NULL:
php_printf("NULL\n");
break;
case IS_BOOL:
php_printf("Boolean: %s\n", Z_LVAL_P(arr) ? "TRUE" : "FALSE");
break;
case IS_LONG:
php_printf("Long: %ld\n", Z_LVAL_P(arr));
break;
case IS_DOUBLE:
php_printf("Double: %f\n", Z_DVAL_P(arr));
break;
case IS_STRING:
php_printf("String: ");
PHPWRITE(Z_STRVAL_P(arr), Z_STRLEN_P(arr));
php_printf("\n");
break;
case IS_RESOURCE:
php_printf("Resource\n");
break;
case IS_ARRAY:
php_printf("Type is Array\n");
break;
case IS_OBJECT:
php_printf("Object\n");
break;
default:
php_printf("Unknown\n");
}

HashTable *arr_hash;
HashPosition pointer;
int array_count;
zval **data;

arr_hash = Z_ARRVAL_P(arr);
array_count = zend_hash_num_elements(arr_hash);
php_printf("The array passed contains %d elements\n", array_count);

// pass to the so
int *arr_so = (int*)malloc(sizeof(int) * array_count);
int len_so = array_count;
int i= 0;

for(zend_hash_internal_pointer_reset_ex(arr_hash, &pointer);
zend_hash_get_current_data_ex(arr_hash, (void**) &data, &pointer) == SUCCESS;
zend_hash_move_forward_ex(arr_hash, &pointer))
{
if (Z_TYPE_PP(data) == IS_LONG)
{
php_printf("%ld\t%ld\n", Z_LVAL_PP(data), (**data).value.lval);
arr_so[i++] = Z_LVAL_PP(data);
}
}

Car *car;
car_object *obj = (car_object*)zend_object_store_get_object(
getThis() TSRMLS_CC);
car = obj->car;
if (car != NULL)
{
car->bubble_sort(arr_so, len_so);
}
for(i = 0; i < len_so; i++)
{
php_printf("%d\n", arr_so[i]);
}
}

[/php]

这段代码还是比较容易懂的,可能会对zval这个变量不熟悉。其实所有用户定义的变量在PHP中都是用zval类型来表示的,它的内部表示如下

[c]
typedef pval zval;

typedef struct _zval_struct zval;

typedef union _zvalue_value {
long lval; /* long value */
double dval; /* double value */
struct {
char *val;
int len;
} str;
HashTable *ht; /* hash table value */
struct {
zend_class_entry *ce;
HashTable *properties;
} obj;
} zvalue_value;

struct _zval_struct {
/* Variable information */
zvalue_value value; /* value */
unsigned char type; /* active type */
unsigned char is_ref;
short refcount;
};
[/c]

然后再看上面那段代码。

switch里面是写给大家的说明程序,为了展示出如何判断传入的参数类型,可以不写略过。下面这句printf代码也是为了向大家展示 Z_LVAL_PP的用法,它其实就是对指针的指针取值,你也可以写成后面一种形式,即使**data的形式。不过建议使用第一种。

php_printf("%ld\t%ld\n", Z_LVAL_PP(data), (**data).value.lval);

接着看代码。首先我们用zend_parse_parameters接收穿过来的参数,这里我们传递的是数组。PHP中数组在zval里都是以hash表的形式储存的,所以我们这里声明一个hash表来接收这个参数。通过zend_hash_num_elements()则可以得到hash表元素的个数,也就是数组的个数。

然后我们将传递过来的参数通过for循环复制给我们的数组,最后通过调用car的bubble_sort函数进行排序。而bubble_sort调用的就是写好的so库函数了。

3. 编译、安装、测试

重新 make & make install,然后写一个PHP脚本测试一下,可以如下写:

Selection_203

然后运行该PHP脚本,如果浏览器里出现了排序后的数列0,1,2,3,4,5,则代表成功了。

That’s all,

Enjoy!

参考文献

[1]       Al-Qahtani, S. S., Arif, R., Guzman, L. F., Pietrzynski, P., & Tevoedjre, A. (2010). Comparing selected criteria of programming languages java, PHP, C++, perl, haskell, AspectJ, ruby, COBOL, bash scripts and scheme revision 1.0.Cornell University.

[2]       Sterling Hughes. Extending PHP [J]. Web Techniques, 2001, 6(1), 56 – 60.

[3]       PHP, http://www.php.net/manual/en/internals2.structure.php

[4]       Wikipedia, PHP, https://en.wikipedia.org/wiki/PHP

[5]       C++ dlopen mini HOWTO, http://www.isotton.com/devel/docs/C++-dlopen-mini-HOWTO/C++-dlopen-mini-HOWTO.html#theproblem

[6]       Extension Writing Part I: Introduction to PHP and Zend, http://devzone.zend.com/303/extension-writing-part-i-introduction-to-php-and-zend/

[7]       Wrapping C++ Classes in a PHP Extension, http://devzone.zend.com/1435/wrapping-c-classes-in-a-php-extension/

[8]       PHP Extensions – How and Why?, http://abhinavsingh.com/blog/2008/12/php-extensions-how-and-why/

[9]       How does PHP echo’s a “Hello World”? – Behind the scene, http://abhinavsingh.com/blog/2008/11/how-does-php-echos-a-hello-world-behind-the-scene/

[10]      Zend API:Zend_parse_parameters, http://zhaojunjie.blog.51cto.com/5475365/945302

[11]     【翻译】PHP扩展编写第二步:参数,数组,以及ZVAL, http://weizhifeng.wordpress.com/2011/07/20/extension-writing-part2-parameters-arrays-and-zvals/

[12]      php扩展 c,传参,传数组,zvar类型,全局变量, http://donbe.blog.163.com/blog/static/1380480212010225113531433/

[13]      A Close Look Into PHP Zval, http://blog.jjyao.me/blog/2013/03/17/a-close-look-into-php-zval/

[14]      convert_to_xxx系列函数帮助我们进行类型转换, http://9212219.i.sohu.com/blog/view/175458610.htm

[15]       深入理解php内核 编写扩展 II:参数、数组和ZVALs, http://blog.csdn.net/hguisu/article/details/7377235

[16]       Zend API:深入 PHP 内核, http://xiaobin.net/wp-content/uploads/2011/09/zend/