记忆碎片

       昨天去席老师哪里论文格式审查，回来再次修改论文。这一段时间，忙的简直要抽风了，改论文，看论文，再改论文…总算差不多了。

       最近写论文的时候，第五章要写到一个测试，其中包括性能测试。本意是想测出系统中每个模块的性能，也就是每个模块运行次数以及运行时间。经过一番的百度和谷歌，最后决定使用Linux平台的Gprof。Gprof是一个GNU Profiler工具，其中GProf可以打印出每个函数的运行次数以及运行消耗时间，并且可以打印出函数的调用关系，配合KProf还可以显示函数的调用关系树。因此本测试使用Gprof，可以查看进程处理时间耗费情况。

       使用Gprof之前，我们有必要了解一下他的工作原理：通过在编译和链接程序的时候（使用-pg编译和链接选项），gcc在应用程序的每个函数中都加入了一个名为mcount (or”_mcount”,or “__mcount”, 依赖于编译器或操作系统)的函数，也就是说你的应用程序里的每一个函数都会调用mcount,而mcount 会在内存中保存一张函数调用图，并通过函数调用堆栈的形式查找子函数和父函数的地址。这张调用图也保存了所有与函数相关的调用时间，调用次数等等的所有信息。

       Gprof的用法：gprof [ -b ] [ -e Name ] [ -E Name ] [ -f Name ] [ -F Name ] [ -L PathName ] [ -s ] [ -z] [ a.out [ gmon.out ... ] ]

       -b 不再输出统计图表中每个字段的详细描述。

       -p 只输出函数的调用图（Call graph的那部分信息）。

       -q 只输出函数的时间消耗列表。

       -e Name 不再输出函数Name 及其子函数的调用图（除非它们有未被限制的其它父函数）。可以给定多个 -e 标志。一个 -e 标志只能指定一个函数。

       -E Name 不再输出函数Name 及其子函数的调用图，此标志类似于 -e 标志，但它在总时间和百分比时间的计算中排除了由函数Name 及其子函数所用的时间。

       -f Name 输出函数Name 及其子函数的调用图。可以指定多个 -f 标志。一个 -f 标志只能指定一个函数。

       -F Name 输出函数Name 及其子函数的调用图，它类似于 -f 标志，但它在总时间和百分比时间计算中仅使用所打印的例程的时间。可以指定多个 -F 标志。一个 -F 标志只能指定一个函数。-F 标志覆盖 -E 标志。

       -z 显示使用次数为零的函数（按照调用计数和累积时间计算）。

使用例子：

       假如我写了一个程序count_data.cpp，如果要使用gprof的话，在编译程序的时候需要加上-pg，如下：

       g++ -gp -o count_data count_data.cpp

       编译没有错误的话，直接运行 count_data程序

       ./ count_data

运行过程序以后，会在程序当前文件夹下生成一个gmon.out文件，这个文件便是程序运行记录文件。下一步我们就可以使用gprof来读取分析该文件了。

       gprof –q test gmon.out

    如果你想多次运行程序并且记录函数运行时间，便可以用shell来实现。下面是我写的一个shell脚本。测试本程序运行。本程序被调用四次，每次传入不同参数。

#!/bin/sh
i=1
while [ $i -le 23 ]
do
echo $i
time ./count_data $i > null
cp gmon.out ${i}gmon.out
gprof -b count_data ${i}gmon.out > ${i}.txt
let i+=7
done 

通过上面shell的运行，程序会产生一下几个文件：

1.txt 2.txt 3.txt 4.txt

       我们可以统计该程序运行函数的时间来分析每个函数的性能。该功能可以对程序运行效率进行优化，也可以在写论文是完成测试。呵呵，下面是我的测试结果以及对测试结果的分析，直接在论文里复制出来了，懒得改了，呵呵

       本次测试过程如下，首先将数据库中数据清空，然后程序循环读取七天的离线数据，模拟在线统计一小时数据，进行处理。处理过程中记录下该数据记录条数，以及更新数据条数。对Gprof产生的gmon.out文件进行分析。依次运行和分析第二批数据、第三批和第四批数据。

       表1主要函数运行时间

