随笔-341  评论-2670  文章-0  trackbacks-0
    有个同学近来一直在做一个魔兽世界战况分析(名字好像叫DeusCraft),说是很火。只是用C#觉得不是很爽,想移植到C++上面来。但是那个东西在分析的时候用了好多正则表达式,于是只好找了些正则表达式引擎来测。

    测试的文件一共有27万多行,首先通过一个检查时间的正则表达式。如果成功,则在接下来的20几条正则表达式中验证字符串命中哪一条,然后开始做剩余的工作。原先在C#上花了12秒分析,后来换了boost的正则表达式花费40秒,然后从MSR上找了一个号称比boost快4倍的正则表达式引擎,结果还是40秒(都是微软的,咋差距这么大……)。于是同学用他自己做的正则表达式引擎花了23秒(此数据不太记得),我用我以前那个东西花费108秒(-_-|||)。

    于是我们这几天就在优化正则表达式引擎,到了今天同学那个花费13秒,我那个12秒。Visual Studio 2008 Team System上有一个Performance Wizard,用于在程序执行的过程中统计各个函数所占用的时间,可以方便定位,看出效率瓶颈,非常好用。

    我之前的正则表达式为了保持很多语法上的一致性(譬如选择操作符“|”需要遵守交换律等等),使用了一种花费很大的办法来对字符串进行分析。这种分析方法找出所有符合正则表达式要求的所有匹配的路径然后进行筛选。筛选的过程中浪费了很多new和delete的操作,而且做了很多计算,维护了一个非常复杂的数据结构。后来想到有些事情是可以让人来操心的,于是在原来的接口上加了一个option,添加了一种叫做“贪婪式”的分析方法。现在就同时有两种分析方法用了。第二种分析方法的优点是快,缺点是丧失了一些语法上的优美(不过这个对于大部分人来说应该是没什么关系的了。要是正则表达式的执行过程不复杂的话,《精通正则表达式》也就卖不出去了,反正别人的正则表达式大多都是贪婪的)。贪婪式的分析方法不同时扫描所有路径,而是使用回溯的方法。不过这种方法最大的优点在于数据结构可以大幅度简化为三个堆栈(NFA状态、已捕获子串、捕获状态),从而大量减少包括申请和释放等的指针操作。

    上文中的测试是在同学他自己进行的。我在我自己的电脑上使用了一条表达式(而不是20几条)来跑相同的文件,非贪婪式用了23秒,贪婪式用了3.5秒。

    虽然这个正则表达式引擎的接口跟现在C#或Java流行的那些差不多,只是这东西属于Syngram的一部分,所以不是很想单独分隔成一个dll发布。至于代码就要等Vczh Free Script 3.0或者Vczh Lazy Script 1.0发布的时候再一起开放了,因为使用Syngram做编译器是很爽的。到时候再考虑如何将正则表达式和上下文无关文法两个强大的字符串分析库封装成dll用吧。嘿嘿。
posted on 2008-05-07 05:21 陈梓瀚(vczh) 阅读(15316) 评论(21)  编辑 收藏 引用 所属分类: C++

评论:
# re: 正则表达式——一点小插曲 2008-05-07 19:19 | xiaolige
你自己写的那个功能有boost的全吗,能够全面实现boost.regex功能并且性能上超越它这么多就很厉害了  回复  更多评论
  
# re: 正则表达式——一点小插曲 2008-05-07 20:13 | 空明流转
现在MSR的不一定有boost好了,你用的是regex还是xpressive的那个,我都分不清有什么区别,囧  回复  更多评论
  
# re: 正则表达式——一点小插曲 2008-05-07 20:39 | Fox
正要看看正则表达式,不妨写详细点,参考一下:D  回复  更多评论
  
# re: 正则表达式——一点小插曲 2008-05-07 21:39 | eXile
boost::xpressive有两种使用方式, 一种就是和boost::regex一样的动态解析,一种是静态解析,类似于boost::spirit .
如果你使用的正则式是硬编码的字符串(大多数情况下都是如此), 那么使用 xpressive的静态解析具有更高的效率, 因为它的解析模板是在编译期生成的.  回复  更多评论
  
# re: 正则表达式——一点小插曲 2008-05-08 05:10 | 陈梓瀚(vczh)
boost::regex不能命名捕获,只能匿名捕获,我的可以,这是功能上的唯一区别。其他的特性我全有。毕竟是参考过他和.net两边的语法然后自己改了一下的。

至于spirit,那个不是正则表达式,是上下文无关文法。这个就是另外一个问题了。我那套syngram有一个东西是用来处理上下文无关文法的,这两个我还没比。不过以前的spirit是不能处理左递归的,不知道现在的行不行。

不过xpressive写的正则表达式在boost的主页上号称快了15%,估计有所限制。把文本的正则表达式换成那种直接写代码的东西,本质上并没有改变什么。因为状态机还是状态机,操作符重载是不可能静态编译的,只有直接用模板才行。这样的话会变成类似
seq_p<
ch_p<'a'>,
opt_p<
ch_p<'b'>,
ch_p<'c'>
>
>
的,用于表达a(b|c)。这种形式才有可能达到编译器编译出分析字符串的代码。  回复  更多评论
  
