search

pagination-problem / tree_structure

0 stars 0 forks source link

Renumérotation continue des symboles à partir de zéro #8

Closed laowantong closed 4 years ago

laowantong commented 4 years ago

Fait

Par rapport au dernier point d'étape sur le refactoring, j'ai fait principalement trois choses :

  1. Renommage de size en weight (on était d'accord) et suppression de la méthode __len__() de tile, qui prêtait fortement à confusion.
  2. Choix de noms plus explicites pour certaines variables du FPTAS, à mesure où je comprenais à quoi elles servaient. Par exemple:
    • matrix, qui décrivait un type et non sa sémantique, est devenu costs.
    • a, b, i, j, k, etc. sont devenues respectivement w1 (pour poids dans le bin 1), w2, new (pour numéro de la nouvelle tuile à placer), last1 (pour numéro de la dernière tuile ajoutée dans le bin), last2, etc. Les noms d'une lettre sont super en maths, mais en programmation c'est plus douteux, même s'il y a un équilibre à trouver pour que les expressions ne soient pas trop longues (d'où w1 au lieu de weight1, mais c'est déjà plus parlant que a).
  3. Renumérotation continue des symboles à partir de zéro. Cela évite déjà de devoir écrire du code tordu pour gérer des matrices creuses, des offsets, une notion de feuille, etc.. Surtout c'est un premier pas vers la vectorisation, à laquelle je vais enfin pouvoir m'attaquer. Voilà ce que donne ton instance fétiche après renumérotation (soit dit en passant, ce genre de commentaires me paraît plus à sa place dans un test que dans le code lui-même, puisqu'il permet de documenter un exemple actionnable) : https://github.com/pagination-problem/tree_structure/blob/c85f9a608ceb5d316e4d8b247e378ad6930f6b45/tests/test_fptas.py#L19-L31 et voici ce que devient la matrice des coûts : https://github.com/pagination-problem/tree_structure/blob/c85f9a608ceb5d316e4d8b247e378ad6930f6b45/tests/test_fptas.py#L36-L48 J'ai conservé le principe fondamental de ton algorithme, que je trouve très élégant, mais, pour des raisons de facilité d'implantation, ai légèrement modifié la structure de ta matrice triangulaire. Je n'avais plus de colonne 0 pour placer les poids des tuiles isolés, je les ai donc mis en colonne -1. Lors du remplissage initial, j'ai opté pour une répétition de ces poids sur chaque colonne, cela évitait une boucle dédiée pour l'initialisation de la colonne -1. Ceci dit, les seules valeurs auxquelles je fais accès dans la suite sont le triangle inférieur (strictement) à la diagonale, ainsi que la dernière colonne. Toutes les autres valeurs peuvent être quelconques. J'ai un peu regardé si une structure encore plus compacte (en N^2/2) pouvait être appropriée, mais je n'ai pas eu l'impression.

À faire

J'ai eu d'autres idées, mais qui ne me reviennent pas pour le moment.

SarahMinich commented 4 years ago

Fait

  1. ok !

  2. Je suis d'accord que ce n'était pas des bons noms (même dans le pseudocode) car ils n'étaient pas parlant mais puisque c'est la coutume dans le pseudocode, je l'ai suivie. Et de la même manière, comme j'avais le pseudocode en tête quand j'ai codé et au cas où Imed voudrait relire, j'ai gardé les mêmes conventions.

  3. La notion de feuille est normalement très importante puisqu'avec la racine, elles délimitent le début et la fin d'une tuile. Fin du 3 : C'est noté !

A faire :

  1. Le test qu'on a mis en place n'est pas là pour vérifier ça ? Celui qui compare à une instance déjà exécutée et vérifiée ?

  2. J'aimerais trouver le bug dans 2-tile avant de me plonger dans autre chose mais on peut en parler comme ça je pourrai commencer dès que j'aurais résolu cet étrange problème.

  3. Alors je suis tout à fait d'accord, au moins d'un point de vue algorithmique, qu'il serait sûrement plus efficace de choisir les représentants au fur et à mesure, je ne sais pas pourquoi Imed écrit toujours cette étape à part.

  4. D'accord !

  5. Tout à fait. On fait un back track en partant de la valeur de Cmax. Sachant qu'on sait quelle tuile on a placé en dernier et où est-ce qu'on l'a placé, on peut remonter d'un cran, Cmax devient égal à Cmax - somme poids dans la tuile , etc.

  6. L'algorithme ne peut pas marcher si les tuiles ne sont pas traitées dans le bon ordre (le bon ordre étant : soit de la gauche vers la droite, soit de la droite vers la gauche quand on regarde les feuilles dans une représentation graphique de l'arbre avec un parcours en largeur d'abord). Si on reprend l'exemple que vous avez cité dans votre post, il faut parcourir les tuiles de la tuile terminant par la feuille n°6 à la tuile terminant par la feuille n°10 (ou inversement) sinon on ne peut pas s'appuyer sur la matrice costspour calculer l'augmentation du remplissage des pages. Seules les heuristiques basic FPTAS et improved FPTAS ont besoin de ce tri, une autre heuristique n'en aura pas forcément besoin. C'est pourquoi je n'ai pas trié les tuiles dans l'input de mon problème directement.

laowantong commented 4 years ago

La notion de feuille est normalement très importante puisqu'avec la racine, elles délimitent le début et la fin d'une tuile.

Je revois pas l'utilité de la conserver au-delà de la génération. Une tuile est un ensemble, il n'y a pas de notion de début et de fin. Étant donné que lors de la génération, la numérotation s'est faite en largeur d'abord, que la renumérotation a conservé cet ordre, un simple tri numérique à l'issue de la génération suffit à assurer la propriété que tu rappelles en 6.

Le test qu'on a mis en place n'est pas là pour vérifier ça ? Celui qui compare à une instance déjà exécutée et vérifiée ?

Encore une fois, je ne l'ai revérifié que superficiellement avec la nouvelle numérotation. Tu peux reprendre ton déroulement à la main et renuméroter sur ton papier pour vérifier précisément les étapes (j'ai ajouté le log des étapes dans test_fptas.py), ça devrait être assez rapide.

On fait un back track en partant de la valeur de Cmax

Ok, je vais écrire ça, je ne l'ai vu nulle part.

codecov-io commented 4 years ago

Codecov Report

Merging #8 into master will not change coverage by %. The diff coverage is n/a.

Impacted file tree graph

@@           Coverage Diff           @@
##           master       #8   +/-   ##
=======================================
  Coverage   68.76%   68.76%           
=======================================
  Files           8        8           
  Lines         317      317           
=======================================
  Hits          218      218           
  Misses         99       99

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update 515bc6a...515bc6a. Read the comment docs.

laowantong commented 4 years ago

J'ai coché dans ma liste initiale ce qui est effectivement fait, à savoir :

Ce qui reste à faire :

SarahMinich commented 4 years ago

Voici un petit document qui récapitule le fonctionnement du deuxième FPTAS et la raison de pourquoi on l'appelle «improved» FPTAS même si pour le moment, les résultats expérimentaux disent le contraire. J'espère que ça vous aidera à le comprendre ! document.pdf

laowantong commented 4 years ago

Il y a des différences par rapport à l'article qui est dans Dropbox ?

SarahMinich commented 4 years ago

Sur le fond, il n'y a pas de différence. Dans le document que j'ai mis dans mon commentaire précédent, j'ai juste élagué et j'ai été à l'essentiel concernant le deuxième FPTAS.

laowantong commented 4 years ago

Avec le backtracking du FPTAS « amélioré », ces 6 derniers commits devraient clore le refactoring entrepris depuis... un certain temps.

@SarahMinich Voici un résumé de ce que j'ai fait ces deux jours-ci, ainsi que mes conclusions après discussion avec Imed.

Équivalence des deux FPTAS

Conformément à ce que je soupçonnais, les deux FPTAS sont strictement équivalents, c'est-à-dire qu'ils génèrent dans tous les cas exactement la même suite d'états. Je l'ai vérifié dans un premier temps expérimentalement par des tests, et m'en suis convaincu formellement par refactoring graduel. L'avantage du FPTAS « amélioré » se limite à montrer que la complexité du FPTAS « simple » est en fait inférieure à celle qui a été précédemment évaluée en multipliant brutalement les tailles des domaines des 4 variables d'état. Brutalement, parce que les valeurs des deux derniers termes, disons (i, j), du quadruplet ne sont pas indépendantes. L’un de ces i ou j est nécessairement égal au numéro de la tuile courante - 1. Donc il n’y a que 2 m choix au pire des cas, et non m m. À mon sens, ce raisonnement peut très bien être mené sur le FPTAS simple, ce qui rend inutile le détour par un FPTAS soi-disant « amélioré ». Celui-ci est en effet surtout « embrouillé » : du fait du jeu d'escamotage sur le troisième slot, il est très difficile de comprendre ce qui se passe, d'ailleurs tu n'avais manifestement pas réalisé non plus qu'il était équivalent au premier, et ceci malgré mes questions de plus en plus insistantes sur le sujet.

Note bien que j'ai cru moi-même un temps qu'il pouvait donner des résultats différents du FPTAS « simple » : c'était dû à une erreur dans ton implantation de la fonction de choix du représentant, que j'avais reproduite de confiance quand j'ai repris ton code. J'explique ça dans la section suivante.

Correction du choix du représentant

Quand on fait:

https://github.com/pagination-problem/tree_structure/blob/d7a4d52f5ac0dad052d002f696efadcbb019282d/deprecated/fptas.py#L66

... on ne compare pas seulement les deux premiers termes (le couple de poids) mais l'ensemble du quadruplet. Cela n'a pas d'incidence sur la qualité du résultat, mais introduit une sorte de « non-déterminisme » dans le choix de deux couples équivalents. D'où les différences constatées ici et là entre les séquences d'états des FPTAS simple et « amélioré ». Elles disparaissent dès que l'on restreint la comparaison aux deux premiers termes :

https://github.com/pagination-problem/tree_structure/blob/d7a4d52f5ac0dad052d002f696efadcbb019282d/solver_fptas.py#L94

La deuxième erreur se trouve a priori également dans ton article, même si, vu le flou artistique avec lequel est exprimée la règle de dominance (cf. algorithme 3 page 15, déjà signalé)...

image

... je serais enclin à t'accorder le bénéfice du doute. Dans ton algorithme en tout cas, un représentant est identifié par son couple de poids « discrétisés ». Dans les faits, il faut compléter cet identifiant avec les deux derniers termes du quadruplet. C'est du moins ce que veut Imed, à qui j'ai réussi à extorquer (au terme d'efforts surhumains) une véritable formulation mathématique :

