4

次の形式で多数のスピンタックスを含む何千もの記事/エントリを処理することを目的としたアプリケーションを作成しています:

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

3 に答える 3

7

高速バージョン ( no Regex、 no Split、 no Substring、 no 、Replaceおよびその他の文字列操作メソッド) を実装しました。私が使用している文字列をコピーString.CopyToするには、シンボルをプレーンchar配列にコピーします。

このコードは、ネストされた Spintaxes (潜在的に無制限の深さ) を完全にサポートします。1 つの制限は、Spintax ごとのオプションの最大数です。現在は 100 ですが、1000 以上に変更できます... もう 1 つの制限は、入力文字列の最大長です。現在は 100000 ですが、増やすこともできます。

パフォーマンスに関して - 私のテストでは、このコードは、最適化された正規表現ソリューション (Jim Mischel のソリューションを含む) よりも 15 倍以上高速であり、Substring やその他の文字列操作メソッドを使用しているバージョンよりも最大 5 倍高速であることが示されました。VS 2012 の最適化コード設定を使用してリリース モードでこれをテストしました。

    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-26T23:31:15.253 に答える
4

これが非正規表現の代替手段です。

更新2012-12-27（新しいideoneデモを参照）

  1. ループ内で変数を宣言する代わりに静的メンバーを使用するようにOPのコードを最適化しRegexOptions.Compiled、andを使用し、andSubstringの代わりにTrimLeftを使用しTrimRightます。これらの最適化により、OPのコードの実行時間が33％近く短縮されます。
  2. SpinNoRE任意にネストされたスピンタックス、最適化されたコード、および追加されたコメントを処理するように更新されました。
  3. わかりやすくするために、名前をとに、それぞれに変更SpinしSpinFasterましたSpinRE。SpinNoRE
  4. ネストされた例でテストケースを更新しました。OPのコードは、ネストされたスピンタックスを処理するのにはるかに時間がかかりました（当然のことながら、ネストのすべてのレベルで追加の正規表現の一致が強制されるため）。

新しいideoneデモが利用可能です。以下のコード（コメントはデモで利用可能。リンクを参照）：

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年以上経ちます。ご容赦ください。間違いを指摘してください。）

于 2012-12-26T15:15:14.327 に答える
1

コードにいくつかの変更を加えることをお勧めします。まず、正規表現の定義をメソッドの外に移動し、RegexOptions.Compiledオプションを使用して呼び出しごとのセットアップ時間を短縮します。また、乱数ジェネレーターの作成を頻繁に使用される方法から移動します。

また、正規表現にマッチングの開始位置を指定することで、不必要な文字列検索を大幅に削減できます。これは、ループを何度も繰り返す場合に重要です。文字列の位置 M までの置換を既に行っている場合、一致がないかどうかをチェックする理由はありません。

式を次のように置き換えることで、 TrimStartandの呼び出しを削除できます。TrimEnd

String[] parts = m.Value.Substring(1, m.Value.Length-2).Split('|');

{文字列が で始まり で終わり}、途中にこれら 2 つの文字がないことはすでにわかっているので、最初と最後の文字を切り取るだけです。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;
}

とは言っても、これはネストをサポートしないため、ネストをサポートする正規表現ソリューションを作成するのはやや困難になる可能性があります。また、文字列の構築と再構築に多くの時間を費やすため、速度の点でも最適とは言えませんtext。少し考えれば、もう少し最適化できますが、SergyS が提供するような最適化されたカスタム パーサー ソリューションほど高速になることはありません。

速度が最も重要な場合は、カスタム パーサーが必要になります。正規表現バージョンはそれほど高速ではありませんが、十分に高速であれば、サイズが小さくなり、カスタム パーサーよりも理解しやすく、変更しやすいという利点があります。

于 2012-12-26T19:51:41.960 に答える