1

我有一个非常大的文件，看起来像这样（见下文）。我有两种基本的正则表达式可供选择（我知道可能还有其他选择，但我真的想比较贪婪和否定字符类）方法。

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

注意：如果我去掉 \d 周围的括号怎么办？

现在 + 是贪婪的，它强制回溯，但 Negated Char 类需要逐个字符比较。哪个更有效率？假设文件非常非常大，因此由于文件的长度，处理器使用的微小差异将变得夸大。

既然您已经回答了这个问题，如果我的 Negated Char Class 非常大，比如说 18 个不同的字符怎么办？这会改变你的答案吗？

谢谢。

ftp：1117 字节
ftp：5696 字节
ftp：3207 字节
ftp：5696 字节
ftp：7200 字节

4

6 回答 6

3

[^\D]{1,} 和 \d+ 完全相同。正则表达式解析器会将 [^\D] 和 \d 编译成内容相同的字符类，而 + 只是 {1,} 的缩写。

如果你想要懒惰的重复，你可以添加一个？在末尾。

\d+?

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

对于 ASCII，查找时间在大小上是恒定的。对于 Unicode，它是对数或线性的。

于 2008-10-03T19:42:14.090 回答
2

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

同样在这种情况下，贪婪对执行速度的影响并不大，因为在 \d* 之后没有任何内容。在这种情况下，表达式将简单地处理它可以找到的所有数字，并在遇到空格时停止。这些表达式不应发生回溯。

为了使其更明确，如果您有这样的表达式，则应该进行回溯：

\d*123

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

于 2008-10-03T19:57:05.150 回答
1

我最初的测试表明 [^\D{1,} 比 \d+ 慢一点，在 184M 文件上，前者需要 9.6 秒，而后者需要 8.2

没有捕获（（）的）两者都快了大约 1 秒，但两者之间的差异大致相同。

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

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

编辑：拆分版本改进和时间减少到相同或低于 (\d+)

迄今为止最快的版本（有人可以改进吗？）：

while (<>)
{
    if ($foo = (split / /)[1])
    {
        print $foo . "\n";
    }
}
于 2008-10-03T19:44:22.057 回答
1

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

于 2008-10-03T19:44:25.503 回答
1

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

于 2008-10-03T19:46:50.023 回答
0

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

于 2008-10-03T19:39:11.007 回答