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?

Moderator: Effiziente Graphenalgorithmen
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.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?
java.util.Scanneryourmaninamsterdam 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.
Meines Wissens ist Scanner schon implizit gepuffert.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.
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 |
|-------------------|---|------------|------------|------------|------------|
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
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
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