[alg] Algoritme: veel albums op weinig cd's *

[bodiam]

Hallo allen,

sorry dat de titel een beetje erg algemeen is, maar ik ben niet zo thuis in algoritmes en ik heb ook geen flauw idee hoe ik het issue pakkend kan omschrijven.

Mijn probleem is dat ik een programmatje wil schrijven (in Java, maar dat is in dit geval onbelangrijk) die voor mij een directorystructuur doorgaat (laten we zeggen 50 mappen met daarin 30 GB aan mp3's.) Nu zou ik graag de inhoud van deze mappen zo sorteren dat ze in mappen uitkomen van bijvoorbeeld 650 of 700 mb. (Inderdaad: ik probeer een programma te maken die voor mij de meest efficiente (lees: minst mogelijk aantal cd's) manier uitrekent om een cd te branden, hierbij geen rekening houdend met kwaliteit en catagorie van de mp3.)

Nu is mijn vraag of iemand mij een schop in de goeie richting kan geven, of wat tips, want qua algoritmes ben ik echt een nul.

Alvast bedankt voor de hulp,

Erik Pragt

[Tuinhark]

Zegt de term 'recursiviteit' je al iets?

Zo niet, eerst ff opzoeken bij Google oid.. recursive

[Hu9o]

Dat is niet echt een antwoord op de vraag algoritme. Ik denk dat de ts meer nadruk legt op de vraag: Hoe bepaal ik hoeveel cd's ik minimaal nodig heb.

Even voor de duidelijkheid, het is dus zo dat de mp3's van een album niet bij dat album hoeven te blijven??

Zo zou ik het aanpakken:

Zet alle mp3's in een lijst gesorteerd op grootte.

Begin bij de grootste en tel daarna die eronder er bij op.
Netzolang totdat bij een sommatie de grens van 700mb is overschreden.
Dan moet geprobeerd worden een kleinere bij het totaal opgeteld worden. totdat onderaan de lijst is gekomen.

Dit moet herhaalt worden totdat de lijst leeg is.


Ik ben me ervan bewust dat dit algoritme niet optimaal kan zijn, maar denk dat je zo aardig bij het minimum aantal uit zal komen.

succes.

[BCC]

Jaah, recursief met Backtracking :)! In Miranda zou het één regel zijn :)!

[Genoil]

wil je dit puur 'voor de kick' doen, of maakt het je echt zo vreselijk veel uit dat je op een dikke 40 CD-R's er een paar meer nodig hebt, wat ook nog eens ten koste gaat van enige logische indeling van de bestanden?

lijkt me iig best pittig zo'n algoritme...
is dit niet iets: je berekent de totale aantal MB's van je mp3's, deelt die door 650 of 700MB, heb je het minimaal aantal CD's dat je nodig hebt. Daarna sorteer je al je mp3tjes op grootte en begint ze 1 voor 1 te verdelen (te beginnen bij de grootste) over je minimaal aantal cdtjes. als een nummer niet meer past op een cd probeer je em op de volgende te zetten enz. als alles vol zit pak je een extra cdtje. niet gegarandeerd de beste indeling maar lijkt me een aardig eind in de goede richting..

hmm Hu9o heeft iets eenvoudigers wat bij nader inzien wel beter werkt denk ik

[ Voor 12% gewijzigd door Genoil op 13-01-2003 12:30 ]

[Zoijar]

Is dat niet het knapsack probleem? Niet zeker, als het zo is het NP en moet je op heuristics overgaan. Dan is wat hu9o vertelede een goed algoritme.

[Dr. Cheeks]

Dit is inderdaad (een vorm van) het knapsack probleem. Om de 100% meest optimale oplossing te vinden zul je alle combinaties van mogelijke indeleingen af moet gaan. Ik kan je alvast vertellen dat als het om 30Gb aan mp3's gaat je computer daar wel héél erg lang over aan het rekenen is (minstens een week, misschien wel een jaar). Er zijn namelijk nogal wat mogelijkheden.

