search

pagination-problem / tree_structure

0 stars 0 forks source link

Génération des instances #6

Closed laowantong closed 4 years ago

laowantong commented 4 years ago
  1. Pourquoi n'y a-t-il pas d'instances de petite taille dans ta base ? En fait seule la configuration type_3a_epsilon-0.3.json déclare moins de 100 tuiles (40).
  2. Y en a-t-il qui puissent être traitées rapidement (moins d'une seconde) ?
  3. Où sont les programmes de génération de ces instances ?
  4. Pourquoi as-tu utilisé un seed flottant ?
SarahMinich commented 4 years ago

  1. Non effectivement, je n'ai pas fait beaucoup d'instances de petites tailles car il me semble que les modèles linéaires arrivaient à résoudre ce problème quand il y avait peu de tuiles, ça n'avait donc pas beaucoup d'intérêt.

  2. Il en faut plus que les quelques toutes petites instances de tests ?

  3. Vous m'aviez dit de ne pas les mettre tout de suite en ligne (mais j'ai oublié la raison), je les ajoute au dossier.

  4. Je ne trouve pas de seeddans mon code et pourtant je viens de passer en revue tout le dossier des deux branches master et refactoring donc je ne peux pas vous répondre.

SarahMinich commented 4 years ago

Re réponse pour le 3. Dans quelle branche voulez-vous que je mette le code de génération d'instances ? Le master ?

laowantong commented 4 years ago
  1. Je pense qu'il faut des problèmes de toutes tailles : petites, moyennes, grosses, avec une progression continue. Ça permet de voir où un algo « décroche » en termes d'efficacité et de capacité à trouver l'optimum. Ça permet aussi d'avoir un jeu d'instances raisonnable en termes de variété / brièveté / rapidité d'exécution pour faire des tests.
  2. Cf. 1.
  3. Probablement un malentendu.
  4. Exemple: https://github.com/pagination-problem/tree_structure/blob/54d7dc35d65b77cfeb1d7174a70936f9a15e10d4/inputs/200-tiles/H8-nbT200-001.json#L655 Je suppose que tu es au courant des limitations du standard IEEE pour la représentation des flottants. Il faudrait utiliser des entiers. À moins que tu aies eu une raison particulière pour choisir des flottants, mais si tu ne sais même pas où ça se trouve, il ne semble pas.
laowantong commented 4 years ago

Oui, dans le master. C'est moi qui gère la branche refactoring.

SarahMinich commented 4 years ago
  1. D'accord, j'en ferai de nouvelles alors. Pour le moment, il y a trois types d'instances, chacune testant l'impact d'un paramètre sur les performances (= nombre d'états générés et temps d'exécution) des FPTAS.
    • Le type 1 teste l'impact de la hauteur de l'arbre.
    • Le type 2 teste l'impact de la valeur de P.
    • Le type 3 teste l'impact du nombre de tuiles.

