当前位置：首页 → 问答吧 → 寻找C语言的图形绘制功能

寻找C语言的图形绘制功能

时间：2011-08-17

来源：互联网

最近学字符串匹配算法。听谁说GCC的strstr是暴力匹配。测试了一下，貌似不是呢。

我写了两个函数，一个是strstr_bm，用了Boyer-Moore–Horspool算法（简化的BM算法，没BM快）；一个strstr_fxxx，纯暴力匹配。用来比较标准库的strstr：

代码:

char *strstr_fxxx (char *text, char *pattern)
{
for (char *p = text; *p; p++)
{
char *pp = p, *t = pattern;
while (*pp == *t && *t)
pp++, t++;

if (!*t)
return p;
}

return NULL;
}

char *strstr_bm (char *text, char *pattern)
{
int bad[256];
int txtlen = strlen(text), patlen = strlen(pattern);

if (!txtlen || !patlen)
return NULL;

for (int i=0; i<256; i++)
bad[i] = patlen;
for (int i=0; i<patlen-1; i++)
bad[(unsigned char)pattern[i]] = patlen - i - 1;

int ptxt, ppat;
for (ptxt=ppat=patlen-1; ptxt<txtlen;
ptxt+=bad[(unsigned char)text[ptxt]], ppat=patlen-1)
{
int i, j;
for (i=ptxt, j=ppat; j>=0; i--, j--)
if (text[i] != pattern[j])
goto BADCHAR;

return text+i+1;
BADCHAR:;
}

return NULL;
}

测试程序一次读取整个文本文件，搜索指定字符串。显示的时间以微秒为单位。

搜索比较短的字符串：

代码:

cuihao@cuihao-arch mystrstr $ ./a.out /tmp/zshrc "END OF FILE"
FIRST, USE strstr():
pattern found @ byte 130968
time: 3371

SECOND, USE strstr_bm():
pattern found @ byte 130968
time: 253

FINALLY, USE strstr_fxxx():
pattern found @ byte 130968
time: 936

搜索比较长的字符串：

代码:

cuihao@cuihao-arch mystrstr $ ./a.out /var/log/messages.1 "2011-08-14T12:39:22+08:00 localhost systemd-tmpfiles[1494]: Two or more conflicting lines for /tmp/.Test-unix configured, ignoring."
FIRST, USE strstr():
pattern found @ byte 1091251
time: 1459

SECOND, USE strstr_bm():
pattern found @ byte 1091251
time: 1907

FINALLY, USE strstr_fxxx():
pattern found @ byte 1091251
time: 12517

GCC的strstr，貌似给小数时据垃圾得很（比我想到的暴力匹配还烂），大数据却又变飞快了。是个啥方法嘞？

作者: cuihao 发布时间: 2011-08-17

PS，编译用了-O2。
时间都比较典型，不是特例。

作者: cuihao 发布时间: 2011-08-17