您现在的位置: 主页 > 华夏黑客联盟 > QQ黑客软件 > 文章内容

黑基网扫描器的高效实现

作者: QQ黑客 来源:未知 时间: 2014-03-03 阅读:
编译器进行词法分析时,不可避免地需要对源文件进行扫描,实现该功能的模块称为扫描器。扫描器读取源文件,按序返回文件内的字符,直到文件结束。
 
扫描器的功能
 
实现文件的读一般使用库函数fscanf或者fread,那么按照怎样的读取方式才能让扫描器的性能更佳呢?
 
(1)使用fscanf逐字扫描,并返回。
 
char scan(FILE*file){
 
    char ch;
 
    if(fscanf(file,"%c",&ch)==EOF){
 
       ch=-1;
 
    }
 
    return ch;
 
}
 
这是最简单的实现方式,缺点是每次读取字符时都需要访问文件进行IO。
 
我们先看看它的效率,首先在主函数内调用扫描器。
 
//主函数
 
int main()
 
{
 
    FILE*file=fopen("test.c","r");
 
    for(int i=0;i<1000000;i++)
 
       while(scan(file)!=-1);
 
    fclose(file);
 
    return 0;
 
}
 
主函数内使用扫描器扫描测试文件1000000次,然后使用time命令查看代码的执行时间(测试文件可以是任意文件,这里不给出文件内容了,区别只是执行的时间不同而已)。
 
$ time main
 
我们测试了五次,并取了平均值(单位:ms)。
 
次数
 
1
 
2
 
3
 
4
 
5
 
平均值
 
real
 
370
 
366
 
374
 
368
 
377
 
371
 
user
 
112
 
140
 
132
 
144
 
140
 
133.6
 
sys
 
256
 
228
 
240
 
224
 
232
 
236
 
可以计算代码的CPU平均执行时间为133.6+236=369.6ms。
 
(2)使用fscanf和缓冲区结合的方式,每次读取字符时首先尝试从缓冲区内取,缓冲区为空时使用fscanf重新加载缓冲区。
 
#define BUFLEN 80
 
int lineLen=0;
 
int readPos=-1;
 
char line[BUFLEN];
 
char scan(FILE*file)
 
{
 
    if(readPos==lineLen-1)//缓冲区读取完毕
 
        {
 
       int pos;
 
        for(pos=0;pos<BUFLEN;pos++)//尝试将缓冲区加载满
 
           if(fscanf(file,"%c",&line[pos])==EOF){//加载时文件结束
 
               line[pos++]=-1;//文件结束标记
 
              break;
 
           }
 
        lineLen=pos;//记录缓冲区长度
 
       readPos=-1;//恢复读取位置
 
    }
 
    readPos++;//移动读取点
 
    return line[readPos]; //获取新的字符
 
}
 
按照前边的方式测试代码的执行时间。
 
次数
 
1
 
2
 
3
 
4
 
5
 
平均值
 
real
 
374
 
380
 
371
 
371
 
374
 
374
 
user
 
140
 
124
 
148
 
136
 
108
 
131.2
 
sys
 
232
 
252
 
220
 
232
 
264
 
240
 
计算代码的CPU平均执行时间为131.2+240=371.2ms。虽然这种方法只是在缓冲区为空时重新加载缓冲区,避免了每次读取符号进行文件IO的问题,但是却比第一种方式的性能还差。主要是因为加载缓冲区时使用fscanf是按照字节进行加载的,如果使用fread可能会不同。
 
(3)和方法二类似,只是加载缓冲区时使用fread。fread的参数size表示加载数据块的大小,count表示加载数据块的个数,这里每次加载BUFLEN个1字节数据块。
 
#define BUFLEN 80
 
int lineLen=0;
 
int readPos=-1;
 
char line[BUFLEN];
 
char scan(FILE*file)
 
{
 
    if(readPos==lineLen-1)//缓冲区读取完毕
 
        {
 
       lineLen=fread(line,1,BUFLEN,file);//重新加载缓冲区数据
 
       if(lineLen==0)//没有数据了
 
        {
 
           lineLen=1;
 
           line[0]=-1;//文件结束标记
 
        }
 
        lineLen=pos;//记录缓冲区长度
 
       readPos=-1;//恢复读取位置
 
    }
 
    readPos++;//移动读取点
 
    return line[readPos]; //获取新的字符
 
}
 
