Comparatif sort . nub vs nub . sort (Suite)

Date de publication : 21/11/2020 18:35:00

Suite au comparatif de performance que j'ai réalisé entre nub . sort et sort . nub, j'ai constaté que dans certains cas, la combinaison sort . nub était plus performante que nub . sort pour trier et supprimer les doublons d'une liste.

j'ai eu envie de savoir quelle était la limite à partir de laquelle il valait mieux utiliser une combinaison plutôt que l'autre

Pour cela, il est nécessaire d'avoir des séries de données dont on connaît les caractéristiques et surtout la quantité de doublons qu'elle contient. Dans la mesure ou les comparatifs se font d'un point de vue statistiques, ces caractéristiques seront également obtenus avec un grand nombre de valeurs.

Recherche des caractéristiques

Méthodologie

La principale caractéristique dont j'ai besoin est (statistiquement) le nombre de valeurs identiques que l'on trouve dans une série. Pour cela, je vais générer une centaine de séries (avec le même générateur que dans le précédent tutoriel) avec une taille et une plage de valeurs définie et chercher cette caractéristique.

Je vais ensuite, modifier progressivement la plage de valeurs de façon à obtenir les valeurs de plages permettant d'obtenir des séries avec :

• 1% de doublons

• 5% de doublons

• 10% de doublons

• 20% de doublons

• 25% de doublons

• 30% de doublons

• 40% de doublons

• 50% de doublons

• 60% de doublons

• 70% de doublons

• 75% de doublons

• 80% de doublons

• 90% de doublons

• 95% de doublons

• 99% de doublons

Note: Il est certainement possible de trouver ces valeurs avec des formules mathématiques, mais je n'ai pas envie de passer du temps à faire de la recherche documentaire sur le sujet.

Étant donné que trouver ces caractéristiques prend du temps, le test ne pourra se faire que sur trois séries de :

• 100 éléments

• 1000 éléments

• 10000 éléments

Implémentation

Générateur de valeurs

Le générateur de valeurs est le même que précédemment.

Calcul des valeurs caractéristiques

Pour calculer les valeurs caractéristiques d'une liste de séries, on utilise une fonction mean. Cette fonction va lancer nb fois le générateur gen et appliquer sur la série de résultat les fonctions numberOfDuplicatesValues et maxNumberOfDuplicatesValuesOccurences.

mean :: (Monad m)
     => Int               -- ^ Nombre de séries à générer
     -> m [Int]           -- ^ Générateur d'entier à utiliser
     -> m (Double,Double) -- ^ La valeur moyenne du nombre de doublons et du nombre d'occurence max
mean nb  gen = do
  v <- mapM (\_ -> gen) [1 .. nb]
  let 
      dupv = map numberOfDuplicatesValues v
      dupo = map maxNumberOfDuplicatesValuesOccurences v
      moy v = fromIntegral (sum v) / fromIntegral nb
  return $ (moy dupv,moy dupo)

Valeurs caractéristiques

Les valeurs caractéristiques sont :

• Le nombre de valeurs redondantes d'une liste.

• Le nombre maximum d'occurrences d'une valeur.

Ces valeurs sont implémentées de la sorte:

numberOfDuplicatesValues :: [Int] -> Int
numberOfDuplicatesValues lst = length $ duplicates lst

maxNumberOfDuplicatesValuesOccurences :: [Int] -> Int
maxNumberOfDuplicatesValuesOccurences lst = case duplicates lst of
  []  -> 0
  dup -> maximum $ map length $ dup

et leurs résultats sont :

ghci> numberOfDuplicatesValues [0,1,2,4,2,6,1,5,7,9,1,3,2,1,5,4,1,2,9,1,8,1]
5
ghci> maxNumberOfDuplicatesValuesOccurences [0,1,2,4,2,6,1,5,7,9,1,3,2,1,5,4,1,2,9,1,8,1]
7

Dans la liste, on a bien 5 valeurs distinctes ( 1, 2, 3, 4, 5). 0, 7, 8 et 9 ne sont pas pris en compte car elles n'apparaissent qu'une seule fois.

La valeur 1 est bien la plus représentée et elle apparaît 7 fois.

Le compte est bon!

Statistique d'une série

Pour calcul les statistiques sur une série, on utilise la

stat nb min max = do
  (dupv,dupo) <- mean 200  (genValues nb min max)
  putStrLn
    $  "Serie "
    ++ show nb
    ++ "("
    ++ show min
    ++ "->"
    ++ show max
    ++ "),"
    ++ show nb
    ++ ","
    ++ show min
    ++ ","
    ++ show max
    ++ ","
    ++ show dupv
    ++ ","
    ++ show dupo
    ++ ","
    ++ printf "%3.6f" (100 * dupv / fromIntegral nb)

