SarahMinich commented 4 years ago

Dans la branche «Ajout fonctionnalités», j'ai ajouté quelques lignes de code pour calculer la moyenne et l'écart type de la distribution des valeurs dans la matrice appelée M(i,j) dans l'article et costs dans le programme.

J'ai dû modifier le code par rapport à la version de vendredi car la moyenne ne doit pas être sur la totalité de la variable costs. En effet, dans cette matrice, il y a des valeurs répétées pour faciliter l'algorithme. Je les ai donc retirées avant de calculer les deux statistiques qui nous intéressaient.

Je mets la vérification que j'ai faite sur l'instance «h=03_t=005_s=011_m=06.json» pour expliquer les étapes du code :

                 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
symbol_weights: [0, 5, 3, 1, 2, 6, 2, 1, 4, 3, 5]

tiles: [
    [0, 1, 3, 6],
    [0, 1, 4, 7],
    [0, 1, 4, 8],
    [0, 2, 5, 9],
    [0, 2, 5, 10]
]

costs: [
    [8, 8, 8, 8, 8],
    [3, 8, 8, 8, 8],
    [6, 4, 11, 11, 11],
    [12, 12, 12, 12, 12],
    [14, 14, 14, 5, 14]
]

epurated_costs:[
    [8],
    [3, 8],
    [6, 4, 11],
    [12, 12, 12, 12],
    [14, 14, 14, 5, 14]
]

flatten_costs:
[8, 3, 8, 6, 4, 11, 12, 12, 12, 12, 14, 14, 14, 5, 14]

mean computed by the program:
9.933333333333334

mean computed by me:
9,9333333333333333333333333333333

codecov-commenter commented 4 years ago

Codecov Report

Merging #20 into master will decrease coverage by 7.27%. The diff coverage is 31.83%.

@@            Coverage Diff             @@
##           master      #20      +/-   ##
==========================================
- Coverage   49.05%   41.77%   -7.28%     
==========================================
  Files           9       10       +1     
  Lines         475      766     +291     
==========================================
+ Hits          233      320      +87     
- Misses        242      446     +204

Impacted Files	Coverage Δ
run_solvers.py	`0.00% <0.00%> (ø)`
verif.py	`0.00% <0.00%> (ø)`
generate_instances.py	`68.31% <71.92%> (+6.09%)`	:arrow_up:
solver_fptas.py	`77.94% <87.50%> (+0.16%)`	:arrow_up:
instance.py	`87.17% <100.00%> (+1.06%)`	:arrow_up:
tile.py	`90.47% <0.00%> (+4.76%)`	:arrow_up:

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 4f37b09...6880c2e. Read the comment docs.

laowantong commented 4 years ago

C'est pas mal, j'ai toutefois fait quelques renommages, je te laisse regarder.

Il y a quand même un gros problème d'architecture à résoudre. En l'état, il a pour conséquence de faire planter run_solvers sur tous les solveurs autres que le FPTAS. Tu n'as toujours pas le réflexe de tester systématiquement tes modifs, et ça inclut bien sûr la regénération des snapshots.

Le problème logique que tu n'as pas vu est que les nouvelles valeurs calculées (moyenne et écart-type) ne font pas partie du résultat, mais des données. Les colonnes correspondantes devraient être dans la partie « instance » (avant step count) et non « solution ». Plus grave, elles devraient être calculées pour tous les solveurs.

Je vois au moins deux solutions possibles pour le refactoring.

La première est :

dans AbstractSolver, créer une méthode set_instance() qui s'occupe de calculer la matrice des coûts et les statistiques associées; cette méthode devra être a priori appelée par les classes héritières à un moment à l'intérieur de leur propre méthode set_instance() (ça se fait avec super().set_instance(instance)).
dans run_solvers.py, découpler l'appel de set_instance() de celui de solve_one(), ce qui permettra d'insérer entre les deux l'affichage des colonnes de la partie « instance ».

Le calcul de la matrice des coûts sera en tout cas fait systématiquement pour tous les solveurs, même ceux qui n'en ont pas besoin, dans ce dernier cas seulement à des fins statistiques. Le temps de calcul devrait être asymptotiquement négligeable devant celui demandé par le solveur.

Une autre solution consisterait à calculer la matrice des coûts et les statistiques associées directement au moment de la création d'une instance. Cela demanderait donc à modifier generate_instances.py ou instance.py, je n'ai pas regardé.