# re: 正则表达式——一点小插曲 2008-05-09 06:20 | 路人甲
不知天高地厚,你和你同学竟然都超过了regex,真是太有才了
  回复  更多评论
  
# re: 正则表达式——一点小插曲 2008-05-09 06:24 | 路人甲
原先在C#上花了12秒分析,后来换了boost的正则表达式花费40秒,然后从MSR上找了一个号称比boost快4倍的正则表达式引擎,结果还是40秒(都是微软的,咋差距这么大……)。
=======================
C++比C#慢这么多,差距怎么这么大啊,为什么C++比C#慢这么多啊?哦,原来使用者是头猪哟  回复  更多评论
  
# re: 正则表达式——一点小插曲 2008-05-09 07:27 | eXile
@陈梓瀚(vczh)
你所写的模板形式和xpressive的表达式模板并没有太大的差别, 因为表达式模板最终生成的也是类似于这样的东西.
另外, 程序库为了实现功能的全面性和通用性, 必然要损失一部分效率, 楼上的对此也不用大惊小怪, 还是要注意素质.....
  回复  更多评论
  
# re: 正则表达式——一点小插曲 2008-05-09 09:40 | 陈梓瀚(vczh)
@路人甲
C#的正则表达式也是C++写的,谢谢合作。
至于速度问题,好像没人规定我就不能比boost做得好吧。

不过路人甲想必是没有写过正则表达式引擎了。在测试的过程中,瓶颈不在分析,而在于分析完了之后产生的数据结构。正则表达式分析字符串的过程本身是很快的,分析完了制造那些数据出来给你用的时候,就会消耗大量的时间。明白?不过话说回来,我那个库是没有用到stl的。  回复  更多评论
  
# re: 正则表达式——一点小插曲 2008-05-11 19:53 | 胡人
鼓励原创,鼓励创新,鼓励提高,一个字,好!
期待能早些见到东西,而不是一些有点自吹自擂的数据!
  回复  更多评论
  
# re: 正则表达式——一点小插曲 2008-05-11 21:45 | 陈梓瀚(vczh)
东西不能着急。做是做出来了。改进前的代码其实已经发布了,改进后的还没有。只是以前没做广告到大家不知道罢了。现在还不拿出来的原因有三:

1:没充分测试。因为平时还要上课做作业。
2:我用的库是我自己开发的,没有stl,跟大家的代码要接上不是那么容易。所以就算看到了,也就只能看。想用的话还得再花一些功夫。因为这个正则表达式当初只是想给自己用的。
3:正则表达式隶属于我自己的那套文法工具,按照计划是在下一个编译器发布的时候一起给出来。  回复  更多评论
  
# re: 正则表达式——一点小插曲 2008-05-11 22:03 | 空明流转
鄙视造车轮啊造车轮。。。  回复  更多评论
  
# re: 正则表达式——一点小插曲 2008-05-24 07:04 | missdeer
我有一个项目里用MSR的greta全文匹配5种模式,一个3万行的文件,占用CPU99%可能要1分钟左右。最近发现,用lex和yacc来做,达到同样的效果,可能不会超过3秒钟。正则表达式要用好,还是很有文章可作的。  回复  更多评论
  
# re: 正则表达式——一点小插曲 2008-05-24 09:10 | 陈梓瀚(vczh)
当然,你用lex生成代码,是不能动态修改的。当然快了。  回复  更多评论
  
# re: 正则表达式——一点小插曲 2009-03-20 02:20 | 林林
不知到能不能把你的测试数据与程序公布一下,不用提供正则库的源码
我也写了一个,想比较一下?  回复  更多评论
  
# re: 正则表达式——一点小插曲 2009-03-20 02:54 | 陈梓瀚(vczh)
那个在旧电脑里面,而且是一个100多M的文本文件……你去比较C#那个吧,我的速度是它的96%(比率较稳定)  回复  更多评论
  
# re: 正则表达式——一点小插曲 2009-03-22 01:38 | 白开水
LSS的,你把一份C文件,用gcc -E 跑一次后,在粘贴个几十次,基本就OK了  回复  更多评论
  
# re: 正则表达式——一点小插曲 2009-03-24 08:29 | wow
@路人甲
毫无水准  回复  更多评论
  
# re: 正则表达式——一点小插曲 2010-07-27 17:57 | 路人癸
要鼓励~而不是讽刺~支持国产~打到小日本~  回复  更多评论
  
# re: 正则表达式——一点小插曲 2010-09-02 00:45 | yoco
@路人甲

boost::regex 的效能本來就是慢的,這是常識。

切莫妄自菲薄,您自己實現一個,效能也是有可能比 boost::regex 好的。  回复  更多评论
  
# re: 正则表达式——一点小插曲 2016-08-03 11:24 | Bread
明天开工。
来踩一下轮子哥的脚印。  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理