Benchmarks

Comparatif de performance de fonctions de filtrage de mots

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.

La première façon de faire serait de simplement filtrer la liste de mots wrdstxt en testant l'absence de chaque mot de la liste wrdsfilt en utilisant notElem:

filterByList (wrdsfilt, wrdstxt) = filter (`notElem` wrdsfilt) wrdstxt

Pour un petit nombre de mots servant de filtre, cette fonction serait adaptée, mais plus le nombre de mots à supprimer va augmenter, plus le temps de traitement va augmenter 1.

Il faut donc trouver un moyen d'optimiser le processus.

La solution serait de stocker les mots non plus dans une liste mais dans un arbre de recherche. Les mots ainsi triés et organisés seraient plus rapides à rechercher.

Après avoir recherché de la documentation sur le sujet, j'ai trouvé plusieurs solutions permettant de répondre à mon problème.

Mais quelle est la solution la plus performante ?

C'est ce que nous allons voir dans ce benchmark!

Méthodologie

Généralité

Le benchmark sera réalisé avec Haskell et Criterion avec toutes les optimisations de compilation activées ghc -o2 -fforce-recomp.

La liste de mots à filtrer sera celle-ci: Mots_a_filtrer.txt

Le texte à balayer sera Voyage au centre de la terre récupéré sur le site Gutenberg

Les mots seront chargés avant le test, afin de ne pas fausser les résultats.

Les arbres de recherches seront créés pendant le test afin de prendre en compte le temps de création de l'arbre.

Solutions

Les différentes solutions passées en revue sont :

Data.Set

Le paquet container fournit différents modules standards pour stocker des données et notamment les Set.

Cette structure est un arbre de recherche binaire (2 branches) automatiquement équilibré lors de sa création.

Arbre personnalisé multibranche (WordTree1)

Cet arbre est un arbre de ma propre conception contenant une branche pour chaque lettre de l'alphabet. L'ordre des arbres, correspond à l'ordre alphabétique: abcdefghijklmnopqrstuvwxyz

Cet arbre ne peut pas se rééquilibrer tout seul.

La fonction member permettant de tester la présence d'un élément est implémenté de cette manière:

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 Tip Tip 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 t13 t14 t15 t16 t17 t18 t19 t20 t21 t22 t23 t24 t25 t26) | a == 'a'  = go as t1
                                                                                                                             | a == 'b'  = go as t2
                                                                                                                             | a == 'c'  = go as t3
                                                                                                                             | a == 'd'  = go as t4
                                                                                                                             | a == 'e'  = go as t5
                                                                                                                             | a == 'f'  = go as t6
                                                                                                                             | a == 'g'  = go as t7
                                                                                                                             | a == 'h'  = go as t8
                                                                                                                             | a == 'i'  = go as t9
                                                                                                                             | a == 'j'  = go as t10
                                                                                                                             | a == 'k'  = go as t11
                                                                                                                             | a == 'l'  = go as t12
                                                                                                                             | a == 'm'  = go as t13
                                                                                                                             | a == 'n'  = go as t14
                                                                                                                             | a == 'o'  = go as t15
                                                                                                                             | a == 'p'  = go as t16
                                                                                                                             | a == 'q'  = go as t17
                                                                                                                             | a == 'r'  = go as t18
                                                                                                                             | a == 's'  = go as t19
                                                                                                                             | a == 't'  = go as t20
                                                                                                                             | a == 'u'  = go as t21
                                                                                                                             | a == 'v'  = go as t22
                                                                                                                             | a == 'w'  = go as t23
                                                                                                                             | a == 'x'  = go as t24
                                                                                                                             | a == 'y'  = go as t25
                                                                                                                             | otherwise = go as t26

        go _ _ = False

Le module complet se trouve ici : WordTree1.hs

Arbre personnalisé multibranche (WordTree2)