Daarnaast lijkt het erop dat je een zeer beginnende programmeur bent (als algoritmes al een ver van je bed show zijn...), dus misschien moet je maar gewoon voor de simpele oplossing gaan...

[bodiam]

Even voor de duidelijkheid (als reactie op Hu9o): Ik wil wel graag de mp3's per album bij elkaar houden. Oftwel: het zou een sortering van albums moeten worden, niet van losse mp3's.
Hu9o, Ik denk overigens dat jouw oplossing uitstekend zou kunnen werken als de mp3tjes niet bij elkaar hoeven te blijven. Echter, ik denk dat dit een minder geschikte manier is als de mappen wel bij elkaar moeten blijven. In ieder geval bedankt voor je reactie. Als ik niet met knapsack uit de voeten kan, ga ik zeker jou oplossing gebruiken.

Als reactie op op Genoil: antwoord: beiden. Het lijkt me handig om zo'n programma te hebben, die automatisch alle albums sorteert in mapjes en dat ik op die manier makkelijk een map kan selecteren en branden. Daarnaast natuurlijk ook 'voor de kick'. Het is natuurlijk niet een echte kick, maar het lijkt me wel 'grappig' om zo'n programmatje te bouwen.

Als reactie op Zoijar: Ik dacht wel aan zoiets als knapsack, maar ook dit weet ik niet helemaal zeker. Ik ken het algoritme (van naam) maar de logica en implementatie is mij onbekend.

Erik

[ Voor 22% gewijzigd door bodiam op 13-01-2003 12:50 ]

[Zoijar]

bodiam schreef op 13 januari 2003 @ 12:48:

Als reactie op Zoijar: Ik dacht wel aan zoiets als knapsack, maar ook dit weet ik niet helemaal zeker. Ik ken het algoritme (van naam) maar de logica en implementatie is mij onbekend.

Erik

Knapsack is geen algoritme, het is de naam van een probleem. Dat probleem komt in verschillende varianten voor en valt in de klasse "NP problemen". Simpel gezegd komt dat erop neer dat er geen optimaal algoritme voor is, niet in redelijke tijd. Encryptie is bv vaak gebasseerd op NP problemen, omdat het te lang duurt om optimaal op te lossen.
Wat hu9o beschreef is een algoritme dat een goede benadering aan de optimale oplossing geeft. Dit worden ook wel heuristic algoritmen genoemd.

[bodiam]

Daarnaast lijkt het erop dat je een zeer beginnende programmeur bent (als algoritmes al een ver van je bed show zijn...)

Sorry dat ik hier toch even op moet reageren, maar ik weet uiteraard niet wat jou definitie van beginnend is, maar op dit moment heb ik 3 jaar programmeer ervaring, maar ik kom in mijn dagelijkse werkzaamheden gewoon erg weinig algoritmes tegen.

Maar misschien dat je wel gelijk hebt: ik ga inderdaad maar eens de 'simpele' aanpak proberen. Ik ben namelijk benieuwd wat de resultaten daarvan zijn.


Erik

edit:
overigens, iedereen hardstikke bedankt voor de hulp!!

[ Voor 8% gewijzigd door bodiam op 13-01-2003 13:01 ]

[Dr. Cheeks]

Sorry dat ik hier toch even op moet reageren, maar ik weet uiteraard niet wat jou definitie van beginnend is, maar op dit moment heb ik 3 jaar programmeer ervaring, maar ik kom in mijn dagelijkse werkzaamheden gewoon erg weinig algoritmes tegen.

3 jaar is inderdaad niet meer beginnend. Het kwam alleen raar op me over: wel thuis in programmeren maar niet in algoritmes. Het één leek het ander uit te sluiten. Maar goed, ik zal zelf ongetwijfeld een te beperkte kijk om het programmeurswezen hebben.

Succes met je probleem in elk geval!

PS: Ik weet niet hoe vaak je het programma nodig hebt, maar ik denk dat je met de hand heel wat CD's kan samenstellen (die ongeveer de CD vullen) in de tijd die het kost om een proggie te schrijven...

[bodiam]

