[Algo] Optimalisering van indeling backup files *

[Verwijderd]

Ik heb 532 bestanden van gemiddeld tussen de 40 en de 60 Mb groot. Ik wil graag dat deze bestanden zo efficiënt mogelijk worden weggeschreven naar CD's (700 Mb).

Mijn doel is het schrijven van een scriptje dat alle files naloopt en uiteindelijk een directory of 40 uitspuugd met daarin elk voor 700 Mb aan bestanden, zo bijelkaar gezocht dat er geen optimalere combinatie bestaat met een van de andere bestanden in een van de andere directory's.

Ik ga ervan uit dat ik probeer het wiel opnieuw uit te vinden en dat hier allang een oplossing voor is bedacht.

pseudo:

lees directory met bestanden en maak array: naam en grootte

while cd1.grootte is niet tussen 702 en 698
- lees directory met bestanden
- voeg eerste bestand toe aan array(of: directory) cd1

(*op dit moment zou voor het laatste bestand eventueel meerder pogingen gedaan kunnen worden zodat de 700 Mb het beste wordt benaderd, naarmate het aantal cd's richting de 40 loopt wordt dit natuurlijk steeds zeldzamer. Daarom lijkt het mij slim om eventueel alle directory's die al klaar zijn, toch nog te gebruiken op de een of andere manier.)

Heeft iemand hier al eerder over na gedacht ?

[Janoz]

Dit probleem is (afaik) np compleet. Dat komt in het kort er op neer dat je ale mogenlijke combinaties moet proberen om te garanderen dat je de meest ideale oplossing hebt. Dat zijn er bij 532 bestanden een heleboel . Er is dus niet een makkelijke en snelle oplossing voor je probleem. Er zijn echter wel een enorme berg met algoritmen die het optimale benaderen. Je hebt dan niet gegarandeerd het optimale, maar je zit er wel redelijk dicht bij in de buurt.

[pietje63]

Beetje offtopic, maar wil je dit wel echt??
Dan weet je namelijk niet makkelijk welk bestand je waar terug moet gaan vinden enzo.. Dan moet je moeilijk alle doosjes gaan lezen ofzo. Een logische indeling werkt veel beter, ok je hebt dan misschien 1 of 2 (desnoods 5) extra cd's nodig, maar dat kost maar een euro of 2..

[Verwijderd]

Inderdaad, maar het gaat me ook eigenlijk meer om de uitdaging

[Soultaker]

edit:
Ik had het probleem wat verkeerd ingeschat. Het is een bin-packing probleem en dat is inderdaad NP-compleet. Je moet dus ofwel genoegen nemen met een exponentiële complexiteit ofwel een suboptimaal algoritme gebruiken.

MathWorld:
A simple algorithm (the first-fit algorithm) takes items in the order they come an places them in the first bin in which they fit. In 1973, J. Ullman proved that this algorithm can differ from an optimal packing by as much at 70% (Hoffman 1998, p. 171). An alternative strategy first orders the items from largest to smallest, then places them sequentially in the first bin in which they fit. In 1973, D. Johnson showed that this strategy is never suboptimal by more than 22%, and furthermore that no efficient bin-packing algorithm can be guaranteed to do better than 22%.

Ik neem aan dat met efficient algorithm hierboven een algoritme van polynomale complexiteit bedoeld wordt.

[ Voor 85% gewijzigd door Soultaker op 04-01-2004 15:18 ]

[Infinitive]

Voor het knapsack probleem bestaat wel een algoritme die een optimale oplossing binnen polynominale tijd berekend. Maar zoals Soultaker al aangeeft is het knapsack probleem anders:

- items g1..gn met respectievelijke waardering w1..wn
- zak met maximum gewicht G
- welke items in de zak stappen zodat het totaalgewicht maximaal G is met de hoogste totaalwaardering.

Het probleem is nu dat je geen maximum gewicht hebt, maar items met
g1..gn zo moet verdelen over een verzameling G1..Gm waarbij je m minimaliseerd. Hoewel het op knapsack probleem lijkt, is het toch eigenlijk wel heel verschillend.

Voor het knapsack probleem kan je een oplossing geven in de vorm van een recurrente betrekking op twee parameters en dan vertalen naar een imperatief-algoritme op een array, zodat er een polynominaal algoritme ontstaat.

