Benchmarks
Comparaison de fonctions avec Criterion
Comparatif HsIndex
Comparatif sort . nub vs nub . sort
Comparatif sort . nub vs nub . sort (Suite)
Comparatif de performance de fonctions de filtrage de mots
Comparatif de performance de fonctions de filtrage de mots (Suite)
Comparatif de performance de fonctions pour calculer la distance de Levenshtein avec un seuil
Comparatif de performance de fonctions de filtrage de mots (Suite)
Introduction
Pour un de mes programmes, je suis amené à filtrer et supprimer certains mots d'un texte long. J'ai besoin de supprimer les pronoms, les verbes conjugués, les déterminants et certains autres mots.
Dans le précédent tutoriel, j'avais présenté et comparé plusieurs structures de données de type arbre afin d'accélérer le tri de ces mots.
Afin de boucler ce comparatif, j'ai voulu tester une dernière structure en tenant compte des derniers résultats
Arbre personnalisé multibranche (WordTree4x)
Selon moi, l'idée de repartir plusieurs lettres dans une seule branche comme je l'ai fait avec les arbres WordTree2g et WordTree3g est la bonne. Les mauvaises performances de ces arbres vient du test de répartition en lui même. En effet pour sélectionner les bonnes les lettres à mettre dans chaque branche, je procédais à un test avec la fonction elem qui ralentit beaucoup le programme.
La solution serait de remplacer cette fonction par un test plus simple et moins couteux en temps de traitement. Par exemple un test d'égalité == ou d'ordre <, >, <= ou >=. Mais si on veut procéder de la sorte, il faudra alors effectuer les tests de répartition en fonction de l'odre alphabétique des lettres. L'idée d'utiliser un ordre de lettre spécifique sera donc purement et simplement abandonné. En revanche, le groupement des lettres sera spécifique et adapté aux mots à trier.
En reprenant les statistiques des lettres, on aura:
-
A 77
-
B 4
-
C 34
-
D 27
-
E 133
-
F 19
-
G 9
-
H 4
-
I 85
-
J 5
-
L 46
-
M 18
-
N 59
-
O 61
-
P 21
-
Q 21
-
R 49
-
S 103
-
T 90
-
U 102
-
V 21
-
X 9
-
Y 4
-
Z 8
Pour un total de 1009 lettres.
Pour chaque version, on placera les coupures de façon a minimiser l'écart de nombres d'éléments dans chaque branche.
-
Si on coupe à la lettre M (inclue), on aura :
Branche
Nb éléments
A-M
461
N-Z
548
L'écart maximum avec une répartition parfaite des éléments est de
-
Si on coupe à la lettre N (inclue), on aura :
Branche
Nb éléments
A-M
520
N-Z
489
L'écart maximum avec une répartition parfaite des éléments est de
L'écart est donc plus faible avec une coupure à la lettre N (inclue).
Et on appliquera cette méthode à tous les autres arbres.
Implémentations
Plusieurs tests seront effectués avec un nombre de branches différent afin de voir l'influence de ce nombre sur les performances de l'arbre.
On aura donc les implémentations suivantes:
Arbre personnalisé 2 branches (WordTree42)
member v0 tree = go v0 tree
where
go _ Tip = False
go _ t@(Fork vs Tip Tip) = v0 `elem` vs
go [] t@(Fork vs _ _ ) = v0 `elem` vs
go (a : as) (Fork vs t1 t2) | a <= 'l' = go as t1
| otherwise = go as t2
go _ _ = False
Arbre personnalisé 3 branches (WordTree43)
member v0 tree = go v0 tree
where
go _ Tip = False
go _ t@(Fork vs Tip Tip Tip) = v0 `elem` vs
go [] t@(Fork vs _ _ _ ) = v0 `elem` vs
go (a : as) (Fork vs t1 t2 t3) | a <= 'h' = go as t1
| a <= 'r' = go as t2
| otherwise = go as t3
go _ _ = False
Arbre personnalisé 4 branches (WordTree44)
member v0 tree = go v0 tree
where
go _ Tip = False
go _ t@(Fork vs Tip Tip Tip Tip) = v0 `elem` vs
go [] t@(Fork vs _ _ _ _ ) = v0 `elem` vs
go (a : as) (Fork vs t1 t2 t3 t4) | a <= 'e' = go as t1
| a <= 'n' = go as t2
| a <= 's' = go as t3
| otherwise = go as t4
go _ _ = False
Arbre personnalisé 5 branches (WordTree45)
member v0 tree = go v0 tree
where
go _ Tip = False
go _ t@(Fork vs Tip Tip Tip Tip Tip) = v0 `elem` vs
go [] t@(Fork vs _ _ _ _ _ ) = v0 `elem` vs
go (a : as) (Fork vs t1 t2 t3 t4 t5) | a <= 'd' = go as t1
| a <= 'i' = go as t2
| a <= 'q' = go as t3
| a <= 't' = go as t4
| otherwise = go as t5
go _ _ = False
Arbre personnalisé 6 branches (WordTree46)
member v0 tree = go v0 tree
where
go _ Tip = False
go _ t@(Fork vs Tip Tip Tip Tip Tip Tip) = v0 `elem` vs
go [] t@(Fork vs _ _ _ _ _ _ ) = v0 `elem` vs
go (a : as) (Fork vs t1 t2 t3 t4 t5 t6) | a <= 'd' = go as t1
| a <= 'h' = go as t2
| a <= 'm' = go as t3
| a <= 'r' = go as t4
| a <= 't' = go as t5
| otherwise = go as t6
go _ _ = False
Arbre personnalisé 7 branches (WordTree47)
member v0 tree = go v0 tree
where
go _ Tip = False
go _ t@(Fork vs Tip Tip Tip Tip Tip Tip Tip) = v0 `elem` vs
go [] t@(Fork vs _ _ _ _ _ _ _ ) = v0 `elem` vs
go (a : as) (Fork vs t1 t2 t3 t4 t5 t6 t7) | a <= 'd' = go as t1
| a <= 'g' = go as t2
| a <= 'm' = go as t3
| a <= 'q' = go as t4
| a <= 's' = go as t5
| a == 't' = go as t6
| otherwise = go as t7
go _ _ = False
Arbre personnalisé 8 branches (WordTree48)
member v0 tree = go v0 tree
where
go _ Tip = False
go _ t@(Fork vs Tip Tip Tip Tip Tip Tip Tip Tip) = v0 `elem` vs
go [] t@(Fork vs _ _ _ _ _ _ _ _ ) = v0 `elem` vs
go (a : as) (Fork vs t1 t2 t3 t4 t5 t6 t7 t8) | a <= 'd' = go as t1
| a <= 'f' = go as t2
| a <= 'l' = go as t3
| a <= 'o' = go as t4
| a <= 'r' = go as t5
| a == 's' = go as t6
| a == 't' = go as t7
| otherwise = go as t8
go _ _ = False
Arbre personnalisé 9 branches (WordTree49)
member v0 tree = go v0 tree
where
go _ Tip = False
go _ t@(Fork vs Tip Tip Tip Tip Tip Tip Tip Tip Tip) = v0 `elem` vs
go [] t@(Fork vs _ _ _ _ _ _ _ _ _ ) = v0 `elem` vs
go (a : as) (Fork vs t1 t2 t3 t4 t5 t6 t7 t8 t9) | a <= 'c' = go as t1
| a <= 'e' = go as t2
| a <= 'i' = go as t3
| a <= 'm' = go as t4
| a <= 'o' = go as t5
| a <= 'r' = go as t6
| a == 's' = go as t7
| a == 't' = go as t8
| otherwise = go as t9
go _ _ = False
Arbre personnalisé 10 branches (WordTree410)
member v0 tree = go v0 tree
where
go _ Tip = False
go _ t@(Fork vs Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip) = v0 `elem` vs
go [] t@(Fork vs _ _ _ _ _ _ _ _ _ _ ) = v0 `elem` vs
go (a : as) (Fork vs t1 t2 t3 t4 t5 t6 t7 t8 t9 t10) | a <= 'c' = go as t1
| a <= 'e' = go as t2
| a <= 'i' = go as t3
| a <= 'm' = go as t4
| a == 'n' = go as t5
| a <= 'q' = go as t6
| a == 'r' = go as t7
| a == 's' = go as t8
| a == 't' = go as t9
| otherwise = go as t10
go _ _ = False
Arbre personnalisé 11 branches (WordTree411)
member v0 tree = go v0 tree
where
go _ Tip = False
go _ t@(Fork vs Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip) = v0 `elem` vs
go [] t@(Fork vs _ _ _ _ _ _ _ _ _ _ _ ) = v0 `elem` vs
go (a : as) (Fork vs t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11) | a <= 'c' = go as t1
| a <= 'e' = go as t2
| a <= 'h' = go as t3
| a <= 'j' = go as t4
| a <= 'm' = go as t5
| a == 'n' = go as t6
| a <= 'q' = go as t7
| a == 'r' = go as t8
| a == 's' = go as t9
| a == 't' = go as t10
| otherwise = go as t11
go _ _ = False
Arbre personnalisé 12 branches (WordTree412)
member v0 tree = go v0 tree
where
go _ Tip = False
go _ t@(Fork vs Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip Tip) = v0 `elem` vs
go [] t@(Fork vs _ _ _ _ _ _ _ _ _ _ _ _ ) = v0 `elem` vs
go (a : as) (Fork vs t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12) | a <= 'c' = go as t1
| a <= 'e' = go as t2
| a <= 'h' = go as t3
| a <= 'j' = go as t4
| a <= 'm' = go as t5
| a == 'n' = go as t6
| a <= 'q' = go as t7
| a == 'r' = go as t8
| a == 's' = go as t9
| a == 't' = go as t10
| a == 'u' = go as t11
| otherwise = go as t12
go _ _ = False
Résultats
Les résultats sont présentés dans les rapports et le tableau récapitulatif suivant:
|
List |
Set |
WordTree 3 |
WordTree 42 |
WordTree 43 |
WordTree 44 |
WordTree 45 |
WordTree 46 |
WordTree 47 |
WordTree 48 |
WordTree 49 |
WordTree 410 |
WordTree 411 |
WordTree 412 |
|
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
sec |
100,11463 |
9,08085 |
6,80515 |
7,25959 |
5,98261 |
5,84642 |
5,70404 |
5,69355 |
5,77493 |
5,95812 |
5,85358 |
5,90960 |
5,97161 |
6,05108 |
|
xfaster/List |
/ |
11,0248 |
14,7116 |
13,7907 |
16,7343 |
17,1241 |
17,5515 |
17,5839 |
17,3361 |
16,8030 |
17,1031 |
16,9410 |
16,7651 |
16,5449 |
|
%lower/List |
/ |
-90,93 % |
-93,20 % |
-92,75 % |
-94,02 % |
-94,16 % |
-94,30 % |
-94,31 % |
-94,23 % |
-94,05 % |
-94,15 % |
-94,10 % |
-94,04 % |
-93,96 % |
|
xfaster/Set |
/ |
1,00 |
1,3344 |
1,25 |
1,52 |
1,55 |
1,59 |
1,59 |
1,57 |
1,52 |
1,55 |
1,54 |
1,52 |
1,50 |
|
%lower/Set |
/ |
/ |
-10,00 % |
-20,06 % |
-34,12 % |
-35,62 % |
-37,19 % |
-37,30 % |
-36,41 % |
-34,39 % |
-35,54 % |
-34,92 % |
-34,24 % |
-33,36 % |
|
xfaster/WordTree3 |
/ |
/ |
1,00 |
0,94 |
1,14 |
1,16 |
1,19 |
1,20 |
1,18 |
1,14 |
1,16 |
1,15 |
1,14 |
1,12 |
|
%lower/WordTree3 |
/ |
/ |
/ |
6,68 % |
-12,09 % |
-14,09 % |
-16,18 % |
-16,33 % |
-15,14 % |
-12,45 % |
-13,98 % |
-13,16 % |
-12,25 % |
-11,08 % |
![!!! File report-Voyage-full2_p1.[1131x1600@256d].png not found !!!](report-Voyage-full2_p1.[1131x1600@256d].png)
![!!! File report-global2_p1.[1131x1600@256d].png not found !!!](report-global2_p1.[1131x1600@256d].png)
Conlusion
On constate que la vitesse de traitement est la plus faible avec 5 ou 6 branches dans l'arbre. La vitesse d'éxécution est alors:
-
Environ 17 fois plus rapide que le traitement avec une liste.
-
1,59 fois plus rapide que le Set.
-
1,17/1,19 fois plus rapide que la structure WordTree 3.
Cette structure est donc la plus optimisée que j'ai pu trouver pour effectuer le filtrage de mots.
Je tiens à rappeler que cette structure, le nombre de branches et la distribution des lettres dans ces branches n'est valable que pour la liste de mots à filtrer. Une liste différentes, dans une autre langue donnera très certainement des résultats différents et nécessitera des réajustements pour que les performances restent optimales.
Et rappelons aussi que pour la plupart des usage la structure Set fournit pas le module container de Haskell conviendra parfaitement, sera plus généraliste que la structure présentée ici et évitera du temps de développement.