函数名(耗时ms)	第一批	第二批	第三批	第四批
get_userid()	86733	116327	110690	120245
count_net()	54571	77240	70421	72147
update_max_area()	小于10	小于10	小于10	小于10
Insert_hourflow()	小于10	小于10	小于10	小于10
update_max_sc()	小于10	小于10	小于10	小于10
update_ip_num()	小于10	小于10	小于10	小于10
insert_top_ten()	小于10	小于10	小于10	小于10
heap_adjust()	小于10	小于10	小于10	小于10
其他代码	39395	39086	54410	48099
总耗时	180699	232653	235521	240491

 

       表2主要函数运行次数

函数名(次数)	第一批	第二批	第三批	第四批
get_userid()	13498152	15346753	14668286	14059765
count_net()	1885952	2377368	2317642	2342265
update_max_area()	1	1	1	1
Insert_hourflow()	1	1	1	1
update_max_sc()	1	1	1	1
update_ip_num()	1	1	1	1
insert_top_ten()	1	1	1	1
heap_adjust()	247	321	276	229
数据条数	13498152	15346753	14668286	14059765

       由表1和表2可以看出，第一次数据处理中共统计出13498152条记录，其中有1885952用户匹配成功，其他数据不在监控范围内，因此被get_userid()函数过滤掉，count_net()函数被调用了1885952次，耗时54571ms，数据库插入函数仅仅被调用了一次，耗时非常小，可以被忽略掉。表1第一批数据总体耗时为180699ms，用户过滤模块耗时较多，达到86733ms，接近50%。因为每条记录均要过滤，所以耗时较多，其他代码耗时39395ms。其他代码耗时主要表现在程序环境初始化、读取离线数据文件、调用存储过程等。在表2可以分析得知，四次数据处理数据文件整体记录数大致在一千五百万左右。用户匹配成功以后的数据调用count_net()函数处理的记录数大概在二百万左右。分析表1可知，程序主要耗时在get_userid()和count_net()，这两个函数分别为用户过滤模块和数据处理模块。另外由表1可得第一批数据处理耗时比第二、三、四批数据少，因为第一批数据条数较少。还可以分析到，处理响应时间在第一批到第四批的整个过程略微有些增长。此现象是正常的，因为数据库在第一批处理过程中是空的，随着记录的增多数据库表中记录会增长。

       根据上面的分析我们可以看出，系统满足对记录数据处理的响应速度。处理千万级数据，耗时仅仅为三到五分钟，因此该数据处理过程满足需求。

最近在写论文，发现一个问题，很多同学写论文的时候也被这个问题所困扰。用visio画图时候，如果画出的图文件过大，元素过多时，visio中的虚线框复制到 word中就会自动变成实线,在Word里双击图片进入VISIO编辑状态又变回虚线。

下面提出两个解决方案。

解决方法1：
这个方法也是一个比较简单的办法，修改visio中虚线的粗细，具体方法：点击相应的虚线，单击右键，“格式”—>“线条”，在这里调整线条的粗细，一般设置到“5”就可以变成虚线了。
解决方法2：
修改注册表：
【运行regedit】－>【HKEY_CURRENT_USER】－>【Software】－>【Microsoft】－>【Office】－>【12.0】（office2003是11.0）－>【VISIO】－>【Application】，选择【新建】－>【Dword值】，名称为MetafileDashLineAsSolid，取值为0。
 
如果感觉修改起来复杂的话，可以复制我已经写好的注册表导入。

2003

Windows Registry Editor Version 5.00

[HKEY_CURRENT_USER\Software\Microsoft\Office\12.0\Visio\Application]
“MetafileDashLineAsSolid”=dword:00000000

2007

Windows Registry Editor Version 5.00

