我能否进一步提高这个正则表达式的性能?

5

我想从线程转储文件中获取线程名称。 每个线程转储的第一行通常包含在“双引号”中的线程名称。 它可能看起来很简单,如下所示:

"THREAD1" daemon prio=10 tid=0x00007ff6a8007000 nid=0xd4b6 runnable [0x00007ff7f8aa0000]

或者像下面这样大:
"[STANDBY] ExecuteThread: '43' for queue: 'weblogic.kernel.Default (self-tuning)'" daemon prio=10 tid=0x00007ff71803a000 nid=0xd3e7 in Object.wait() [0x00007ff7f8ae1000]

我写的正则表达式很简单:"(.*)"。它捕获双引号内的所有内容作为一个组。然而,它会导致大量回溯,因此需要很多步骤,可以在这里看到。口头上,我们可以解释这个正则表达式为“捕获双引号括起来的任何内容作为一个组”
所以我想出了另一个正则表达式,它执行相同的操作:"([^\"])"。口头上,我们可以将这个正则表达式描述为“捕获双引号括起来的任意数量的非双引号字符作为一个组”。我没有发现比这更快的正则表达式。它不执行任何回溯,因此需要最少的步骤,可以在这里看到。
我告诉我的同事这一点。他想出了另一个:"(.*?)"。我不明白它是如何工作的。它的回溯要比第一个少得多,但稍微慢一些,可以在这里看到。然而,
  • 我不明白为什么回溯会提前停止。
  • 我理解?是一个量词,表示一次或者不出现。但我不明白它在这里如何使用。
  • 事实上,我无法猜测我们如何口头描述这个正则表达式。
我的同事试图解释给我听,但我仍然无法完全理解。有人能解释一下吗?

我认为你应该使用.*?,这将使搜索变得懒惰。我认为你当前的正则表达式有一个缺陷。如果在线程名称后面有一个“some text here”,那么最后一个"将被映射。 - TheLostMind
@VinodMadyalkar:您提出的是最低效的解决方案之一。惰性匹配有一些非常重要的缺点。否定字符类解决方案是最好的选择。 - Wiktor Stribiżew
@stribizhev - 但是看着这个字符串,贪心算法会涉及到很多回溯。如果线程名后面还有另一个 "" ,那怎么办?线程名从字符串的开头开始,回溯值得吗? - TheLostMind
3
@VinodMadyalkar жҸҗдҫӣзҡ„жӯЈеҲҷиЎЁиҫҫејҸ "([^"]*+)" жҳҜеҢ№й…Қзұ»дјјдәҺ "no-quotes-here" иҝҷж ·зҡ„еӯ—з¬ҰдёІзҡ„жңҖдҪійҖүжӢ©гҖӮ - Wiktor Stribiżew
@stribizhev - 同意。看起来那确实是最快的。 - TheLostMind
显示剩余8条评论
1个回答

14

简要解释和解决方案

"(.*)" 正则表达式涉及很多回溯,因为它找到第一个 " 然后抓取整个字符串并向后回溯寻找距离字符串结尾最近的 "。由于您有一个更靠近开头的带引号子字符串,所以比使用 "(.*?)" 更需要回溯,因为这个 惰性 量词 *? 使正则表达式引擎在找到第一个 " 后寻找距离它最近的 "

否定字符类解决方案 "([^"]*)" 是三种方法中最好的,因为它不必抓取 所有 字符,只需除了 " 之外的所有字符。然而,为了防止任何回溯并使表达式最终有效,您可以使用 占有量词

如果您需要匹配像 " + no quotes here + " 这样的字符串,请使用:

"([^"]*+)"

在这种情况下,甚至不需要匹配尾引号:

"([^"]*+)

请看 正则表达式演示

事实上,我无法猜测我们如何用语言描述这个正则表达式。

