Dateiformat für 08/09 grid.xsd

Moderator: Praktikum: Algorithmen

patrik_s.stud.tu
Mausschubser
Mausschubser
Beiträge: 69
Registriert: 12. Okt 2006 20:56

Re: Dateiformat für 08/09 grid.xsd

Beitrag von patrik_s.stud.tu » 3. Nov 2008 21:34

Ich hab mal ein wenig ueberschlagen...
Kannst grob mit dem fuenf- bis sechsfachen Speicherbedarf rechnen zwischen den verschiedenen Notationen.
Wenn man z.B. ein 80x80x80er Cube hat und das mit sagen wir 10 Mengen a 40 Knoten gleichverteilter Positionen, bekommt man ungefaehr pro Menge knapp 1600 Steinerknoten heraus... Wenn man nun diese Loesung notieren moechte, haette man grob 150k Zeichen, bei einer Notation von x;y;z<LF>, was bei UTF-8 mit 4byte pro Zeichen stolze 600KB waeren... schaut man sich nun das Verhaeltniss von XML zu der obigen Notation an, bekommt man bei einem Vergroesserungsfaktor von sechs ungefaehr 3,6MB...
Ist Kleinscheisserei, aber man kann halt nicht Allgemein, bei den Problemen wo immense Speichermengen aufkommen, so programmieren... Wuerde ich so an das Problem im Code herangehen, dann koennte man es nicht ohne Kaffeepause loesen... aber was ist schon ein linearer Faktor...

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Dateiformat für 08/09 grid.xsd

Beitrag von Prof. Karsten Weihe » 4. Nov 2008 14:32

Maradatscha hat geschrieben: Ich möchte damit nicht gegen XML sprechen, möchte nur das Problem aufzeigen.
Gut, wenn Sie nicht gegen XML sprechen möchten, gibt es ja keinen wirklichen Dissens. Sie haben recht, dieses problem aufzuzeigen, aber ich denke, in diesem spezifischen Projekt können wir gut damit leben.

Ich möchte alle Mitleser bitten, weitere Einwände bis spätestens Montag, 10.11., 23:59 MEZ vorzubringen. Sollte es bis dahin kein entsprechendes Reply auf dieses mein Posting geben, betrachten Sie das Format als fest.

Danke und Gruß,

KW

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Dateiformat für 08/09 grid.xsd

Beitrag von Prof. Karsten Weihe » 10. Nov 2008 14:49

Hallo allerseits,

ich bin außerhalb des Forums (aka reale Welt 8) ) angesprochen worden, dass die hier diskutierten XML-Ideen overkill seien, das nicht jeder Teilnehmer fit ist in der Verwendung der Tools und entsprechend viel Zeit in die Einarbeitung benötigen würde.

Da das Dateiformat nun wahrlich nicht Kern des projektes werden soll, nehme ich diese Einwände entsprechend schwer, d.h. ich würde doch eher einem primitiv gehaltenen Dateiformat zuneigen, in dem die einzelnen Zahlen einfach in spezifischer Reihenfolge gegeben sind.

Ich bitte um Gegenreden bis Donnerstag (13.11.) frühmorgens.

Gruß,

KW

patrik_s.stud.tu
Mausschubser
Mausschubser
Beiträge: 69
Registriert: 12. Okt 2006 20:56

Re: Dateiformat für 08/09 grid.xsd

Beitrag von patrik_s.stud.tu » 10. Nov 2008 16:36

Wenn ein simpleres Dateiformat her soll, dann bietet sich immernoch folgendes an:

wobei //Kommentare sind und <variable> durch deren Wert ersetzt wird

fuer das Einlesen von Problemen

Code: Alles auswählen

<Breite>;<Hoehe>;<Tiefe>
<AnzahlVonTerminalmengen=m>
<AnzahlVonTerminalen=n1>
<x>;<y>;<z> //erster Knoten implizit Quelle
<x>;<y>;<z>
<x>;<y>;<z>
.
.
.
<x>;<y>;<z> //n1-mal
<AnzahlVonTerminalen=n2>
<x>;<y>;<z>
<x>;<y>;<z>
<x>;<y>;<z>
.
.
.
<x>;<y>;<z> //n2-mal
//das ganze m-mal
untere Grenze von m ist 0
untere Grenze von nX ist 1 (oder 2) also mindestens eine Quelle (und ein Terminal)
Grenzen von x;y;z liegen zwischen 0;0;0 und Breite;Hoehe;Tiefe

als Beispiel:

Code: Alles auswählen

10;10;1
2
3
0;0;0
2;3;0
4;3;0
2
5;6;0
9;9;0
fuer die Loesung (falls gewollt)

Code: Alles auswählen

