src/Dpz.Core.Simple.Test/AdvancedWildcardComparisonTest.cs 网站源码

Root / src / Dpz.Core.Simple.Test / AdvancedWildcardComparisonTest.cs

using System.Collections.Concurrent;
using System.Diagnostics;

namespace Dpz.Core.Simple.Test;

/// <summary>
/// 高级通配符匹配算法对比测试
/// 对比简单实现 vs 复杂状态机实现的性能差异
/// </summary>
public class AdvancedWildcardComparisonTest
{
    // 测试数据集 - 不同复杂度的模式
    private readonly (string input, string pattern, bool expected)[] _basicTestCases =
    [
        // 基础通配符测试
        ("/api/users/123", "/api/*", true),
        ("/api/users/123", "/admin/*", false),
        ("file.txt", "*.txt", true),
        ("file.doc", "*.txt", false),
        ("test", "t?st", true),
        ("tast", "t?st", true),
        ("test", "t??t", true), // test 匹配 t??t: t=t, e=?, s=?, t=t
        // 复杂模式测试
        ("/api/v1/users/123/profile", "/api/*/users/*/profile", true),
        ("/api/v2/posts/456/comments", "/api/*/users/*/profile", false),
        ("long-file-name.config.xml", "*.config.*", true),
        ("file.backup.txt", "*.config.*", false),
        // 边界情况
        ("", "*", true),
        ("test", "", false),
        ("", "", true), // 空字符串匹配空字符串应该是 true
        ("*", "*", true),
        ("?", "?", true),
    ];

    private readonly string[] _performanceInputs =
    [
        "/api/users/123/profile/settings/advanced",
        "/static/images/gallery/thumbnails/img001.jpg",
        "/admin/dashboard/statistics/monthly/report.pdf",
        "/public/assets/css/themes/dark/main.min.css",
        "/api/v2/articles/456/comments/789/replies",
        "/downloads/software/utilities/compression/archive.zip",
        "/user/documents/projects/web/frontend/components",
        "/system/logs/application/errors/2024/01/error.log",
    ];

    private readonly string[] _performancePatterns =
    [
        "/api/users/*/profile/*",
        "/static/images/*/*.jpg",
        "/admin/*/statistics/*/*",
        "*.min.css",
        "/api/*/articles/*/comments/*",
        "/downloads/*/*/*.zip",
        "/user/*/projects/*/*",
        "*.log",
    ];

    [Test]
    public void CompareAlgorithmPerformance()
    {
        const int iterations = 50000;

        Console.WriteLine("=== 高级通配符算法性能对比测试 ===");
        Console.WriteLine($"执行迭代次数: {iterations:N0}");
        Console.WriteLine($"测试模式数量: {_performancePatterns.Length}");
        Console.WriteLine($"测试输入数量: {_performanceInputs.Length}");
        Console.WriteLine(
            $"总匹配次数: {_performancePatterns.Length * _performanceInputs.Length * iterations:N0}"
        );
        Console.WriteLine();

        // 预热
        WarmupAlgorithms();

        // 测试简单实现（我们的版本）
        var simpleTime = MeasureTime(() => TestSimpleAlgorithm(iterations), "简单通配符算法");

        // 测试复杂实现（提供的版本）
        var advancedTime = MeasureTime(() => TestAdvancedAlgorithm(iterations), "高级状态机算法");

        // 测试缓存版本
        var cachedTime = MeasureTime(() => TestCachedAlgorithm(iterations), "缓存优化版本");

        // 输出结果
        Console.WriteLine("\n=== 性能测试结果 ===");
        Console.WriteLine($"简单通配符算法: {simpleTime.TotalMilliseconds:F2} ms");
        Console.WriteLine($"高级状态机算法: {advancedTime.TotalMilliseconds:F2} ms");
        Console.WriteLine($"缓存优化版本: {cachedTime.TotalMilliseconds:F2} ms");

        Console.WriteLine("\n=== 性能对比分析 ===");
        var simpleVsAdvanced = advancedTime.TotalMilliseconds / simpleTime.TotalMilliseconds;
        var simpleVsCached = simpleTime.TotalMilliseconds / cachedTime.TotalMilliseconds;
        var advancedVsCached = advancedTime.TotalMilliseconds / cachedTime.TotalMilliseconds;

        Console.WriteLine(
            $"简单算法 vs 高级算法: {simpleVsAdvanced:F2}x (简单算法 {(simpleVsAdvanced > 1 ? "更快" : "更慢")})"
        );
        Console.WriteLine($"缓存版本 vs 简单算法: {simpleVsCached:F2}x 性能提升");
        Console.WriteLine($"缓存版本 vs 高级算法: {advancedVsCached:F2}x 性能提升");

        // 功能一致性验证
        ValidateConsistency();
    }