[HKEY_CURRENT_USER\Software\Microsoft\Office\12.0\Visio\Application]
“MetafileDashLineAsSolid”=dword:00000000

       找完工作以后，又忙着修改以前项目中的数据录入以及存储中问题的优化。

       前几天，空间要到期了，甚是郁闷，不想再用这个空间了，想换一个，还好永超说他有个空间可以帮我绑定一下，借一部门空间给我用一段时间，我甚是感激呀！折腾了一两天才把东西全部移过去。这下算是安稳了。

       同学小明，现在就职某规划局，据他说，他每天都要登录一个招标网站，查看这个网站有没有更新相关信息。漏掉的信息就会被其他的单位抢走。他很想做个软件帮他处理这些事务。让我帮他想想办法。

       我想了下这个应该不难，获取到网站中的招标目录，去除HTML，匹配更新，提示，搞定！这样做来比较快就实现了。他用起来也比较舒心。但是过了一段时间，感觉还是有些不太方便：如果不再电脑旁边，而又想接收到实时更新呢？怎么办？我突然间想起来，是不是可以用由邓东东开发的LibFetion的lib包，开发一个飞信的发送呢？理论上是可行的，但是这样操作起来复杂度比较高。而且还要熟悉lib接口。然后就想到了使用mail发送移动的139邮箱，然后139邮箱有免费短信提醒的功能。这样见解可以实现信息的短信提醒。

        以前做过N多的mail发送了，写起来比较简单。比较纠结的是，这个东西我电脑上发送邮件十分的正常，到我同学电脑上发送一直不成功，“提示连接被关闭”。因为同学远在郑州，跑过去debug也不太现实。想了好久，决定让同学安装一个抓包软件，配合我调试一下，看到同学抓过来的包，提取SMTP的信息流，大概如下：

为什么是data发送不成功呢？

我们知道，发送了rcpt to 命令以后，接下来的便是data命令，但是我们的程序怎么直接就QUIT了呢？是发送不成功？还是程序在data之前就quit了？还是data发送失败，但是没有检查失败？带着以上疑问，我抓了下自己的发送数据包：

我们可以看我的数据包发送了data，而且数据也是正常的，这个是为什么呢？考虑了上面我们想到的，一一排除，最后，我决定把get_response中的服务器返回数据全部打到log里面，看下问题所在。结果一下就看到了比较悲剧的事情，是瑞星的邮件保护措施，屏蔽了DATA命令。

看到服务器交互认证成功以后，发送出去的数据全部改成了：

250 Send from Rising mail proxy

这个数据应该是瑞星把mail发送的数据拦截了，然后又再次发送出去。让同学把瑞星的邮件屏蔽功能关掉。程序OK了。

程序其实没有问题，只是瑞星屏蔽了。通过远程的debug，分析问题，解决问题。呵呵

以前做项目的时候，没有深入的考虑过这些问题，只是和同学在讨论问题的时候稍微摄入过TCP状态的一些问题。最近找工作国内两个比较大的互联网公司都问了相关问题。突然间感觉到TCP在网络编程中还是很重要，包括他的原理以及具体函数的意义。所以今天就整理了下TCP三次握手，以及相关的问题。

1.TCP状态转换中的小问题： 

连接建立：

我们从上面的图就可以看到，黑色加粗线是客户端的正常变迁过程。其中就是主动打开发动SYN以后，接受SYN，ACK后进入连接状态。

还有看黑色虚线是服务器的正常变迁过程。其中listen被动打开，指定一个接受队列，等收到SYN后发送ACK,SYN，然后收到ACK以后进入连接状态，通过accept函数返回客户端信息以及连接句柄。

断开连接：

由主动发起方发起FIN(注：通常但不是总是客户端发起断开连接)，被动关闭方收到FIN发ACK，主动发起方收到ACK进入fin_wait2状态，如果收到FIN以后再次发送ACK就进入了TIME_WAIT状态，TIME_WAIT状态比较特殊，要等一个2MSL时间，就是一个二倍的网络延迟。

