我可以进一步提高这个正则表达式的性能吗？

Question

我试图从线程转储文件中获取线程名称.线程名称通常包含在每个线程转储的第一行的"双引号"中.它可能看起来很简单如下:

"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]

我写的正则表达式很简单:"(.*)".它将双引号内的所有内容作为一组捕获.但是它会导致沉重的回溯,因此需要很多步骤,可以看出这里.在口头上,我们可以将此正则表达式解释为"捕获任何包含在双引号内的任何内容"

所以我提出了另一个正则表达式,它执行相同的操作:"([^\"])".在口头上,我们可以将此正则表达式描述为"捕获双引号内包含的任意数量的非双引号字符".我没有发现任何快速正则表达式.它不执行任何回溯,因此它需要最少的步骤,可以看出这里.

我把这个告诉了我的同事.他想出了另一个:"(.*?)".我没弄明白它是如何工作的.它执行相当大的比第一个少回溯但比第二个可以看出慢一点这里.然而

• 我不明白为什么回溯会提前停止.
• 我理解的?是量词,意思是once or not at all.但是我不明白如何once or not at all在这里使用.
• 事实上,我无法猜测我们如何口头描述这个正则表达式.

我的同事试图解释我,但我仍然无法完全理解它.谁能解释一下？

Answer 1

简要说明和解决方案

在"(.*)"正则表达式涉及到很多回溯,因为它找到的第一个",然后抓住了整个字符串,并回溯寻找"最接近字符串的结尾.因为你有一个更接近开头的带引号的子串,所以有更多的回溯而不是"(.*?)"因为这个懒惰的量词*?使得正则表达式引擎"在第一次"找到后找到最接近的.

否定的角色类解决方案"([^"]*)"是3中最好的解决方案,因为它不需要抓取所有内容,只需要除了之外的所有字符".但是,要停止任何回溯并使表达最终有效,您可以使用占有量词.

如果你需要匹配"+ no quotes here+之类的字符串",请使用

"([^"]*+)"

或者甚至在这种情况下你不需要匹配尾随引用:

"([^"]*+)

请参阅正则表达式演示

事实上,我无法猜测我们如何口头描述这个正则表达式.

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

• "- 找到"字符串左边的第一个符号
• ([^"]*+)- 匹配并捕获第1组零个或多个符号",尽可能多,并且一旦引擎找到双引号,匹配将立即返回,无需回溯.

量词

有关量词的更多信息,请访问Rexegg.com:

A* 零或更多As尽可能多(贪婪),如果引擎需要回溯(温顺)
A*? 零或更多,则放弃字符As,尽可能少的允许整体模式匹配(懒惰)
A*+ 零或更多As,as尽可能多(贪婪),如果引擎试图回溯(占有),不要放弃字符

如您所见,?它不是一个单独的量词,它是另一个量词的一部分.

我建议阅读更多关于为什么懒惰量词是昂贵的,并且否定类解决方案是非常安全和快速处理您的输入字符串(您只需匹配引号后跟非引号然后最终引用).

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

• 贪婪的"(.*)"解决方案是这样的:检查从左到右寻找的每个符号",并且一旦发现将整个字符串抓到最后并检查每个符号是否等于".因此,在输入字符串中,它会回溯160次.

• 懒惰"(.*?)"溶液是这样的:发动机找到的第一个",然后在图案前进并尝试下一个标记(这是")针对T在THREAD1.这失败了,所以引擎回溯并允许将.*?其匹配扩展一个项目,以便它匹配T.再一次,发动机在模式中前进.现在会尝试"对H在THREAD1.这失败了,所以引擎回溯并允许.*?扩展和匹配H.然后该过程重复进行 - 引擎前进,失败,回溯,允许懒惰.*?将其匹配扩展一个项目,前进,失败等等.对于匹配的每个字符.*?,引擎必须回溯.从计算的角度来看,匹配一个项目,推进,失败,回溯,扩展的过程是"昂贵的".

由于下一步"不远,回溯步骤的数量远远少于贪婪匹配.

• 具有否定字符类的占有量词解决方案的"([^"]*+)"工作原理如下:引擎找到最左边的",然后抓取所有不"符合第一个字符的字符".否定的字符类[^"]*+贪婪地匹配零个或多个不是双引号的字符.因此,我们保证点星永远不会跳过第一次遇到的".这是一些更直接有效的匹配方式之间的匹配方式.请注意,在此解决方案中,我们完全可以信任*量化的[^"].即使它是贪婪的,也没有[^"]太多的风险,因为它与之相互排斥".这是正则表达式样式指南中的对比原理[见源代码].

注意,占有量词不会让正则表达式引擎回溯到子表达式,一旦匹配,它们之间的符号"就会变成一个硬块,由于正则表达式引擎遇到一些"不方便"而无法"重新排序",它将是无法将任何字符从此文本块中移出.

对于当前表达式,它并没有产生很大的不同.