    private void WarmupAlgorithms()
    {
        Console.WriteLine("算法预热中...");
        for (var i = 0; i < 1000; i++)
        {
            SimpleWildcardMatch(_performanceInputs[0].AsSpan(), _performancePatterns[0].AsSpan());
            AdvancedMatchPattern(
                _performancePatterns[0].AsSpan(),
                _performanceInputs[0].AsSpan(),
                true,
                false
            );
            CachedMatch(_performanceInputs[0], _performancePatterns[0]);
        }
    }

    private TimeSpan MeasureTime(Action action, string description)
    {
        GC.Collect();
        GC.WaitForPendingFinalizers();
        GC.Collect();

        var stopwatch = Stopwatch.StartNew();
        action();
        stopwatch.Stop();

        Console.WriteLine($"{description}: {stopwatch.ElapsedMilliseconds:N0} ms");
        return stopwatch.Elapsed;
    }

    private void TestSimpleAlgorithm(int iterations)
    {
        for (var i = 0; i < iterations; i++)
        {
            foreach (var input in _performanceInputs)
            {
                foreach (var pattern in _performancePatterns)
                {
                    SimpleWildcardMatch(input.AsSpan(), pattern.AsSpan());
                }
            }
        }
    }

    private void TestAdvancedAlgorithm(int iterations)
    {
        for (var i = 0; i < iterations; i++)
        {
            foreach (var input in _performanceInputs)
            {
                foreach (var pattern in _performancePatterns)
                {
                    AdvancedMatchPattern(pattern.AsSpan(), input.AsSpan(), true, false);
                }
            }
        }
    }

    private void TestCachedAlgorithm(int iterations)
    {
        for (var i = 0; i < iterations; i++)
        {
            foreach (var input in _performanceInputs)
            {
                foreach (var pattern in _performancePatterns)
                {
                    CachedMatch(input, pattern);
                }
            }
        }
    }

    private void ValidateConsistency()
    {
        Console.WriteLine("\n=== 算法一致性验证 ===");
        var allConsistent = true;
        var totalTests = 0;
        var inconsistentTests = 0;

        foreach (var (input, pattern, expected) in _basicTestCases)
        {
            totalTests++;
            var simpleResult = SimpleWildcardMatch(input.AsSpan(), pattern.AsSpan());
            var advancedResult = AdvancedMatchPattern(
                pattern.AsSpan(),
                input.AsSpan(),
                true,
                false
            );
            var cachedResult = CachedMatch(input, pattern);

            if (
                simpleResult != advancedResult
                || simpleResult != cachedResult
                || simpleResult != expected
            )
            {
                Console.WriteLine($"❌ 不一致: '{input}' vs '{pattern}'");
                Console.WriteLine(
                    $"   预期: {expected}, 简单: {simpleResult}, 高级: {advancedResult}, 缓存: {cachedResult}"
                );
                allConsistent = false;
                inconsistentTests++;
            }
        }

        // 额外的随机测试
        foreach (var input in _performanceInputs.Take(4))
        {
            foreach (var pattern in _performancePatterns.Take(4))
            {
                totalTests++;
                var simpleResult = SimpleWildcardMatch(input.AsSpan(), pattern.AsSpan());
                var advancedResult = AdvancedMatchPattern(
                    pattern.AsSpan(),
                    input.AsSpan(),
                    true,
                    false
                );
                var cachedResult = CachedMatch(input, pattern);

                if (simpleResult != advancedResult || simpleResult != cachedResult)
                {
                    Console.WriteLine($"❌ 不一致: '{input}' vs '{pattern}'");
                    Console.WriteLine(
                        $"   简单: {simpleResult}, 高级: {advancedResult}, 缓存: {cachedResult}"
                    );
                    allConsistent = false;
                    inconsistentTests++;
                }
            }
        }

        Console.WriteLine($"测试总数: {totalTests}");
        Console.WriteLine($"不一致: {inconsistentTests}");
        Console.WriteLine(
            allConsistent ? "✅ 所有算法结果完全一致" : $"❌ 发现 {inconsistentTests} 个不一致的情况"
        );
    }

