Discussion :

[Eric80]

Bonjour,

A la recherche d'une méthode pour supprimer les accents d'une chaine de caractère afin de faciliter la comparaison entre 2 chaînes, j'ai implémenter plusieurs solutions et me suis intéressé aux performances.

Comme j'ai relevé des différences notables entre ces solutions et entre les versions du Framework, je me suis dit que cela pourrait interesser d'autres développeurs

Voici le code que j'utilise en boucle (> 40000 itérations) et plusieurs fois dans une autre methode pour comparer les resultats.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
       public static string RemoveDiacritics(string inputString)
        {
            string result = inputString.Trim().ToLower();
            // nothing: algo takes 2,06 s
            //string res0 = result;
            // Method1: String.Replace   -> 2,28s 
            //string res1 = RemoveDiacriticsStringReplace(result);
            // Method2: char replace + string builder -> 2,25s
            //string res2 = RemoveDiacriticsCharReplace(result);
            // Method3: Regex.Replace -> 5,8 s -> 2 times slower
            //string res3 = RemoveDiacriticsRegex(result);
            // Method4, need .NET 2.0: normalization -> 2,28 s
            string res4 = RemoveDiacriticsNormalizationDotNet2(result);
            //Debug.Assert(res1 == res2 && res1 == res3 && res1 == res4 && res2 == res3 && res2 == res4 && res3 == res4);
            return res4;
        }

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
        public static string RemoveDiacriticsStringReplace(string inputString)
        {
            string result = inputString;
            result = result.Replace('à', 'a');
            result = result.Replace('á', 'a');
            result = result.Replace('ä', 'a');
            result = result.Replace('â', 'a');
            result = result.Replace('ã', 'a');
            result = result.Replace('å', 'a');
            result = result.Replace('é', 'e');
            result = result.Replace('è', 'e');
            result = result.Replace('ê', 'e');
            result = result.Replace('ë', 'e');
            result = result.Replace('ì', 'i');
            result = result.Replace('í', 'i');
            result = result.Replace('ï', 'i');
            result = result.Replace('î', 'i');
            result = result.Replace('ò', 'o');
            result = result.Replace('ó', 'o');
            result = result.Replace('ô', 'o');
            result = result.Replace('ö', 'o');
            result = result.Replace('û', 'u');
            result = result.Replace('ü', 'u');
            result = result.Replace('ù', 'u');
            result = result.Replace('ú', 'u');
            result = result.Replace('ý', 'y');
            result = result.Replace('ÿ', 'y');
            result = result.Replace('ç', 'c');
            result = result.Replace('ñ', 'n');            
            return result;
        }

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
        public static string RemoveDiacriticsCharReplace(string inputString)
        {
            string result;
            StringBuilder builder = new StringBuilder();
            char[] car = inputString.ToCharArray();
            foreach (char c in car)
            {
                if (c == 'ä' || c == 'á' || c == 'à' || c == 'â' || c == 'ã' || c == 'å')
                    builder.Append('a');
                else if (c == 'é' || c == 'è' || c == 'ê' || c == 'ë')
                    builder.Append('e');
                else if (c == 'ì' || c == 'í' || c == 'ï' || c == 'î')
                    builder.Append('i');
                else if (c == 'ò' || c == 'ó' || c == 'ô' || c == 'ö')
                    builder.Append('o');
                else if (c == 'ù' || c == 'ú' || c == 'ü' || c == 'û')
                    builder.Append('u');
                else if (c == 'ÿ' || c == 'ý')
                    builder.Append('y');
                else if (c == 'ç')
                    builder.Append('c');
                else if (c == 'ñ')
                    builder.Append('n');
                else builder.Append(c);
            }
            result = builder.ToString();
            return result;
        }

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
        public static string RemoveDiacriticsRegex(string inputString)
        {
            string result = inputString;
            result = System.Text.RegularExpressions.Regex.Replace(result, @"(à|á|ä|â|ã|å)+", "a");
            result = System.Text.RegularExpressions.Regex.Replace(result, @"(é|è|ê|ë)+", "e");
            result = System.Text.RegularExpressions.Regex.Replace(result, @"(ì|í|ï|î)+", "i");
            result = System.Text.RegularExpressions.Regex.Replace(result, @"(ò|ó|ö|ô)+", "o");
            result = System.Text.RegularExpressions.Regex.Replace(result, @"(ü|û|ù|ú)+", "u");
            result = System.Text.RegularExpressions.Regex.Replace(result, @"(ÿ|ý)+", "y");
            result = System.Text.RegularExpressions.Regex.Replace(result, @"(ç)+", "c");
            result = System.Text.RegularExpressions.Regex.Replace(result, @"(ñ)+", "n");
            return result;
        }

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
        public static string RemoveDiacriticsNormalizationDotNet2(string inputString)
        {
            string result = inputString;
            String normalizedString = result.Normalize(NormalizationForm.FormD);
            StringBuilder stringBuilder = new StringBuilder();
            for (int i = 0; i < normalizedString.Length; i++)
            {
                Char c = normalizedString[i];
                if (CharUnicodeInfo.GetUnicodeCategory(c) != UnicodeCategory.NonSpacingMark)
                    stringBuilder.Append(c);
            }
            result = stringBuilder.ToString();
            return result;
        }