被动发起方发送FIN以后进入LAST_ACK，收到ACK后退出连接。

这里有个问题。主动发起方为什么要有个2MSL呢？如果没有会怎么样呢？我们可以看到，2MSL这个时候，连接基本上算关闭了，因此可以停止通信了，LAST_ACK状态的如果收不到ACK怎么办？一直等待？他应该是重发FIN，这个时候如果TIME_WAIT不存在，被动发起方就会收到一个RST，影响稳定性。如果2MSL存在，就会有一个问题。如果有人利用这个问题造成服务器出现大量的TIME_WAIT状态，因此这个是一个稳定性和效率的均衡。

2.另外再次讨论一下listen以后服务器协议栈做了那些工作：

Listen(int sockfd,int backlog)//0-成功，  -1失败 

由上面的示意图，可以看出，当Listen以后就可以接受对方的连接。当时面试的时候就遇到了这个问题，hr问我，Listen之后能接受客户端连接吗？如果能的话，是什么情况？连接以后客户端发送一系列信息会出现什么情况？呵呵，从上面的原理，我们应该看到比较清楚了，可以接受连接，并且理论上可以接受buffer大小的数据。

3.相关问题讨论，这些问题是我在面试以及在学习中，自己思考或者和同学讨论的结果。

A.当连接成功建立后，客户端拔去网线，客户端电脑重启后插入网线，启动客户端进程，会出现什么情况？

分析：首先如果TCP打开了keeplive选项，那么客户端关机时间久了以后，服务器就能感知到，如果keeplive关闭，或者客户端快速重启，那么这个时候，服务器没有发现异常。客户端重启过后是一个全新状态，由TCP状态转换图可知，客户端会发起SYN，而服务器收到客户端发来的SYN的话，发现在ESTABLISHED状态收到SYN是异常的，于是，返回RST，自己也复位改连接。客户端收到RST后，复位，重新连接。

B. 当连接成功建立后，如果send函数发送数据立即返回后，拔掉客户端网线，请问数据会在那些地方存留？

分析：send是glib函数通过系统调用传入内核协议栈的buffer中，然后队列等待发送。如果当前没有数据等待的话，该数据部分可能已经发送到网络上，但是也有可能正在buffer队列中等待发送。

C．当连接成功建立后，如果send函数发送数据立即返回后，且保证数据已经正常发送到网络上，这个时候拔掉服务器网线，会出现什么情况？

分析：首先服务器如果没有发送数据，只是等待接受的话，那么服务器可能等到了数据，也有可能永远等不到数据。如果网络状态非常好，在拔去网线之前已经收到了数据，或者网络不太好，数据还没有到达服务器。那么数据还是会正常传输，至少第一个数据包会正常传输，传到和服务器直接相连的交换机这里。交换机发现ip不通，通过arp广播寻求服务器mac，失败后，返回ICMP数据包：目的地址不可达。客户端收到数据包后感知服务器不可达。

D．在处于TIME_WAIT状态下，2MSL前，对方再次简历连接，请问连接可以简历成功吗？

分析：这个问题我就不打字了，网上分析的不错：书中给的图里面，有一个TIME_WAIT等待状态，这个状态又叫做2MSL状态，说的是在TIME_WAIT2发送了最后一个ACK数据报以后，要进入 TIME_WAIT状态，这个状态是防止最后一次握手的数据报没有传送到对方那里而准备的（注意这不是四次握手，这是第四次握手的保险状态）。这个状态在很大程度上保证了双方都可以正常结束，但是，问题也来了。由于插口的2MSL状态（插口是IP和端口对的意思，socket），使得应用程序在2MSL时间内是无法再次使用同一个插口的，对于客户程序还好一些，但是对于服务程序，例如httpd，它总是要使用同一个端口来进行服务，而在2MSL时间内，启动httpd就会出现错误（插口被使用）。为了避免这个错误，服务器给出了一个平静时间的概念，这是说在2MSL时间内，虽然可以重新启动服务器，但是这个服务器还是要平静的等待2MSL时间的过去才能进行下一次连接。

