Inverse String.Replace - Un modo più veloce di farlo?

Question

Ho un metodo per sostituire ogni carattere tranne quelli che specifico. Ad esempio,

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

ritornerebbe

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

Ora, questa non è un'istanza di ottimizzazione prematura. Questo metodo lo chiamo parecchie volte durante un'operazione di rete. Ho scoperto che su stringhe più lunghe, sta causando un po 'di latenza e rimuoverlo ha aiutato un po'. Qualsiasi aiuto per accelerare questo sarebbe apprezzato.

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

N. finale. Ho anche aggiunto un caso di test per una stringa di caratteri 3K, eseguito a 100K volte anziché 1M per vedere quanto bene ciascuna di queste scale. L'unica sorpresa è stata che l'espressione regolare "è migliorata in scala" rispetto alle altre, ma non è di aiuto poiché è molto lento all'inizio:

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

Aggiornamento: ho reso la creazione dell'espressione regolare per la versione di Peter una variabile statica e l'ho impostata su RegexOptions.Compilata per essere corretta:

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

Link Pastebin al mio codice di test, per favore correggimi se è sbagliato:   http: //pastebin.com/f64f260ee

Answer 1

Bene, su una stringa di ~ 60 KB, questo funzionerà circa il 40% più veloce della tua versione:

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

Il trucco è inizializzare una nuova stringa con tutti i caratteri sostitutivi, poiché la maggior parte di essi verrà sostituita.

Answer 2

Non puoi usare Regex. Sostituisci così:

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

Answer 3

Non so se sarà più veloce, ma evita di rinnovare le stringhe solo in modo che possano essere aggiunte al generatore di stringhe, il che può aiutare:

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

Se il numero di caratteri nel modello sarà di qualsiasi dimensione (cosa che suppongo che generalmente non lo farà), potrebbe pagare per ordinarlo ed eseguire un Array.BinarySearch () anziché Array.indexOf () .

Per una trasformazione così semplice, scommetto che non avrà problemi a essere più veloce di una regex.

Inoltre, poiché il tuo set di caratteri in pattern probabilmente proviene comunque da una stringa (almeno questa è stata la mia esperienza generale con questo tipo di API), perché non hai il la firma del metodo è:

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

o meglio ancora, hai un sovraccarico in cui pattern può essere un char [] o string ?

Answer 4

Ecco un'altra versione per te. I miei test suggeriscono che le sue prestazioni sono piuttosto buone.

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

StringBuilder ha un sovraccarico che richiede un carattere e un conteggio, quindi non è necessario creare stringhe intermedie da aggiungere a StringBuilder. Ottengo circa il 20% di miglioramento sostituendo questo:

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

con:

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

e questo:

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

con:

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

(Ho testato il codice che hai detto era circa quattro volte più veloce e lo trovo circa 15 volte più lento ...)

Answer 6

Sarà O (n). Sembra che tu stia sostituendo tutti gli alfabeti e gli spazi bianchi con * , perché non provare semplicemente se il carattere corrente è un alfabeto / spazio bianco e sostituirlo?