Cet arbre est du même type que l'arbre WordTree1 a ceci près que l'ordre des arbres correspond à l'ordre des lettres les plus couramment utilisées dans la langue française2: eairsntolucmpdghbfvyqkzx

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 Tip 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 t13 t14 t15 t16 t17 t18 t19 t20 t21 t22 t23 t24 t25) | a == 'e'  = go as t1
                                                                                                                         | a == 'a'  = go as t2
                                                                                                                         | a == 'i'  = go as t3
                                                                                                                         | a == 'r'  = go as t4
                                                                                                                         | a == 's'  = go as t5
                                                                                                                         | a == 'n'  = go as t6
                                                                                                                         | a == 't'  = go as t7
                                                                                                                         | a == 'o'  = go as t8
                                                                                                                         | a == 'l'  = go as t9
                                                                                                                         | a == 'u'  = go as t10
                                                                                                                         | a == 'c'  = go as t11
                                                                                                                         | a == 'm'  = go as t12
                                                                                                                         | a == 'p'  = go as t13
                                                                                                                         | a == 'd'  = go as t14
                                                                                                                         | a == 'g'  = go as t15
                                                                                                                         | a == 'h'  = go as t16
                                                                                                                         | a == 'b'  = go as t17
                                                                                                                         | a == 'f'  = go as t18
                                                                                                                         | a == 'v'  = go as t19
                                                                                                                         | a == 'y'  = go as t20
                                                                                                                         | a == 'q'  = go as t21
                                                                                                                         | a == 'k'  = go as t22
                                                                                                                         | a == 'z'  = go as t23
                                                                                                                         | a == 'x'  = go as t24
                                                                                                                         | otherwise = go as t25

        go _ _ = False

Le module complet se trouve ici : WordTree2.hs

Cet arbre ne peut pas se rééquilibrer tout seul.

Arbre personnalisé multibranche groupées (WordTree2g)

Cet arbre est une modification de l'arbre WordTree2 avec un regroupement de certaines lettres dans certaines branches de l'arbre. Ce regroupement est effectué en fonction des occurrences de ces lettres et effectué à l'aide de la fonction elem.

Le regroupement des lettres sera:

  1. E

  2. A

  3. I

  4. R

  5. S

  6. N

  7. T

  8. O

  9. LU

  10. CMP

  11. DGHB

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 == 'e'      = go as t1
                                                                     | a == 'a'      = go as t2
                                                                     | a == 'i'      = go as t3
                                                                     | a == 'r'      = go as t4
                                                                     | a == 's'      = go as t5
                                                                     | a == 'n'      = go as t6
                                                                     | a == 't'      = go as t7
                                                                     | a == 'o'      = go as t8
                                                                     | elem a "lu"   = go as t9
                                                                     | elem a "cmp"  = go as t10
                                                                     | elem a "dghb" = go as t11
                                                                     | otherwise     = go as t12

        go _ _ = False

Le module complet se trouve ici : WordTree2g.hs

Arbre personnalisé multibranche (WordTree3)

Cet arbre est une amélioration de l'arbre WordTree2. L'ordre des arbres correspond à l'ordre des lettres le plus couramment utilisé dans la liste de mots à filtrer3:

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 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 t13 t14 t15 t16 t17 t18 t19 t20 t21 t22 t23 t24) | a == 'e'  = go as t1
                                                                                                                     | a == 't'  = go as t2
                                                                                                                     | a == 'u'  = go as t3
                                                                                                                     | a == 's'  = go as t4
                                                                                                                     | a == 'i'  = go as t5
                                                                                                                     | a == 'a'  = go as t6
                                                                                                                     | a == 'o'  = go as t7
                                                                                                                     | a == 'r'  = go as t8
                                                                                                                     | a == 'n'  = go as t9
                                                                                                                     | a == 'l'  = go as t10
                                                                                                                     | a == 'c'  = go as t11
                                                                                                                     | a == 'd'  = go as t12
                                                                                                                     | a == 'q'  = go as t13
                                                                                                                     | a == 'p'  = go as t14
                                                                                                                     | a == 'f'  = go as t15
                                                                                                                     | a == 'v'  = go as t16
                                                                                                                     | a == 'm'  = go as t17
                                                                                                                     | a == 'x'  = go as t18
                                                                                                                     | a == 'z'  = go as t19
                                                                                                                     | a == 'h'  = go as t20
                                                                                                                     | a == 'g'  = go as t21
                                                                                                                     | a == 'j'  = go as t22
                                                                                                                     | a == 'y'  = go as t23
                                                                                                                     | otherwise = go as t24

        go _ _ = False

