Re: OT: Optimalen Inhalt einer CDR bestimmen

[Adalbert Dawid]

Am Sat, 18 Mar 2006 15:12:50 +0100 schrieb Moritz Lenz:
> Das Problem nennt sich, mich mein eines Informatiksemester nicht im Stich
> lässt ;), "eindimensionales Rucksackprobem".

Knapp daneben. Es ist, um genau zu sein, das "Bin Packing"-Problem, bei
dem es darum geht, die Anzahl der zu füllenden Behälter (hier:
CD-Rohlinge) zu minimieren, aber auf jeden Fall alle Items (Verzeichnisse)
"einzupacken". Im Gegensatz dazu soll beim Rucksackproblem das zur
Verfügung stehende Volumen *eines* Behälters (des Rucksacks) durch
geschickte Auswahl der verschieden großen Items möglichst stark gefüllt
werden werden. Zugegebenermaßen sind die Probleme ähnlicher Natur (es
sind beide "Packing Probleme" und beide NP-vollständig), aber sie
erfordern unterschiedliche Algorithmen.

Siehe auch:
http://de.wikipedia.org/wiki/BIN_PACKING
http://de.wikipedia.org/wiki/Rucksackproblem

Gruß
Adalbert


-- 
Haeufig gestellte Fragen und Antworten (FAQ): 
http://www.de.debian.org/debian-user-german-FAQ/

Zum AUSTRAGEN schicken Sie eine Mail an [EMAIL PROTECTED]
mit dem Subject "unsubscribe". Probleme? Mail an [EMAIL PROTECTED] (engl)

Re: OT: Optimalen Inhalt einer CDR bestimmen

[Claus Malter]

Hallo Jochen,

Jochen Schulz wrote:
> Eduard Bloch:
>> [dirsplit]
>>
>> b) Der Kode ist wirklich übel, das Programm ist ohne grosse
>> Design-Überlegungen über längere Zeit gewachsen. Ich bin grade dabei,
>> das etwas zu refaktoren.
> 
> Wenn ich das richtig sehe, kann man damit keine Verzeichnisse als
> "Atome" (also unteilbare Einheiten) behandeln, oder? Das wäre ein nettes
> Feature.

Doch das geht. Sofern die Verzeichnisse keine Unterverzeichnisse mehr
haben, habe ich es mit der Option "-e 2" hinbekommen, dass die Inhalte
der Verzeichnisse "zusammen" bleiben.

> J.

Claus

-- 
GnuPG-ID: 0x08B86210 http://wwwkeys.de.pgp.net


-- 
Haeufig gestellte Fragen und Antworten (FAQ): 
http://www.de.debian.org/debian-user-german-FAQ/

Zum AUSTRAGEN schicken Sie eine Mail an [EMAIL PROTECTED]
mit dem Subject "unsubscribe". Probleme? Mail an [EMAIL PROTECTED] (engl)

Re: OT: Optimalen Inhalt einer CDR bestimmen

[Jochen Schulz]

Eduard Bloch:
> 
> [dirsplit]
>
> b) Der Kode ist wirklich übel, das Programm ist ohne grosse
> Design-Überlegungen über längere Zeit gewachsen. Ich bin grade dabei,
> das etwas zu refaktoren.

Wenn ich das richtig sehe, kann man damit keine Verzeichnisse als
"Atome" (also unteilbare Einheiten) behandeln, oder? Das wäre ein nettes
Feature.

J.
-- 
If nightclub doormen recognised me I would be more fulfilled.
[Agree]   [Disagree]
 


signature.asc
Description: Digital signature

Re: OT: Optimalen Inhalt einer CDR bestimmen

[Eduard Bloch]