Het kwam alleen raar op me over: wel thuis in programmeren maar niet in algoritmes. Het één leek het ander uit te sluiten. Maar goed, ik zal zelf ongetwijfeld een te beperkte kijk om het programmeurswezen hebben.

Nouja, ik had net nog even overlegd over die opmerking van je met een collega van je, en we zijn tot de conclusie gekomen dat programmeren en algoritmes echt niet van elkaar los te zien zijn. Alleen de ingewikkeldheid van de algortimes verschilt uiteraard sterk. Dus je had/hebt wel gelijk!

Bedankt voor je hulp, ik ga eens proberen wat ik tevoorschijn kan toveren.

Groeten, Erik

[RickN]

Dit is geen knapzak probleem hoor.
Bij een knapzak probleem probeer je een zak (cd) zoveel mogelijk te vullen met items van verschillende grootte (mp3's).

Als je dit probleem gaat oplossen door het te zien als een verzameling knapzakken die je dan één voor één zo ver mogelijk gaat vullen, minimaliseer je niet je eigenlijk doelfunctie, het aantal knapzakken.

Voorbeeld:

een cd kan 12 mb bevatten.
Je hebt 7 mp3tjes van de volgende grootte:
4,4,4,7,7,7,7

Als je gelijk één cd optimaal gaat vullen met 4,4,4 dan heb je voor de overige mp3s één cd per stuk nodig, resultaat: 5 cd's
Als je het probleem optimaal oplost heb je 3 cd's met 11 erop (7+4) en één met 7, dus een resultaat van 4 cd's.

Wellicht geeft in jouw specifieke situatie de knapzak methode (greedy aanpak) wel een goed resultaat hoor. Greedy is een heel simpel, maar soms best effectief voorbeeld van een heuristische methode. Er zijn andere betere heuristische zoekmethoden.

Het probleem is eigenlijk een partitionerings probleem, best lastig.

[bodiam]

Hoi RickN,

maar als je de methode van Hu9o gaat gebruiken, sorteer je eerst de mp3tjes.
Uitgaande van jouw verzameling wordt het dan:

7,7,7,7,4,4,4.

Pak daarbij de 1ste (7), en pak dan de volgende (7). Dit is samen meer dan 12, dus pak weer de volgende (7). Weer meer dan 12, tot we bij de 4 komen. 7+4=11. Dan de volgende 4 erbij, etc,etc. Als we dan de getallen wegstrepen die we al gehad hebben, komen we uit op 7+4, 7+4, 7+4, en 7, dus op het meest optimale resultaat.

Nu weet ik niet wat de kans is dat dit meest optimale resultaat voorkomt, maar het zou best kunnen zijn dat in het meest van de gevallen (90%??) de meest optimale combinatie voor komt. 90% zou voor mij een zeer optimale uitkomst zijn.

[Zoijar]

Rickn bedoelde dat het geen verzameling knapsack problemen is. Omdat je dan elke cd appart zou beschouwen, en dus de eerste vulling met 3x 4 beter is dan 7 en 4.
Blijft een feit dat beide problemen NP zijn, en dus equivalent. (zodat ik toch nog een beetje gelijk had hehehe )

[RickN]

bodiam schreef op 13 January 2003 @ 16:32:
Hoi RickN,

maar als je de methode van Hu9o gaat gebruiken, sorteer je eerst de mp3tjes.
Uitgaande van jouw verzameling wordt het dan:

7,7,7,7,4,4,4.

Pak daarbij de 1ste (7), en pak dan de volgende (7). Dit is samen meer dan 12, dus pak weer de volgende (7). Weer meer dan 12, tot we bij de 4 komen. 7+4=11. Dan de volgende 4 erbij, etc,etc. Als we dan de getallen wegstrepen die we al gehad hebben, komen we uit op 7+4, 7+4, 7+4, en 7, dus op het meest optimale resultaat.

Klopt, maar Hu9o's methode geeft dan ook geen optimale oplossing voor het knapzak probleem. Ik zei alleen dat het als meerdere knapzak problemen interpreteren geen optimale oplossing voor je probleem geeft. Verder durf ik ook best te beweren dat Hu9o's methode geen optimale oplossing voor je probleem is, al heb ik even geen zin om nog een tegenvoorbeeld te verzinnen.
Als je niet opzoek bent naar een 100% optimale oplossing is Hu9o's oplossing en andere greedy varianten daarop best aardig hoor, en lekker simpel te implementeren.

Eigenlijk is het een soort dubbele greedy methode:

Hu9o's methode is een greedy manier om het knapzak probleem op te lossen en het knapzak probleem oplossen is een greedy manier om jouw probleem op te lossen.

[ Voor 18% gewijzigd door RickN op 13-01-2003 16:44 ]

[MSalters]

Overigens maakt het voor het algoritme natuurlijk weinig uit of je een CD vult met tracks, albums, losse MP3s, zips of wat dan ook. Je hebt een verzameling ondeelbare elementen, in dit geval dus albums, met elk een aparte grootte. Hu9o's algoritme is goed, dat werkt dus ook voor albums

_{Abstract kunnen denken - en dus realiseren dat een algoritme ook werkt als je eenheid "album" ipv "MP3" is - dat is een elementaire skill voor programmeurs.}

[Sjaaky]

Het verschil tussen de optimale en een triviale oplossing zal hooguit 1 cd zijn.
Er vanuit gaande dat de gemiddelde grootte van je mp3's 10MB is, zal er hooguit 10MB per cd overblijven. Omdat je 30GB/650MB = ±46 cd's nodig hebt, is de slack dus maximaal 460MB, wat makkelijk op 1 cd past.

Dit verhaal gaat uiteraard niet op als het overgrote gedeelte van je mp3's een grootte van zeg 200-600 MB heeft.

[.oisyn]

* .oisyn doet een poging de topictitel te verduidelijken

[PommeFritz]

Grappig. Dit onderwerp doet me denken aan mijn oude Sony CD-speler. Daar zat een functie op waarbij je de lengte van een cassettebandje kon invoeren en dan zocht hij automatisch de nummers van de cd bij elkaar zodat het bandje zo goed mogelijk gevuld werd :-)