Le module complet se trouve ici : WordTree3.hs

Arbre personnalisé multibranche groupées (WordTree3g)

Cet arbre est une modification de l'arbre WordTree3 avec un regroupement de certaines lettres dans certaines branches de l'arbre. Ce regroupement est effectué en fonction des occurrences de ces lettres et effectué à l'aide de la fonction elem.

Le regroupement des lettres sera:

  1. E

  2. T

  3. U

  4. R

  5. S

  6. IA

  7. OR

  8. NLC

  9. DQPFVMXZH

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 == 'e'           = go as t1
                                                         | a == 't'           = go as t2
                                                         | a == 'u'           = go as t3
                                                         | a == 's'           = go as t4
                                                         | elem a "ia"        = go as t5
                                                         | elem a "or"        = go as t6
                                                         | elem a "nlc"       = go as t7
                                                         | elem a "dqpfvmxzh" = go as t8
                                                         | otherwise          = go as t9

        go _ _ = False

Le module complet se trouve ici : WordTree3g.hs

Fonctions de test

Lecture des fichiers texte

Les listes de mots à filtrer et servant de filtres sont lues depuis un fichier texte avec readFile puis découpés en mots, convertit en minuscule avec map (map toLower) . words et renvoyés sous forme d'un doublet.

Cette fonction est exécutée hors test pour ne pas prendre en compte le temps de construction des listes dans le test.

readWordsIO :: FilePath -> FilePath -> IO ([String], [String])
readWordsIO pathfil pathtxt = do
    wrdsfil <- map (map toLower) . words <$> readFile pathfil
    wrdstxt <- map (map toLower) . words <$> readFile pathtxt
    return (wrdsfil, wrdstxt)

Filtrage

Le filtrage des listes se fera avec des fonctions identiques utilisant la fonction member de chaque module.

Seule la fonction de fitlrage par liste est un peu différente, utilisant notElem.

filterByList (wrdsfilt, wrdstxt) = filter (`notElem` wrdsfilt) wrdstxt

filterTextSet (wrdsfilt, wrdstxt) = filter (\w -> not (Set.member w tree)) wrdstxt
    where tree = Set.fromList wrdsfilt

filterText1 (wrdsfilt, wrdstxt) = filter (\w -> not (WT1.member w tree)) wrdstxt
    where tree = WT1.fromList wrdsfilt

Construction

La construction des arbres sera évaluée simplement avec la fonction fromList de chaque module.

constSet (wrdsfilt, wrdstxt) = Set.fromList wrdsfilt

constTree1 (wrdsfilt, wrdstxt) = WT1.fromList wrdsfilt

Résultats

Temps de filtrage

Les valeurs données par le benchmark sont les suivantes:

Lists

Set

WordTree 1

WordTree 2

WordTree 2g

WordTree 3

WordTree 3g

sec

96,44437

8,73092

7,63710

6,94024

10,84359

6,83521

15,85130

xfaster/List

/

11,0463

12,6284

13,8964

8,8941

14,1099

6,0843

%lower/List

/

-90,95 %

-92,08 %

-92,80 %

-88,76 %

-92,91 %

-83,56%

xfaster/Set

/

/

1,14

1,26

0,81

1,28

0,55

%lower/Set

/

/

-12,53 %

-20,51 %

24,20 %

-21,71 %

81,55 %

!!! File report-Voyage-full1_p1.[1131x1600@256d].png not found !!!!!! File report-global1_p1.[1131x1600@256d].png not found !!!

On remarque déjà l'écart entre le filtrage par liste et le filtrage avec des arbres. Le gain est énorme ! Le traitement est 10 fois plus rapide qu'avec la liste.

On remarque également que si le le filtrage avec le Set est très performant, un filtrage avec un arbre dédié a chaque lettre est un peu plus rapide.