#include 
* Claus Malter [Sat, Mar 18 2006, 02:43:30PM]:
> Hallo Thomas,
> 
> Thomas Antepoth wrote:
> >> [...Optimale Größenverteilung von Dateien und Verzeichnissen...]
> >> Ich wäre für Ratschläge sehr dankbar! Vielen Dank vorweg...
> > 
> > Sourcecode bei:
> > http://www-user.rhrk.uni-kl.de/~bloch/dirsplit/
> 
> Danke. Das ist fast perfekt! Die CDs werden super eingeteilt. Einziger
> Kritikpunkt ist, dass sich das Programm absolut nicht an eine
> alphabetische Ordnung hält.
> Ja, jetzt werde ich aber sehr anspruchsvoll. Vielleicht kann ich mich
> intensiv mit Perl auseinander setzen, aber vorerst muss das Programm
> seinen Dienst erfüllen. Alphabetisch oder nicht.

a) da ist ein kleiner Widerspruch - entweder ist das Ergebniss (fast)
optimal oder schön aussehend (und dann entsprechend alphabetisch
sortiert)
b) Der Kode ist wirklich übel, das Programm ist ohne grosse
Design-Überlegungen über längere Zeit gewachsen. Ich bin grade dabei,
das etwas zu refaktoren.

Eduard.

Re: OT: Optimalen Inhalt einer CDR bestimmen

[Gerhard Gaußling]

Am Samstag, 18. März 2006 15:02 schrieb Gerhard Gaußling:
> oder ob da die andersartige filesystem
> struktur stört ([a-z]: und \).
Scheinbar läuft das auch unter linux:
http://tnfo.delta-arts.de/indexdeu.htm#linux

ciao

Gerhard

Re: OT: Optimalen Inhalt einer CDR bestimmen

[Gerhard Gaußling]

Am Samstag, 18. März 2006 15:12 schrieb Moritz Lenz:
> "eindimensionales Rucksackprobem"
http://www.or.deis.unibo.it/knapsack.html

Re: OT: Optimalen Inhalt einer CDR bestimmen

[Eduard Bloch]

#include 
* Claus Malter [Sat, Mar 18 2006, 12:10:23PM]:
> Hallo beisammen,
> 
> ich habe folgendes Problem, dass sich mit dem Buch UNIX-Shell
> Programmierung IMHO nicht lösen lässt. Ich hoffe jemand von Euch, hat
> sich sowas schon gebastelt.

man dirsplit -- ist bei mkisofs dabei.

Eduard.

Re: OT: Optimalen Inhalt einer CDR bestimmen

[Gerhard Gaußling]

Am Samstag, 18. März 2006 14:43 schrieb Claus Malter:
> Hallo Thomas,
>
> Thomas Antepoth wrote:
> >> [...Optimale Größenverteilung von Dateien und Verzeichnissen...]
> >> Ich wäre für Ratschläge sehr dankbar! Vielen Dank vorweg...
> >
> > Sourcecode bei:
> > http://www-user.rhrk.uni-kl.de/~bloch/dirsplit/
>
> Danke. Das ist fast perfekt! Die CDs werden super eingeteilt.
> Einziger Kritikpunkt ist, dass sich das Programm absolut nicht an
> eine alphabetische Ordnung hält.
> Ja, jetzt werde ich aber sehr anspruchsvoll. Vielleicht kann ich mich
> intensiv mit Perl auseinander setzen, aber vorerst muss das Programm
> seinen Dienst erfüllen. Alphabetisch oder nicht.

Es gibt ein Windowstool "New File Order"

Keine Ahnung, ob dieses vollständig in Java geschriebene Tool auch unter 
Linux seinen Dienst tut, oder ob da die andersartige filesystem 
struktur stört ([a-z]: und \).
http://tnfo.delta-arts.de/indexdeu.htm

ciao

Gerhard

Re: OT: Optimalen Inhalt einer CDR bestimmen

[Moritz Lenz]

Hallo,

>>>Und zwar habe ich hier auf unserem File Server Verzeichnisse sortiert
>>>nach Thematik. In diesen Verzeichnissen liegen mehr oder weniger große
>>>PowerPoint Präsentationen unserer Abteilung. Diese Verzeichnisse sollen
>>>jetzt optimal auf CD gebrannt werden (es macht keinen Unterschied ob DVD
>>>oder CD, weil es etliche Gigabytes sind. Im Datei Server ist derzeit
>>>nur ein CD-R Laufwerk.).

