Formalisation d'un algo de mélange (en Groovy)

Voici un problème auquel je suis confronté sur mon projet d’Android pour l’école : je dois implémenter une fonctionnalité de mélange de titres de musique. L’occasion pour moi de me pencher sur un problème que j’ai rencontré avec tous les lecteurs de musique que j’ai utilisé : la lecture aléatoire n’est pas si aléatoire et, avec un échantillon de musique suffisamment grand et sur un nombre d’écoutes suffisamment important, un petit échantillon de titres semble revenir plus souvent que tous les autres. Essayons de voir si l’on peut élaborer un algo de mélange efficace.

Formalisation du problème et algorithme

Le problème est le suivant : soit une liste l de taille n composée d’éléments notés x_1 à x_n, le but est de définir un algo de mélange qui donne une distribution aléatoire des titres dans la liste, c’est-à-dire que n’importe quel titre x_m a autant de chances d’être à une place p_a qu’à une autre place p_b à chaque mélange.

Pour mesurer l’efficacité de l’algo, nous allons créer une liste d’entiers, la mélanger un nombre important de fois et repérer, après chaque mélange, quel élément x_m est à quelle position p_a. À la fin du test, le taux d’apparition d’un couple (x_m, p_a) devrait être équivalent pour tous les couples. En maths, cette propriété est donnée par la variance qui se calcule de la façon suivante :

dfrac{1}{n} times sum_{i=1}^{n}(n_i-m)^2

m désigne la moyenne et n_i, le nombre d’apparition d’un couple i.

L’algorithme que j’ai imaginé procède de la façon suivante : pour une liste l de taille n, nous allons effectuer un nombre fini de permutations entre deux éléments pas nécessairement distincts mais choisis de manière aléatoire. Ce nombre de permutations est une fonction de la taille de la liste — mettons 2n, par exemple. Nous allons modéliser ça avec le code Groovy suivant :

Groovy, c’est si sexy ! <3

Cet algorithme a une complexité algorithmique linéaire d’ordre O(n), ce qui n’est pas trop mal pour un algo simple. Il serait possible de faire plus optimisé en adoptant une approche diviser-conquerir et en faisant tourner cet algo en parallèle sur plusieurs portions de tableau mais l’optimisation au dernier degré n’est pas mon but pour le moment. Je compte, de toute façon, dans la gestion de mes playlists me servir massivement des threads de Java. C’est donc une optimisation que je garde quand-même de côté.

Analyse de l’algo

Afin de tester son efficacité, nous allons faire tourner l’algo dans différentes conditions. Dans un premier temps, nous allons tester sa fiabilité sur une liste de 500 éléments sur quatre tirages :

  1. sur 100 mélanges
  2. sur 500 mélanges
  3. sur 1000 mélanges
  4. sur 2000 mélanges

Nous allons tester notre algo avec le code suivant :

Quelques explications s’imposent. La méthode  testShuffle()  va faire un nombre de mélanges définis et va, après chaque mélange, parcourir la liste générée pour repérer quel élément est à quel position. Ce couple (element, position) est stocké dans un Tuple2 . Chaque couple rencontré est stocké dans une LinkedHashMap  qui fait le lien entre le couple et la fréquence d’apparition. La méthode computeAverage()  calcule la fréquence d’apparition moyenne sur tous les couples, la méthode computeVariance() calcule la variance des fréquences d’apparition et la méthode computePopFreq() calcule, pour chaque fréquence d’apparition, le nombre de couples qui sont apparus à cette fréquence.

Voici les résultats pour nos 4 tirages :

Sur 100 mélanges, notre algo est plutôt fiable, la variance est assez faible, inférieure à 0.25, ce qui est plutôt bon signe. On remarque tout de même que deux titres ont réussi à se retrouver 6 fois à la même position au cours des 100 mélanges, ce qui n’est pas particulièrement étonnant, mais nous aimerions éviter que cela arrive plus fréquemment. Sur 500 mélanges, notre algorithme est encore assez fiable : la variance reste inférieure à 1.

Sur 1000 et 2000 mélanges, notre algo commence à montrer quelques signes de faiblesse mais rien d’extraordinaire. Notre variance reste contrôlée sur 1000 mélanges à un chiffre proche de 2 mais est quand-même multipliée par 3 dès qu’on passe à 2000 mélanges.