后面的 "([^"]*+) 正则表达式可以描述为:

  • " - 从字符串左侧找到第一个 " 符号
  • ([^"]*+) - 匹配并捕获除了 " 以外的零个或多个符号,尽可能多地匹配,一旦引擎找到一个双引号,匹配就会立即返回,不会回溯。

量词

更多关于 Rexegg.com 上的量词 的信息:

A*表示零个或多个A,尽可能多的匹配(贪婪),如果引擎需要回溯,则放弃字符(顺从)
A*?表示零个或多个A,尽可能少的匹配以使整体模式匹配(懒惰)
A*+表示零个或多个A,尽可能多的匹配(贪婪),如果引擎尝试回溯,则不放弃字符(占有)

如您所见,?并不是一个独立的量词,它是另一个量词的一部分。

我建议了解更多关于为什么懒惰量词很耗费资源以及否定类解决方案真正安全快速地处理输入字符串(在其中只匹配引号后面的非引号字符,然后是最终引号)。

.*?.*[^"]*+量词之间的区别

贪心算法 "(.*)" 的解决方案工作流程如下:从左到右检查每个符号,寻找",一旦找到,它会抓取整个字符串直到结束,并检查每个符号是否等于"。因此,在您的输入字符串中,它会回溯160次。

enter image description here


Lazy "(.*?)" 解决方案的工作方式如下:引擎找到第一个 ",然后在模式中前进并尝试下一个标记(即 ")与 THREAD1 中的 T 匹配。这失败了,因此引擎回溯并允许 .*? 扩展其匹配项,使其匹配 T。再次,引擎在模式中前进。现在它尝试将 "THREAD1 中的 H 匹配。这也失败了,因此引擎回溯并允许 .*? 扩展并匹配 H然后该过程重复进行——引擎前进、失败、回溯、允许惰性的 .*? 扩展其匹配项、前进、失败等等。对于每个由 .*? 匹配的字符,引擎都必须回溯。从计算的角度来看,这种匹配一项、前进、失败、回溯、扩展的过程是“昂贵”的。 由于下一个"不远,因此回溯步骤的数量比贪婪匹配要少得多。

enter image description here

  • 使用否定字符类的占有量词解决方案 "([^"]*+)" 的工作原理如下: 引擎找到最左边的 ",然后获取所有不是 " 直到第一个 " 的字符。否定字符类[^"]*+ 贪婪地匹配零个或多个不是双引号的字符。因此,我们保证点星(dot-star)永远不会跳过第一个遇到的 "。这是一种更直接和高效的在某些分隔符之间进行匹配的方法。请注意,在这种解决方案中,我们可以完全信任量化 [^"]*。即使它是贪婪的,也没有风险让 [^"] 匹配太多,因为它与 " 互斥。这是正则表达式风格指南中对比原则的体现[见来源]
请注意,所有权量词不允许正则表达式引擎回溯到子表达式中,一旦匹配成功,"之间的符号将成为一个硬块,由于正则表达式引擎遇到的某些“不便”,它将无法重新排序此文本块中的任何字符。
对于当前表达式,这并没有太大的区别。

enter image description here


1
“懒惰量词”是“非贪婪量词”的一个不恰当的名称。它们在计算机领域中并不像其他地方应用该词汇一样“懒惰”。 - Borodin
1
@Borodin - 我不同意。术语“懒惰”恰当而简洁地描述了这个修饰符的行为。此外,这个术语在杰弗里·弗里德尔的经典著作《精通正则表达式》中被广泛使用。毫无疑问,这是我读过的最有用的书籍。 - ridgerunner
@ridgerunner:当然你有权发表自己的意见,但我不同意。 A 在编程中,“懒惰”操作通常是指延迟到其效果被要求时再执行的操作,这与非贪婪正则表达式量词无关。 B 在英语中,“懒惰”并不是“贪婪”的相反。 C 无论你对Friedl的书有多高的评价,想象其中所说的一切都是真实、不可辩驳且无法更好的是很奇怪的。而且现在这本书已经非常过时,尽管基本原理仍然适用。 - Borodin
我很好奇是否可以用一个正则表达式来回答这个问题,而不是我的两个正则表达式解决方案...? - T.J. Crowder

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接