读研这两年，平时项目都在用C语言在Linux下做，两年下来，也写了不少的代码，再加上我平时的不懈努力，多看书，也算是C语言的基础知识比较扎实了，因此在自己的简历上，就写上了“精通C语言编程”；这个在面试华为、中兴以及华赛的时候，都还好，问的问题都没有被卡壳，但是就在前几天，我去成都面试某互联网公司的时候，就结结实实的被打击了一下：当时面试管GG 看到我简历上写的“精通C语言编程”，就说：你精通C语言编程啊？我当时就一个汗啊！GG又说：那好吧!我给你说个最简单的吧：

struct empty{ }a ; //sizeof(a)

我只记得 在C++里面 空class 是 1；但是 在C语言的标准下，就不太好说了4? 1? 0? ,我一时之间想不到为什么了，这样的东西和编译器有关系？

当时大脑飞速运转，思考很多知识，总结推理…

回答：C++的标准下是1，C语言里面不确定，但是我推测是0或者4，原因：….

面试官GG 笑而不语。

我晓得自己回答的，他肯定不太满意。

然后GG接着问：问什么在C++中是1呢？

汗！这次是真的回答不上来了，由此想到自己还是真的不能堪称“精通C”啊！

回来以后，在VC下试了一下 结果是1，GCC下试了一下是0；

看来这个问题和编译器有关系啊！

再想一下，不免可以有一个比较清楚的认识了：每个结构体，编译器在处理的时候，都要对他进行识别，空的结构体就不能用结构体内部来识别他，就要编译器帮忙，这样的话，VC就产生了一个字节的空间来存储结构体的标识。GCC在处理的过程中节省了空间，但是他是怎么识别的呢？呵呵，回头想一下，其实两个空的结构体是没有用的，识别与否关系不太大！

由这个题目，我还想起来一个知识点：

#define print( n ) printf( “data”#n” = %d\n “, data##n )
int main()
{
      int data5=100;
      print(5);
      return 0;
}

上面这个代码是多少呢？有没有思考过呢？平时做项目的时候有没有用到过呢？

呵呵，如果我告诉你 结果是 ：data5=100；
你会不会有些惊讶？

为什么是这样的呢？我们要从#号的功能谈起了
# 本身为指令 没有其他意义,也没有其他效果
# 号必须是该行除了任何空白字符外的第一个字符。预处理指令就是以#号开头的代码行。
# 后是指令关键字，在关键字和#号之间允许存在任意个数的空白字符。
整行语句构成了一条预处理指令，该指令将在编译器进行编译之前对源代码做某些转换。

下面举例说明下:
形式为： #define 标识符 字符串.
其中的“#”表示这是一条预处理命令。凡是以“#”开头的均为预处理命令。 #x中的#是字符串化运算符，作为是把参数x字符串化，即用双引号包围，例如，在这个程序中：

print(4);

参数4经过宏替换并字符串化之后，就成了：

printf(“the no. ” “4″ “,is”);

由于相邻的字符串会自动被连接，所以，它最终相当于：

printf(“the no. 4 ,is”);

由此 我们可以在 gcc 下试一下：

[root@localhost ~]# gcc -E –o test test.c
[root@localhost ~]# cat test
# 1 “test1.c”
# 1 “<built-in>”
# 1 “<command line>”
# 1 “test1.c”

int main()
{
      int data5=100;
      printf( “data ” “5″” = %d\n “, data5 );
      return 0;
}

这下就比较清楚了吧！

呵呵，其实C语言几十年不衰，还是有原因的，他有很经典的地方。很值得我们深入的研究它！

前天在网上看到一个题目，说的是求中位数，但是这个中位数，不是我们所讨论的那样简单。看题目如下：

