Forum général.cherche-logiciel Répartir les fichiers dans des dossiers

• # .

  Posté par snt le 23 décembre 2005 à 16:55. Évalué à 4.

  

  J'ai vu ce soft passer sur freshmeat y'a pas longtemps :
  
  http://unix.freshmeat.net/projects/gaffitter/?branch_id=6218(...)
  
  Je sais pas si ça répond à tes besoins :
  "Genetic Algorithm File Fitter (gaffitter) is a command-line tool that uses a genetic algorithm to extract subsets of an input list of files and directories that best fit a given volume size such as a CD or DVD. This is used to find different combinations of the files on the list such that lost space will be minimized."

  • [^] # Re: .

    Posté par Arnaud le 23 décembre 2005 à 22:29. Évalué à 2.

    

    Gaffiter ne semble pas répondre à la problématique multi-volume :-( Il va optimiser un volume, puis après un autre, etc etc, ce qui est moins intéressant qu'une optimisation globale.

• # C'est pas trivial

  Posté par Arthur Accroc le 23 décembre 2005 à 20:10. Évalué à 5.

  

  C'est un problème d'algorithmique non trivial.
  
  On peut trouver des articles dessus en faisant une recherche avec la chaîne bin packing.
  Par exemple, la page http://www.ams.org/featurecolumn/archive/bins1.html présente le problème de manière abordable pour le commun des mortels.
  http://www.loria.fr/~jcohen/enseignement/binpacking.pdf le présente en français de manière très complète, mais plus théorique...
  
  À la base, le problème est dit NP-complet, c'est-à-dire que la recherche de la meilleure solution parmi toutes les solutions possibles est exponentielle.
  La plupart des articles sur le problème s'attachent à trouver un algorithme rapide qui trouve de bonnes solutions (mais pas forcément les meilleures).
  
  Cela dit, tant que le nombre d'éléments manipulés est assez faible, on peut aussi envisager de tester toutes les solutions avec un algorithme bien bourrin du style : calculer toutes les permutations des éléments à classer (leur nombre est la factorielle du nombre d'éléments !) et pour chacune évaluer la qualité de la solution obtenue en rangeant les éléments dans des DVD dans l'ordre où ils sont.
  La fonction d'évaluation des solutions pourrait par exemple être le nombre de DVD utilisés par 4.7*1024 - la place restante sur le dernier en Mo.
  
  Le plus rapide pour toi serait évidemment de trouver un programme déjà tout fait. Cela dit, je suppose que tes fichiers correspondent aux pistes et sont classés en répertoires correspondants aux CD et que tu ne tiens pas à les mélanger. Je crains un peu que les logiciels existants (en tout cas ceux que j'ai vus) traitent le problème fichier par fichier...
  
  Bonne chance.

  « Le fascisme c’est la gangrène, à Santiago comme à Paris. » — Renaud, Hexagone

  • [^] # Re: C'est pas trivial

    Posté par Arnaud le 23 décembre 2005 à 22:34. Évalué à 2.

    

    Effectivement, ce n'est pas trivial. Je pense que je vais coder une appli 'brute" en C++/Qt4, sur une approche 'je remplis bêtement' puis j'essaye par permutations d'optimiser un peu, sur un nombre de passes configurables.

    • [^] # Re: C'est pas trivial

      Posté par Arthur Accroc le 24 décembre 2005 à 02:50. Évalué à 2.

      

      sur une approche 'je remplis bêtement' puis

      
      Tu peux peut-être prendre un meilleur point de départ en utilisant une heuristique comme par exemple classer tes éléments dans l'ordre décroissant pour placer les plus gros en premier.
      
      En tout cas, bon courage.
      Je serais curieux de savoir ce que tu vas trouver comme solution intéressante à ton problème...

      « Le fascisme c’est la gangrène, à Santiago comme à Paris. » — Renaud, Hexagone

  • [^] # Petite rectification

    Posté par Arthur Accroc le 24 décembre 2005 à 04:49. Évalué à 2.

    

    Cela dit, tant que le nombre d'éléments manipulés est assez très faible...
    
    Non, je viens de me torcher un petit calcul de factorielle pour me rappeler les ordres de grandeur, et ça croît vraiment très très vite !
    Donc tu peux oublier cette solution-là...
    Notons que plusieurs permutations seraient équivalentes (ordre différent sur un même DVD, échange complet entre deux DVD...) mais que le tester serait aussi long que de tester directement la pertinence de la permutation et qu'on ne peut pas non plus marquer les permutations équivalentes à la permutation courante, faute de mémoire pour contenir un tableau assez grand...

    « Le fascisme c’est la gangrène, à Santiago comme à Paris. » — Renaud, Hexagone

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.