> Mir ist bewusst, dass das Problem, der Algorithmus ist, mit dem man den
> optimalen Inhalt berechnet. Ich krieg Bläschen im Kopf, wenn ich nur
> versuche, da was zu entwickeln.

Das Problem nennt sich, mich mein eines Informatiksemester nicht im
Stich lässt ;), "eindimensionales Rucksackprobem". Ich bin mir sicher,
die Suchmaschine deiner Wahl wird zu dem Stichwort jede Menge
Algorithmen liefern.

Grüße,
Moritz

-- 
Moritz Lenz
http://moritz.faui2k3.org/



signature.asc
Description: OpenPGP digital signature

Re: OT: Optimalen Inhalt einer CDR bestimmen

[Claus Malter]

Hallo Thomas,

Thomas Antepoth wrote:
>> [...Optimale Größenverteilung von Dateien und Verzeichnissen...]
>> Ich wäre für Ratschläge sehr dankbar! Vielen Dank vorweg...
> 
> Sourcecode bei:
>   http://www-user.rhrk.uni-kl.de/~bloch/dirsplit/

Danke. Das ist fast perfekt! Die CDs werden super eingeteilt. Einziger
Kritikpunkt ist, dass sich das Programm absolut nicht an eine
alphabetische Ordnung hält.
Ja, jetzt werde ich aber sehr anspruchsvoll. Vielleicht kann ich mich
intensiv mit Perl auseinander setzen, aber vorerst muss das Programm
seinen Dienst erfüllen. Alphabetisch oder nicht.

Vielen Dank.

> HTH
> 
>   t++

Claus

-- 
GnuPG-ID: 0x08B86210 http://wwwkeys.de.pgp.net


-- 
Haeufig gestellte Fragen und Antworten (FAQ): 
http://www.de.debian.org/debian-user-german-FAQ/

Zum AUSTRAGEN schicken Sie eine Mail an [EMAIL PROTECTED]
mit dem Subject "unsubscribe". Probleme? Mail an [EMAIL PROTECTED] (engl)

Re: OT: Optimalen Inhalt einer CDR bestimmen

[Claus Malter]

Hallo Jochen,

Jochen Schulz wrote:
> Claus Malter:
> 
>>Und zwar habe ich hier auf unserem File Server Verzeichnisse sortiert
>>nach Thematik. In diesen Verzeichnissen liegen mehr oder weniger große
>>PowerPoint Präsentationen unserer Abteilung. Diese Verzeichnisse sollen
>>jetzt optimal auf CD gebrannt werden (es macht keinen Unterschied ob DVD
>> oder CD, weil es etliche Gigabytes sind. Im Datei Server ist derzeit
>>nur ein CD-R Laufwerk.).
> 
> 
> Für ein ähnliches Problem habe ich auch mal was selbst in Python
> geschrieben (hängt an). Allerdings geht dieses Skript recht stupide vor:
> es geht rekursiv eine Verzeichnisstruktur durch und guckt jeweils, ob
> das nächste Verzeichnis noch passt. Wenn nicht, wird sozusagen ein
> "neues Volume" aufgemacht. Am Ende hat man dann ein par durchnumerierte
> Dateien im aktuellen Verzeichnis rumliegen, in denen die
> Verzeichnisnamen stehen.

Danke für das Skript. Wenn ich DVDs brennen würde,  wäre das Skript
schon sehr hilfreich (da macht es ja nichts, ob noch 100-200MB Platz
ist). Aber aufgrund der begrenzten 700MB einer CDR würde mit dem Skript
nicht all zu viel eingespart werden.

Mir ist bewusst, dass das Problem, der Algorithmus ist, mit dem man den
optimalen Inhalt berechnet. Ich krieg Bläschen im Kopf, wenn ich nur
versuche, da was zu entwickeln.

Aber vielleicht kann ich mit Deiner Vorlage "etwas" zaubern.

> 
> Aktuell ist auch die Größe eines Datenträgers hartkodiert, das kann man
> aber ohne großartige Kenntnisse leicht selbst ändern.
> 
> J.

Claus


