Inverse String.Replace - Schneller Weg, es zu tun?

Question

Ich habe eine Methode jedes Zeichen mit Ausnahme der angeben zu ersetzen. Zum Beispiel:

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

zurückkehren würde

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

Nun, dies ist nicht eine Instanz der vorzeitigen Optimierung. Ich nenne diese Methode schon ein paar Mal während eines Netzwerkbetrieb. Ich fand, dass auf längere Strings, es einige Latenz verursacht, und entfernt es ein wenig geholfen. Jede Hilfe, dies zu beschleunigen würde geschätzt.

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

Schluss # 's. Ich habe auch einen Testfall für eine 3K Zeichenfolge, lief anstelle von 1M bei 100K mal, wie gut jede dieser Skalen zu sehen. Die einzige Überraschung war, dass der reguläre Ausdruck ‚besser skaliert‘ als die anderen, aber es ist keine Hilfe, da es sehr langsam beginnen:

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

Update: Ich habe die Schaffung des regulären Ausdrucks für Peters Version eine statische Variable, und legen Sie es auf RegexOptions.Compiled fair zu sein:

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

Pastebin Link zu meinem Test-Code, bitte korrigieren Sie mich, wenn es falsch ist:   http: //pastebin.com/f64f260ee

Answer 1

In Ordnung, auf einem ~ 60KB String, wird dies etwa 40% schneller als die Version ausführen:

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

Der Trick ist, eine neue Zeichenfolge mit allen Ersatzzeichen zu initialisieren, da die meisten von ihnen ersetzt werden.

Answer 2

Können Sie nicht Regex.Replace verwenden wie folgt:

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

Answer 3

Ich weiß nicht, ob dies schneller sein wird, aber es vermeidet Strings newing bis nur so können sie auf den String-Builder angehängt werden, die helfen können:

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

Wenn die Anzahl der Zeichen in pattern jede Größe sein wird (was ich es in der Regel bin zu raten, nicht), könnte es zahlen, um es zu sortieren und ein Array.BinarySearch() anstelle der Array.indexOf() durchführen.

Für eine solche einfache Transformation, ich würde wetten, dass es kein Problem haben, werden schneller sein als ein regex auch.

Auch, weil Ihr Satz von Zeichen in pattern wahrscheinlich ist in der Regel aus einem String trotzdem kommen (zumindest, dass meine allgemeine Erfahrung mit dieser Art von API ist schon), warum Sie nicht die Methodensignatur haben sein:

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

oder noch besser, haben eine Überlastung wo pattern ein char[] oder string sein kann?

Answer 4

Hier ist eine andere Version für Sie. Meine Tests deuten darauf hin, dass seine Leistung ist ziemlich gut.

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

Answer 5

Der String hat eine Überlastung, die ein Zeichen und eine Zählung erfolgt, so dass Sie sich keine Zwischen Saiten erstellen, um den String hinzuzufügen. Ich bekomme etwa 20% ige Verbesserung durch diese ersetzt:

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

mit:

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

und folgt aus:

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

mit:

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

(I getestet, um den Code, den Sie sagte, war etwa viermal so schnell, und ich finde es etwa 15 mal langsamer ...)

Answer 6

Es wird O (n) sein. Sie scheinen alle Buchstaben und Leerzeichen durch * zu ersetzen, warum nicht nur testen, ob das aktuelle Zeichen ist ein Alphabet / Leerzeichen und ersetzen Sie es?