AskOverflow.Dev

AskOverflow.Dev Logo AskOverflow.Dev Logo

AskOverflow.Dev Navigation

  • 主页
  • 系统&网络
  • Ubuntu
  • Unix
  • DBA
  • Computer
  • Coding
  • LangChain

Mobile menu

Close
  • 主页
  • 系统&网络
    • 最新
    • 热门
    • 标签
  • Ubuntu
    • 最新
    • 热门
    • 标签
  • Unix
    • 最新
    • 标签
  • DBA
    • 最新
    • 标签
  • Computer
    • 最新
    • 标签
  • Coding
    • 最新
    • 标签
主页 / coding / 问题 / 77934024
Accepted
Luis Abreu
Luis Abreu
Asked: 2024-02-04 06:49:56 +0800 CST2024-02-04 06:49:56 +0800 CST 2024-02-04 06:49:56 +0800 CST

正则表达式:将 url 与多个 or 表达式匹配的最佳选择是什么

  • 772

假设您正在尝试匹配与以下 2 条规则兼容的 url:

  1. 以单词 .../contactos(/) 结尾
  2. 或者在 url 中间有 .../gestao/... 一词

最初,我从以下模式开始(模式 1):

^(?:(?:/.+)+/contactos/?(?!.))|(?:(?:/.*)+/gestao(?:/.+))$

它有效,但在这种情况下所需的负前瞻似乎不合适,所以我用以下模式替换(我们称之为模式 2):

^(?:(?:/.+)+/contactos/?)$|^(?:(?:/.*)+/gestao(?:/.+))$

主要区别在于,我使用开始/结束锚点来分隔每个表达式,而不是像第一个示例中那样使用单个对(我没有在两种情况下捕获组,因此这实际上是两种模式之间的唯一区别)。通过“隔离”每个“选项”,我可以放弃模式 1 中使用的负前瞻。

由于模式 2 不使用前瞻,我预计它应该比模式 1 更快。但是,情况似乎并非如此。我用 .net 8 构建了一个小型基准测试,看起来模式 1 比匹配 url 的模式稍快。这是我编写的代码(并不是真正有经验的 Benchmark 用户,所以也许我遗漏了一些东西):

[MemoryDiagnoser]
public class RegexPerformance {
    
    private const string _patternNoCapture = "^(?:(?:/.+)+/contactos/?(?!.))|(?:(?:/.*)+/gestao(?:/.+))$";
    private const string _patternNoCaptureWithStartEndAnchors = "^(?:(?:/.+)+/contactos/?)$|^(?:(?:/.*)+/gestao(?:/.+))$";

    private Regex _noCapture = default!;

    private Regex _noCaptureWithStart = default!;

    [GlobalSetup]
    public void Setup() {
        _noCapture = new (_patternNoCapture,
                               RegexOptions.Compiled | RegexOptions.IgnoreCase);
        
        _noCaptureWithStart = new (_patternNoCaptureWithStartEndAnchors,
                                        RegexOptions.Compiled | RegexOptions.IgnoreCase);
    }
    
    public IEnumerable<string> Urls => [
        "/test/contactos",
        "/test/contactos/",
        "/test/someplace/gestao/123/yyy",
        "/test/someplace/gestao/123"
    ];
    
    [Benchmark]
    [ArgumentsSource(nameof(Urls))]
    public bool MatchPatternNoCapture(string url) => _noCapture.IsMatch(url);
    
    [Benchmark]
    [ArgumentsSource(nameof(Urls))]
    public bool MatchPatternNoCaptureWithStartEndAnchors(string url) => _noCaptureWithStart.IsMatch(url);


}

结果如下:


| Method                                   | url                  | Mean       | Error     | StdDev    | Median     | Allocated |
|----------------------------------------- |--------------------- |-----------:|----------:|----------:|-----------:|----------:|
| MatchPatternNoCapture                    | /test/contactos      |   244.5 ns |   8.25 ns |  23.53 ns |   238.6 ns |         - |
| MatchPatternNoCaptureWithStartEndAnchors | /test/contactos      |   224.3 ns |   3.14 ns |   2.62 ns |   223.5 ns |         - |
| MatchPatternNoCapture                    | /test/contactos/     |   256.6 ns |   5.67 ns |  15.80 ns |   259.9 ns |         - |
| MatchPatternNoCaptureWithStartEndAnchors | /test/contactos/     |   278.6 ns |  18.98 ns |  53.84 ns |   260.6 ns |         - |
| MatchPatternNoCapture                    | /test(...)o/123 [26] | 1,081.5 ns |  37.01 ns | 104.39 ns | 1,057.7 ns |         - |
| MatchPatternNoCaptureWithStartEndAnchors | /test(...)o/123 [26] | 1,367.4 ns | 167.26 ns | 493.18 ns | 1,121.6 ns |         - |
| MatchPatternNoCapture                    | /test(...)3/yyy [30] | 1,861.4 ns |  73.08 ns | 201.28 ns | 1,789.4 ns |         - |
| MatchPatternNoCaptureWithStartEndAnchors | /test(...)3/yyy [30] | 1,925.6 ns |  58.13 ns | 168.65 ns | 1,919.0 ns |         - |

顺便说一句,我使用不匹配的 url ( /test/contactosbad) 运行了另一个简单测试,在这种情况下,模式 2 的表现似乎比模式 1 稍好:

| Method                                   | url                | Mean     | Error    | StdDev   | Allocated |
|----------------------------------------- |------------------- |---------:|---------:|---------:|----------:|
| MatchPatternNoCapture                    | /test/contactosbad | 668.4 ns | 13.44 ns | 14.38 ns |         - |
| MatchPatternNoCaptureWithStartEndAnchors | /test/contactosbad | 518.2 ns | 10.30 ns | 14.43 ns |         - |

我必须承认我对这些结果有点困惑。我预计模式 2 的表现会比模式 1 好得多,但情况似乎并非如此。关于为什么会发生这种情况有什么想法吗?

谢谢。

c#
  • 1 1 个回答
  • 43 Views