-- 
Haeufig gestellte Fragen und Antworten (FAQ): 
http://www.de.debian.org/debian-user-german-FAQ/

Zum AUSTRAGEN schicken Sie eine Mail an [EMAIL PROTECTED]
mit dem Subject "unsubscribe". Probleme? Mail an [EMAIL PROTECTED] (engl)

Re: OT: Optimalen Inhalt einer CDR bestimmen

[Jochen Schulz]

Claus Malter:
> 
> Und zwar habe ich hier auf unserem File Server Verzeichnisse sortiert
> nach Thematik. In diesen Verzeichnissen liegen mehr oder weniger große
> PowerPoint Präsentationen unserer Abteilung. Diese Verzeichnisse sollen
> jetzt optimal auf CD gebrannt werden (es macht keinen Unterschied ob DVD
>  oder CD, weil es etliche Gigabytes sind. Im Datei Server ist derzeit
> nur ein CD-R Laufwerk.).

Für ein ähnliches Problem habe ich auch mal was selbst in Python
geschrieben (hängt an). Allerdings geht dieses Skript recht stupide vor:
es geht rekursiv eine Verzeichnisstruktur durch und guckt jeweils, ob
das nächste Verzeichnis noch passt. Wenn nicht, wird sozusagen ein
"neues Volume" aufgemacht. Am Ende hat man dann ein par durchnumerierte
Dateien im aktuellen Verzeichnis rumliegen, in denen die
Verzeichnisnamen stehen.

Aktuell ist auch die Größe eines Datenträgers hartkodiert, das kann man
aber ohne großartige Kenntnisse leicht selbst ändern.

J.
-- 
No-one appears to be able to help me.
[Agree]   [Disagree]
 
#!/usr/bin/python2.4

import sys, os
from os.path import join, getsize, dirname
from optparse import OptionParser

source_dir = sys.argv[1]
# according to 'man 1 growisofs', DVDs contain up to 4482 MB
max_chunk_size = 4482 * 1024 * 1024
#max_chunk_size = 50

def subdir_sizes(topdir, include_empty_dirs=False):
tree = os.walk(topdir)
for dirpath, dirnames, filenames in tree:
if filenames and not include_empty_dirs:
files = (join(dirpath, name) for name in filenames)
sizes = (getsize(filename) for filename in files)
yield dirpath, sum(sizes, 0)

class Chunk(list):

def __init__(self, size=0):
self.size = size

def __str__(self):
#return "" % (len(self), self.size)
return "\n".join(path for path in self)


def main():
cur_chunk = Chunk()
chunks = []
for dirpath, dir_size in subdir_sizes(source_dir):
if dir_size > max_chunk_size:
sys.stderr.write("skipping... %s -- too large for single medium!\n" % dirpath)
continue
if dir_size + cur_chunk.size >= max_chunk_size:
# next dir doesn't fit into chunk
chunks.append(cur_chunk)
#print "chunk no. %03d: %s" % (len(chunks), cur_chunk)
cur_chunk = Chunk()
cur_chunk.append(dirpath)
cur_chunk.size += dir_size
else:
chunks.append(cur_chunk)
#print "chunk no. %03d: %s" % (len(chunks), cur_chunk)

for i in range(0, len(chunks)):
f = file('chunk-%03d' % i, 'w')
f.write("\n".join("%s=%s" % (path,path) for path in chunks[i]))
#print("\n".join("%s=%s" % (path,path) for path in chunks[i]))
f.close()

if __name__ == '__main__':
main()

# vim: set et ts=4


signature.asc
Description: Digital signature

Re: OT: Optimalen Inhalt einer CDR bestimmen

[Thomas Antepoth]

> [...Optimale Größenverteilung von Dateien und Verzeichnissen...]
> Ich wäre für Ratschläge sehr dankbar! Vielen Dank vorweg...

Sourcecode bei:
http://www-user.rhrk.uni-kl.de/~bloch/dirsplit/

Beispiel bei:

http://www.cyberciti.biz/nixcraft/vivek/blogger/2006/03/splits-directory-into-multiple-with.php

HTH

t++