使用 python 和 javascript 的正则表达式速度慢，但在 go 和 php 中快速失败

Question

我写了一个正则表达式来解析 PostgreSQL 错误，试图向用户显示哪个字段有重复数据。正则表达式是这个：^DETAIL:.[^\(]+.(.[^\)]+).[^\(]+.(.[^\)]+). already exists如果你像这样针对正确的消息运行它，它会非常快（https://regex101.com/r/GZuREV/1）：ERROR:  duplicate key value violates unique constraint "uq_content_block_internal_name_store_id" DETAIL:  Key (lower(internal_name::text), store_id)=(some content block-32067683, 0c6d20a7-d843-44f3-af9c-4a2cf2a47e4c) already exists.但是，如果 PostgreSQL 发出另一条消息，如下所示，我的机器中 python 将花费大约 30 秒的时间来回答 ( https://regex101.com/r/GZuREV/2 )。ERROR:  null value in column "active" violates not-null constraint DETAIL:  Failing row contains (2018-08-16 14:23:52.214591+00, 2018-08-16 14:23:52.214591+00, null, 6f6d1bc9-c47e-46f8-b220-dae49bd58090, bf24d26e-4871-4335-9f18-83c5a52f1b3a, Some Product-a1c03dde-2de9-401c-92d5-5c1500908984, {"de_DE": "Fugit tempore voluptas quos est vitae.", "en_GB": "Qu..., {"de_DE": "Fuga reprehenderit nobis reprehenderit natus magni es..., {"de_DE": "Fuga provident dolorum. Corrupti sunt in tempore quae..., my-product-53077578, SKU-53075778, 600, 4300dc25-04e2-4193-94c0-8ee97b636739, 52553d24-6d1c-4ce6-89f9-4ad765599040, null, 38089c3c-423f-430c-b211-ab7a57dbcc13, 7d7dc30e-b06b-48b7-b674-26d4f705583b, null, {}, 0, null, 9980, 100, 1, 5).如果转到 regex101 链接，您可以看到，如果您切换到不同的语言，如 php 或 go，它们都很快返回说没有找到匹配项，但如果您选择 python 或 javascript，您将超时。我的快速脏修复是这样的：match = 'already exists' in error_message and compiled_regex.search(error_message)你认为这可能是什么原因造成的？会不会是贪婪的运营商在我达到我想要的数据之前消费？

Answer 1

包正则表达式

import "regexp"

包 regexp 实现正则表达式搜索。

接受的正则表达式语法与 Perl、Python 和其他语言使用的通用语法相同。更准确地说，它是 RE2 接受并在https://golang.org/s/re2syntax中描述的语法 ，\C 除外。有关语法的概述，请运行

go doc regexp/syntax

此包提供的正则表达式实现保证按输入大小线性运行。（这是大多数正则表达式的开源实现不保证的属性。）有关此属性的更多信息，请参阅

http://swtch.com/~rsc/regexp/regexp1.html

或任何有关自动机理论的书。

---

通过设计，Go 正则表达式保证在输入的大小上按线性时间运行，这是正则表达式的其他一些实现无法保证的属性。请参阅正则表达式匹配可以简单快速。

Answer 2

使用这个：

^DETAIL:\s*+Key[^\(]++\((.+)\)[^\(]+\(([^\)]+)\) already exists

查看匹配示例和非匹配示例

解释：

首先，原始正则表达式似乎与整个键组不匹配，您停在了lower(internal_name::text，遗漏了复合键的某些列以及一个不平衡的括号。如果你这样修改它，它应该可以捕获复合键。如果不应该这样做，请告诉我：

^DETAIL:.[^\(]+.(.+)\)[^\(]+.(.[^\)]+). already exists

只需更改它，正则表达式就可以“运行”，但仍然很慢。

他的主要原因之一就是这个[^\(]+。它首先匹配并DETAIL:  Failing row contains(space)继续匹配正则表达式的其余部分。它不会匹配，所以它回溯到少一个字符，直到DETAIL:  Failing row contains并继续正则表达式的其余部分。它不会匹配，所以会回到DETAIL:  Failing row contain......等等。

避免这种情况的一种方法是使用所有格量词。这意味着一旦你获取了一些东西，你就无法返回。所以使用这个[^\(]++而不是这个[^\(]+（即：）^DETAIL:.[^\(]++.(.+)\)[^\(]+.(.[^\)]+). already exists使正则表达式将步数从 28590 减少到 1290。

但你仍然可以改进它。如果您知道您所需的数据使用关键字key，请使用它！这样，由于它不存在于失败的示例中，它会使正则表达式很快失败（一旦它读取 DETAIL 和下一个词）

所以如果你使用^DETAIL:\s*+Key[^\(]++.(.+)\)[^\(]+.(.[^\)]+). already exists步骤现在只有 12。

如果您觉得使用key过于具体，您可以使用不太通用的东西来尝试找到“不是'失败'”。像这样：

^DETAIL:\s*+(?!Fail)[^\(]++.(.+)\)[^\(]+.(.[^\)]+). already exists

这样就是17步。

最后，您可以调整匹配内容的正则表达式。

改变这个：

^DETAIL:\s*+Key[^\(]++.(.+)\)[^\(]+.
           # <============= here, use \( instead
           (.[^\)]+). already exists

这样：

^DETAIL:\s*+Key[^\(]++.(.+)\)[^\(]+\((.[^\)]+). already exists

这将步骤从 538 减少到 215，因为你减少了回溯。

然后，在删除几个无用的点并将一些（应该是括号的）点替换为\(或\)（个人品味）之后，您将获得最终的正则表达式：

^DETAIL:\s*+Key[^\(]++\((.+)\)[^\(]+\(([^\)]+)\) already exists

Answer 3

这是一个正则表达式怪物:)

为什么不拆分 2 个正则表达式？

1. 检查是否already exists匹配（非常快）

2. 使用现有的正则表达式提取要显示的数据^DET.[^\(]+.(.[^\)]+).[^\(]+.(.[^\)]+)

那应该可以大大加快您的代码速度。（你甚至可以像我一样缩短细节）

Answer 4

这并不是问题的真正答案，但我认为问题可能出在贪婪的运营商身上。无论如何，我认为你应该让它的一部分变得懒惰以快速失败。

我使用了这种模式，在 regex101 上的所有语言引擎上都可以：

^DETAIL:.+?\((.+)\).+?\((.+)\) already exists.