Et voici les résultats en temps d'exécution (secondes): j'ai juste changé les commentaires dans ma méthode principale RemoveDiacritics.
Et j'ai compilé mon code sous VS2003 aussi bien que sous VS2005.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
                .net2     .net1.1
rien            2,06      1,85
string replace  2,28      2,41      
char replace    2,25      2,15
regex           5,8      22 !!
normalization   2,28      n/a

J'ai lancé chq test 4-5 fois et fait la moyenne ici.

Deux points particulièrement intéressant concernant les Regex:
1) c'est plus lent que des simples Replace
2) cela a été drolement bien amélioré dans le .NET 2.0 !
-> les regex sont 2 fois plus lentes que des replaces en .NET 2.0 mais 10 fois plus lentes en 1.1!

Petite remarque sur mes regex: elles ne sont pas tout à fait correctes puisqu'elles remplacent par ex un "éé" en "e" au lieu de "ee".

Enfin, la seule méthode qui soit complète est celle utilisant les classes Normalization et CharUnicodeInfo. Les autres sont du manuels où j'ai mis seulement les élements nécessaires (via mon Assert).

Que dites vous de tels résultats? Impressionnants qd meme, non?

[Jérôme Lambert]

Pour Regex, je m'y attendais à ce que ce soit 2 fois plus lent qu'un simple String. Mais la différence avec la version 1 du Framework me surprend et me choque énormément

En tout cas, très bonne idée d'avoir pris la peine de faire de tels tests sur ce point.

[Mose]

Très bonne idée ce test.
Mais la chaîne d'entrée est-elle aléatoire ?

Note : Pas très étonné pour les Regex, quand on sait comment c'est implémenté derrière.
Pour info, si tu utilises plusieurs fois la même Regex, tu peux spécifier l'option Compiled pour aller plus vite (ça évite de refaire à chaque fois l'étape de parsing de ta regex)

[Eric80]

en fait, cette méthode fait partie d'un algorithme de filtrage (recherche de doublons) à partir d'une liste multi colonne de environ 44000 lignes, donc je parcourre plusieurs fois la listes et compare les string des colonnes sélectionnées.

j'avais commencé par un programme .NET 1.1 qui recherchait pour chq ligne les redondances dans toutes les autres lignes, mais cela prennait trop de temps (dans les 5-6 min), et ai donc optimisé drastiquement en triant au préalable ma liste afin de chercher que dans les lignes suivantes tant que les valeurs sont égales. C'est là que j'obtiens ds les 2 sec de temps d'exécution.

Ensuite, j'ai implémenté cette méthode de suppression des accents pour rechercher plus de doublons. A vrai dire, j'ai d'abord trouvé sur des blogs la méthode dotnet 2.0, et ai donc exporté ma solution vers vs2005, mais comme j'avais des petits soucis ds certains cas avec ma gestion multithreads, je suis repassé au 1.1.
J'ai alors commencé par utiliser les regex pour avoir du code concis, mais vu le temps d'exécution, je me suis intéressé aux simples replace. Et c'est seulement ds un deuxieme temps que j'ai eu la curiosité de tester les memes algo ds ma solution .NET 2.0, et c'est en effet la différence entre les 2 Framework qui m'a le + impressionné et motivé pour poster ici.

Au final, je suis resté avec la methode de normalisation en .NET 2.0 et avec le char.Replace en 1.1: les regex ici ne font que ralentir le tout.

Tout cela pour dire que la chaîne d'entrée n'est donc pas du tout aléatoire puisque issue d'une liste triée.

C'est quoi l'option Compiled dont du parles?

[StormimOn]

Désolé pour ce petit hors sujet, mais j'utilise la méthode suivante pour supprimer les accents.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
string str = "àâäéèêëîïôöùûü";
byte[] tab = System.Text.Encoding.GetEncoding(1251).GetBytes(str);
string result = System.Text.Encoding.ASCII.GetString(tab);

Elle me donne entière satisfaction (pour des langues autres que le français je ne sais pas, mais en français aucun problème) et j'aurai bien voulu savoir s'il était possible d'avoir les performances de cette méthode dans le même cadre que les tests précédents

[Mose]

C'est quoi l'option Compiled dont du parles?

RegexOptions.Compiled
Un paramètre de l'objet Regex.

[theMonz31]

en utilisant une chaine bateau de 60 caractères, avec le code suivant, ca met
190 millisecondes... record à battre ?

The Monz, Toulouse

Le code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
        private void button1_Click(object sender, EventArgs e)
        {
            Stopwatch clock = new Stopwatch();
            string str = "à la claîre fontaîne l'élève à fait de grâve erreur où pas ?";
            clock.Start();
            for (int i = 0; i < 40000; i++)
            {
                Method(str);
            }
 
            clock.Stop();
            MessageBox.Show(clock.ElapsedMilliseconds.ToString());
 
        }
 
        private string Method(String str)
        {
            byte[] tab = System.Text.Encoding.GetEncoding(1251).GetBytes(str);
            return (System.Text.Encoding.ASCII.GetString(tab));
        }

Test sur PIV 2.4 Ghz 1Go de Ram, windows XP SP2. Framework 2.0

(c'était pour pouvoir comparer car à proc équivalent... ca serait mieux)

EDIT : en mettant la methode en static plutot que juste private, on gagne
sur ma machine 6 ms (c'est peu mais bon, c'est utile de la savoir