Je te laisse choisir.

SarahMinich commented 4 years ago

Je suis d'accord avec les renommages, je ne voulais pas mettre lower_triangle_costs (que j'avais choisi à la base) de peur que ça fasse un nom trop long mais tant mieux alors !

Effectivement je n'ai pas pensé à relancer sur les snapshots, ce n'est vraiment pas quelque chose avec lequel je suis familière. Je vais le graver dans ma main histoire d'y penser à l'avenir !

Je n'arrive pas à prendre une décision quant à l'appartenance des statistiques à la solution ou aux données du problème mais si vous dites que ça fait partie des données, je me range à votre avis car je n'arrive pas à faire le mien. Je déplacerai donc les lignes de code mais avant de passer au point suivant, j'ai une question. Vous dites

elles devraient être calculées pour tous les solveurs.

Est-ce qu'en l'état actuel des choses, les stats sont en théorie calculées pour tous les solveurs (même si j'ai bien compris que ce n'était pas possible pour naive cut) ? Parce que j'ai essayé de mettre mon ajout là où j'étais sûre que ça serait fait pour tout le monde et donc si ce n'est pas le cas, c'est que je n'ai pas compris quelque chose dans la classe Runner.

Je préfère la deuxième solution car quitte à dire que les stats font partie des données, au temps qu'on les intègre au même endroit que toutes les autres données, qu'en pensez-vous ?

laowantong commented 4 years ago

C'est fait pour tout le monde, c'est d'ailleurs pour ça que ta version modifiée plante pour les solveurs qui n'ont pas d'attribut costs.

Ok pour calculer et stocker la matrice des coûts et les statistiques au moment de la génération des instances.

SarahMinich commented 4 years ago

Le code n'est pas encore fonctionnel car pas du tout fini mais je voulais faire un premier push pour avoir votre avis sur le calcul des stats dans la génération d'instances. Je ne sais pas si c'est bien car j'ai dû recopier du code d'ailleurs pour pouvoir calculer les coûts puis les stats sur ces coûts et généralement, c'est mauvais signe de faire de la duplication de code.

Après ça, il faudra :

[ ] Ajouter la lecture des stat quand on charge une instance
[ ] Recréer un ensemble de snapshots puisqu'il y aura deux nouvelles données
[ ] Insérer les stats dans le tableau de résultats affiché à la fin de run_solvers

Mais je m'interroge. Puisque je calcule les coûts à la génération de l'instance, est-ce que je ne devrais pas les écrire dans le fichier .json de l'instance pour ne pas avoir à les recalculer plus tard quand on chargera cette même instance ?

laowantong commented 4 years ago

generate_instances.py crée des fichiers JSON. Évidemment le but de lui faire calculer les coûts directement est de les écrire dans le fichier JSON.

SarahMinich commented 4 years ago

Mais je ne sais pas comment faire autrement, c'est bien mon souci. Dans la génération d'instances, on ne travaille pas avec des Tiles mais avec des paths et je ne sais pas comment calculer les coûts autrement qu'en manipulant des Tiles. C'est pour ça qu'il y a un premier paragraphe de code qui est dupliqué.

Pour le deuxième il ne sera plus dupliqué puisque le calcul des coûts ne sera fait que dans la génération d'instance puis écrit dans le fichier .json correspond. Cependant, on va avoir des informations dans les fichiers d'instances qui ne seront pas toujours utiles, ce n'est pas un problème ?

laowantong commented 4 years ago

Bon, en programmation, il y a une règle qui ne se discute pas : DRY.

Si pour la respecter ça demande du refactoring, alors il faut le faire.

Si tu ne connais pas Tile à ce niveau, alors adapte le code pour qu'il travaille sur des paths. Ou bien crée une interface autour des calculs de façon à pouvoir les appeler d'ailleurs. En tout cas, jamais de duplication de code.

Désolé d'en rester aux principes, je n'ai pas le temps de me pencher sur les détails d'implantation en ce moment. Essaie jusqu'à trouver une version où tu ne te dis pas « y a un truc qui me plaît pas trop, mais je vais toujours le soumettre à Aristide pour voir si ça passe ». Si ton code est correct, tu auras une satisfaction esthétique, pas un sentiment de gêne. C'est le critère.

SarahMinich commented 4 years ago