IMG_2378

Les modifications correspondantes sont ici : 9da5182.

À propos, cela justifie les calculs de complexité (qui ne correspondait pas à celle de tes implantations), tout en faisant au passage exploser le nombre d'états : du coup, j'ai dû augmenter la valeur de epsilon dans mes tests.

Backtracking

Tu l'as déjà compris, je n'éprouve aucune tendresse pour le FPTAS lourd et tordu qui se drape indûment dans le qualificatif d'« amélioré ». Il n'y a aucune raison de le faire apparaître où que ce soit. Avant de l'oublier à tout jamais, en espérant ainsi recouvrer quelque peu ma santé mentale, j'ai décidé cependant de le pourvoir lui aussi d'une fonctionnalité de backtracking.

Je ne voyais pas comment les informations stockées permettait de le faire, et tu ne me semblais pas non plus capable de le faire. Après avoir essayé quelques moments sur un exemple, j'ai sollicité Imed. Il m'a rapidement confirmé que c'est impossible. Les informations stockées dans les états ne sont pas suffisantes. Je suppose que tu ne l'avais pas vu non plus, car sinon tu me l'aurais sans doute dit quand je t'ai annoncé que je m'attaquais au problème ?

Bref, comme de toute façon cet algorithme n'a pas d'avenir, je n'ai pas cherché l'élégance ou l'économie : lors de la génération des états, j'ai juste suffixé au quadruplet le couple des dernières tuiles dans chaque bin (technique déjà utilisée pour le FPTAS normal). Cela m'a permis de réutiliser la fonction de backtracking déjà écrite.