    #region 简单通配符算法

    private static bool SimpleWildcardMatch(ReadOnlySpan<char> input, ReadOnlySpan<char> pattern)
    {
        // 处理空字符串的特殊情况
        if (pattern.Length == 0)
        {
            return input.Length == 0;
        }

        if (input.Length == 0)
        {
            // 输入为空，只有模式全部是 '*' 才匹配
            for (var i = 0; i < pattern.Length; i++)
            {
                if (pattern[i] != '*')
                {
                    return false;
                }
            }
            return true;
        }

        var inputIndex = 0;
        var patternIndex = 0;
        var starIndex = -1;
        var match = 0;

        while (inputIndex < input.Length)
        {
            // 如果模式字符是 '?' 或者字符匹配
            if (
                patternIndex < pattern.Length
                && (
                    pattern[patternIndex] == '?'
                    || char.ToLowerInvariant(input[inputIndex])
                        == char.ToLowerInvariant(pattern[patternIndex])
                )
            )
            {
                inputIndex++;
                patternIndex++;
            }
            // 如果模式字符是 '*'
            else if (patternIndex < pattern.Length && pattern[patternIndex] == '*')
            {
                starIndex = patternIndex;
                match = inputIndex;
                patternIndex++;
            }
            // 如果之前遇到过 '*'，回溯
            else if (starIndex != -1)
            {
                patternIndex = starIndex + 1;
                match++;
                inputIndex = match;
            }
            // 不匹配
            else
            {
                return false;
            }
        }

        // 跳过模式末尾的 '*'
        while (patternIndex < pattern.Length && pattern[patternIndex] == '*')
        {
            patternIndex++;
        }

        return patternIndex == pattern.Length;
    }

    #endregion

    #region 高级状态机算法（提供的实现）