Cependant, le dossier Type 2 a disparu et je ne me souviens pas l'avoir supprimé ou déplacé. Savez-vous ce qu'il est devenu ?

  1. X

  2. Très bien, je l'upload dans le master après avoir publié ce commentaire

  3. Oui je n'aime pas utiliser les float à cause de ça. Il y a effectivement un seed dans des instances mais j'ai vite laissé tomber car il ne m'est pas nécessaire. En effet, je n'ai pas besoin de me souvenir du seed d'une instance car je n'ai pas besoin de pouvoir retrouver les conditions dans lesquelles elle a été créée (contrairement à un algo randomisé où il peut être intéressant de retrouver les conditions d'exécution).

laowantong commented 4 years ago

Ces dossiers ou fichiers semblent n'avoir jamais été placés sous contrôle de version, donc de leur création à leur destruction ils ne sont jamais sortis de ton disque dur.

Je vais sans doute devoir les réécrire de toute façon. Si j'arrive à comprendre ce que tu as fait.

SarahMinich commented 4 years ago

Je suis surprise de ne pas les avoir mis en ligne en même temps que les autres types mais bon ce n'est pas bien grave. Y a t'il un autre moyen que de regarder la liste de tous les commits pour avoir l'historique des créations et des suppressions ?

laowantong commented 4 years ago

En d7d9a13 j'ai terminé la génération d'instances aléatoires. Je ne versionne pas pour l'instant les résultats, mais tu peux les recréer à l'identique chez toi en exécutant instance_maker.py. Cherche-les ensuite dans le dossier instances/1_results qui sera créé automatiquement.

Quand tu lances ce script, il va lire le fichier de configuration suivant:

https://github.com/pagination-problem/tree_structure/blob/d7d9a139a6c277ad81e9c892d6604cfce8a77f22/instances/1_config.json#L1-L14

La plupart des champs devraient se passer d'explication. Lors de la génération d'une instance, tous les paramètres entiers arg tels que le fichier de configuration contient deux champs min_arg et max_arg sont tirés aléatoirement entre ces deux bornes (incluses). Il s'agit dans l'ordre de :

Note que j'ai laissé la possibilité de prendre comme support des arbres non seulement binaires, mais ternaires, etc. (champ arity). J'ai modifié le template pour les noms de fichiers et y ai concaténé une valeur de hachage calculée à partir du contenu caractéristique (à savoir, tuiles + poids).

Tu me diras si c'est ok pour toi ou s'il y a d'autres besoins.

SarahMinich commented 4 years ago

On peut tout à faire parler de poids plutôt que de tailles des symboles, je n'ai pas de préférence.

Pourquoi ne pas avoir gardé un numéro d'instance ?

Par contre, je ne pourrai plus facilement faire des groupes d'instances ayant toutes le même nombre de tuiles et j'ai peur que ce soit gênant pour les tests des FPTAS.

laowantong commented 4 years ago
  1. Pour les poids, disons que comme on parle déjà de taille pour les tuiles (nombre de symboles), parler de taille aussi pour les symboles revient à dire que la taille d'une tuile n'est pas égale à la somme de la taille de ses symboles constituants. Parler de poids permet de définir, outre le poids d'un symbole, celui d'une tuile (distinct, donc, de sa taille). EDIT: non, dans ton code je vois qu'il y a une longueur length de tuile qui est la somme des size de symboles. Pour l'instant je ne vais pas toucher ces notations, qui selon moi devraient être mises à plat une bonne fois pour toutes.
  2. Je n'ai pas gardé les numéros d'instances, car ceux-ci n'avaient pas de relation avec les « données-métier » et n'étaient pas non plus des identifiants. Je les ai remplacés par une empreinte qui possède ces deux propriétés.
  3. Tu veux dire, faire ce genre de choses ? image En quoi est-ce difficile ? Si tu veux vraiment générer des tonnes d'instances ayant le même nombre de tuiles, et que celles-là (ce dont l'intérêt ne me saute toujours pas aux yeux), je peux ajouter deux paramètres optionnels min_tile_count et max_tile_count dans le fichier de configuration pour ne garder que les résultats voulus.
SarahMinich commented 4 years ago

  1. Je comprends tout à fait le problème et c'est pour ça que je suis d'accord pour changer de terme. On parlera dorénavant de poids de symbole et de taille de tuile.

  2. Vu qu'il y a la fonction de hachage, j'imagine qu'il y a peu de risque que deux instances aient le même nom car elles ont les mêmes caractéristiques ? Et j'avais nommé les instances avec leurs caractéristiques au début puis un numéro pour dire «voici la 56ème instance de type 100 tuiles, hauteur 8 etc.» Parce que là actuellement les noms de fichiers sont assez indigestes.

  3. Imed m'a demandé de générer des instances avec un certain nombre de tuiles donc je fais en sorte de pouvoir le faire. Vous m'avez demandé mon avis sur la nouvelle façon de générer des instances, je vous fais donc part des problèmes qui me viennent à l'esprit.

laowantong commented 4 years ago
  1. Ok.
  2. Je peux te proposer une alternative qui a un sens. Numéroter consécutivement, mais en préfixant par la valeur du germe du générateur aléatoire.
laowantong commented 4 years ago

Finalement je pense préférable de garder l'idée d'une empreinte caractérisant l'instance, pas le processus pour la générer. Pour un compromis entre probabilité de collisions et lisibilité, j'ai opté pour une empreinte de 4 caractères en base 36.