On voit déjà que l'idée de regrouper les lettres dans certaines branches avec la fonction elem est une mauvaise idée. Ces fonctions bien que plus rapide que le tri par liste sont plus lentes que le tri par Set et surtout plus lentes que leur version non groupée.

On constate aussi que l'arbre WordTree2 est un peu plus rapide que l'arbre WordTree1 et que l'arbre WordTree3 est un peu plus rapide que le WordTree2.

Il est donc intéressant d'avoir un arbre dont le classement est optimisé pour la liste de mots servant de filtre.

Temps de construction des arbres

Comme on le voit sur ce tableau récapitulatif, Le temps de construction d'un set est beaucoup plus important que l'arbre WordTree1 (environ 5 fois plus lent). Cela s'explique très bien car les Set sont des arbres qui s'équilibrent automatiquement lors de leur construction. Cela nécessite des tests et des modifications de l'arbre qui entraîne un ralentissement de la construction.

On remarque également que plus on utilise un arbre adapté (optimisé) pour les mots servant de filtre, plus son temps de construction est faible.

Set

WordTree 1

WordTree 2

WordTree 2g

WordTree 3

WordTree 3g

sec

0,04696

0,00831

0,00781

0,01192

0,00784

0,01606

xfaster/Set

1,00

5,65

6,02

3,94

5,99

2,92

%lower/Set

/

-82,30 %

-83,38 %

-74,62 %

-83,31 %

-65,80 %

!!! File report-construct-full1_p1.[1131x1600@256d].png not found !!!

Conclusion

Utiliser un filtrage par arbre est extrêmement intéressant est permet d'accélérer considérablement le traitement par rapport à un filtrage par liste. Le gain étant de l'ordre de 90%

Un arbre adapté aux mots servant de filtre permet également d'accélérer le traitement. Le gain pouvant aller jusqu'a 20%/25% par rapport à un Set.

Néanmoins, réaliser une statistique des lettres utilisées et implémenter un arbre optimisé pour cette série prend du temps.

Pour un usage occasionnel et standard, l'utilisation d'un Set reste la solution la plus simple et la plus rapide à mettre en œuvre.

Pour un usage intensif sur une quantité massive de données, utiliser un arbre dédié peut accélérer notablement le temps de traitement.


Notes

1.

Le temps de traitement augmentera de façon exponentielle.

2.

Lettres les plus utilisées dans la langue française

Selon cette page, les lettres les plus souvent utilisées dans la langue française sont:

  1. E 12,80 %

  2. A 8,82 %

  3. I 8,53 %

  4. R 7,72 %

  5. S 7,17 %

  6. N 7,01 %

  7. T 6,63 %

  8. O 6,25 %

  9. L 4,68 %

  10. U 4,16 %

  11. C 3,72 %

  12. M 2,89 %

  13. P 2,46 %

  14. D 2,37 %

  15. G 1,95 %

  16. H 1,93 %

  17. B 1,76 %

  18. F 1,29 %

  19. V 1,19 %

  20. Y 0,72 %

  21. Q 0,54 %

  22. K 0,52 %

  23. Z 0,46 %

  24. X 0,35 %

  25. J 0,25 %

3.

Une analyse faite a part a montrée que les lettres les plus courantes dans les mots à chercher sont:

\ [('e',133),('s',103),('u',102),('t',90),('i',85),('a',77),('o',61),('n',59),('r',49),('l',46),('c',34),('d',27),('q',21),('p',21),('v',21),('f',19),('m',18),('x',9),('g',9),('z',8),('j',5),('y',4),('h',4),('b',4)] \ [('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)]

  1. E 133

  2. S 103

  3. U 102

  4. T 90

  5. I 85

  6. A 77

  7. O 61

  8. N 59

  9. R 49

  10. L 46

  11. C 34

  12. D 27

  13. Q 21

  14. P 21

  15. V 21

  16. F 19

  17. M 18

  18. X 9

  19. G 9

  20. Z 8

  21. J 5

  22. Y 4

  23. H 4

  24. B 4