    private static bool AdvancedMatchPattern(
        ReadOnlySpan<char> expression,
        ReadOnlySpan<char> name,
        bool ignoreCase,
        bool useExtendedWildcards
    )
    {
        if (expression.Length == 0 || name.Length == 0)
        {
            return false;
        }

        if (expression[0] == '*')
        {
            if (expression.Length == 1)
            {
                return true;
            }

            ReadOnlySpan<char> expressionEnd = expression.Slice(1);

            var hasWildcards = useExtendedWildcards
                ? expressionEnd.ContainsAny("\"<>*?")
                : expressionEnd.ContainsAny('*', '?');
            if (!hasWildcards)
            {
                if (name.Length < expressionEnd.Length)
                {
                    return false;
                }

                return name.EndsWith(
                    expressionEnd,
                    ignoreCase ? StringComparison.OrdinalIgnoreCase : StringComparison.Ordinal
                );
            }
        }

        var nameOffset = 0;

        var matchCount = 1;

        var nameChar = '\0';

        scoped Span<int> temp = default;
        Span<int> currentMatches = stackalloc int[16];
        Span<int> priorMatches = stackalloc int[16];
        priorMatches[0] = 0;

        var maxState = expression.Length * 2;
        int currentState;
        var nameFinished = false;

        while (!nameFinished)
        {
            if (nameOffset < name.Length)
            {
                nameChar = name[nameOffset++];
            }
            else
            {
                if (priorMatches[matchCount - 1] == maxState)
                {
                    break;
                }

                nameFinished = true;
            }

            var priorMatch = 0;
            var currentMatch = 0;
            var priorMatchCount = 0;

            while (priorMatch < matchCount)
            {
                var expressionOffset = (priorMatches[priorMatch++] + 1) / 2;

                while (expressionOffset < expression.Length)
                {
                    currentState = expressionOffset * 2;
                    var expressionChar = expression[expressionOffset];

                    if (currentMatch >= currentMatches.Length - 2)
                    {
                        var newSize = currentMatches.Length * 2;
                        temp = new int[newSize];
                        currentMatches.CopyTo(temp);
                        currentMatches = temp;

                        temp = new int[newSize];
                        priorMatches.CopyTo(temp);
                        priorMatches = temp;
                    }

                    if (expressionChar == '*')
                    {
                        goto MatchZeroOrMore;
                    }

                    if (useExtendedWildcards && expressionChar == '<')
                    {
                        var notLastPeriod = false;
                        if (!nameFinished && nameChar == '.')
                        {
                            for (var offset = nameOffset; offset < name.Length; offset++)
                            {
                                if (name[offset] == '.')
                                {
                                    notLastPeriod = true;
                                    break;
                                }
                            }
                        }

                        if (nameFinished || nameChar != '.' || notLastPeriod)
                        {
                            goto MatchZeroOrMore;
                        }

                        goto MatchZero;
                    }

                    currentState += 2;

                    if (useExtendedWildcards && expressionChar == '>')
                    {
                        if (nameFinished || nameChar == '.')
                        {
                            goto NextExpressionCharacter;
                        }

                        currentMatches[currentMatch++] = currentState;
                        goto ExpressionFinished;
                    }

                    if (useExtendedWildcards && expressionChar == '"')
                    {
                        if (nameFinished)
                        {
                            goto NextExpressionCharacter;
                        }
                        else if (nameChar == '.')
                        {
                            currentMatches[currentMatch++] = currentState;
                        }
                        goto ExpressionFinished;
                    }

                    if (expressionChar == '\\')
                    {
                        if (++expressionOffset == expression.Length)
                        {
                            currentMatches[currentMatch++] = maxState;
                            goto ExpressionFinished;
                        }

                        currentState = expressionOffset * 2 + 2;
                        expressionChar = expression[expressionOffset];
                    }

                    if (nameFinished)
                    {
                        goto ExpressionFinished;
                    }

                    if (expressionChar == '?')
                    {
                        currentMatches[currentMatch++] = currentState;
                    }
                    else if (
                        ignoreCase
                            ? char.ToUpperInvariant(expressionChar)
                                == char.ToUpperInvariant(nameChar)
                            : expressionChar == nameChar
                    )
                    {
                        currentMatches[currentMatch++] = currentState;
                    }

                    goto ExpressionFinished;

                    MatchZeroOrMore:
                    currentMatches[currentMatch++] = currentState;
                    MatchZero:
                    currentMatches[currentMatch++] = currentState + 1;
                    NextExpressionCharacter:
                    if (++expressionOffset == expression.Length)
                    {
                        currentMatches[currentMatch++] = maxState;
                    }
                }

                ExpressionFinished:

                if ((priorMatch < matchCount) && (priorMatchCount < currentMatch))
                {
                    while (priorMatchCount < currentMatch)
                    {
                        var previousLength = priorMatches.Length;
                        while (
                            (priorMatch < previousLength)
                            && (priorMatches[priorMatch] < currentMatches[priorMatchCount])
                        )
                        {
                            priorMatch++;
                        }
                        priorMatchCount++;
                    }
                }
            }
            if (currentMatch == 0)
            {
                return false;
            }

            temp = priorMatches;
            priorMatches = currentMatches;
            currentMatches = temp;

            matchCount = currentMatch;
        }

        currentState = priorMatches[matchCount - 1];

        return currentState == maxState;
    }

    #endregion

    #region 缓存优化版本

    private static readonly ConcurrentDictionary<(string input, string pattern), bool> MatchCache =
        new();
    private const int MaxCacheSize = 10000;

    private static bool CachedMatch(string input, string pattern)
    {
        if (string.IsNullOrEmpty(input) || string.IsNullOrEmpty(pattern))
        {
            return false;
        }

        // 检查缓存
        var cacheKey = (input.ToLowerInvariant(), pattern.ToLowerInvariant());
        if (MatchCache.TryGetValue(cacheKey, out var cachedResult))
        {
            return cachedResult;
        }

        // 执行匹配
        var result = SimpleWildcardMatch(input.AsSpan(), pattern.AsSpan());

        // 缓存结果（有大小限制）
        if (MatchCache.Count < MaxCacheSize)
        {
            MatchCache.TryAdd(cacheKey, result);
        }

        return result;
    }

