Inverse String.Replace - maneira mais rápida de fazê-lo?

Question

Eu tenho um método para substituir todos os personagens, exceto aqueles que eu especificar. Por exemplo,

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

voltaria

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

Agora, isso não é uma instância de otimização prematura. Eu chamo este método algumas vezes durante uma operação de rede. Descobri que em cordas mais longas, ele está causando alguns latência, e removê-lo ajudado um pouco. Qualquer ajuda de acelerar isso seria 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. Eu também adicionei um caso de teste para uma 3K cadeia de caracteres, correu para 100K vezes em vez de 1M para ver quão bem cada uma dessas escalas. A única surpresa foi que a expressão regular 'escalado melhor' do que os outros, mas não é nenhuma ajuda, uma vez que é muito lento para começar com:

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: Eu fiz a criação da expressão regular para a versão de Peter uma variável estática, e configurá-lo para RegexOptions.Compiled para ser justo:

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

link Pastebin ao meu código de teste, por favor, corrija-me se estiver errado: http: //pastebin.com/f64f260ee

Answer 1

Tudo bem, em uma corda ~ 60KB, este irá executar cerca de 40% mais rápido do que a sua versão:

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

O truque é para inicializar uma nova string com todos os caracteres de substituição, uma vez que a maioria deles vai ser substituído.

Answer 2

Você não pode usar Regex.Replace assim:

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

Answer 3

Eu não sei se isso vai ser mais rápido, mas evita Newing-se cordas apenas para que possam ser anexados ao construtor corda, o que pode ajudar:

    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 o número de caracteres em pattern vai ser de qualquer tamanho (que eu estou supondo que geralmente não), pode pagar para classificá-lo e realizar uma Array.BinarySearch() vez do Array.indexOf().

Para uma transformação tão simples, eu aposto que ele não terá nenhum problema de ser mais rápido que um regex também.

Além disso, desde o seu conjunto de caracteres em pattern é provável que geralmente vêm de uma seqüência de qualquer maneira (pelo menos essa tem sido a minha experiência geral com este tipo de API), por que você não tem a assinatura do método ser:

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

ou melhor ainda, tem uma sobrecarga onde pattern pode ser um char[] ou string?

Answer 4

Aqui está uma outra versão para você. Meus testes sugerem que seu desempenho é muito bom.

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

O StringBuilder tem uma sobrecarga que leva um personagem e uma contagem, para que você não tem que criar cadeias de intermediários para adicionar ao StringBuilder. Eu recebo cerca de 20% de melhoria, substituindo o seguinte:

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

com:

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

e este:

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

com:

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

(Eu testei o código que você disse foi cerca de quatro vezes mais rápido, e acho que é cerca de 15 vezes mais lenta ...)

Answer 6

Ele vai ser O (n). Você parece estar substituindo todos os alfabetos e espaços em branco por *, porque não basta teste se o personagem atual é um alfabeto / espaço em branco e substituí-lo?