在32位机器中，int占4字节，存在文件中的4T个数中找出第2T大的数，内存只有2G。请列出解法。

这个题目，其中有个问题有些复杂，不过肯定是有解法的。其中，4T个数，每个数占用4个字节，那么就应该是16TB的内存才能存的下，这样算来，是不能在内存里面处理全部数据了，其实如果真的想不到好的办法，可以用最朴素(也可以说是最笨)的方法，对文件进行外排(归并),就可以求出来了。

看到这个问题，我首先想的到的是用分治法。分治是肯定可以解决这个问题的。

解法1 分治法

依次读取数据，按每一个数据的最高位分别写到文件(bit_32_1、bit_32_0)里面去，并同时记录最高位为1的个数，这样就可以找到第2T个数是在bit_32_1 or bit_32_0中，依次递归下去，就能找到第2T个数是多少。

我们考虑到，数据比较大，而且是放到文件中的，如果用这种方法，就多次(<=32次)读取文件，时间复杂度应该是O(32*N)。有没有更好的办法呢？答案肯定是有的。我们在群里讨论了这个问题。提出了一个基于计数的思想。

解法2 计数分治

既然全部的数据在内存中存放不下，那么我就考虑存放两个计数桶，分别求出第2T个数的高16位和低16位，这样就不把问题解决了吗。而且使用内存较小。64K x 8 x 2 = 1MBytes下面是我写的一个伪代码，可能有些疏忽的地方，但是思想肯定是对的啦！呵呵

long long High[1<<16];
long long Low[1<<16];
long long x = 0 , i = 0;
int  Number = 0 ;
while(x<= 4T)
{
     data = read();
     High[x>>16]++;//记录高16位–yqshare
     Low[x&0xFFFF]++;  //记录低16位–yqshare
}
x = 0 ;
while(x>=2T)
{
     x += High[i++];//累计大小–yqshare
}
Number = (i–)<<16 ;
x = 0 ;
i = 0 ;
while(x>=2T)
{
     x += Low[i++];
}
Number |= (i–)&0xFFFF;//添加上低16位–yqshare

上面是错误的解法，Harvey指出来以后，我思考了下，发现自己图略了一个问题。然后修改了一下算法。

long long High[1<<16] = {0} ;
long long Low[1<<16]= {0} ;
long long x = 0 , i = 0 ,HighCount;
int  Number = 0 ;
int HighNumber , LowNumber;;
while(x<= 4T)
{
   data = read();
   High[data>>16]++;//记录高16位–yqshare
   x++;
}
x = 0 ;
i = 0;
while(x>=2T)
{
   x += High[i++];//累计大小–yqshare
}
HighNumber = (–i)<<16 ;
HighCount = i ;
while(HighCount>=High[i])
{
   i++ ;//计算出小于2T数的个数–yqshare
}

//这里可以用堆的思想，也可以用桶的思想。
x = 0 ;
while(x<= 4T)
{
   data = read();
   if(data&0XFFFF0000 == HighNumber)
      Low[data&0XFFFF]++;//记录高16位为HighNumber的数的低16位–yqshare
   x++;
}

x = i ;
while(x>=2T)
{
   x += Low[i++]; //累计大小–yqshare
}

LowNumber = (–i)&0xFFFF;//添加上低16位–yqshare

Number = HighNumber | LowNumber ;

这样就可以求出该数了。

今天抽时间看了下字符串的模式匹配，觉得算法导论上讲的还是蛮好的，rabin-karp算法，有限状态机算法，以及KMP算法，呵呵。想深入研究下rabin-karp算法，算法导论上面用了那么多的公式说明这个问题，其实这个算法就是有点使用hash的思想了。把模式字符串进行一个预处理，并mod，主字符串进行逐个进行简单的hash映射，然后mod比较…虽然最差是O(m(n-m+1)),一般情况下是O(m)次。

比如：子串“421″和源串”4234212456″