[RickN]

MSalters schreef op 13 January 2003 @ 16:56:
Overigens maakt het voor het algoritme natuurlijk weinig uit of je een CD vult met tracks, albums, losse MP3s, zips of wat dan ook. Je hebt een verzameling ondeelbare elementen, in dit geval dus albums, met elk een aparte grootte. Hu9o's algoritme is goed, dat werkt dus ook voor albums

_{Abstract kunnen denken - en dus realiseren dat een algoritme ook werkt als je eenheid "album" ipv "MP3" is - dat is een elementaire skill voor programmeurs.}

Dat is niet helemaal waar natuurlijk. Als je items klein (en van ongeveer gelijke grootte) zijn t.o.v. je cd kom je makkelijker tot een redelijke oplossing dan wanneer ze groot zijn en/of er groot verschil in grootte voor komt. Een eenvoudige heuristiek zal in het eerste geval een aardige oplossing leveren, terwijl in het tweede geval wellicht een geavanceerder algoritme nodig is. Als je mp3's gaat groeperen in albums vergroot je effectief je items, waardoor partitioneren moeilijker wordt en je makkelijker verder van het optimum komt af te zitten. Vergelijk dit ook met de berekening die Sjaaky maakte; met grotere items wordt de maximale afwijking van de optimale oplossing groter.

Vooral heuristische en gerandomizeerde algoritmes zijn niet zomaar templates die altijd eenvoudig en met hetzelfde resultaat voor elke probleem instantie te instantiëren zijn; abstract denken is goed, maar als je niet oppast ga je door je genaralizerende bril een probleem eenvoudiger zien dan het werkelijk is.

[Verwijderd]

Ik zou het als volgt doen:

Begin eens een heel simpel progje te schrijven dat elk album in een aparte map zet. Je programma eindigt dus met 1 folder waar alle albums in staan.

Vervolgens moet je een lijst maken met de grootte van elke map. Dan schrijf je het volgende (naieve) algoritme:

koppel aan elke grootte (dus aan elke map) een RANDOM! geheel getal.
sorteer op het random nummer.
neem zoveel mappen bijelkaar als maximaal op cd past.
Tel het aantal cd's dat je nodig hebt, en sla de oplossing op.

koppel opnieuw aan elke grootte (dus aan elke map) een RANDOM! geheel getal.
doe het zelfde geintje, en als je minder cd's nodig hebt, dan vervang je de oplossing.


Dit is een hele simpele manier waarop je 'het lot', oftewel de random toewijzing voor je kunt gebruiken.

Met 100 stappen heb je bij lange na niet een goede oplossing. Maar als je je pc een uur laat rekenen, dan heeft ie minstens miljoen random opdelingen gecheckt, en daar zit vast een hele optimale bij.

[RickN]

Ik ben niet helemaal van je oplossing gecharmeert.
Stel TS heeft 100 albums, er zijn 100! manieren om aan die albums een uniek random getal toe te kennen, als de getallen niet uniek hoeven te zijn zelfs 100^100. Zelfs als je je computer een jaar laat rekenen doorzoek je slechts een fractie van de oplossingsruimte en de kans dat daar een echt goede oplossing tussen zit is dan niet zo heel erg groot.

Dit volledig randomizeren is dus niet zo effectief. Wat wel zou kunnen werken is

een kleine random aanpassing maken op de beste oplossing tot dan toe (x) en dan kijken of deze nieuwe oplossing beter is, zo ja x=y;
herhaal.

[Verwijderd]

jep...je hebt helemaal gelijk.

Ik wilde met het oog op eenvoud een oplossing aandragen. Jouw methode (of beter, de algemeen aanvaarde methode) vergt ook nog eens een modificatie algoritme, iets wat in zichzelf weer een heel vakgebied is.

Verder, veel albums zullen ongeveer van de zelfde grootte zijn, en ik denk toch dat als je alleen maar een fractie van de oplossingsruimte doorloopt, je toch redelijk verschillen zult zien in goede en slechte oplossingen. Nou, en dat is nu net leuk.

[Verwijderd]

Sjaaky schreef op 13 januari 2003 @ 16:58:
Het verschil tussen de optimale en een triviale oplossing zal hooguit 1 cd zijn.
Er vanuit gaande dat de gemiddelde grootte van je mp3's 10MB is, zal er hooguit 10MB per cd overblijven. Omdat je 30GB/650MB = ±46 cd's nodig hebt, is de slack dus maximaal 460MB, wat makkelijk op 1 cd past.

Dit verhaal gaat uiteraard niet op als het overgrote gedeelte van je mp3's een grootte van zeg 200-600 MB heeft.

Ik heb even iets inelkaar gefiets in perl wat een triviaal (greedy) algoritme gebruikt, en dit is precies wat ik zie.

Als ik naar mijn eigen MP3 collectie kijk zijn hele CDs zo tussen de 20 en de 150 MB (afhankelijk van hoeveelheid nummers en qualiteit). En veel zijn zo 60 a 70 MB.

Eerst een test-programmaatje dat een random test-set genereert, binnen bepaalde grenzen. Het echte programma volgt...

Perl:

#
# Genereer een lijst van CD "namen" en groottes. 
#
#
my $totSize   = 30000; # Totaal aantal MBs (kan iets worden overschreden)
my $minCdSize = 40;    # Minimum CD grootte in MBs
my $maxCdSize = 80;    # Maximum CD grootte in MBs

my $soFar     = 0;
my $cdId      = 1;

while( $soFar < $totSize )
{
    my $rndSize = $minCdSize + int( rand( $maxCdSize - $minCdSize + 1 ) );
    print "CD$cdId $rndSize\n";
    $soFar += $rndSize;
    $cdId++;
}

[ Voor 3% gewijzigd door Verwijderd op 13-01-2003 20:25 ]

[Verwijderd]

Het programma

Perl:

my $maxSetSize = 650;

if( @ARGV != 1 ) {
    die "Usage: perl nrcds.pl inFile.txt\n";
}

open( FILE, $ARGV[0] ) || die "Couldn't open $ARGV[0]\n";

