作者lg31cm (我住5F)
看板RegExp
标题Re: [问题] 正规表示法处理的很慢
时间Sat Jul 11 03:39:21 2009
※ 引述《ta0306556 (POIL)》之铭言:
: 有一堆资料,我手上有的资讯为 本文和词性
: 那有时候我需要用到词性去做比对,有时候要用到本文做比对
: 但是我都是要结取出本文,而正规表示法又不能够比对字串阵列
: 所以我必须把正规表示法做成下列的样子:
: @严长寿~Nb@,~.*(<value>@.*~.*@.*~.*@.*~.*)@出生~.*
: 我以@作为词的分隔,每个词有两个栏位,分别为:「本文~词性」
: 那我要去做比对的时候,把我要的资讯放上去
: 要忽略的地方改为".*",因此会有很多个".*"
: 但是这样会让程式几乎跑不动,太慢了
: 请问有没有其他的方法可以改善...
典型的.*滥用,假如你的 regex engine 是 NFA(大部分
regex都是采用NFA),可以说一定慢到你受不了,因为.*
会一直往後吃字元直到字串结尾或是end of line,接着
因为你的.*後面又有其他字元,regex engine只好不断
backtracking直到找到match的字元为止,假如你要处理的
资料很短还没关系,资料一长一定会让match时间成指数级成长
你的.*还不只一个,engine光是backtracking就够忙的了,当然
慢到让你觉得电脑当了
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 122.124.98.159
1F:推 ta0306556:恩,感谢指教,可是我的问题我想不到更好的方法了~ 07/11 21:51
2F:→ ta0306556:请问有没有什麽其他的方法让我可以解我的问题呢? 07/11 21:52
3F:推 ta0306556:因为我的每个.*後面不是@就是~我可以设定遇到这两个符号 07/11 23:08
4F:→ ta0306556:就中断的方法吗? 07/11 23:09
5F:推 MichaelHsin: [^@]* 07/12 00:14
6F:推 ta0306556:对吼,以前用过,我居然忘了...感谢提醒! 07/12 01:17