Inverse String.Replace - Une façon plus rapide de le faire?

Question

J'ai une méthode pour remplacer tous les caractères sauf ceux que je spécifie. Par exemple,

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

reviendrait

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

Ce n’est pas une instance d’optimisation prématurée. J'appelle cette méthode plusieurs fois au cours d'une opération réseau. J'ai constaté que sur les chaînes plus longues, cela causait une certaine latence, et le supprimer aidait un peu. Toute aide pour accélérer ce processus serait appréciée.

    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 ° final. J'ai également ajouté un scénario de test pour une chaîne de caractères de 3K, exécuté à 100K fois au lieu de 1M, pour voir à quel point chacune de ces échelles était performante. La seule surprise a été que l'expression régulière était "plus efficace" que les autres, mais ce n'est pas une aide, car elle est très lente au début:

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

Mise à jour: j'ai créé la variable statique de la création de l'expression régulière pour la version de Peter et je l'ai définie sur RegexOptions.Compiled pour être juste:

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

Pastebin lien vers mon code de test, corrigez-moi s'il est faux:   http: //pastebin.com/f64f260ee

Answer 1

D'accord, sur une chaîne d'environ 60 Ko, cela fonctionnera environ 40% plus vite que votre version:

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

L'astuce consiste à initialiser une nouvelle chaîne avec tous les caractères de remplacement, car la plupart d'entre eux seront remplacés.

Answer 2

Ne pouvez-vous pas utiliser Regex.Replace comme suit:

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

Answer 3

Je ne sais pas si ce sera plus rapide, mais cela évite de créer des chaînes juste pour qu'elles puissent être ajoutées au constructeur de chaînes, ce qui peut aider:

    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 le nombre de caractères dans le motif a une taille quelconque (ce que je suppose, ce ne sera généralement pas le cas), il pourrait être rentable de le trier et d'effectuer un Array.BinarySearch () au lieu de Array.indexOf () .

Pour une transformation aussi simple, je parierais qu’elle n’aurait aucun problème à être plus rapide qu’une expression régulière.

De plus, puisque vos jeux de caractères pattern sont susceptibles de provenir de toute façon d'une chaîne (en tout cas, c'est mon expérience générale avec ce type d'API), pourquoi n'avez-vous pas la signature de la méthode être:

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

ou mieux encore, avez une surcharge où motif peut être un char [] ou une chaîne ?

Answer 4

Voici une autre version pour vous. Mes tests suggèrent que ses performances sont plutôt bonnes.

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 a une surcharge qui prend un caractère et un nombre, vous n'avez donc pas besoin de créer de chaînes intermédiaires à ajouter au StringBuilder. J'obtiens environ 20% d'amélioration en remplaçant ceci:

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

avec:

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

et ceci:

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

avec:

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

(J'ai testé le code que vous avez dit être environ quatre fois plus rapide, et je le trouve environ 15 fois plus lent ...)

Answer 6

Ça va être O (n). Vous semblez remplacer tous les alphabets et les espaces par * , pourquoi ne pas simplement vérifier si le caractère actuel est un alphabet / espace et le remplacer?