首先把423对某个质数取模，比如7，把模值和421对7取模的值进行对比。如果相同，则再用朴素算法逐字符对比，如果不同，把423变成234.可以通过(423-400)*10+4=234计算。其实对于任何位数的xyz（具体xyz是几位，要看子串的长度）都可以划分成(xyz-x*100)*10+m

其中m表示父串的下一位。这里的100是以子串长度为3来作比较的. 其中如果换成字符的话应该就是26了。

另外还在百度的时候就看到了POJ上一道题，大概也是这个思想啦。反正又是hash，现在感觉hash真是有用，要速度的地方到处都是它，呵呵。

花了一个多小时写了这道题，唉！有个很弱智的地方耗费了好大一会时间。

#include <stdio.h>
#include <stdlib.h>
#define  M  20000000
int hash[M];
char str[16000001];
int word_map[256],hash_add=0;
int n=0,nc=0;

int strhash(char * key)
{
	int i,h=0;
	for (i=0;i<n;i++)
	{
		h = h*nc + word_map[*(key + i)]; //just like the rabin-karp.
	}
	return h%M;
}
int main()
{
	int i=0,sizeNC=0,count=0,j;
	scanf("%d %d",&n,&nc);
	sizeNC = nc;
	scanf("%s",str);

	//init the map,we can not use the acsiic code
	while (sizeNC)
	{
		if (!word_map[str[i]])
		{
			word_map[str[i]] = sizeNC;
			sizeNC--;
		}
		i++;
	}

	// use the bash to count the words
	i=0;
//这里曾一度写成str[i+nc-1],害的我调了10几分钟，低级错误！
	while (str[i+n-1]!='\0')
	{
		hash_add = strhash(str+i);
		if (!hash[hash_add])
		{
			hash[hash_add]++;
			count++;
		}
		i++;
	}
	printf("%d\n",count);
}

/*
author:yqshare
*/

#include<stdio.h>
#include<string.h>
#include <stdlib.h>
#define M 30000
struct word_entry{
char * word;
char * foreign_word;
struct word_entry * next;
};
typedef struct word_entry WORD_ENTRY;
ELFHash(char * str)
{
unsigned int hash = 0;
unsigned int x    = 0;
while (*str)
{
hash = (hash << 4) + (*str++);
if ((x = hash & 0xF0000000L) != 0)
{
hash ^= (x >> 24);
hash &= ~x;
}
}
return (hash & 0x7FFFFFFF);
}
WORD_ENTRY  * alloc_entry(char * word , char * foreign)
{
WORD_ENTRY  * word_entry =NULL;
word_entry = (WORD_ENTRY *)malloc(sizeof(WORD_ENTRY));
word_entry->foreign_word = ( char * )malloc(strlen(foreign)+1);
strcpy(word_entry->foreign_word,foreign);
word_entry->word = ( char * )malloc(strlen(word)+1);
strcpy(word_entry->word,word);
word_entry->next = NULL;
return word_entry ;
}
int main()
{
char word[11],foreign_word[11],buff[50];
int hash_size=0,i;
WORD_ENTRY  ** hash_base = (WORD_ENTRY *)calloc(M,sizeof(WORD_ENTRY *));
WORD_ENTRY  * hash_tmp=NULL, * word_tmp = NULL;
memset(word,0,10);
memset(foreign_word,0,10);
while(gets(buff) && strcmp (buff,"")!= 0)
{
      for (i=0;buff[i]!=' ';i++)
word[i]=buff[i];
word[i++]='\0';
strcpy(foreign_word,buff+i);
hash_size = ELFHash(foreign_word)%M;
hash_tmp = *(hash_base+hash_size);
word_tmp = hash_tmp;
hash_tmp = alloc_entry(word,foreign_word);
hash_tmp->next = word_tmp;
       *(hash_base+hash_size) = hash_tmp;
       memset(word,0,10);
memset(foreign_word,0,10);
       memset(buff,0,50);
}
   while(gets(foreign_word)&& strcmp (foreign_word,"")!= 0)
{
hash_size = ELFHash(foreign_word)%M;
hash_tmp = *(hash_base+hash_size);
while(hash_tmp)
{
if(strcmp(hash_tmp->foreign_word,foreign_word)==0)
break;
hash_tmp = hash_tmp->next;
}
if(hash_tmp != NULL)
printf("%s\n",hash_tmp->word);
else
printf("eh\n");
}
}

