Comparatif sort . nub vs nub . sort

Date de publication : 10/10/2020 12:12:00

En développant avec Haskell, j'ai souvent eu à associer les fonctions :

nub : 

Élimination des doublons d'une liste.

sort : 

Tri d'une liste.

Mais quelle est la combinaison la plus efficace ? nub . sort ou sort . nub. J'ai toujours été tenté de dire nub . sort mais j'aimerais le vérifier en effectuant un benchmark avec criterion pour en être sûr.

Méthodologie

Outils

Pour effectuer ce comparatif, je vais utiliser la bibliothèque criterion pour tester la vitesse d’exécution de fonctions en association avec quickcheck pour générer arbitrairement des valeurs.

Matériel

Ce test sera réalisé sur une machine tournant sous Linux Debian 10 avec un processeur AMD FX-8350 8 cœurs (FD8350FRW8KHK) avec 32Go de mémoire DDR3

Listes

Je testerais différents types de liste.

• Liste aléatoire de tailles différentes avec une forte redondance de valeurs.

• Liste aléatoire de tailles différentes avec une faible redondance de valeurs.

• Liste aléatoire de tailles différentes avec absence¹ de redondance de valeurs.

Génération des valeurs

Les valeurs seront générées avec les fonctions de vectorOf et choose venant de quickcheck combinées ensemble.

genValues nb min max = do
  generate $ vectorOf nb (choose (min, max))

La fonction générera une série d'entier Int de taille nb avec des valeurs comprises en min et max (inclus).

Main> genValues 50 1 10
[10,2,5,6,9,6,4,10,9,6,8,6,4,2,4,9,5,7,3,6,2,9,2,2,5,5,7,6,3,3,9,7,9,8,1,6,10,3,1,9,9,2,5,6,10,5,6,2,1,3]

Afin de vérifier la qualité des séries générées, je teste le nombre de valeurs différentes et le plus grand nombre de valeurs identiques avec les fonctions suivantes:

let numberOfValues = length <$> duplicates 
let maxNumberOfDuplicates = maximum <$> map length <$> duplicates 

Il faudrait normalement tester un grand nombre de séries pour avoir des valeurs statistiquement valables, mais je ne donne ici qu'un seul résultat:

ghci> numberOfDuplicatesValues <$> genValues 1000 1 10
1000
ghci> maxNumberOfDuplicatesValuesOccurences <$> genValues 1000 1 10
113
ghci> numberOfDuplicatesValues <$> genValues 1000 1 1000
626
ghci> maxNumberOfDuplicatesValuesOccurences <$> genValues 1000 1 1000
6
ghci> numberOfDuplicatesValues <$> genValues 1000 1 100000
8
ghci> maxNumberOfDuplicatesValuesOccurences <$> genValues 1000 1 100000
2
ghci> numberOfDuplicatesValues <$> genValues 1000 1 536870911
0
ghci> maxNumberOfDuplicatesValuesOccurences <$> genValues 1000 1 536870911
*** Exception: Prelude.maximum: empty list

Note : 536870911 est la limite du type Int (indépendamment du système).

Benchmark

Le lancement des benchmarks sera lancé avec la fonction main et avec les fonctions defaultMainWith, bgroup et bench venant de criterion

main = do
  defaultMainWith
    myConfig { reportFile = Just "report-sort-nub1.html" }
    [ bgroup "sort . nub" $ map
      (\(n, mi, ma) -> env
        (genValues n mi ma)
        (\x -> bench (show n ++ "(" ++ show mi ++ "->" ++ show ma ++ ")") $ nf sortNub x)
      )
      [ (100 , 1, 1400)
      , (200 , 1, 1400)
      , (400 , 1, 1400)
      , (600 , 1, 1400)
      , (800 , 1, 1400)
      , (1000, 1, 1400)
      , (1250, 1, 1400)
      , (1500, 1, 1400)
      , (2000, 1, 1400)
      , (3000, 1, 1400)
      , (4000, 1, 1400)
      , (5000, 1, 1400)
      ]
    ...

Analyse des résultats

Les rapports criterion se trouvent ci-dessous:

Séries avec beaucoup de doublons

La fonction sort . nub est plus rapide que nub . sort.

Cela pourrait s'explique par le fait que dans ce cas, la fonction nub devient prépondérante.

Séries avec un nombre de doublons moyen

Dans cette situation la fonction nub . sort est plus rapide que sort . nub.

Séries avec un nombre de doublons faibles

Dans cette situation la fonction nub . sort est toujours plus rapide que sort . nub mais avec un gain qui semble moindre qu'avec le cas précédent.

Séries sans doublons

Le gain semble encore moins flagrant. Il semble même ne plus y avoir de gain de temps du tout

Conclusion

nub . sort semble bien être le meilleur choix pour trier et supprimer les doublons d'une liste, mais il semble qu'il subsiste des limites et des cas où le gain n'est plus aussi évident.

Cependant, le test n'est pas exhaustif et ne permet pas de trancher.

Une étude plus approfondie devrait être effectuée pour connaître avec plus de précision les gains entre les deux fonctions.

---

Notes

1.↑	Ou quasi-absence de redondance.