# Input file laden...
my @cds;    # CD namen
my %cdSize; # hash met CD groottes geindexeerd op naam
while( <FILE> ) {
    chomp;
    my ( $name, $size ) = split;
    push @cds, $name;
    $cdSize{$name} = $size;
}
my $nrCds = @cds;

# Sorteren, grootste eerst
my @sortedCds = sort { $cdSize{$b} <=> $cdSize{$a} } @cds;

my @cdsLeft = @sortedCds;
my @allSets = ();

while( @cdsLeft ) {
    my $currentSetSize = 0;
    my @currentCdSet = ();
    my $firstFit = "";
    my $foundFit = 0;

    my @dontFit = ();
    my @notChecked = @cdsLeft;

    # Deze set vullen met zo veel als past, beginnen met de grootste
    while( @notChecked ) {
        my $cd = shift @notChecked;
        my $size = $cdSize{$cd};

        if( ( $currentSetSize + $size ) <= $maxSetSize ) {
            $currentSetSize += $size;
            push @currentCdSet, $cd;
        }
        else {
            push @dontFit, $cd;
        }
    }

    @cdsLeft = @dontFit;
    if( @notChecked ) {
        push @cdsLeft, @notChecked;
    }
    push @allSets, \@currentCdSet;
}

# Oplossing afdrukken...
my $totalSize = 0;
my $setIndex = 1;
foreach my $pSet ( @allSets ) {
    my $setSize = 0;

    print "Set $setIndex\n";

    foreach my $cd ( @$pSet ) {
        print "    $cd $cdSize{$cd}\n";
        $setSize += $cdSize{$cd};
    }

    print "total: $setSize\n\n";

    $totalSize += $setSize;
    $setIndex++;
}

my $ideal = int( $totalSize / $maxSetSize );
$ideal++ if( $totalSize % $maxSetSize > 0 );

print "Total MBs: " . $totalSize . "\n";
print "Ideal: $ideal\n";

[ Voor 5% gewijzigd door Verwijderd op 13-01-2003 20:25 ]

[Verwijderd]

Bij gebruik van bovenstaande grenzen [40-80] wordt er bijna altijd een CD meer dan ideaal gebruikt, maar bij grenzen van [30-90] is gebruikt de oplossing bijna altijd evenveel CDs als ideaal.

De laatste CD is natuurlijk de helft van de tijd lang niet vol.

[Lister]

Ik heb een paar jaar terug ook eens zoiets gemaakt voor het maximaal vullen van floppy disks en het algoritme voor het proberen met de grootste eerst bleek in de praktijk goed te werken.
Het ging alleen niet helemaal lekker als er een of meerdere hele grote files in zaten dan slokten die meestal alle kleine files als vulling op. Dan kreeg ik bijvoorbeeld als resultaat 2 volledig gevulde floppies en 5 grotendeels gevulde, terwijl ik dan 4 volledig gevulde floppies en 3 grotendeels gevuld kreeg als ik de grote files er buiten liet.
Effectief bleef dezelfde hoeveelheid vrije ruimte over alleen was het dan minder verspreid.
Toen heb ik het algoritme zo aangepast dat hij eerst met de grootste file begon en daar een oplossing bij zocht, daarna met de op 1 na grootste enz.. De oplossing waarbij het meeste aantal floppies volledig gevuld waren gebruikte ik dan.

Wat hier nog niet gemeld is, is dat je ook nog rekening moet houden met het filesysteem en dan met name de grootte van de clusters, de eenheden waarmee bestanden en directories worden opgeslagen.
Om de ruimte te berekenen die een file inneemt moet je de filegrootte delen door de clustergrootte, dit naar boven afronden en weer vermenigvuldigen met de clustergrootte.
Elke subdirectory neemt ook minimaal 1 cluster in en eventueel meer als er erg veel files in staan.
Dit geldt in ieder geval voor floppies, hoe dit precies met CD's zit weet ik niet, ik geloof dat je dan ook nog rekening moet houden met de manier waarop je brandt in verband met overhead bij mult-session CD's.