Aufgabenstellung P1

[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?

[zimpfer]

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

[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.

[Stille]

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?

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.

[Stille]

Ü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.

[yourmaninamsterdam]

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 |
|-------------------|---|------------|------------|------------|------------|

[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!

[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

[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?

[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]

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.

[MisterD123]

oder einfach java -Xprof Class ^^

[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.

[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.)

[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.