Aufgabenstellung P1

Moderator: Effiziente Graphenalgorithmen

Benutzeravatar
Render
Windoof-User
Windoof-User
Beiträge: 32
Registriert: 12. Okt 2008 17:21

Re: Aufgabenstellung P1

Beitrag von Render »

Laden des MST3 dauert bei mir so ~6s, und kruskal/prim irgendwas zwischen 1.2 und 2.5s.


Wegen Round Robin, da steht in den Folien nicht so viel zur effizienten implementierung, ich vermute mal im Round Robin einfach den Prim Algorithmus aufrufen zählt nicht? :D

Benutzeravatar
zimpfer
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 144
Registriert: 15. Mär 2009 01:07

Re: Aufgabenstellung P1

Beitrag von zimpfer »

Kruskal (ohne Einlesen und Schreiben) braucht bei mir 15 sekundenzum Berechnen des MST für MST3.ug

yourmaninamsterdam
Nerd
Nerd
Beiträge: 681
Registriert: 26. Okt 2006 14:04
Kontaktdaten:

Re: Aufgabenstellung P1

Beitrag von yourmaninamsterdam »

Ich habe grad mal meine Überprüfung des Dateiformats für MST3.ug durchlaufen lassen. Dauer: 11 Sekunden.

Übrigens scheint das ja doch weitesgehender unbekannt zu sein als ich dachte: Es gibt in Java eine Klasse Scanner, die das einfache Einlesen solcher textbasierter Formate ermöglicht.

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: Aufgabenstellung P1

Beitrag von Stille »

Render hat geschrieben: Wegen Round Robin, da steht in den Folien nicht so viel zur effizienten implementierung, ich vermute mal im Round Robin einfach den Prim Algorithmus aufrufen zählt nicht? :D
Es sollte klar sein, dass hier eine Implementierung des Verfahrens gefragt ist, welches in jedem Schritt einen Baum mit minimaler Anzahl von Knoten betrachtet. Ansonsten wäre diese Aufgabe in der Tat witzlos.

Wenn Sie den Determinismus des so beschriebenen Algorithmus beibehalten, können Sie meinetwegen aufrufen, was Sie möchten, vorausgesetzt Sie haben es selbst implementiert. :D
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: Aufgabenstellung P1

Beitrag von Stille »

yourmaninamsterdam hat geschrieben: Übrigens scheint das ja doch weitesgehender unbekannt zu sein als ich dachte: Es gibt in Java eine Klasse Scanner, die das einfache Einlesen solcher textbasierter Formate ermöglicht.
java.util.Scanner

Wichtig ist auch, gepufferte I/O zu verwenden, z.B. in Form von java.io.BufferedInputStream, und direkte Operationen auf Strings nach Möglichkeit zu vermeiden. Die sind in JAVA in der Regel extrem unperformant.
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

yourmaninamsterdam
Nerd
Nerd
Beiträge: 681
Registriert: 26. Okt 2006 14:04
Kontaktdaten:

Re: Aufgabenstellung P1

Beitrag von yourmaninamsterdam »

Stille hat geschrieben:Wichtig ist auch, gepufferte I/O zu verwenden, z.B. in Form von java.io.BufferedInputStream, und direkte Operationen auf Strings nach Möglichkeit zu vermeiden. Die sind in JAVA in der Regel extrem unperformant.
Meines Wissens ist Scanner schon implizit gepuffert.

Das mit den String-Operationen finde ich zwar erstaunlich, aber es stimmt. Hier meine Messergebnisse, einmal mit StringBuilder und einmal mit normaler Stringkonkatenation. Ich baue einen String der Länge 100000 auf.

Code: Alles auswählen

|-------------------|---|------------|------------|------------|------------|
| Measurement Point | # |   Average  |     Min    |     Max    |    Total   |
|-------------------|---|------------|------------|------------|------------|
| Buffered          | 1 |     23.131 |     23.131 |     23.131 |     23.131 |
|-------------------|---|------------|------------|------------|------------|
| Unbuffered        | 1 | 17,246.488 | 17,246.488 | 17,246.488 | 17,246.488 |
|-------------------|---|------------|------------|------------|------------|

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

Re: Aufgabenstellung P1

Beitrag von MisterD123 »

Meine "Performance"-Ergebnisse: (sorry für die zerballerte formatierung, aber das forum mag tabulatoren wohl nicht =) ich habs hinreichend zurechtgeschoben denk ich)

MST1.ug:

Code: Alles auswählen

[INFO ] [EtmMonitor] JETM 1.2.3 started.
Result Kruskal: Total Weight of MST: 261159288
Result Prim: Total Weight of MST: 261159288
Result Round-Robin: Total Weight of MST: 261159288
[INFO ] [EtmMonitor] Shutting down JETM.
 Algorithm	| Total (ms)	| Sorting (ms)	| Edge Comparisons (#)	| Component Update (ms)	| Component Checks (#)	| Node Assignments (#)
----------------+---------------+---------------+-----------------------+-----------------------+-----------------------+----------------------
 Kruskal	 |     18695,236	|     12363,365	|               6454996	|               712,136	|                733842	|              1996936
 Prim		 |     18698,674	|     15082,180	|               7592264	|             18361,734	|                730100	|               264346
 Round-Robin|     21907,865	|     13639,333	|               2359865	|              4762,572	|                386516	|              1083758
MST2.ug:

Code: Alles auswählen

[INFO ] [EtmMonitor] JETM 1.2.3 started.
Result Kruskal: Total Weight of MST: 1323900090
Result Prim: Total Weight of MST: 1323900090
Result Round-Robin: Total Weight of MST: 1323900090
[INFO ] [EtmMonitor] Shutting down JETM.
 Algorithm	| Total (ms)	| Sorting (ms)	| Edge Comparisons (#)	| Component Update (ms)	| Component Checks (#)	| Node Assignments (#)
----------------+---------------+---------------+-----------------------+-----------------------+-----------------------+----------------------
 Kruskal	 |     27431,264	|     17998,459	|               9542237	|              1173,927	|               1057062	|              2804518
 Prim		 |     24243,660	|     19146,747	|              10440312	|             23748,909	|               1042400	|               435666
 Round-Robin|     35232,187	|     20915,376	|               2634079	|              6236,108	|                637763	|              1789921
MST3.ug:

Code: Alles auswählen

[INFO ] [EtmMonitor] JETM 1.2.3 started.
Result Kruskal: Total Weight of MST: 1806814846
Result Prim: Total Weight of MST: 1806814846
Result Round-Robin: Total Weight of MST: 1806814846
[INFO ] [EtmMonitor] Shutting down JETM.
 Algorithm	| Total (ms)	| Sorting (ms)	| Edge Comparisons (#)	| Component Update (ms)	| Component Checks (#)	| Node Assignments (#)
----------------+---------------+---------------+-----------------------+-----------------------+-----------------------+----------------------
 Kruskal	 |    109513,523	|     66513,318	|              26383201	|              3317,530	|               2712772	|              7231008
 Prim		 |     83283,900	|     66809,793	|              29827393	|             81654,046	|               2687902	|              1070376
 Round-Robin|    127786,375	|     71584,908	|               7250461	|             29959,579	|               1562491	|              4388876
die zeiten gehen teilweise noch so um die 10% bis 15% runter wenn ich meine tastatur nicht anfassen würde während die kiste rechnet, aber die größenordnung stimmt ungefähr.

Was man relativ gut sehen kann ist, dass der Prim extrem wenig knotenzuweisungen braucht weil jeder knoten nur genau einmal einer komponente zugewiesen wird.

Genauso Kruskal benötigt sehr wenig Komponenten-Updates aufgrund der effizienten UnionFind datenstruktur, beim round robin dauern die updates der selben Datenstruktur ne ganze ecke länger weil da gleichzeitig eine nach größe sortierte liste der komponenten gehalten wird um die kleinste immer parat zu haben.

Was man auch relativ gut sehen kann ist, dass der Round-Robin am "effektivsten" arbeitet, der führt von allen aktionen jeweils ziemlich am wenigsten aus. Allerdings hab ich bei dem offenbar so viel overhead in der implementierung an zusätzlichen und temporären datenstrukturen, dass der enorme Vorfaktor die bessere Laufzeitkomplexität in den Schatten stellt. :(

/edit: Zeiten geupdated mit gefixtem prim. -> Warnung an alle: remove(object) der java.util.PriorityQueue ist O(n) und NICHT O(logn)!! wer die methode benutzt, zum beispiel um "decreaseKey(v,k)" durch "remove(v)-update(v.k)-insert(v)" zu erreichen (oder ähnliches) wird quadratisch mit seinem Prim!

Benutzeravatar
zimpfer
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 144
Registriert: 15. Mär 2009 01:07

Re: Aufgabenstellung P1

Beitrag von zimpfer »

Ich habe Prim nun mit Hilfe von FibonacciHeap aus JGraphT als Queue gelöst, da ich mit PriorityQueue aus Java nicht mehr weiterkam (Wenn ich die Priorität eines Queue-Objekts geändert hatte, wurde die Queue nicht aktualisiert).

Ist das in Ordnung oder sind ausschließlich Datenstrukturen aus JUNG und JAVA erlaubt?


EDIT: Ich habs umgestellt auf TreeSet
Zuletzt geändert von zimpfer am 20. Nov 2010 12:58, insgesamt 1-mal geändert.

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: Aufgabenstellung P1

Beitrag von Stille »

Hmmm, die Aufgabenstellung ist in diesem Punkt ja recht unmißverständlich. Was meint unser Mann in Amsterdam? Können wir das ausnahmsweise verantworten?
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

Re: Aufgabenstellung P1

Beitrag von MisterD123 »

nimm statt der PriorityQueue einfach ein TreeSet, da funktioniert alles in log(n). in der PriorityQueue genauso wie im TreeSet musst du ein objekt entfernen bevor du seine priorität änderst und danach neu einfügen. Das ist aber bei der PriorityQueue halt nur in linearer zeit möglich. TreeSet schaffts logarithmisch.

yourmaninamsterdam
Nerd
Nerd
Beiträge: 681
Registriert: 26. Okt 2006 14:04
Kontaktdaten:

Re: Aufgabenstellung P1

Beitrag von yourmaninamsterdam »

Mir soll es grundsätzlich recht sein, auch wenn ich zustimmen muss, dass die Aufgabenstellung das nicht vorsieht.

Ich erinnere mich in der Tat auch daran, dass Java Datenstrukturen und vor allem die PriorityQueue einige Laufzeitkuriositäten hat. Man muss da sehr aufpassen. Es hilft übrigens sehr, das eigene Programm auf den großen Eingaben zu profilen. Ich benutze da normalerweise JRat, es gibt aber sicher auch andere Profiler.

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

Re: Aufgabenstellung P1

Beitrag von MisterD123 »

oder einfach java -Xprof Class ^^

Benutzeravatar
zimpfer
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 144
Registriert: 15. Mär 2009 01:07

Re: Aufgabenstellung P1

Beitrag von zimpfer »

Ich hab nun den Fibonacci-Heap ersetzt durch ein TreeSet<PriorityElement>, wobei PriorityElement eine einfache Comparable-Klasse mit 2 integern (vertex und priority) ist.

Nun fehlen aber immer ein paar Kanten nach dem Ausführen...
In compareTo() von PriorityElement vergleiche ich nach priority, das bereitet allerdings Probleme beim Updaten der Queue mit remove() und add(), weil wenn ich im TreeSet bereits ein PriorityElement habe mit gleicher priority, gibt es Probleme bei add()...
Deshalb wird mir auch nach dem Initialisieren der Queue queue.size() = 1 ausgegeben, da ich alle mir <Knotennummer, Max_Value> initialisiert hatte.

Was kann ich da tun??


EDIT: Was der NAchfolgepost geschrieben hat, hatte ich gestern schon probiert, hatte erst nicht geklappt, aber jetzt hab ich den Fehler und es läuft.
Zuletzt geändert von zimpfer am 20. Nov 2010 12:57, insgesamt 1-mal geändert.

Tobias
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 132
Registriert: 20. Okt 2004 14:17
Kontaktdaten:

Re: Aufgabenstellung P1

Beitrag von Tobias »

Genau dann, wenn die Priorität zweier Knoten gleich ist, gib in compareTo() nicht einfach 0 zurück, sondern vergleiche als nächstes die Knoten-ID. (Stichwort lexikographische Sortierung, bloß nicht mit Buchstaben.)
Wise people talk, because they have something to say; fools, because they have to say something. (Plato)

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

Re: Aufgabenstellung P1

Beitrag von MisterD123 »

Richtig. Das TreeSet fordert compareTo als "consistent with equals", das heißt, dass compareTo GENAU DANN 0 zurückgibt, wenn equals true wäre. Das heißt, wenn du zwei "gleich große" objekte hast, die aber trotzdem unterschiedlich sind, musst du dir irgendein weiteres sortierkriterium ausdenken. zB obj1.hashCode() - obj2.hashCode, das geht für alle Typen.

Antworten

Zurück zu „Effiziente Graphenalgorithmen“