Ubuntu-fr

thurston

Re : [RESOLU] Combiner x repertoires parmi y pour remplir un CD

ben pas de fichier créé justement
A+
Thurston

Totor

Re : [RESOLU] Combiner x repertoires parmi y pour remplir un CD

et quel est le contenu du fichier ./rangedir.tmp ?

---

-- Lucid Lynx --

nicolas66

Re : [RESOLU] Combiner x repertoires parmi y pour remplir un CD

Certe, mais cela ne répond pas à la demande qui est :

Avez vous déjà écrit un script qui permette de déterminer quelle est la combinaison gagnante pour arriver à remplir au mieux un CD?

par ailleurs, j'ai été confronté à un problème de limite numérique du shell ....

Par rapport à la méthode que j'ai présenté, suffit de créer un script qui liste les répertoires avec les tailles des albums et d'écrire le résultat dans `albums.dat'.

Donc à la question fermée "Avez vous déjà écrit un script qui permette de déterminer quelle est la combinaison gagnante pour arriver à remplir au mieux un CD?", je réponds non car je n'ai pas tout écrit. En revanche, je pense avoir donné suffisamment d'infos à ce sujet pour que thurston se débrouille. Ce forum a été créé pour aider ceux qui ont des difficultés pas pour faire le travail à leur place

---

"The computer was born to solve problems that did not exist before." (B. Gates)

thurston

Re : [RESOLU] Combiner x repertoires parmi y pour remplir un CD

@ nicolas66
D'accord avec toi. Le forum est un lieu d'entraide et non une armée d'esclaves au service du demandeur.
J'arrive avec un script sur le sujet d'ici Lundi (week end).
On pourra comparer...et donc partager, car c'est bien le but.
A+
Thurston

Totor

Re : [RESOLU] Combiner x repertoires parmi y pour remplir un CD

Salut !

Je n'ai pas pu me pencher sur le sujet depuis mon premier post. Je vais essayer de produire un autre script ce WE mais dans un autre language car le shell n'est vraiment pas approprié pour ce genre de traitement.

---

-- Lucid Lynx --

thurston

Re : [RESOLU] Combiner x repertoires parmi y pour remplir un CD

Bon alors, je dois etre honnete, mon pote a tout fait, mais c'est un peu mon king of bash au boulot.
Ci joint sa création donc.
Ca marche et même super bien.
A+
Thurston

#!/usr/bin/perl -w

use strict;

# Globals

my @best;               # Best combination found
my $best_size   = 0;    # Size of best combination
my $combs_chkd  = 0;    # Number of combinations checked
my %sizes;              # File sizes
my $target;             # Target size

# Autoflush stdout
# (This is needed for printing progress)

$| = 1;

# Read sizes of all files / dirs in CWD

sub read_sizes()
{
    open(DU, '-|', 'du -bs *');
    while(<DU>)
    {
        chomp;

        my ($size, $file)   = split("\t", $_);
        $sizes{$file}       = $size;
    }
    close(DU);
}

# Find closest combination of sizes to target

sub find_closest(@$@);
sub find_closest(@$@)
{
    my ($set, $size, $rem) = @_;

    my @new_rem = @$rem;

    foreach my $file (@$rem)
    {
        $combs_chkd++;

        # Print progress

        if(!($combs_chkd % 10000))
        {
            print "$combs_chkd combinations checked\r";
        }

        # Check whether combination is better than best seen so far

        my $new_size = $size + $sizes{$file};

        if($new_size > $best_size && $new_size <= $target)
        {
            $best_size  = $new_size;
            @best       = (@$set, $file);
        }

        # Remove file from those remaining to be checked

        shift(@new_rem);

        # Search for closer matches with more files if size is less than target

        if($new_size < $target && @new_rem)
        {
            find_closest([@$set, $file], $new_size, \@new_rem);
        }
    }
}


die "Usage: $0 <target_size>\n" if(@ARGV != 1);
($target) = @ARGV;

read_sizes();
find_closest([], 0, [keys(%sizes)]);

print "$combs_chkd combinations checked.\n";
if(@best)
{
    print "Closest match is $best_size bytes and contains:\n\t";
    print join("\n\t", sort(@best)), "\n";
}
else
{
    die "Nothing in this directory fits within target size.\n";
}

# EOF

nicolas66

Re : [RESOLU] Combiner x repertoires parmi y pour remplir un CD

Ah cool. Un ptit résolu ?

---

"The computer was born to solve problems that did not exist before." (B. Gates)

thurston

Re : [RESOLU] Combiner x repertoires parmi y pour remplir un CD

Et une nouvelle version de mon pote (Stephen), avec une petite upgrade

#!/usr/bin/perl -w

use strict;

# Globals

my @best;               # Best combination found
my $best_size   = 0;    # Size of best combination
my $combs_chkd  = 0;    # Number of combinations checked
my %sizes;              # File sizes
my $target;             # Target size

# Autoflush stdout
# (This is needed for printing progress)

$| = 1;

# Read sizes of all files / dirs in CWD

sub read_sizes()
{
    open(DU, '-|', 'du', '-bs', <*>) or die "Failed to open du: $!\n";
    while(<DU>)
    {
        chomp;

        my ($size, $file)   = split("\t", $_);
        $sizes{$file}       = $size;
    }
    close(DU);
}

# Find closest combination of sizes to target

sub find_closest(@$@);
sub find_closest(@$@)
{
    my ($set, $size, $rem) = @_;

    print 2 ** keys(%sizes) - 1, " combinations max\n" if(!@$set);

    while(my $file = shift(@$rem))
    {
        $combs_chkd++;

        # Print progress

        if(!($combs_chkd % 10000))
        {
            print "$combs_chkd combinations checked\r";
        }

        # Check whether combination is better than best seen so far

        my $new_size = $size + $sizes{$file};

        if($new_size > $best_size && $new_size <= $target)
        {
            $best_size  = $new_size;
            @best       = (@$set, $file);
        }

        # Search for closer matches with more files if size is less than target

        if($new_size < $target && @$rem)
        {
            find_closest([@$set, $file], $new_size, [@$rem]);
        }
    }
    print "$combs_chkd combinations checked\n" if(!@$set);
}


die "Usage: $0 <target_size>\n"     if(@ARGV != 1);
($target) = @ARGV;
die "Target size must be numeric\n" if($target !~ /^\d+$/);

read_sizes();
find_closest([], 0, [sort { $sizes{$b} <=> $sizes{$a} } keys(%sizes)]);

if(@best)
{
    print "Closest match is $best_size bytes and contains:\n\t",
          join("\n\t", sort(@best)), "\n";
}
else
{
    die "Nothing in this directory fits within target size.\n";
}

# EOF

Dernière modification par thurston (Le 25/10/2008, à 08:30)

thurston

Re : [RESOLU] Combiner x repertoires parmi y pour remplir un CD

Le script fonctionne vraiment bien.
Par contre, effectivent 2^n possibilités, ça grimpe vite.
Traiter 20 repertoires prend environ 2 secondes
Traiter 30 repertoires prend environ 2 min.
Et encore, le script est suffisament optimisé pour ne traiter que les cas intéressants.
je veux dire, sur  2 147 483 647 possibilités dans mon cas, seulement 48 434 727 sont étudiées (car les autres ne collent pas), ce qui fait gagner du temps processeur. Soit un rapport de 44 entre les 2. (à comparer par rapport à une approche brutale, qui aurait été de collecter l'ensemble de toutes les possiblités et les comparer seulement après coup (approche c'est vrai un peu...brutos).
C'est aussi une bonne occasion pour changer de processeur. Sur la même tache: P4 2.4GHz ancien: 23 sec, quand un coreduo récent met 2 sec.

Voilà.
A+
Thurston

nicolas66

Re : [RESOLU] Combiner x repertoires parmi y pour remplir un CD

C'est aussi une bonne occasion pour changer de processeur. Sur la même tache: P4 2.4GHz ancien: 23 sec, quand un coreduo récent met 2 sec.

Cherche plutôt à baisser la complexité de tes algos, ca te coûtera beaucoup moins cher

---

"The computer was born to solve problems that did not exist before." (B. Gates)