Cette fonction lancera la génération de 200 listes en utilisant la fonction mean avec le générateur de valeur genValues et la fonction appropriée.

Les résultats sont affichés avec une virgule comme séparateur afin de pouvoir être exporté vers un fichier CSV.

Fonction principale

Enfin la fonction principale qui permettra de créer l'en tête du fichier CSV et de lancer les différentes fonctions stat avec les différentes plages de valeurs.

Les différentes plages de valeurs ont été sélectionnés avec plusieurs tests en mode interactif (ghci).

main = do
  putStrLn
    $  "SerieName"
    ++ ","
    ++ "Length"
    ++ ","
    ++ "MinValue"
    ++ ","
    ++ "MaxValue"
    ++ ","
    ++ "NbOfRedondantValues"
    ++ ","
    ++ "maxNumberOfDuplicatesValuesOccurences"
    ++ ","
    ++ "PercentOfRedondantValues"
  mapM (\m -> stat 100 1 m)  lstRange100

lstRange100 = [2..11000]++other

lstRange1000 =  [10..50]++
  range 230 30++
  range 350 30++
  range 430 30++
  range 630 30++
  range 710 30++
  range 830 30++
  range 1070 30++
  range 1430 30++
  range 1910 30++
  range 2710 40++
  range 3290 50++
  range 4460 30++
  range 9300 30++
  range 19650 50++
  [94000,94250..99000] ++ other

other = [1000000, 536870911]

Résultats

Ce programme permet de générer un fichier CSV contenant pour chaque série d'une taille fixée et avec des valeurs comprises entre 1 et une limite maximum le nombre de valeurs redondantes (doublons), et le nombre d'occurences maximum des doublons.

Rappelons que ces valeurs sont des valeurs moyennes.

Les résultats sont synthétisés dans les tableaux suivant:

Série de 100 éléments

Nom	nb	min	max	nb dups	siz dups	% dups
Serie 100(1->22)	100	1	22	98,97	9,02	98,97
Serie 100(1->33)	100	1	33	95,01	7,26	95,01
Serie 100(1->43)	100	1	43	90,26	6,24	90,26
Serie 100(1->62)	100	1	62	80,26	5,15	80,26
Serie 100(1->71)	100	1	71	74,90	4,97	74,90
Serie 100(1->82)	100	1	82	70,17	4,58	70,17
Serie 100(1->108)	100	1	108	60,08	4,08	60,08
Serie 100(1->144)	100	1	144	50,04	3,59	50,04
Serie 100(1->193)	100	1	193	40,11	3,36	40,11
Serie 100(1->283)	100	1	283	30,00	2,87	30,00
Serie 100(1->348)	100	1	348	24,94	2,70	24,94
Serie 100(1->452)	100	1	452	20,00	2,54	20,00
Serie 100(1->906)	100	1	906	9,99	2,17	9,99
Serie 100(1->1881)	100	1	1881	5,00	1,83	5,00
Serie 100(1->10837)	100	1	10837	1,00	0,76	1,00

Série de 1000 éléments

Nom	nb	min	max	nb dups	siz dups	% dups
Serie 1000(1->217)	1000	1	217	990,18	11,61	99,02
Serie 1000(1->334)	1000	1	334	949,42	9,06	94,94
Serie 1000(1->432)	1000	1	432	900,59	8,04	90,06
Serie 1000(1->621)	1000	1	621	800,12	6,65	80,01
Serie 1000(1->724)	1000	1	724	750,15	6,22	75,02
Serie 1000(1->835)	1000	1	835	699,89	5,87	69,99
Serie 1000(1->1089)	1000	1	1089	599,95	5,39	60,00
Serie 1000(1->1445)	1000	1	1445	499,80	4,60	49,98
Serie 1000(1->1929)	1000	1	1929	400,08	4,36	40,01
Serie 1000(1->2731)	1000	1	2731	301,69	3,99	30,17
Serie 1000(1->3334)	1000	1	3334	256,11	3,63	25,61
Serie 1000(1->4467)	1000	1	4467	200,06	3,29	20,01
Serie 1000(1->9330)	1000	1	9330	100,03	2,92	10,00
Serie 1000(1->19654)	1000	1	19654	50,00	2,41	5,00
Serie 1000(1->95000)	1000	1	95000	10,03	2,03	1,00

Comparaison de nub . sort et sort . nub

Méthodologie

Maintenant que l'on connaît les caractéristiques que prendra une série de 100, 1000 et 10000 éléments sur une plage de valeurs définie, on peut comparer les résultats en fonction du pourcentage de doublons que contiendra cette série.