De manière étonnante, cependant, il semble que notre algo soit plus efficace avec un nombre plus important d’éléments. Sur 1000 éléments, les variances sont alors de l’ordre de :

  • 0.07 pour 100 mélanges contre 0.12 avec 500 éléments,
  • 0.4 pour 500 mélanges contre 0.8 avec 500 éléments,
  • 1.16 pour 1000 mélanges contre 2.4 avec 500 éléments,
  • 3.11 pour 2000 mélanges contre 6.4 avec 500 éléments

On divise quand-même la variance par 2 dans le cas de 2000 mélanges ! Je vous avoue que je m’attendais plutôt au contraire.

Questionnements et améliorations possibles

Notre algorithme est donc plutôt performant ce qui est une bonne surprise. Mais que se serait-il passé s’il ne l’avait pas été ? Là se serait formulé le problème qui se pose tôt ou tard à tout programmeur qui développe un algorithme : puis-je améliorer la situation et cela vaut-il le coût ?

Lorsqu’on rend un algo plus fiable, il est rare que ça ne se paie pas en perte de performance. Il est alors très important de déterminer si la perte engendrée de performance engendrée par l’amélioration est suffisamment inférieure au gain en fiabilité.

Ici, l’algorithme commence à montrer des faiblesses sur 2000 mélanges de 500 titres. Il est quand-même assez peu probable qu’une personne déclenche suffisamment de lectures en suffisamment peu de temps pour que cette récurrence devienne agaçante. Sur mes iPods, on parlait quand-même d’une playlist d’environ 2000 titres dont une soixantaine d’entre eux seulement revenaient systématiquement dans les premières positions à chaque nouveau mélange…

Deux solutions me viennent naturellement à l’esprit pour améliorer les choses :

  • augmenter le nombre de permutations à 3n voire choisir un nombre de permutations aléatoire compris entre 2n et 3n
  • utiliser une technique de mémoisation en retenant les fréquences d’apparition des couples (element, position) pour éliminer les permutations qui reviennent trop fréquemment

La première solution est naïve et pourrait ne pas vraiment améliorer les choses s’il s’avère que le problème vient en fait de la classe Random  qui n’est pas assez fiable. Le coût en perf qui en résulterait sur une plus grande liste d’éléments serait trop importante pour un gain en fiabilité assez faible, voire nul.

La seconde solution est un patron de conception très connu pour l’optimisation de grandes quantités de calculs. Il est notamment utilisé pour simuler de très (très) grand automates cellulaires[1]. Sauf qu’ici, on l’utilise, non pas pour prédire des résultats, mais pour en éviter. Il ne s’agit donc pas d’optimisation. Ce genre d’algo de mémoisation peut être difficile à implémenter d’autant qu’ici, nous souhaiterions que les résultats des précédents mélanges soient retenus d’une exécution de l’appli à l’autre donc inscrire les résultats dans un fichier à chaque fermeture et les recharger à chaque ouverture. Notre algo étant suffisamment performant, je ne testerais pas cette méthode.

Par curiosité, tout de même, testons la première méthode sur 500 éléments et voyons si la variance peut significativement augmenter. Modifions notre fonction shuffle()  comme ceci :

Pour rappel, la variable size  est initialisée à la taille de la liste à la construction de notre classe Shuffler donc notre objet Random nous retournera un entier compris entre 0 et la taille de la liste. Il suffit de lui ajouter 2 fois la taille de la liste pour que le résultat soit compris entre 2n et 3n. Les résultats semblent sensiblement meilleurs. On obtient alors des variances de 0.10, 0.6, 1.7 et 4.2 contre 1.2, 0.8, 2.3 et 6.4.

Cela semble encourageant. Comme ça ne me coûte rien, j’ai fait aussi le test sur 2000 éléments et une nouvelle fois, cette méthode se révèle meilleure que la première version de l’algo. On obtient respectivement 0.03, 0.16, 0.3, 0.8 contre 0.07, 0.4, 1.16 et 3.11 pour 100, 500, 1000 et 2000 mélanges. Il semble que cette version fasse considérablement infléchir la variance avec l’augmentation du nombre de mélanges et d’éléments.

Tout ceci est prometteur mais il se trouve que le SDK Java a aussi son algo de mélange dans la classe Collections . Voyons si cela vaut le coup de l’utiliser. J’agrémente donc ma classe Shuffler  de la méthode suivante :

J’obtiens les variances suivantes : 0.10, 0.6, 1.5, 3.7 contre 0.10, 0.6, 1.7 et 4.2 sur une liste de 500 éléments pour, respectivement, 100, 500, 1000, 2000 mélanges.

