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

本文关键字：性能 问题 正则表达式 Spintax | 更新日期: 2023-09-27 17:49:30

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

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

然而，当我用分析器运行应用程序时，我注意到处理Regex的部分占用了大量资源，我的应用程序最终由于内存不足而崩溃。谁能建议一种方法来改进我的代码或更好的方法来解析自旋税?

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;
  }

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

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

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

关于性能-我的测试表明这段代码比任何优化的Regex解决方案(包括吉姆米歇尔的一个)快>15倍，比使用Substring和其他字符串操作方法的版本快~5倍。我已经在vs2012中使用优化代码设置的发布模式下进行了测试。

    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;
    }

这里有一个非正则表达式的替代。

更新2012-12-27(参见新的ideone演示)

    优化OP的代码，使用静态成员而不是在循环中声明变量，使用RegexOptions.Compiled，使用Substring而不是TrimLeft和TrimRight。这些优化将OP代码的执行时间减少了近33%。
  1. 更新SpinNoRE以处理任意嵌套的自旋税，优化代码，并添加注释。
  2. 为了清晰，将Spin和SpinFaster分别改名为SpinRE和SpinNoRE。
    3. 更新的测试用例与嵌套的例子。OP的代码在处理嵌套的自旋税时要慢得多(可以理解，因为每一级嵌套都强制进行额外的正则表达式匹配)。

新的ideone演示可用;代码如下(demo中有注释;见链接):

public static String SpinNoRE(String text)
{
    int i, j, e = -1;
    char[] curls = new char[] {'{', '}'};
    text += '~';
    do
    {
        i =  e;
        e = -1;
        while ((i = text.IndexOf('{', i+1)) != -1)
        {
            j = i;
            while ((j = text.IndexOfAny(curls, j+1)) != -1 && text[j] != '}')
            {
                if (e == -1) e = i;
                i = j;
            }
            if (j != -1)
            {
                parts = text.Substring(i+1, (j-1)-(i+1-1)).Split('|');
                text = text.Remove(i, j-(i-1)).Insert(i, parts[rand.Next(parts.Length)]);
            }
        }
    }
    while (e-- != -1);
    return text.Remove(text.Length-1);
}
结果:

Input Text:       Oh! {{I'm|You're} here!|How are you{ doing{|, {buddy|pal|guy}}|}?}
Testing SpinRE:   Oh! You're here!
Testing SpinRE:   Oh! How are you doing?
Testing SpinRE:   Oh! How are you?
Testing SpinRE:   Oh! How are you doing, buddy?
Testing SpinRE:   Oh! I'm here!
Testing SpinRE:   Oh! How are you doing, guy?
Testing SpinRE:   Oh! How are you doing?
Testing SpinRE:   Oh! I'm here!
Testing SpinRE:   Oh! I'm here!
Testing SpinRE:   Oh! How are you doing?
Testing SpinNoRE: Oh! How are you doing, buddy?
Testing SpinNoRE: Oh! You're here!
Testing SpinNoRE: Oh! How are you?
Testing SpinNoRE: Oh! How are you?
Testing SpinNoRE: Oh! You're here!
Testing SpinNoRE: Oh! I'm here!
Testing SpinNoRE: Oh! How are you doing?
Testing SpinNoRE: Oh! How are you?
Testing SpinNoRE: Oh! How are you doing, buddy?
Testing SpinNoRE: Oh! I'm here!
Time elapsed over 100,000 runs of each in alternation:
SpinRE:           03.686s
SpinNoRE:         00.921s
我接触c#已经6年多了。如有错误，请见谅并指出。

我建议对您的代码进行一些更改。首先，将正则表达式定义移出方法并使用RegexOptions.Compiled选项来减少每次调用的设置时间。另外，将随机数生成器的创建从频繁使用的方法中移出。

还可以通过告诉正则表达式从哪里开始匹配来消除很多不必要的字符串搜索。如果要对循环进行多次迭代，这一点很重要。这个想法是，如果你已经完成了字符串中位置M的替换，就没有理由检查匹配，因为不会有任何匹配。

您可以通过将表达式替换为:

来消除对TrimStart和TrimEnd的调用:
String[] parts = m.Value.Substring(1, m.Value.Length-2).Split('|');

您已经知道字符串以{开始，以}结束，并且中间没有这两个字符中的任何一个，因此您所要做的就是切断第一个和最后一个字符。没有理由产生TrimStart和TrimEnd创建的临时字符串的开销。

另一种可能性是在正则表达式中添加捕获组(在要捕获的部分周围放置括号)，并对捕获的文本而不是整个匹配的表达式进行操作。

把所有这些建议放在一起会导致:

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

也就是说，这将不支持嵌套，并且制作一个支持嵌套的regex解决方案可能有些困难。在速度方面，它也不是最优的，因为它花费了大量的时间来构建和重建text字符串。稍微考虑一下，您可以对其进行更多的优化，但它永远不会像SergyS提供的优化自定义解析器解决方案那样快。

如果速度是最重要的，那么您将需要一个自定义解析器。regex版本不会那么快，但如果它足够快，它的好处是比自定义解析器更小，更容易理解和修改。

相关文章：