Voor het nieuwe probleem kan ik niet zo snel zo'n soort van recurrente betrekking bedenken, omdat het aantal 'zakken' niet vast staat.
En zoals SoulTaker in een nieuwe post aangeeft, is er blijkbaar bewezen dat het een NP-compleet probleem is en dan zal deze recurrente betrekking ook niet bestaan. Nou ja, er is nog steeds niet bewezen dat je een NP-compleet probleem niet in polynominale tijd kan opgelossen.

[ Voor 15% gewijzigd door Infinitive op 04-01-2004 15:27 ]

[Verwijderd]

Waarvoor zip/rar je ze niet gewoon ? Lijkt me handiger, kan je nog crc controle (en herstel) toevoegen etc.

[Macros]

Infinitive schreef op 04 januari 2004 @ 15:25:
Voor het knapsack probleem bestaat wel een algoritme die een optimale oplossing binnen polynominale tijd berekend....

Als jij dat algoritme hebt, dan zal iedereen blij zijn, want dan heb je bewezen dat NP = P en dan wordt je waarschijnlijk milionair.
Er zijn algoritmes die bij veel instanties van het knapsack probleem een optimale oplossing in een polynomiale tijd berekend, maar er is geen algoritme dat dat voor alle instanties kan.

[dingstje]

Waarvoor zip/rar je ze niet gewoon ? Lijkt me handiger, kan je nog crc controle (en herstel) toevoegen etc.

... en dan heb je weer juist hetzelfde probleem. Of je moet ze al echt gaan splitten op 700 MB maar dan moet je eerst elke cd erin steken voor je één besand kan uitlezen.

[Verwijderd]

Als je nu gewoon rar'ed zipp'ed () op 15MB ofzo, dan kan je ze en perfect verdelen over de cd's en je hebt je crc check en je hoeft niet 1voor1 de cd's erin te doen.

[Infinitive]

Er zijn algoritmes die bij veel instanties van het knapsack probleem een optimale oplossing in een polynomiale tijd berekend, maar er is geen algoritme dat dat voor alle instanties kan.

De versie van knapsack waar ik het over heb gaat over discrete gewichten. En die versie is polynominaal in zowel het aantal items, als het aantal mogelijke gewichten uit 0..Gmax. Voor een versie met reële gewichten kan je dat algoritme niet gebruiken, want dan heb je oneindig veel mogelijke gewichten.

[ Voor 14% gewijzigd door Infinitive op 04-01-2004 21:20 ]

[Olaf van der Spek]

Infinitive schreef op 04 januari 2004 @ 21:19:
De versie van knapsack waar ik het over heb gaat over discrete gewichten. En die versie is polynominaal in zowel het aantal items, als het aantal mogelijke gewichten uit 0..Gmax. Voor een versie met reële gewichten kan je dat algoritme niet gebruiken, want dan heb je oneindig veel mogelijke gewichten.

Is de verzameling gehele getallen wel eindig dan?

[Infinitive]

Ik heb het nu dus over het knapsack probleem (en blijkbaar een specifieke instantie daarvan) en niet over het probleem waar antcore het over heeft:

Is de verzameling gehele getallen wel eindig dan?

In dit geval wel. De waarden zitten in het interval 0 .. Gmax. Waarbij Gmax gedefinieerd is als het maximum van het gewicht dat in de knapzak past en het maximale gewicht van de items.

De optimale waarde dat mogelijk is, kan je met de volgende recurrente betrekking berekenen:

code:

stel wi = { waarde van item i }
stel gi = { gewicht van item i }

s i g = { geeft optimum waarde voor items t/m i met maximum gewicht g }

voor i < 0 of g < gi:
s i g = 0

voor i >= 0 en g >= gi:
s i g = max [ s (i-1) g   -- gebruik item i niet
                  , wi + s (i-1) (g - gi)   -- gebruik item i wel
                  ]

Je kan dit omschrijven in niet-recursieve code, door in te zien dat voor het berekenen van s i g, je het antwoord kan vinden als je s (i-1) g en s (i-1) (g-gi) berekent hebt. De makkelijkste manier is het gebruiken van een tweedimensionale array R [0..i, 0..g] en een loopje te maken die alle i's afgaat en daar binnen een loopje die de g's afgaat. De waarde van zo'n element i', g' is dan een kwestie de berekening in de recurrente betrekking, waarbij de recursiefheid nu vervangen wordt door het opzoeken van de waarde in de array. Ofwel, je hebt twee geneste loops met als body operaties van constante tijd, dus je hebt een algoritme in polynominale tijd.