Meh…
Sur 2000 éléments, mon algo se prend aussi une monumentale tatouillée : 0.02, 0.13, 0.29 et 0.66, contre 0.07, 0.4, 1.16 et 3.11 pour, respectivement, 100, 500, 1000, 2000 mélanges.

Bon, soyons honnêtes, j’ai conçu cet algo en 5 minutes dans ma tête juste pour le fun et j’ai pris soin d’écrire du code de test pour les besoins de cet article. Je n’avais aucun espoir que mon algo batte celui des ingénieurs de chez Java qui ont probablement plus de connaissances que moi dans le domaine. Mais peut-être peut-il se rattraper sur la vitesse d’exécution (soyons optimistes ! :p) ?

Benchmark

Pour mesurer le temps d’exécution de chaque méthode, nous allons, comme avant, procéder à 100, 500, 1000 et 2000 mélanges successifs. La différence, c’est que nous allons noter l’heure système avant et après l’exécution. La différence nous donnera le temps d’exécution. Rajoutons la méthode suivante dans la classe Shuffler :

Elle va tester la fonction de mélange maison de Java. Ensuite, nous remplacerons :

par :

pour voir si ma méthode est plus performante (lol). Les résultats sont donc :

  • 0.051 secondes pour 100 mélanges,
  • 0.032 secondes pour 500 mélanges,
  • 0.068 secondes pour 1000 mélanges,
  • 0.114 secondes pour 2000 mélanges.

C’est très compétitif ! Et on voit qu’en plus d’afficher de très bons scores, la méthode a un temps d’exécution presque constant. Voyons si ma méthode peut faire mieux :

  • 0.401 secondes pour 100 mélanges,
  • 1.107 secondes pour 500 mélanges,
  • 2.176 secondes pour 1000 mélanges,
  • 4.241 secondes pour 2000 mélanges.

 

nowai

J’ai honte… Je vous laisse, je vais aller me rouler en boule dans un coin pour pleurer…

Conclusion

La méthode du SDK de Java est plus performante que la mienne en tout point (aille). En plus d’être plus fiable que la mienne en affichant une variance plus de deux fois plus stable, elle affiche un temps d’exécution de 8 à 37 fois plus rapide que la mienne. Donc si je peux donner un conseil aux jeunes étudiant(e)s qui commencent la programmation : ne vous prenez jamais pour des brutes en essayant de réinventer la roue. N’écrivez pas une seule fonction si vous n’êtes pas absolument certains qu’une API ne peut pas le faire pour vous. Utiliser des API au maximum a en plus un autre avantage : vous éloignez le risque de bugs dûs à votre code et l’externalisez vers une API utilisée par plus de monde et qui a donc plus de chances d’être fiable.

Post scriptum

L’algorithme utilisé par Collections.shuffle() n’est en fait pas spécialement différent du mien. Vous pouvez le consulter ici, il commence à la ligne 496. Le voici :

Ce qui est très étonnant, c’est qu’avant de procéder au mélange, l’algorithme jette la liste dans un tableau, procède au mélange dans le tableau puis réinsère chaque élément à sa nouvelle place. Il y a donc au total 3 parcours complets de la liste : la première fois pour la jeter dans un tableau, la seconde pour échanger chaque élément avec un autre, aléatoirement, la troisième, pour réinsérer chaque élément à sa nouvelle place dans la liste. L’algo a donc une complexité algorithmique de l’ordre de O(3n) alors que le mien avait une complexité algorithmique de O(2n).

J’ai deux hypotèses qui pouraient expliquer que l’algo de Java soit plus performant que le mien :

  • les accès à un élément (lecture ou écriture) sont en temps constant pour un tableau mais en temps linéaire (O(n)) pour une liste,
  • j’ai écrit mon algo en Groovy qui est un langage interprété ce qui signifie des pertes de performances.

La source de la classe LinkedList de Java que j’ai trouvé ici (ligne 523) me conforte dans la première hypothèse (sans exclure la seconde). Les méthodes get(int index)  et set(int index, T o) ne semblent pas aussi simples qu’un accès dans un tableau. Voyez plutôt :

Bref, je suis content, j’étais quand-même sur la bonne voie avec mon algo ! o/

Notes de bas de page :
  1. Comme l’algorithme Hashlife qui vise à simuler de très grands plateaux de jeu de la vie. Voir, par exemple cette vidéo

Aucun avis pertinent dans Formalisation d'un algo de mélange (en Groovy)

Laisser un commentaire

indique des champs obligatoire.