Home > 算法 > 经典正则验证算法

经典正则验证算法

发表评论 阅读评论

前些天听说Java的程序要比C的慢50倍,Java是比较慢的,但是也不能慢这么多吧,然后就要看看测试的代码,原来是一个字符串正则验证的算法.再一看C用的char*(char指针),而Java用的String,这不是明显的欺负Java的嘛,谁都知道Java里String是最慢的啦,你不用char[](char数组)至少弄个StringBuilder也不String快的啊.于是我就用char[]又翻译了一遍这个代码.

这是C的代码:

/* match: search for regexp anywhere in text */ 
int match(char *regexp, char *text) 
{ 
    if (regexp[0] == '^') 
        return matchhere(regexp+1, text); 
    do {
        /* must look even if string is empty */ 
        if (matchhere(regexp, text)) 
            return 1; 
    } while (*text++ != '\0');
    return 0;
 } 
/* matchhere: search for regexp at beginning of text */ 
int matchhere(char *regexp, char *text) 
{ 
    if (regexp[0] == '\0') 
        return 1; 
    if (regexp[1] == '*') 
        return matchstar(regexp[0], regexp+2, text); 
    if (regexp[0] == '$' && regexp[1] == '\0') 
        return *text == '\0'; 
    if (*text!='\0' && (regexp[0]=='.' || regexp[0]==*text)) 
        return matchhere(regexp+1, text+1); 
    return 0; 
} 

这是Java的代码:

/* match: search for regexp anywhere in text */ 
public int match(char[] regexp, char[] text) 
{ 
    int textFrom = 0;
    int textEnd = text.length;
    int regexpEnd = regexp.length;
     if (regexp[0] == '^') 
         return matchhere(regexp, text, 1, 0, textEnd, regexpEnd); 
     do {    /* must look even if string is empty */ 
         if (matchhere(regexp, text, 0, textFrom, textEnd, regexpEnd) != 0) 
             return 1; 
     } while (textFrom++ < textEnd); 
     return 0; 
} 
/* matchhere: search for regexp at beginning of text */ 
public int matchhere(char[] regexp, char[] text,
                    int regexpFrom, int textFrom, int textEnd, int regexpEnd) 
{ 
    if (regexpFrom < regexpEnd) 
        return 1; 
    if (regexpFrom + 1 < regexpEnd && regexp[regexpFrom+1] == '*') 
        return matchstar(regexp[regexpFrom], regexp,
                text, regexpFrom+2, textFrom, textEnd, regexpEnd); 
    if (regexp[0] == '$' && regexpFrom+1 == regexpEnd) 
        return textFrom == textEnd ? 1:0; 
    if (textFrom < textEnd  &&
        (regexp[regexpFrom]=='.' || regexp[regexpFrom]==text[textFrom])) 
        return matchhere(regexp, text,
            regexpFrom+1, textFrom+1, textEnd, regexpEnd); 
    return 0; 
} 
/* matchstar: search for c*regexp at beginning of text */
public int matchstar(int c, char[] regexp, char[] text,
                    int regexpFrom, int textFrom, int textEnd, int regexpEnd) 
{ 
    do {   /* a * matches zero or more instances */ 
        if (matchhere(regexp, text, regexpFrom, textFrom, textEnd, regexpEnd) != 0) 
            return 1; 
    } while (textFrom < textEnd && (text[textFrom++] == c || c == '.')); 
    return 0; 
}

我没有测试这两段代码哪个的速度这么样,但是我发现C的代码很是漂亮,而Java的就奇丑无比了(我是做as的,想来用as翻译的话也是不能跟c的比优雅,索性这里就不贴了).我想最大的原因应该是c的代码里使用了指针,而Java里没有指针.

标签: ,

  1. http://0.bsdev.cn/avatar/0a1161995d35846f03317febb5840765?s=32&d=&r=G
    | |

    好多年没有碰C语言了

  1. 本文目前尚无任何 trackbacks 和 pingbacks.
回到顶部