Cadena inversa. Reemplazo: ¿Una forma más rápida de hacerlo?

Question

Tengo un método para reemplazar todos los caracteres, excepto los que especifique. Por ejemplo,

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

volvería

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

Ahora, esto no es una instancia de optimización prematura. Llamo a este método varias veces durante una operación de red. Encontré que en cadenas más largas, está causando algo de latencia, y eliminarla ayudó un poco. Cualquier ayuda para acelerar esto sería apreciada.

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

Final # 's. También agregué un caso de prueba para una cadena de caracteres de 3K, se ejecutó a 100K veces en lugar de 1M para ver qué tan bien cada una de estas escalas. La única sorpresa fue que la expresión regular "escalaba mejor" que las otras, pero no sirve de nada porque, para empezar, es muy lento:

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

Actualización: hice que la creación de la expresión regular para la versión de Peter fuera una variable estática, y la configuré en RegexOptions.Compiled para ser justa:

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

Enlace de Pastebin a mi código de prueba, corríjame si es incorrecto:   http: //pastebin.com/f64f260ee

Answer 1

Muy bien, en una cadena de ~ 60KB, esto funcionará aproximadamente un 40% más rápido que tu versión:

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

El truco es inicializar una nueva cadena con todos los caracteres de reemplazo, ya que la mayoría de ellos serán reemplazados.

Answer 2

No puedes usar Regex. Reemplaza así:

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

Answer 3

No sé si esto será más rápido, pero evita agregar cadenas solo para que se puedan agregar al generador de cadenas, lo que puede ayudar:

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

Si el número de caracteres en patrón será de cualquier tamaño (que supongo que generalmente no lo hará), podría ser conveniente clasificarlo y realizar una Array.BinarySearch () en lugar de Array.indexOf () .

Para una transformación tan simple, apostaría a que no tendrá problemas para ser más rápido que una expresión regular, también.

Además, dado que es probable que su conjunto de caracteres en patrón provenga de una cadena (al menos esa ha sido mi experiencia general con este tipo de API), ¿por qué no tiene la La firma del método será:

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

¿

o mejor aún, tiene una sobrecarga donde patrón puede ser un char [] o cadena ?

Answer 4

Aquí hay otra versión para ti. Mis pruebas sugieren que su rendimiento es bastante bueno.

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

El StringBuilder tiene una sobrecarga que toma un carácter y un conteo, por lo que no tiene que crear cadenas intermedias para agregar al StringBuilder. Obtuve una mejora de alrededor del 20% al reemplazar esto:

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

con:

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

y esto:

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

con:

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

(Probé el código que dijiste que era cuatro veces más rápido, y lo encuentro unas 15 veces más lento ...)

Answer 6

Va ??a ser O (n). Parece que estás reemplazando todos los alfabetos y espacios en blanco por * , ¿por qué no probar si el carácter actual es un alfabeto / espacio en blanco y reemplazarlo?