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

Posté par .
Tags : aucun
0
23
déc.
2005
J'ai maintenant la presque totalité de mes CDs sur un DD externe au format FLAC, et le problème de sauvegarde 'intelligente' se pose. Ayant un graveur DVD, j'me suis dit: et bien je vais tout graver! Oui, mais il se pose un problème: Comment dispatcher automatiquement mes répertoires CD (1 dossier par CD) dans des répertoires à graver (donc contenant maximum 4,7 Go), et ce en perdant le moins de place possible ?

Si quelqu'un a une solution, je suis preneur :-)
  • # .

    Posté par . É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 . É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 . É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.

    ¯ : macron (typographie), petit signe diacritique, qui prétend ne pencher ni à gauche ni à droite, mais se place nettement au dessus des vraies lettres, qu’il considère avec mépris.

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

      Posté par . É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 . É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...

        ¯ : macron (typographie), petit signe diacritique, qui prétend ne pencher ni à gauche ni à droite, mais se place nettement au dessus des vraies lettres, qu’il considère avec mépris.

    • [^] # Petite rectification

      Posté par . É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...

      ¯ : macron (typographie), petit signe diacritique, qui prétend ne pencher ni à gauche ni à droite, mais se place nettement au dessus des vraies lettres, qu’il considère avec mépris.

Suivre le flux des commentaires

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