projet-programmation-imperative/doc/rapport.md

Rapport de projet de programmation impérative

groupe GH-05

Maxime Dubaux

Laurent Fainsin

Introduction

Lors de ce projet nous avons implémenté un algorithme permettant de caculer le PageRank pour un réseau donné. Nous l'avons construit à partir de la methode des raffinages. Nous utiliserons le langage de programmation compilé Ada. Le rapport sera construit de la manière suivante :

1. Architecture des applications
2. Presentation et explication des principaux choix
3. Performance
4. Conclusion
5. Apport personnel

https://en.wikipedia.org/wiki/PageRank

Résumé du sujet

Le PageRank est un algorithme d'analyse des liens entre des pages Web dans un réseau, il mesure la popularité des pages dans celui-ci. En outre il trie les pages internet de la plus populaire à la moins populaire selon des principes simples :

• Une page est respectable si d'autre page la reference, et d'autant plus si elle meme sont populaire.
• Néanmois il faut ajuster la popularité selon la page qui reference, plus une page possède de lien vers d'autre site moins les referencements(il) on de valeur. Pour eviter des pages avec de nombreux hyperliens qui pourraient fausser l'echelle.

insérer image ici

A l'aide du théoreme de point fixe, il peut se résume en un calcul répété d'un produit vecteur-matrice.

Toute la difficulté provient de la taille massive que peut avoir le réseau. Il faut donc choisir les bonnes de structures de données. Il est notamment utilisé par le moteur de recherche Google qui estime leur réseaux à une cinquantaine de milliards de pages.

Architecture

Organisation des modules

Module générique Vector

Module générique Google Naif

Module générique Google Creux

Organisation de l'algorithme du calcul du pageRank

Structures de données (Presentation et explication des principaux choix)

Nous avons besoin d'une structure pour stocker le poids de chaque pages (i.e. sa popularité), nous appellerons cette structure pi. De même, nous avons besoin d'une structure pour stocker le réseau network décrivant les liens entre chaque pages du réseau.

TODO faire la même pour G

Nous connaissons à l'avance les tailles des différentes structures, car le réseau est connu. Il n'est donc pas nécéssaire de créer des types dynamiques (i.e. LCA, TH...), un simple stockage dans le stack suffit.

Notons N le nombre de pages dans le réseau, et N_Links le nombre de liens total dans le réseau.

Ainsi pour stocker pi, nous choissons la structure d'un vecteur statique (array) de dimension 1xN.

afficher extrait de pi

De même, pour stocker le réseau nous choisissons la structure d'une matrice de dimension 2xN_Links.

afficher extrait de network

Pour stocker G, la matrice de Google, nous avons 2 choix:

• Une Matrice Naif
• Une Matrice creuse

Implémentation Naif

Le premier choix consiste à stocker la matrice très Naifment, c'est-à-dire en stockant l'ensemble de ses valeurs dans une matrice de taille NxN.

L'avantage principale de cette structure est que sa construction et sa manipulation (produit vecteur/matrice) est simple. Pour la construire à partir du réseau nous assignons à chaque lien une valeur dans la matrice. De même celle-ci à l'avantage d'être robuste par défaut à la présence de doublons dans le réseau.

L'inconvénient est que nous stockons beaucoup de valeurs inutiles (i.e. des éléments qui se répètent ou bien qui sont égals à 0). Ainsi puisque un produit vecteur/matrice est de compléxité N^2, nous perdons beaucoup de temps à effectuer des opérations inutiles.

Implémentation Creuse

Il faut alors nous orienter vers une autre solution

Pour alléger la taille mémoire de la matrice G, nous pouvons la rendre creuse, c'est-à-dire de ne pas stocker les valeurs nulles de celle-ci.

Cependant nous pouvons aller encore plus loin en compressant G via un algorithme de compression simple: https://en.wikipedia.org/wiki/Sparse_matrix#Compressed_sparse_row_(CSR,_CRS_or_Yale_format)

De cette manière nous ne gardons que les informations qui sont essentielles.

L'inconvénient de cette méthode est que la création de ce type de matrice et son utilisation est plus compliqué que pour une matrice Naif.

Mais l'avantage de cette structure de donnée est son gain d'espace non négligeable ainsi que la rapidité qu'elle propose puisque nous n'effectuons plus que N_Links opérations lors du produit vecteur/matrice, au lieu de N^2 pour la version Naif.

Performance

Conclusion

On remaque facilement la supériorité temporelle et spatiale de la version creuse contre la version Naif.

Améliorations encore possible:

Lors de l'implémentation de la matrice compressé, nous avons choisis de compressé les lignes puisque celle-ci peuvent parfois être entièrement vide, cela est bénéfique d'un point de vu espace. Cepedant ils serait aussi intéressant de compresser G selon les colonnes puisque, bien que l'on perde en espace mémoire, on gagnerait en efficacité temporelle grâce au nombre réduit d'accès mémoire que l'on effecturait par rapport à la compression par ligne.

Il est important de noter qu'un compression par colonne permettrait aussi de paralléliser la problème, le rendant encore plus efficace temporellement. Il est assez simple d'implémenter la parallélisation en Ada puisque cette notion fait partie à part entière du langage de programmation, mais nous ne l'avons pas implémenté par manque de temps.

Apports personnels

Ce projet nous a permis de solidifer nos connaissances sur les structures de données, car nous avons longuement réfléchi sur lequelles étaient les plus adaptées au problème. De même nous avons eu l'occasion de revoir plusieurs algorithme classique, nous permettant de mieux les maitriser.