On va donc faire un comparatif avec différents pourcentage de doublons sur la série.

Les tests seront lancés avec :

• Désactivation des optimisations de ghc (-O0)

• Activation des optimisations de ghc (-O2)

Implémentation

L'implémentation se fait globalement de la même manière qu'avec le précédent test.

main = do
  defaultMainWith
    myConfig { reportFile = Just "report-sort-nub-next1.html", csvFile = Just "report-sort-nub-next1.csv" }
    [ bgroup
      "100% dups"
      [ env (genValues 1000 1 10) (\x -> bench "sort . nub" $ nf sortNub x)
      , env (genValues 1000 1 10) (\x -> bench "nub . sort" $ nf nubSort x)
      ]
    , bgroup
      "99% dups"
      [ env (genValues 1000 1 217) (\x -> bench "sort . nub" $ nf sortNub x)
      , env (genValues 1000 1 217) (\x -> bench "nub . sort" $ nf nubSort x)
      ]
    , bgroup
      "95% dups"
      [ env (genValues 1000 1 334) (\x -> bench "sort . nub" $ nf sortNub x)
      , env (genValues 1000 1 334) (\x -> bench "nub . sort" $ nf nubSort x)
      ]
    , bgroup
      "90% dups"
      [ env (genValues 1000 1 432) (\x -> bench "sort . nub" $ nf sortNub x)
      , env (genValues 1000 1 432) (\x -> bench "nub . sort" $ nf nubSort x)
      ]
    , bgroup
      "80% dups"
      [ env (genValues 1000 1 621) (\x -> bench "sort . nub" $ nf sortNub x)
      , env (genValues 1000 1 621) (\x -> bench "nub . sort" $ nf nubSort x)
      ]
    , bgroup
      "75% dups"
      [ env (genValues 1000 1 724) (\x -> bench "sort . nub" $ nf sortNub x)
      , env (genValues 1000 1 724) (\x -> bench "nub . sort" $ nf nubSort x)
      ]
    , bgroup
      "60% dups"
      [ env (genValues 1000 1 1089) (\x -> bench "sort . nub" $ nf sortNub x)
      , env (genValues 1000 1 1089) (\x -> bench "nub . sort" $ nf nubSort x)
      ]
    , bgroup
      "50% dups"
      [ env (genValues 1000 1 1445) (\x -> bench "sort . nub" $ nf sortNub x)
      , env (genValues 1000 1 1445) (\x -> bench "nub . sort" $ nf nubSort x)
      ]
    , bgroup
      "40% dups"
      [ env (genValues 1000 1 1929) (\x -> bench "sort . nub" $ nf sortNub x)
      , env (genValues 1000 1 1929) (\x -> bench "nub . sort" $ nf nubSort x)
      ]
    , bgroup
      "30% dups"
      [ env (genValues 1000 1 2731) (\x -> bench "sort . nub" $ nf sortNub x)
      , env (genValues 1000 1 2731) (\x -> bench "nub . sort" $ nf nubSort x)
      ]
    , bgroup
      "25% dups"
      [ env (genValues 1000 1 3334) (\x -> bench "sort . nub" $ nf sortNub x)
      , env (genValues 1000 1 3334) (\x -> bench "nub . sort" $ nf nubSort x)
      ]
    , bgroup
      "10% dups"
      [ env (genValues 1000 1 9330) (\x -> bench "sort . nub" $ nf sortNub x)
      , env (genValues 1000 1 9330) (\x -> bench "nub . sort" $ nf nubSort x)
      ]
    , bgroup
      "5% dups"
      [ env (genValues 1000 1 19654) (\x -> bench "sort . nub" $ nf sortNub x)
      , env (genValues 1000 1 19654) (\x -> bench "nub . sort" $ nf nubSort x)
      ]
    , bgroup
      "1% dups"
      [ env (genValues 1000 1 95000) (\x -> bench "sort . nub" $ nf sortNub x)
      , env (genValues 1000 1 95000) (\x -> bench "nub . sort" $ nf nubSort x)
      ]
    , bgroup
      "0% dups"
      [ env (genValues 1000 1 536870911) (\x -> bench "sort . nub" $ nf sortNub x)
      , env (genValues 1000 1 536870911) (\x -> bench "nub . sort" $ nf nubSort x)
      ]
    ] 

Résultats

Après lancement des calculs, j'ai effectué l'analyse des résultats. Et le moins qu'on puisse dire, c'est qu'ils sont … surprenant.

Séries de 100 éléments

Sans optimisation (-O0)