Voir ici : 45819d5.

J'ai donc pu augmenter les rapports d'exécution, non seulement des résultats effectifs des algorithmes, mais aussi du log complet (quand il n'était pas d'une longueur excessive) des états générés. Cela permet de vérifier à la main leur fonctionnement sur des petites instances, et de se prémunir de régression sur les autres.

Voir ici : d7a4d52.

Conclusion

Sauf erreur de ma part, que tu ne manqueras pas de me signaler avec précision, clarté et exemples exécutables à l'appui, je devrais maintenant pouvoir (enfin) m'attaquer à l'aspect performances.

SarahMinich commented 4 years ago

Équivalence des deux FPTAS

Merci pour cet avancement, c'est une bonne chose de le savoir. Je modifierai l'article en conséquence. Imed est donc également au courant de cela ? Peut-on "officiellement" laisser tomber ce deuxième FPTAS ?

Correction du choix du représentant

Je suis désolée de cette erreur. Je me souviens avoir eu du mal à me débrouiller à gérer les trois "dimensions" dans ce choix et il est évident que j'ai merdé.

Backtracking

D'accord !

laowantong commented 4 years ago

Imed est donc également au courant de cela ? Peut-on "officiellement" laisser tomber ce deuxième FPTAS ?

@imedk est au courant, je le mentionne pour qu'il confirme qu'il a vu la conséquence du fait qu'on peut prouver la bonne complexité à partir du FPTAS de base. Le deuxième étant équivalent, mais plus lent en temps d'exécution, plus difficile à comprendre et compliquant aussi le backtracking, je ne vois pas ce qui lui reste pour être aimé.

Ceci dit, à ta place je ne me poserais certainement pas la question de savoir ce qu'en pense tel ou tel. Tu as dit que tu allais modifier l'article en conséquence, ce qui est la bonne réaction. Ensuite, de deux choses l'une : soit tu arrives à prouver la complexité voulue pour le premier FPTAS, et dans ce cas le deuxième est inutile ; soit tu trouves une faille, et dans ce cas il y a matière à réflexion.