代码之家 › 专栏 › 技术社区 › Keng

关于正则表达式中贪婪与否定字符类的一个问题

regex-greedy regex

Keng · 技术社区 · 16 年前

我有一个非常大的文件,看起来像这样(见下文)。我有两个基本的regex选项可以在上面使用(我知道可能还有其他的方法,但我确实在尝试比较贪婪的char类和否定的char类)。

ftp: [^\D]{1,}
ftp: (\d)+
ftp: \d+

注意:如果我去掉了周围的帕伦斯干酪怎么办?

现在+是贪婪的,它强制回溯,但是否定的char类需要逐字符比较。哪个效率更高?假设文件非常大,那么由于文件的长度,处理器使用上的微小差异将被夸大。

既然你已经回答了这个问题,那么如果我的否定字符类非常大,比如说18个不同的字符呢?那会改变你的答案吗?

谢谢。

FTP:1117字节
FTP:5696字节
FTP:3207字节
FTP:5696字节
FTP:7200字节

6 回复 | 直到 13 年前

rslite 16 年前

你的两个表情都有同样的贪婪。正如其他人在这里所说,除了捕获组,它们将以相同的方式执行。

在这种情况下,贪婪在执行速度上不会有太大影响,因为您没有任何跟踪\d*的内容。在这种情况下,表达式将简单地处理它能找到的所有数字,并在遇到空格时停止。这些表达式不应发生回溯。

为了使其更明确,如果您有如下表达式,则应该进行回溯:

\d*123

在这种情况下,解析器将吞没所有的数字,然后回溯以匹配下面的三个数字。

Markus Jarderot 16 年前

[^\d]1、和\d+完全相同。regex解析器将把[^\d]和\d编译成内容相同的字符类,并且+只是1,的缩写。

如果你想要懒散的重复,你可以添加一个?最后。

\d+?

字符类通常被编译成ASCII字符的位图。对于Unicode(>=256),它依赖于实现。一种方法是创建一个范围列表,并对其使用二进制搜索。

对于ASCII,查找时间在大小上是常量。对于Unicode,它是对数或线性的。

jj33 16 年前

这是一个技巧性的问题,因为(\d)+由于捕获括号的开销,需要稍长的时间。如果将其更改为\d+,它们在我的Perl/系统中所用的时间相同。

harpo Binary Worrier 16 年前

是的,我同意米扎德克斯…这两个表达式在语义上是等价的。尽管分组可能需要额外的资源。这不是你要问的。

thelsdj 16 年前

我最初的测试显示,184m文件中的[^\d 1,比\d+慢一点,前者需要9.6秒,后者需要8.2秒。

如果不捕获(第()个),两个都会快1秒钟,但两者之间的差别差不多。

我还做了一个更广泛的测试,将捕获的值打印到/dev/null,并在空间上拆分第三个版本,结果是:

([^\D]{1,}): ~18s
(\d+): ~17s
(split / /)[1]: ~17s

编辑:拆分版本改进,时间缩短到与(\d+)相同或更低

目前最快的版本(有人能改进吗?):

while (<>)
{
    if ($foo = (split / /)[1])
    {
        print $foo . "\n";
    }
}

Jay 16 年前

不是对这个问题的直接回答,但是为什么不采用完全不同的方法呢,因为您已经知道行的格式了?例如,您可以在字段之间的空白处使用regex,或者完全避免regex,在空白处使用split(),这通常比任何正则表达式都快,这取决于您使用的语言。