<Breite>;<Hoehe>;<Tiefe>
<LaengsterPfad>
<AnzahlVonTerminalmengen=m>
<AnzahlVonTerminalen=n1>
<x>;<y>;<z> //erster Knoten implizit Quelle
<x>;<y>;<z>
<x>;<y>;<z>
.
.
.
<x>;<y>;<z> //n1-mal
<AnzahlVonZwischenknoten=nz1>
<x>;<y>;<z>
<x>;<y>;<z>
<x>;<y>;<z>
.
.
.
<x>;<y>;<z> //nz1-mal
<AnzahlVonTerminalen=n2>
<x>;<y>;<z>
<x>;<y>;<z>
<x>;<y>;<z>
.
.
.
<x>;<y>;<z> //n2-mal
<AnzahlVonZwischenknoten=nz2>
<x>;<y>;<z>
<x>;<y>;<z>
<x>;<y>;<z>
.
.
.
<x>;<y>;<z> //nz2-mal
//das ganze m-mal

citta
Mausschubser
Mausschubser
Beiträge: 96
Registriert: 7. Nov 2006 21:52

Re: Dateiformat für 08/09 grid.xsd

Beitrag von citta » 18. Nov 2008 15:51

Gibt's jetzt eine Einigung?

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Dateiformat für 08/09 grid.xsd

Beitrag von Prof. Karsten Weihe » 19. Nov 2008 15:44

Hallo allerseits,

ich lege hiermit endgültig fest, dass das unten von patrick_s spezifizierte Format verbindlich ist.

Gruß,

KW

---

patrik_s.stud.tu hat geschrieben:Wenn ein simpleres Dateiformat her soll, dann bietet sich immernoch folgendes an:

wobei //Kommentare sind und <variable> durch deren Wert ersetzt wird

fuer das Einlesen von Problemen

Code: Alles auswählen

<Breite>;<Hoehe>;<Tiefe>
<AnzahlVonTerminalmengen=m>
<AnzahlVonTerminalen=n1>
<x>;<y>;<z> //erster Knoten implizit Quelle
<x>;<y>;<z>
<x>;<y>;<z>
.
.
.
<x>;<y>;<z> //n1-mal
<AnzahlVonTerminalen=n2>
<x>;<y>;<z>
<x>;<y>;<z>
<x>;<y>;<z>
.
.
.
<x>;<y>;<z> //n2-mal
//das ganze m-mal
untere Grenze von m ist 0
untere Grenze von nX ist 1 (oder 2) also mindestens eine Quelle (und ein Terminal)
Grenzen von x;y;z liegen zwischen 0;0;0 und Breite;Hoehe;Tiefe

als Beispiel:

Code: Alles auswählen

10;10;1
2
3
0;0;0
2;3;0
4;3;0
2
5;6;0
9;9;0
fuer die Loesung (falls gewollt)

Code: Alles auswählen

<Breite>;<Hoehe>;<Tiefe>
<LaengsterPfad>
<AnzahlVonTerminalmengen=m>
<AnzahlVonTerminalen=n1>
<x>;<y>;<z> //erster Knoten implizit Quelle
<x>;<y>;<z>
<x>;<y>;<z>
.
.
.
<x>;<y>;<z> //n1-mal
<AnzahlVonZwischenknoten=nz1>
<x>;<y>;<z>
<x>;<y>;<z>
<x>;<y>;<z>
.
.
.
<x>;<y>;<z> //nz1-mal
<AnzahlVonTerminalen=n2>
<x>;<y>;<z>
<x>;<y>;<z>
<x>;<y>;<z>
.
.
.
<x>;<y>;<z> //n2-mal
<AnzahlVonZwischenknoten=nz2>
<x>;<y>;<z>
<x>;<y>;<z>
<x>;<y>;<z>
.
.
.
<x>;<y>;<z> //nz2-mal
//das ganze m-mal

m_gaber
Windoof-User
Windoof-User
Beiträge: 39
Registriert: 26. Okt 2004 15:09

Re: Dateiformat für 08/09 grid.xsd

Beitrag von m_gaber » 24. Nov 2008 14:52

leider bin ich erst jetzt wieder ins Forum gekommen und habe nun diese Entscheidung gelesen.

ich möchte hier nur mal etwas dazu sagen: wer gelesen hätte was eisnerd und ich geschrieben haben, hätte gesehen, dass der code für den Parser bereits komplett im verlinkten sun-Dokument enthalten war. Diesen brauchte man nur in zwei Klassen zu kopieren und war glücklich. Der Einarbeitungsaufwand für die Tools ist also vermutlich durch 1h nach oben beschränkt.

Benutzeravatar
Maradatscha
Computerversteher
Computerversteher
Beiträge: 353
Registriert: 2. Okt 2006 18:53

Re: Dateiformat für 08/09 grid.xsd

Beitrag von Maradatscha » 28. Nov 2008 19:58

bedenke
es gibt leute die java nicht benutzen

m_gaber
Windoof-User
Windoof-User
Beiträge: 39
Registriert: 26. Okt 2004 15:09

Re: Dateiformat für 08/09 grid.xsd

Beitrag von m_gaber » 1. Dez 2008 15:05

sorry, aber die die kein java verwenden weil sie mit etwas anderem fitter sind halte ich für duchaus in der Lage den passeden XML-Parser-Klassen-Generator zu bedienen der sich sicher für jede Sprache findet (ok ausser vielleicht für brainfuck ;) )

Antworten

Zurück zu „Praktikum: Algorithmen“