c# - Spintax 解析器的正则表达式匹配性能问题

Question

我正在编写一个应用程序，旨在处理具有以下格式的大量 spintax 的数千篇文章/条目:

{Hello|Hi} {World|There!}, how are you?

但是，当我使用探查器运行应用程序时，我注意到处理 Regex 的部分占用了大量资源，我的应用程序最终因内存不足问题而崩溃。谁能建议改进我的代码的方法或更好的解析 spintax 的方法？

public static String Spin(String text)
{
        Regex reg = new Regex(@"\{[^\{\}]*\}");
        Random rand = new Random((int)DateTime.Now.Ticks);
        while (true)
        {
            Match m = reg.Match(text);
            if (!m.Success) break;
            String[] parts = m.Value.TrimStart('{').TrimEnd('}').Split('|');
            int i = rand.Next(parts.Length);
            text = text.Substring(0, m.Index) + parts[i] + text.Substring(m.Index + m.Length);
        }
        return text;
  }

Answer 1

我已经实现了我的快速版本(没有 Regex，没有 Split，没有 Substring，没有 Replace 和其他字符串操作方法)。要复制字符串，我使用 String.CopyTo 将符号复制到普通 char 数组。

此代码完全支持嵌套的 Spintaxes(可能无限深度)。一个限制是每个 Spintax 的最大选项数，目前是 100，但可以更改为 1000 或更多...另一个限制是输入字符串的最大长度，现在是 100000，但也可以增加。

关于性能——我的测试表明这段代码比任何优化的 Regex 解决方案(包括 Jim Mischel 的解决方案)快 15 倍以上，比使用 Substring 和其他字符串操作方法的版本快 ~5 倍。我已经在 VS 2012 中使用优化代码设置在 Release模式下对此进行了测试。

    static int[] partIndices = new int[100];
    static int[] depth = new int[100];
    static char[] symbolsOfTextProcessed = new char[100000];

    public static String SpinEvenMoreFaster(String text)
    {
        int cur = SpinEvenMoreFasterInner(text, 0, text.Length, 0);
        return new String(symbolsOfTextProcessed, 0, cur);
    }

    public static int SpinEvenMoreFasterInner(String text, int start, int end, int symbolIndex)
    {
        int last = start;
        for (int i = start; i < end; i++)
        {
            if (text[i] == '{')
            {
                int k = 1;
                int j = i + 1;
                int index = 0;
                partIndices[0] = i;
                depth[0] = 1;
                for (; j < end && k > 0; j++)
                {
                    if (text[j] == '{')
                        k++;
                    else if (text[j] == '}')
                        k--;
                    else if (text[j] == '|')
                    {
                        if (k == 1)
                        {
                            partIndices[++index] = j;
                            depth[index] = 1;
                        }
                        else
                            depth[index] = k;
                    }
                }
                if (k == 0)
                {
                    partIndices[++index] = j - 1;
                    int part = rand.Next(index);
                    text.CopyTo(last, symbolsOfTextProcessed, symbolIndex, i - last);
                    symbolIndex += i - last;
                    if (depth[part] == 1)
                    {
                        text.CopyTo(partIndices[part] + 1, symbolsOfTextProcessed, symbolIndex, partIndices[part + 1] - partIndices[part] - 1);
                        symbolIndex += partIndices[part + 1] - partIndices[part] - 1;
                    }
                    else
                    {
                        symbolIndex = SpinEvenMoreFasterInner(text, partIndices[part] + 1, partIndices[part + 1], symbolIndex);
                    }
                    i = j - 1;
                    last = j;
                }
            }
        }
        text.CopyTo(last, symbolsOfTextProcessed, symbolIndex, end - last);
        return symbolIndex + end - last;
    }