Les résultats sont incertains et connaissent beaucoup de fluctuations qui rendent difficiles l'interprétation des résultats

Avec optimisation (-O2)

On remarque déjà une diminution de 20% à 47% du temps d’exécution selon les cas¹.

Sur l'ensemble de la plage, c'est sort . nub qui est plus rapide que nub . sort. Ce qui est en contradiction avec le premier benchmark et avec ce que je pensais.

Conclusion

Les listes de 100 éléments ne semblent pas refléter fidèlement ce qui se passe. Le nombre peu élevé d'éléments cause beaucoup de fluctuations d'une passe de tests à l'autre.

Séries de 1000 éléments

Les choses deviennent plus claires.

Sans optimisation (-O0)

On remarque que sur la plage allant de 5% de doublons à 99% de doublons, la fonction nub . sort est plus rapide avec un gain de temps variant de 2% à 48% augmentant avec le pourcentage de doublons dans la liste. Le gain est donc très important.

Dans les cas extrêmes on a :

• 1% : nub . sort va moins vite que sort . nub. Mais il s'agit peut-être d'une valeur aberrante.

• 100% : Comme je l'avais déjà constaté dans le précédent test, dans ce cas nub . sort est jusqu'à 3 fois plus lent.

Avec optimisation (-O2)

Ici, les choses sont un peu moins évidentes. Tout d'abord, on remarque que les vitesses d’exécutions sont plus faibles. Le gain va de 13% à 35% selon les cas¹.

Sur une plage de 99% à 60% de doublons, nub . sort est 12% a 38% plus rapide que sort . nub.

Sur une plage de 50% à 30% de doublons, nub . sort n'est plus que 1% a 8% plus rapide que sort . nub.

Au dela, sur la page 25 à 0% de doublons, nub . sort tourne moins vite que sort . nub avec une augmentation progressive du temps d’exécution de 3% à 11%.

Ces résultats sont étonnants, d'autant qu'ils contredisent les résultats précédents (100 éléments). Mais il faut se rendre à l'évidence, la certitude que j'avais concernant nub . sort n'est pas toujours vrai². Elle n'est valable que sur des listes contenant plus de 25% de valeurs redondantes et n'est vraiment intéressante qu'avec plus de 50% de valeurs redondantes.

Séries de 10000 éléments

Les choses deviennent … stupéfiantes.

Sans optimisation (-O0)

Comme avec les listes de 1000 éléments, nub . sort est plus rapide par rapport à sort . nub de 7% à 78%

Avec optimisation (-O2)

Sur une plage de 99% à 60% de doublons, nub . sort est 13% a 67% plus rapide que sort . nub.

Sur une plage de 50% à 30% de doublons, nub . sort n'est plus que 6% a 12% plus rapide que sort . nub.

Au dela, sur la page 25 à 0% de doublons, nub . sort tourne moins vite que sort . nub avec une augmentation progressive du temps d’exécution de 3% à 13%.

La ou les choses sont incroyables c'est que la version non optimisée de nub . sort est 6% à 12% plus rapide que sa version optimisée !

Et si on compare la version non optimisée de nub . sort à la version optimisée de sort . nub, on remarque que la version non optimisée de nub . sort est toujours plus rapide à l'exception des zones 100% et 0%-5% de doublons. Et encore, dans cette zone, la différence de temps d’exécution n'est que de 1% à 4%.

Conclusion

Ce benchmark m'a permis de faire un comparatif fin de l'association nub . sort et de son opposé. Elle m'a permis de valider ma première idée sur le fait que nub . sort est plus rapide que sort . nub mais en mettant en lumière certaines limitations.

Sans optimisation (-O0)

A l'exception du cas ou il y a 100% de doublons dans la liste, nub . sort est toujours plus rapide pour des listes de plus 1000 éléments.

Avec optimisation (-O2)

nub . sort est plus rapide sur la plage de 25%-30% à 99% de doublons. Sur la plage 0% à 25%, c'est sort . nub qui est plus rapide.

Anomalie optimisation (-O2)

À ce jour, je n'ai pas d'explications sur l'aberration qui survient avec les listes de 10000 éléments traités avec la combinaison nub . sort. Peut-être que les optimisations apportées par le compilateur ghc sur l'une ou l'autre des fonctions nub ou sort ne sont plus valables passé un certain nombre d'éléments dans une liste. Ne pouvant pas passer plus de temps sur ce mystère, je laisse cette question en suspens … pour le moment.

---

Notes

1.↑	D'où l'intérêt de toujours activer l'option -O2 quand on compile un programme.
2.↑	Pour ce qui est de son implémentation avec Haskell en tout cas. Les résultats sont peut-être différents avec un autre langage de programmation.