Très bien alors je vais essayer d'adapter le code ! Merci pour vos réponses

SarahMinich commented 4 years ago

J'ai l'impression que pour supprimer la dernière duplication de code dans generate_instance.py lignes 87 à 90

#Code from method __init__ of class Instance in instance.py: duplication
d = {s[0]: Symbol(*s) for s in enumerate(self.weights)}
tiles = [Tile([d[i] for i in t]) for t in self.paths]
tile_count = len(tiles)

Il faudrait réécrire beaucoup de code déjà écrit car dans la portion d'après

costs = [[tile.weight] * (tile_count + 1) for tile in tiles]
        for (new, new_tile) in enumerate(tiles):
            for (last, last_tile) in enumerate(tiles[:new]):
                costs[new][last] = sum(symbol.weight for symbol in new_tile - last_tile)

on a besoin de fonctionnalités des tuiles et des symboles (tile.weight, symbol.weight (bon ça a la limite, ce n'est pas très grave puisqu'on a le tableau weights) et aussi new_tile - last_tile) et j'ai l'impression que ça serait "plus grave" de réécrire du code propre aux tuiles ou au symboles que d'écrire à nouveau les trois lignes de conversion.

Je sais que c'est faisable de se passer des lignes 87 à 90 mais j'ai l'impression que ça donnerait un code de moins bonne qualité.

laowantong commented 4 years ago

Est-ce que ça ne peut pas se résoudre en créant une instance de Instance justement ?

SarahMinich commented 4 years ago

Je n'y avais pas pensé, la démarche me semblait un peu trop "commencer par la fin pour voir le début" mais c'est une idée. Je vais y réfléchir ! Merci

SarahMinich commented 4 years ago

Je pense que c'est bon. J'ai dû faire plusieurs modifications dans le code (comme créer un dictionnaire temporaire pour le résultat histoire de ne pas écrire plusieurs fois les mêmes infos), j'espère que ça ira quand même.

laowantong commented 4 years ago

All checks have failed

SarahMinich commented 4 years ago