测试代码的执行时间。
 
次数
 
1
 
2
 
3
 
4
 
5
 
平均值
 
real
 
339
 
332
 
334
 
341
 
332
 
335.6
 
user
 
96
 
92
 
116
 
108
 
84
 
99.2
 
sys
 
244
 
236
 
216
 
228
 
244
 
233.6
 
计算代码的CPU平均执行时间为99.2+233.6=332.8ms,可见使用fread读取文件比使用fscanf的效率要高。该方法是每次加载BUFLEN个1字节数据块,如果每次加载1个BUFLEN字节数据块是不是更高效呢?
 
(4)和方法三类似,只是这里每次加载BUFLEN个1字节数据块。
 
#define BUFLEN 80
 
int lineLen=0;
 
int readPos=-1;
 
char line[BUFLEN];
 
static int offset=0;//记录文件指针的偏移,每次打开文件需要初始化为0
 
char scan(FILE*file)
 
{
 
    if(readPos==lineLen-1)//缓冲区读取完毕
 
        {
 
       lineLen=fread(line,BUFLEN,1,file);//重新加载缓冲区数据
 
        if(lineLen){//成功加载
 
           offset+=BUFLEN;//累计偏移
 
           lineLen=BUFLEN*1;
 
        }
 
        else{//最后一段不足BUFLEN,无法获取读取的长度
 
            fseek(file,offset,SEEK_SET);//撤回文件指针
 
            lineLen=fread(line,1,BUFLEN,file);//按字节重读最后一段
 
            line[lineLen++]=-1;//文件结束标记
 
        }
 
        lineLen=pos;//记录缓冲区长度
 
       readPos=-1;//恢复读取位置
 
    }
 
    readPos++;//移动读取点
 
    return line[readPos]; //获取新的字符
 
}
 
测试代码的执行时间。
 
次数
 
1
 
2
 
3
 
4
 
5
 
平均值
 
real
 
2241
 
2223
 
2259
 
2223
 
2221
 
2233.4
 
user
 
620
 
540
 
616
 
600
 
648
 
604.8
 
sys
 
1616
 
1680
 
1640
 
1620
 
1568
 
1624.8
 
计算代码的CPU平均执行时间为604.8+1624.8=2229.6ms,这有点出乎意料。分析原因,可能是因为文件较小时,当读取到最后一块缓冲区时,撤回文件指针比较消耗时间。因此,使用方法三实现的扫描器性能更稳定,且代码更简洁。
 
(5)如果使用fread不是读入1个BUFLEN字节数据,而是读取BUFLEN/2个2字节数据,那么最后一次将读入最后一个字节。
 
#define BUFLEN 80
 
int lineLen=0;
 
int readPos=-1;
 
char line[BUFLEN];
 
char scan(FILE*file)
 
{
 
    if(readPos==lineLen-1)//缓冲区读取完毕
 
        {
 
       lineLen=fread(line,2,BUFLEN/2,file);//重新加载缓冲区数据
 
        if(lineLen){//成功加载
 
               lineLen=lineLen*2;//读取了偶数字节
 
        }
 
        else{//最后一字节已经存储在line[0]
 
           line[1]=-1;//文件结束标记
 
           lineLen=2;//长度
 
        }
 
        lineLen=pos;//记录缓冲区长度
 
       readPos=-1;//恢复读取位置
 
    }
 
    readPos++;//移动读取点
 
    return line[readPos]; //获取新的字符
 
}
 
测试代码的执行时间。
 
次数
 
1
 
2
 
3
 
4
 
5
 
平均值
 
real
 
663
 
657
 
646
 
665
 
659
 
658
 
user
 
208
 
224
 
204
 
212
 
184
 
206.4
 
sys
 
452
 
428
 
440
 
456
 
472
 
449.6
 
计算代码的CPU平均执行时间为206.4+449.6=656ms。虽然该方法不需要撤回文件指针,但是性能仍不如方法三。
 
综上所述,方法三是实现扫描器比较高效的方式:使用缓冲区代替文件的频繁访问,并在缓冲区读取完毕时,使用fread每次加载BUFLEN个1字节数据块更新缓冲区数据。希望本文对你有所帮助。