    #endregion
}

⚠⚠ 以下内容为AI分析的结果，请根据实际情况进行判断。

这是一个专业的通配符匹配算法性能对比测试类，用于评估不同通配符实现的性能差异。让我详细解释一下：

代码整体结构

主要目的

对比三种不同的通配符匹配算法：

简单通配符算法 - 轻量级实现
高级状态机算法 - 复杂的状态机实现
缓存优化版本 - 在简单算法基础上增加缓存

测试数据集

// 基础功能测试用例
private readonly (string input, string pattern, bool expected)[] _basicTestCases

包含各种复杂度的通配符模式：

基础通配符：*（匹配任意字符）、?（匹配单个字符）
复杂嵌套模式
边界情况（空字符串等）

// 性能测试数据 - 模拟真实场景
private readonly string[] _performanceInputs  // 文件路径、URL等
private readonly string[] _performancePatterns // 对应的匹配模式

核心测试方法

主测试方法 `CompareAlgorithmPerformance()`

预热阶段：避免JIT编译影响性能测试
性能测试：分别测试三种算法，每个执行50,000次迭代
结果分析：计算相对性能差异
一致性验证：确保三种算法返回相同结果

性能测量工具

private TimeSpan MeasureTime(Action action, string description)
{
    GC.Collect(); // 强制垃圾回收，确保测试环境一致
    // ... 计时逻辑
}

三种算法实现

1. 简单通配符算法 (`SimpleWildcardMatch`)

特点：

使用回溯策略
处理 * 和 ? 通配符
大小写不敏感
代码简洁，逻辑清晰

核心逻辑：

// 逐字符匹配，遇到 '*' 时记录回溯点
if (pattern[patternIndex] == '*') {
    starIndex = patternIndex;  // 记录星号位置
    match = inputIndex;        // 记录匹配位置
    patternIndex++;
}

2. 高级状态机算法 (`AdvancedMatchPattern`)

特点：

复杂的状态机实现
支持扩展通配符（<、>、"等）
使用状态数组跟踪所有可能的匹配状态
功能更强但复杂度更高

3. 缓存优化版本 (`CachedMatch`)

特点：

在简单算法基础上添加结果缓存
使用 ConcurrentDictionary 保证线程安全
限制缓存大小防止内存泄露
适合重复匹配相同模式的场景

private static readonly ConcurrentDictionary<(string input, string pattern), bool> MatchCache;

测试验证

功能一致性验证 (`ValidateConsistency`)

使用基础测试用例验证所有算法结果一致
随机组合性能测试数据进行额外验证
统计不一致的情况

性能对比分析

输出包括：

绝对执行时间
相对性能倍数
缓存优化效果

代码亮点

内存效率：使用 ReadOnlySpan<char> 避免字符串分配
垃圾回收控制：测试前强制GC，确保测试环境一致
预热机制：避免JIT编译影响性能测试
边界处理：妥善处理空字符串等特殊情况
线程安全：缓存版本使用并发安全的数据结构

适用场景

这个测试类适用于：

文件路径匹配
URL路由匹配
配置文件模式匹配
需要高性能通配符匹配的场景

通过这种对比测试，开发者可以根据具体需求选择最适合的通配符算法实现。

评论加载中...

代码整体结构

主要目的

测试数据集

核心测试方法

主测试方法 CompareAlgorithmPerformance()

性能测量工具

三种算法实现

1. 简单通配符算法 (SimpleWildcardMatch)

2. 高级状态机算法 (AdvancedMatchPattern)

3. 缓存优化版本 (CachedMatch)

测试验证

功能一致性验证 (ValidateConsistency)

性能对比分析

代码亮点

适用场景

主测试方法 `CompareAlgorithmPerformance()`

1. 简单通配符算法 (`SimpleWildcardMatch`)

2. 高级状态机算法 (`AdvancedMatchPattern`)

3. 缓存优化版本 (`CachedMatch`)

功能一致性验证 (`ValidateConsistency`)