C#如何优化遍历400万条数据的List<string>快速过滤用户输入字符串

原代码性能瓶颈 #

• 遍历400万条模式串逐次对message做扫描，每一次Contains和Replace操作都需要完整遍历一次message字符串，时间复杂度为O(k*n)（k为模式串数量，n为message长度），计算开销极高
• 多次Replace会生成大量临时字符串，额外增加GC压力

核心优化方案：使用Aho-Corasick多模式匹配算法 #

该算法专门针对「单文本匹配大量模式串」的场景设计，仅需1次遍历文本即可找出所有匹配的模式串，时间复杂度降低到O(n + m + z)，其中n是文本长度，m是所有模式串的总字符数，z是匹配结果数量，完全不受400万模式串量级的制约。

实现要点 #

• 因为excludes是静态全局变量，仅需在程序启动时一次性构建AC自动机，预处理开销只会产生一次，不会平摊到每次message处理逻辑中
• 预处理阶段先对excludes做去重，避免重复加载相同模式串浪费资源
• 匹配到所有需要删除的子串后，一次性遍历message拼接出最终结果，避免多次Replace生成临时字符串

示例实现代码 #

// AC自动机节点定义
public class AcNode
{
    public Dictionary<char, AcNode> Children { get; } = new();
    public string? Pattern { get; set; }
    public AcNode? Fail { get; set; }
}

// 静态预处理构建自动机，程序生命周期内仅执行一次
private static AcNode BuildAcAutomaton(List<string> excludes)
{
    var root = new AcNode();
    // 先去重，过滤空字符串
    foreach (var pattern in excludes.Distinct().Where(p=>!string.IsNullOrEmpty(p)))
    {
        var current = root;
        foreach (var c in pattern)
        {
            if (!current.Children.TryGetValue(c, out var next))
            {
                next = new AcNode();
                current.Children[c] = next;
            }
            current = next;
        }
        current.Pattern = pattern;
    }
    // BFS构建失败指针
    var queue = new Queue<AcNode>();
    foreach (var child in root.Children.Values)
    {
        child.Fail = root;
        queue.Enqueue(child);
    }
    while (queue.Count > 0)
    {
        var current = queue.Dequeue();
        foreach (var (c, child) in current.Children)
        {
            var failNode = current.Fail;
            while (failNode != null && !failNode.Children.ContainsKey(c))
            {
                failNode = failNode.Fail;
            }
            child.Fail = failNode?.Children.GetValueOrDefault(c) ?? root;
            queue.Enqueue(child);
        }
    }
    return root;
}

// 静态资源初始化
private static readonly List<string> excludes = new List<string>(4000000);
private static readonly AcNode _acRoot = BuildAcAutomaton(excludes);

// 业务逻辑调用的核心处理方法
public string ProcessMessage(string message)
{
    var matches = new List<(int Start, int Length)>();
    var current = _acRoot;
    // 单次遍历message收集所有匹配项
    for (int i = 0; i < message.Length; i++)
    {
        var c = message[i];
        while (current != _acRoot && !current.Children.ContainsKey(c))
        {
            current = current.Fail;
        }
        if (current.Children.TryGetValue(c, out var next))
        {
            current = next;
        }
        // 递归收集失败指针链上的所有匹配
        var temp = current;
        while (temp != _acRoot)
        {
            if (temp.Pattern != null)
            {
                matches.Add((i - temp.Pattern.Length + 1, temp.Pattern.Length));
            }
            temp = temp.Fail;
        }
    }
    // 无匹配直接返回原字符串
    if (matches.Count == 0) return message;
    // 合并重叠匹配区间，构建结果
    matches.Sort((a, b) => a.Start.CompareTo(b.Start));
    var sb = new StringBuilder(message.Length);
    int lastPos = 0;
    foreach (var match in matches)
    {
        if (match.Start >= lastPos)
        {
            sb.Append(message.AsSpan(lastPos, match.Start - lastPos));
            lastPos = match.Start + match.Length;
        }
        else if (match.Start + match.Length > lastPos)
        {
            lastPos = match.Start + match.Length;
        }
    }
    sb.Append(message.AsSpan(lastPos));
    return sb.ToString();
}

可叠加的补充优化点 #

• 如果业务允许，可提前过滤长度大于当前message的模式串，无需加入自动机匹配
• 若业务要求不区分大小写，可在预处理和匹配阶段统一转小写/大写，避免大小写匹配的额外开销
• 若excludes存在大量前缀相同的字符串，AC自动机的前缀树结构会自动合并冗余，进一步降低内存和匹配开销

内容的提问来源于stack exchange，提问作者Persson