1 个回答

  • Voted
  1. Best Answer
    InSync
    2024-02-04T08:20:34+08:002024-02-04T08:20:34+08:00

    你们的两种模式都不好:它们很容易出现灾难性的回溯。

    即,带有全能点的量化组:(?:/.+)+和(?:/.*)+。这些将需要很长时间才能在稍长一点的输入上运行。以下是ReDoS 检查器建议的 115 个字符的输入:

    /stao/stao/stao/stao/stao/stao/stao/stao/stao/stao/stao/stao/stao/stao/stao/stao/stao/stao/stao/stao
    

    这会在大约 10 秒后触发regex101.com超时(在您的计算机上可能会更快一些,因为 regex101 似乎在客户端运行正则表达式)。客观地说,这样一个群的时间复杂度是O(2^n)(指数)。

    相反,保持简单:

    ^
    (?:
      /.+/contactos/?$
    |
      /.+/gestao/.+
    )
    

    第一个.+以 1 步运行直到结束,然后回溯直到找到固定点/contactos(n步);第二个.+做同样的事情(n步)。第三个不需要回溯,所以也只需要1步;.如果您只需要布尔值而不是完整匹配,则可以将其替换为单个。总的来说,该模式的时间复杂度是O(n)(线性)。

    我还没有运行基准测试(咨询 ChatGPT 如何编写正确的 C# 程序),但我希望它在性能和可读性方面都优于您的模式。例如,regex101在短短几毫秒内就报告了比上述输入长十倍的输入不匹配的情况。

    附录

    上面的模式也可以写成:

    ^/.+/(?:contactos/?$|gestao/.+)
    

    引擎只会在回溯.+到/. 因此,这将采取较少的步骤,但仍然O(n)。

    • 3

相关问题

  • Polly DecorlatedJitterBackoffV2 - 如何计算完成所有重试所需的最长时间?

  • Wpf。在 ScrollViewer 中滚动 DataGrid

  • 我在使用 .NET MAUI MVVM 的游戏页面上获得的分数在其他页面上不可见。如何在本地设备中保存分数数据

  • 从 DataTemplate 内部将 TreeView 层次结构与 HierarchicalDataTemplate 结合使用

  • 如何改进 .NET 中的验证接口?

Sidebar

Stats

  • 问题 205573
  • 回答 270741
  • 最佳答案 135370
  • 用户 68524
  • 热门
  • 回答
  • Marko Smith

    Vue 3:创建时出错“预期标识符但发现‘导入’”[重复]

    • 1 个回答
  • Marko Smith

    为什么这个简单而小的 Java 代码在所有 Graal JVM 上的运行速度都快 30 倍,但在任何 Oracle JVM 上却不行?

    • 1 个回答
  • Marko Smith

    具有指定基础类型但没有枚举器的“枚举类”的用途是什么?

    • 1 个回答
  • Marko Smith

    如何修复未手动导入的模块的 MODULE_NOT_FOUND 错误?

    • 6 个回答
  • Marko Smith

    `(表达式,左值) = 右值` 在 C 或 C++ 中是有效的赋值吗?为什么有些编译器会接受/拒绝它?

    • 3 个回答
  • Marko Smith

    何时应使用 std::inplace_vector 而不是 std::vector?

    • 3 个回答
  • Marko Smith

    在 C++ 中,一个不执行任何操作的空程序需要 204KB 的堆,但在 C 中则不需要

    • 1 个回答
  • Marko Smith

    PowerBI 目前与 BigQuery 不兼容:Simba 驱动程序与 Windows 更新有关

    • 2 个回答
  • Marko Smith

    AdMob:MobileAds.initialize() - 对于某些设备,“java.lang.Integer 无法转换为 java.lang.String”

    • 1 个回答
  • Marko Smith

    我正在尝试仅使用海龟随机和数学模块来制作吃豆人游戏

    • 1 个回答
  • Martin Hope
    Aleksandr Dubinsky 为什么 InetAddress 上的 switch 模式匹配会失败,并出现“未涵盖所有可能的输入值”? 2024-12-23 06:56:21 +0800 CST
  • Martin Hope
    Phillip Borge 为什么这个简单而小的 Java 代码在所有 Graal JVM 上的运行速度都快 30 倍,但在任何 Oracle JVM 上却不行? 2024-12-12 20:46:46 +0800 CST
  • Martin Hope
    Oodini 具有指定基础类型但没有枚举器的“枚举类”的用途是什么? 2024-12-12 06:27:11 +0800 CST
  • Martin Hope
    sleeptightAnsiC `(表达式,左值) = 右值` 在 C 或 C++ 中是有效的赋值吗?为什么有些编译器会接受/拒绝它? 2024-11-09 07:18:53 +0800 CST
  • Martin Hope
    The Mad Gamer 何时应使用 std::inplace_vector 而不是 std::vector? 2024-10-29 23:01:00 +0800 CST
  • Martin Hope
    Chad Feller 在 5.2 版中,bash 条件语句中的 [[ .. ]] 中的分号现在是可选的吗? 2024-10-21 05:50:33 +0800 CST
  • Martin Hope
    Wrench 为什么双破折号 (--) 会导致此 MariaDB 子句评估为 true? 2024-05-05 13:37:20 +0800 CST
  • Martin Hope
    Waket Zheng 为什么 `dict(id=1, **{'id': 2})` 有时会引发 `KeyError: 'id'` 而不是 TypeError? 2024-05-04 14:19:19 +0800 CST
  • Martin Hope
    user924 AdMob:MobileAds.initialize() - 对于某些设备,“java.lang.Integer 无法转换为 java.lang.String” 2024-03-20 03:12:31 +0800 CST
  • Martin Hope
    MarkB 为什么 GCC 生成有条件执行 SIMD 实现的代码? 2024-02-17 06:17:14 +0800 CST

热门标签

python javascript c++ c# java typescript sql reactjs html

Explore

  • 主页
  • 问题
    • 最新
    • 热门
  • 标签
  • 帮助

Footer

AskOverflow.Dev

关于我们

  • 关于我们
  • 联系我们

Legal Stuff

  • Privacy Policy

Language

  • Pt
  • Server
  • Unix

© 2023 AskOverflow.DEV All Rights Reserve