Ok, je hebt nu alleen de optimale waarde gevonden. Maar het pad dat je afgelopen bent (kies ik i wel of niet) geeft aan welke items je in de knapsack wilt steken, dus die kan je dan kiezen en dat is je oplossing voor het probleem.

Maar zoals ik zoals eerder gezegt werkt dit alleen voor discrete waarde en moet erbij gezegt worden dat deze polynominaal is in zowel het aantal items als het maximum gewicht. Het zou bijvoorbeeld kunnen zijn dat het maximum gewicht groter is dan 2^(aantal items). De worst-case tijd van deze functie, wanneer je alleen naar het aantal items kijkt, is dan dus nog steeds exponentieel.

[ Voor 3% gewijzigd door Infinitive op 04-01-2004 22:25 ]

[DaCoTa]

Kijk eens op Astrokettle Algorithms. Daar kun je een demo downloaden die je van user data kan voorzien. Kat in 't zakkie zo te zien.

[curry684]

Waarom doet iedereen zo moeilijk? Dit is enkel in theorie een knapsack probleem, in de praktijk een probleem over 532 bestandjes. Knapsack is een zwaar probleem omdat het voor X elementen een zwaar probleem is, maar voor dergelijke kleine hoeveelheden kun je met wat bruteforcen ook rustig een near-perfect oplossing geven.

Doe eens gewoon:
• Sorteer alle bestanden op formaat
• Begin vanaf de grootste alle bestanden erin te stoppen. Skip degenen die niet passen.
• Loop vanaf klein naar groot over je array en controleer of je de betreffende file kunt vervangen door een grotere. Zo ja: doen en opnieuw beginnen met deze stap.

Zodra je de 3e stap niet meer uit kunt voeren zit je binnen 1ms vrijwel gegarandeerd binnen 1% van de beste oplossing. Als je een betere oplossing wil zul je een van de moeilijkere algoritmes moeten uitvoeren en ben je tig keer langer bezig

[Infinitive]

Waarom doet iedereen zo moeilijk?

TS: Inderdaad, maar het gaat me ook eigenlijk meer om de uitdaging

Nu moet ik zeggen dat het loslaten van genetische algoritmen op het probleem wel erg ver gaat

[ Voor 28% gewijzigd door Infinitive op 05-01-2004 02:43 ]

[SWfreak]

curry684 schreef op 05 januari 2004 @ 01:35:
Waarom doet iedereen zo moeilijk? Dit is enkel in theorie een knapsack probleem, in de praktijk een probleem over 532 bestandjes. Knapsack is een zwaar probleem omdat het voor X elementen een zwaar probleem is, maar voor dergelijke kleine hoeveelheden kun je met wat bruteforcen ook rustig een near-perfect oplossing geven.

Doe eens gewoon:
• Sorteer alle bestanden op formaat
• Begin vanaf de grootste alle bestanden erin te stoppen. Skip degenen die niet passen.
• Loop vanaf klein naar groot over je array en controleer of je de betreffende file kunt vervangen door een grotere. Zo ja: doen en opnieuw beginnen met deze stap.

Zodra je de 3e stap niet meer uit kunt voeren zit je binnen 1ms vrijwel gegarandeerd binnen 1% van de beste oplossing. Als je een betere oplossing wil zul je een van de moeilijkere algoritmes moeten uitvoeren en ben je tig keer langer bezig

In theorie is het probleem van de TS geen knapsack-probleem, maar een binpacking probleem, zoals Soultaker al opmerkte. Dat is een stukje lastiger (maar wel aardig en simpel op te lossen met het algoritme van Johnson wat Soultaker noemde).
Jij omschrijft (volgens mij) een variant van het knapsack probleem waarbij we zoveel mogelijk items in de knapsack proberen te stoppen. Dit probleem is bewijsbaar optimaal op te lossen door de items van klein naar groot in de knapsack te stoppen totdat de knapsack volzit...

[Soultaker]

Voor de geïnteresseerde, wat achtergrondinformatie:
Approximation Algorithms for Bin Packing: A Survey (PostScript) (PDF)
Wel een beetje wetenschappelijk verantwoord (lees: saaie kost).

[RickN]

En natuurlijk is dit probleem al eens op GoT tersprake gekomen:

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

Overigens ook toen zonder tot noemenswaardige conclusies te komen.

[ Voor 31% gewijzigd door RickN op 05-01-2004 15:00 ]