很有幸，通过了华为编程大赛的初赛，进入决赛。
决赛时间是7.9号 8：00–15：00，在重庆大学。这次大赛的题目，是关于sudoku的，关于判局、求解、生成游戏。

本次比赛的题目是数独游戏相关的，我就不说了吧，百度一下，网上一大把！

在整整一天的比赛时间里，我花了一个上午的时间写一个MFC的界面，好痛苦。比赛环境，连个MSDN都没得，而且，最近这一年都一直在linux下做，很久没有MFC了。不过还好的是，把界面给做出来了。
中午和下午想了两个算法。

1)判局，也就是要判断用户，填入的数据是不是合法的，首先要判断每一行、每一列、每个九宫格，是不是仅有1-9的全部数字组成。判断这个我使用了位图算法，即，在一个int中的底9位用来匹配行中出现的数字，如果该行是由1，2，3，4，5，6，7，8，9，组成，那么该int的第九位便全部为1，否则会有为0的位，因此该bitmap肯定小于511，这样通过一次遍历就实现了一个匹配。用同样的方法遍历列，以及九宫格。只有个O(N)就可以解决这个问题了，呵呵

2)求解
这个方法应该的比较多的，一般都是DFS来求解。

1.按下标blank由小到大的顺序逐个获取空白位置；
2.对空白位置blank试图填数，填数的规律为从l-9依次由小到大选择(有序)；
3.若找到一个可以填人的数据（调用check(blank)，检查当前字符所在的行、列、九宫格是否满足规定，若不满足，即找不到合适数据填人该位置），将数据填人sudoku[blank]，并将blank入栈push；否则转5.；
4.获取下一个空白位置，若有空白位置则转2.，否则转6.；
5.进行回溯，即pop得到上一次填数的位置sp，重新对该位置试图填数，为了递推的高效性，此时可以仅从当前sp存放的数字大l开始试图填数，转(3)；
6.填数结束。

注：当然还有很多其他的方法，这个是应该是比较想的，呵呵

3)生成游戏
我当时想到的就是用“挖洞”。即生成一个数独全局，然后随机挖去一部分数据即产生有解的数独布局。
用的就是编程之美的上的思想：产生一个不会重复的“九宫格”，然后对其他的九宫格，用行变换的思想去填充。这个比较简单。一下就把代码写出来了…

最后，感觉华为的这个编程大赛还可以，但是有些不健全。比如：可以带书进去，但是又没有集体通知，有的同学带了、有的同学没有带，这样就有些不公平，还有就是，写算法就不要让大家做MFC吗，做MFC就不能算是真正意义上的编程大赛咯！我就是浪费了很多时间到MFC上，估计其他同学也和我差不多，呵呵
这次回来，我突然有买一本《算法导论》回来看的冲动了，虽然自己平常也很注重学习算法，但是，总感觉知识储备不够…

0X0000 0X0001 0X0002 0X0003

LE  04                     03              02             01

BE  01                     02              03               04

big-endian   little-endian

0×0000   0×12       0xcd

0×0001   0×23       0xab

0×0002   0xab       0×34

0×0003   0xcd       0×12

htons 把unsigned short类型从主机序转换到网络序

htonl 把unsigned long类型从主机序转换到网络序

ntohs 把unsigned short类型从网络序转换到主机序

ntohl 把unsigned long类型从网络序转换到主机序

另外：1、网络与主机字节转换函数:htons ntohs htonl ntohl (s 就是short l是long h是host n是network)