Je sais, c'était le cas avant aussi mais je ne sais pas très bien ce que Travis teste ni comment il le fait. Je crois qu'il essaye d'exécuter le code sur les snapshots et dans ce cas, ça ne peut que rater car ces snapshots n'ont pas les trois nouveaux champs (la moyenne, l'écart-type et la matrice de coûts). Après, s'il compare les instances générées avec le fichier de config "snapshot.json" avec les snapshots précédents, c'est aussi normal que ça rate puisqu'on ajoute des infos dans les instances.

Je sais que je dois créer de nouveaux snapshots mais comme justement ça touche aux snapshots qui sont le garde fou du projet, j'ai préféré ne pas y toucher sans votre accord

laowantong commented 4 years ago

pytest

SarahMinich commented 4 years ago

pytest a confirmé mes craintes, il se base sur une instance ne possédant pas les nouveaux champs alors voulez-vous que je génère un nouvelle instance ou peut-être que je la complète en ajoutant à la main les champs moyenne, écart-type et matrice des coûts ?

Résultat de pytest :

L'instance en question :

laowantong commented 4 years ago

complète

SarahMinich commented 4 years ago

C'est parti alors !

SarahMinich commented 4 years ago

J'ai créé un dossier «snapshots_» dans le dossier «instances» dans lequel j'ai copié puis modifié les snapshots en y ajoutant les trois nouveaux champs comme convenu : le champ cost_mean, le champ cost_standard_deviation et le champ costs. J'ai ensuite dupliqué le dossier «snapshots» (de résultats cette fois) et j'ai renommé la copie en «snapshots». Ensuite j'ai fait tourné le programme sur les instances de «instances/snapshots» et j'ai regardé les différences avec github dans les fichiers de «solutions/snapshots_». Il y a eu quelques différences au niveau du champ duration_magnitude mais sinon les seules modifications étaient l'ajout des deux champs supplémentaires cost_mean et cost_standard_deviation.

laowantong commented 4 years ago

Je n’ai pas accès à mon ordinateur aujourd’hui. Si tu as juste ajouté les champs demandés ça devrait être ok. Normalement les branches couvrent une bonne partie des besoins qui conduisent à créer des duplicata modifiés comme tu as l’habitude de faire. Ça veut dire que tu peux refaire un seul dossier snapshots. Pour la fusion dans le master, attends juste que je puisse regarder en détails. De toute façon il n’y a pas d’inconvénient à continuer à travailler dans une branche. Complète les tests au besoin.

SarahMinich commented 4 years ago

D'accord je fais comme ça ! Merci.

SarahMinich commented 4 years ago

J'ai un souci et je ne sais pas comment le régler. Les tests (que je lance avec pytest) fonctionnent chez moi mais pas sur la version en ligne et je viens de comprendre pourquoi. Dans le rapport d'erreur fourni par Travis, il y est dit : Est-ce que ça veut dire scipy n'est pas installée quelque part ? Et si oui comment et où dois-je l'installer ?

laowantong commented 4 years ago

Apparemment tu as installé scipy chez toi et tu l'importes. Travis crée une machine virtuelle vierge, et y installe ce que tu lui dis d'installer (ligne 6 de .travis.yml). Tu dois mettre à jour requirements.txt.

https://docs.travis-ci.com/user/languages/python/

SarahMinich commented 4 years ago

Merci beaucoup, je comprends mieux comment ça fonctionne .

SarahMinich commented 4 years ago

Je ne sais pas du tout comment ça se fait, je viens de regénérer les snapshots chez moi et il n'y a qu'un seul champ tiles et les costs sont indentés correctement et pourtant je n'ai rien modifié dans le code

SarahMinich commented 4 years ago

Je me penche plus avant sur la question dans un moment, je dois d'abord terminer mon rapport d'avancement de thèse.

laowantong commented 4 years ago

Ne comprenant pas ton code, je viens de regarder ton PDF d'explications. Je ne sais pas pourquoi tu fais quelque chose d'aussi compliqué. Ne suffisait-il pas simplement de générer un grand nombre d'instances, et de rejeter celles qui ne satisfont pas aux conditions données ? C'est ce que j'ai fait pour toutes les autres conditions, et en rajouter une ne devrait pas prendre plus d'une demi-journée.

SarahMinich commented 4 years ago

J'ai fait un test pour me convaincre de la nécessité de coder cette version compliquée. J'ai généré plusieurs milliards d'ensembles de valeurs (ces valeurs étant choisies aléatoirement dans un intervalle) et j'ai calculé la moyenne de chaque ensemble.

Il n'est jamais arrivé que la moyenne s'éloigne du milieu de l'intervalle : toutes les moyennes se situaient entre 40 % et 60 % de l'intervalle. On ne peut donc pas espérer qu'en bouclant sur le choix aléatoire d'un ensemble de valeurs, on finisse par tomber sur un ensemble dont la moyenne serait, par exemple, entre 10 et 20 % de l'intervalle.

Alors je sais que ce n'était pas exactement mon problème mais puisque ça ne marchait déjà pas sur ce cas facile, je me suis dit que ça ne pourrait pas non plus marcher sur mon problème.

laowantong commented 4 years ago

Bonne démarche, cependant je ne suis pas encore persuadé que la conclusion soit la bonne. Si un tirage uniforme n'est pas adapté, il est toujours possible d'utiliser d'autres algorithmes. La bibliothèque standard random t'en propose une dizaine: https://docs.python.org/3/library/random.html#real-valued-distributions. On en reparle demain.

codecov-io commented 3 years ago

Codecov Report

Merging #20 (8fd51ae) into master (4f37b09) will decrease coverage by 7.33%. The diff coverage is 31.52%.

@@            Coverage Diff             @@
##           master      #20      +/-   ##
==========================================
- Coverage   49.05%   41.72%   -7.34%     
==========================================
  Files           9       10       +1     
  Lines         475      767     +292     
==========================================
+ Hits          233      320      +87     
- Misses        242      447     +205

Impacted Files	Coverage Δ
run_solvers.py	`0.00% <0.00%> (ø)`
verif.py	`0.00% <0.00%> (ø)`
instance.py	`85.00% <50.00%> (-1.12%)`	:arrow_down:
generate_instances.py	`68.31% <71.92%> (+6.09%)`	:arrow_up:
solver_fptas.py	`77.94% <87.50%> (+0.16%)`	:arrow_up:
tile.py	`90.47% <0.00%> (+4.76%)`	:arrow_up:

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 4f37b09...8fd51ae. Read the comment docs.

pagination-problem / tree_structure

Ajout fonctionnalites #20

Codecov Report

Codecov Report