Inverse String.Replace-より高速な方法？

StackOverflow https://stackoverflow.com/questions/826370

質問

指定した文字以外のすべての文字を置き換える方法があります。たとえば、

ReplaceNot("test. stop; or, not", ".;/\\".ToCharArray(), '*');

返されます

"****.*****;***,****".

現在、これは時期尚早な最適化のインスタンスではありません。ネットワーク操作中にこのメソッドを何度も呼び出します。長い文字列では、レイテンシーが発生することがわかったため、削除すると少し役立ちました。これをスピードアップするための助けをいただければ幸いです。

    public static string ReplaceNot(this string original, char[] pattern, char replacement)
    {           
        int index = 0;
        int old = -1;

        StringBuilder sb = new StringBuilder(original.Length);

        while ((index = original.IndexOfAny(pattern, index)) > -1)
        {
            sb.Append(new string(replacement, index - old - 1));
            sb.Append(original[index]);
            old = index++;
        }

        if (original.Length - old > 1)
        {
            sb.Append(new string(replacement, original.Length - (old + 1)));
        }

        return sb.ToString();
    }

最終番号。また、3Kの文字列のテストケースを追加し、1Mではなく100Kで実行して、これらの各スケールがどれだけ適切かを確認しました。唯一の驚きは、正規表現が他の表現よりも「スケーリングが良い」ということでしたが、最初は非常に遅いため、助けにはなりません。

User            Short * 1M  Long * 100K     Scale
John            319             2125            6.66
Luke            360             2659            7.39
Guffa           409             2827            6.91
Mine            447             3372            7.54
DirkGently      1094            9134            8.35
Michael         1591            12785           8.04
Peter           21106           94386           4.47

更新：Peterのバージョンの正規表現の作成を静的変数にし、それをRegexOptions.Compiledに設定して公平にしました：

User            Short * 1M      Long * 100K     Scale
Peter           8997            74715           8.30

テストコードへのペーストビンリンク。間違っている場合は修正してください。   http： //pastebin.com/f64f260ee

役に立ちましたか？

解決

さて、〜60KBの文字列では、これはあなたのバージョンよりも約40％高速です：

public static string ReplaceNot(this string original, char[] pattern, char replacement)
{
    int index = 0;

    StringBuilder sb = new StringBuilder(new string(replacement, original.Length));

    while ((index = original.IndexOfAny(pattern, index)) > -1)
    {
        sb[index] = original[index++];
    }

    return sb.ToString();
}

トリックは、ほとんどの文字が置換されるため、すべての置換文字で新しい文字列を初期化することです。

他のヒント

Regex.Replaceは次のように使用できません：

Regex regex = new Regex(@"[^.;/\\]");
string s = regex.Replace("test. stop; or, not", "*");

これがもっと速くなるかどうかはわかりませんが、文字列ビルダーに追加できるように文字列を更新することは避けられます。

    public static string ReplaceNot(this string original, char[] pattern, char replacement)
    {
        StringBuilder sb = new StringBuilder(original.Length);

        foreach (char ch in original) {
            if (Array.IndexOf( pattern, ch) >= 0) {
                sb.Append( ch);
            }
            else {
                sb.Append( replacement);
            }
        }

        return sb.ToString();
    }

pattern の文字数が任意のサイズになる場合（通常はそうならないでしょう）、ソートして Array.BinarySearch （） Array.indexOf（）の代わりに。

このような単純な変換の場合、正規表現よりも高速であることにも問題はないと思います。

また、 pattern の文字セットは通常とにかく文字列に由来する可能性が高いため（少なくとも、このタイプのAPIでの私の一般的な経験です）、なぜメソッドシグネチャ：

public static string ReplaceNot(this string original, string pattern, char replacement)

さらに良いことに、 pattern が char [] または string になるオーバーロードがありますか？

これは別のバージョンです。私のテストでは、パフォーマンスがかなり良いことが示唆されています。

public static string ReplaceNot(
    this string original, char[] pattern, char replacement)
{
    char[] buffer = new char[original.Length];

    for (int i = 0; i < buffer.Length; i++)
    {
        bool replace = true;

        for (int j = 0; j < pattern.Length; j++)
        {
            if (original[i] == pattern[j])
            {
                replace = false;
                break;
            }
        }

        buffer[i] = replace ? replacement : original[i];
    }

    return new string(buffer);
}

StringBuilderには、文字とカウントを受け取るオーバーロードがあるため、StringBuilderに追加するために中間文字列を作成する必要はありません。これを置き換えると、約20％改善されます。

sb.Append(new string(replacement, index - old - 1));

with：

sb.Append(replacement, index - old - 1);

そしてこれ：

sb.Append(new string(replacement, original.Length - (old + 1)));

with：

sb.Append(replacement, original.Length - (old + 1));

（あなたが言ったコードを約4倍高速にテストしましたが、約15倍遅いことがわかりました...）

O（n）になります。すべてのアルファベットと空白を * に置き換えているように見えますが、現在の文字がアルファベット/空白かどうかをテストして置き換えてみませんか？

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top