记忆碎片

         上周永超Q我，他空间悲剧的被封掉了，幸好，阿超把数据库和web打了个包给我，否则我也悲剧了~~~看了下以前的记录，不经意间发现博客在阿超哪里已经寄存了一年之久了，还是应该多些阿超的收留！

         翻了翻自己以前写的东西，才发现已经有整整一年没有写东西了~或许是太忙了吧！既然一直都没有更新过，这次本想就把博客关了吧，但是随手翻了下日访问量的统计，发现每天还是有几百的访问量，看了访问明细，都是技术连接~也许以前写的一些技术，对某些人也许会有些帮助，所以决定还是将空间继续维护下去。

         上周末花了一天的时间在淘宝上找了一个还可以落脚点，空间迁移过去以后本以为OK了，但是有网友发邮件说网页只能打开首页，测试看到确实如此，悲了个剧的，折腾了好久才发现是空间的问题。昨天又换了一个空间，终于Done了。

         mark一下自己的生活吧，去年的这个时候整夜整夜的忙论文~没时间折腾博文，经过了悲剧+悲惨的答辩以后，就来工作了~~

         刚入职那段时间更是一头栽进SSH里面，每天都是大半夜才关机睡觉，第二天醒来go on~那段日子连个周末都没有，但是过得很充实。偶尔闲下来也会觉得空虚的要发疯，在北京同学少、连玩的人都木有~

         熟悉了工作流程、掌握了工作方法、适应了快节奏的生活，现在过得还算快乐~不过最近微博上到处在说IT民工猝死的问题，有时候想想又感觉好害怕，所以会督促自己去健身。

       哎呀~写着写着又思路又乱了，额~~~就这样吧！以后尽量多更新下文字了，免得这里都长草了~~~

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

       最近写论文的时候，第五章要写到一个测试，其中包括性能测试。本意是想测出系统中每个模块的性能，也就是每个模块运行次数以及运行时间。经过一番的百度和谷歌，最后决定使用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，分析问题，解决问题。呵呵

从C语言的角度考虑AWK—AWK学习笔记

最近了解脚本，学习到了awk，感觉awk还是神似C语言，作为C语言常用者，如果使用到awk来处理数据，上手应该是比较快速了。

       首先说下，为什么使用awk。第一：awk写出来的数据处理，可移植性强。第二；awk比较简单，用C语言来处理脚本，你可能要写代码，断点调试，折腾一天，或者是一个下午，但是用awk，你一两个小时就可以搞定一个脚本。也许你会说，awk写出来的脚本绝对要比C/C++处理数据慢，是滴，这一点我们要承认，但是据网上大牛们的测试，发现，其实awk处理数据也不是我们想象那么慢，如果你真的感觉速度慢的话，可以先用awk实现了思想，回头来写C的代码，也是很好的一个提高效率的方法。

       为什么说要在C语言的角度来考虑awk脚本呢？因为身为脚本语言的awk，和C语言有很多相似之处。

      1. awk中的变量
        我们知道C语言中变量属于强定义语言。但是awk身为脚本，就有了脚本的特性：若定义语言，一个遍历，不用定义，拿来就可以用，而且初始值为空(或者是0)。那么一个变量，你可以认为它是float、string 等等。这里有一点，若定义语言其实也分字符和数字的，例如“123”，123是截然不同的两个变量，但是他们转换又是非常简单s = “123” # 此处是字符串。n = 0 + s ，这样n就成了数字123 。

     2. awk中的数组
           说道awk中的数组，可能有些特殊了，awk允许你用字符串作为下标。使用C语言的同学看到这一点也许就会笑了，这个特性岂不是牺牲效率换来的？其实如果你仔细去看gawk的源代码就会发现，gawk中数组的实现还是蛮复杂的，array_init()就可以看到，其中array下标的操作以及实现使用了hash算法。还是满巧妙的。
        Awk支持使用for (iggy in foo)，这个令awk的实现负责了不少。

    3. awk中的数值运算符
        awk支持C语言中的大部分数值运算符：++ — ^ ! 等等

    4. awk中的语句
     回车识别语句结束，C语言中是分号了，如果你想把多条语句写到一行上就用分号隔开。
awk同样支持分支语句，用法和C语言中一样。当然啦还有循环，while ，do while for 等 这些都和C中用法一样。

   5. 其他
    awk中同样需要交互性操作：输入和输出。
其中输入可以接受用户键盘输入和重定向输入。Getline
输出的话就比较多了，可以使用print 和 printf函数，其中printf的使用方法和C语言中一样。

以前做项目的时候，没有深入的考虑过这些问题，只是和同学在讨论问题的时候稍微摄入过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语言几十年不衰，还是有原因的，他有很经典的地方。很值得我们深入的研究它！

最近看到网上的一些算法总提到Bloom Filter，很多说明都是搬了一大堆的公式或者是一堆的英文，感觉看起来甚是费解。
Bloom Filter其实就是位图的一个扩展而已，位图会产生重复的冲突，Bloom Filter使用了多个hash函数，共同置位，这样就减少了冲突的误判率。布隆过滤器是由巴顿.布隆于一九七零年提出的。

详细讲一下 这个 思想：
假如我们有一亿个URL需要存储，我们先建立一个八亿的二进制位图，然后将这八亿个二进制全部清零。对于每个URL，我们用不同的K个(我们选择4个)随机函数产生器(不同的hash函数)，产生4个值(h1,h2,h3,h4)。然后再把这四个值通过一个函数映射到0-八亿个数之间的某四个数，这样就可以，直接设置四个位图为1，如下图：

插入成功了的话，那么查找就很简单了。直接用插入过程的运算，判断h1,h2,h3,h4，对应的位是否为1，如果全部为1即是命中！但是，我们可以想到，Bloom Filter有一定的误判率，即该数据不存在，但是，如果hash后的函数数据对应值全部为1的话，那么既是伪命中！这个概率比较小，解决办法既是再重新做一个类似白名单的缓存。

通过上面的理解，很简单可以明白，该算法对数据的插入和查找是比较简单，但是，如果动态数据怎么办呢？也就是说，假如我想删除怎么办呢？很遗憾，Bloom Filter不支持删除操作。不过Bloom Filter改进以后是可以删除的。比如：Counting Bloom Filter，既是把位图中的位，更新为一个技术器，每次映射以后，不是简单的置1，而是+1，然后对应的删除时-1。
具体的应用就是 过滤了，比如过滤IP、URL、Email等。

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

在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);
}