Problem 3 - Schritt 4: minimaler Schnitt

[nt4u]

Hallo,

meine Tests scheinen durchzulaufen (bei Test Big weiß ichs noch nicht), aber es dauert übermäßig lange. Irgendwas hab ich falsch gemacht, bei der Auswahl der Kanten. Wie wählt ihr die Kanten aus? Ich sehe im Moment keine gute Möglichkeit. Bei mir funktioniert es nach folgendem Schema:

Code: Alles auswählen

für alle erreichbaren Knoten k
   für alle Nachbarn n von k
      wenn n nicht in der Menge der erreichbaren Knoten liegt, füge Kante k-n zur Ausgabemenge hinzu

Gruß,
Moritz

[d3non]

Also was bei dir so lange braucht kann ich so nicht sagen - deine implementierung ist auf jeden fall schneller als das was ich da gecodet habe.
wenn ich so drüber nachdenke echt unnötig aufwändig was ich da geschrieben hab...glaub ich muss noch mal ne schöne lösung abgeben

PS: ich vermute dein geschwindigkeitsproblem liegt wo anders

[leviathan]

Ich kann mich dem Vorredner nur anschließen. Mein Code funktioniert auch nach dem gleichen Prinzip; die Geschwindigkeit ist, wenn auch nicht blitzschnell, doch befriedigend (ca. 6 Sekunden für alles). Ich würde den Fehler eventuell in Abbruchbedingungen diverser Schleifen suchen.

[Christian M.]

Bei mir war ein riesiges Performanceloch, dass ich (idiotischerweise) in der BFS eine Schleife hatte, die für jeden Nachbarn von einem Knoten irgendwas macht; und die Liste der Nachbarn habe ich mir nicht über eine Methode geben lassen sondern bin jeden Knoten des Graphen durchgegangen und habe geguckt ob er ein Nachbar ist ...

Aber falls dieses spezielle Problem bei dir nicht in der Fall ist, gibts hier im Forum zum letzten Praktikum noch einen sehr hilfreichen Tipp, wo jemand die nötigen Kommandozeilenparameter beschreibt, die für eine genaue Laufzeitanalyse deines Codes nötig sind: damit habe ich bei mir das Loch direkt identifizeren können. Denn eine performance-technisch versaute BFS kommt bei einem Praktikum, wo die BFS gefühlte eine Millionen mal ausgeführt wird, nicht unbedingt optimal .

[Vockilein]

Ich habs jetzt auch soweit hinbekommen aber mein minimaler Schnitt braucht bei testBig noch ca. 45 s. Ich hab mal nach dem Hinweis vom letzten Praktikum gesucht.

Jetzt hab ich folgendes Problem: Wie mache ich das:

Aufrufen kann man den aus dem Verzeichnis Problem2 dann so:

Code: Alles auswählen
java -Xrunhprof:cpu=samples,depth=8 -cp .:junit.jar org.junit.runner.JUnitCore StrikeForceTest


Die junit.jar muss man sich irgendwoher besorgen, das depth dient dazu dass die Stacktraces aussagekräftiger werden. Dann wartet man ab bis der Test durchläuft, oder drückt strg-alt-\ .

Wie kann ich bei Windows was aus dem Verzeichnis aus aufrufen und so? Wär schön wenn mir da jemand weiterhelfen könnte sonst wird die Suche beschwerlich

[leviathan]

Das Aufrufen in Windows geht über die Kommandozeile (Start->Run->"cmd", danach mit "cd" in das Verzeichnis gehen und da dann ausführen).

Allerdings habe ich jetzt eine weitaus bessere Methode zum Profilen vom Java-Code mit Eclipse gefunden, und zwar den Eclipse-TPTP. Das ist ein Plugin, der es ermöglicht, JUnit-Test zu profilieren, Zeit- und Speichermessungen durchzuführen, und eigentlich noch viel mehr - und das Ganze mit ins Eclipse integriert.

Zu finden in Eclipse mittels Help->Software Updates->Available Software->Ganymede Update Site->Testing and Performance, einfach alle Pakete dort aktivieren und installieren.

Nach der Installation erscheint bei den Debug, Run und Tools Buttons auf dem Toolbar ein Profile Button, mittels dem man JUnit Tests mit Profiler laufen lassen kann und Konfiguration des Profilers anpassen.

[Vockilein]

Muss ich da noch irgendwas besonders einstellen bei dem Profiler? Bei mir klappts irgendwie nicht. Er zeigt keine Ergebnisse an... und zeigt in der Profileransicht auch keine JUnit Tests mehr an...

Habs durch Code durchschauen auf 22s für BigTest() gedrückt. Wie lange läuft das bei euch so?

[leviathan]

Ich lasse den Test mit dem Profiler laufen, dann wechselt er selbst in die Profiler-Perspektive und führt JUnit aus. Nachdem der Test fertig ist (oder terminiert wurde), braucht er ganz kurz zum Verarbeiten der eingesammelten Daten, und danach kann man links im "Profiling Monitor" Execution Time Analysis doppelklicken, worauf er im Editorfenster eine Übersicht der gelaufenen Klassen und Methoden darstellt mit Zeiten und diversen Daten. Die Klassen und Methoden kann man ebenfalls anklicken, um ggf. tiefergehende Details anzusehen, z.B. von wem die Methode aufgerufen wurde und welche Aufrufe am meisten Zeit gekostet haben.

[daniel_b]

Will bei mir irgendwie nich.

IWAT0435E An error occured when connecting to the host.

[Monitor]: The launch requires at least one data collector to be selected.

Muss ich noch irgendwas einrichten/angeben/installieren?

[robert.n]

Cool, das ist ja geil. Danke!

Habe nur noch das Problem, dass immer diese Fehlermeldung in der Konsole ausgegeben wird:

ERROR: JVMPI, an experimental interface, is no longer supported.
Please use the supported interface: the JVM Tool Interface (JVM TI).
Error occurred during initialization of VM
-Xrun library failed to init: piAgent
Could not resolve to JVMPI interface

Dazu hab ich folgendes gefunden:

19.4. TPTP and Java 6

An important thing to know about TPTP is that, at the time of this writing (using Eclipse 3.3 Europa), the TPTP profiling tools do not support Java 6. TPTP relies on JVMPI (JVM profiling interface), which it uses to capture data about applications running in the JVM. Now JVMPI was dropped in Java 6 in favor of the more modern and flexible JVMTI (JVM Tool Interface). If you try to run TPTP using a Java 6 VM, you will obtain an error along the lines of "FATAL ERROR: JVMPI, an experimental interface, is no longer supported." So if you are using Java 6, make sure that you are running Eclipse under Java 5 if you want to use TPTP.

You can run Eclipse using a different JVM using the vm command-line option. Here is how you might do this on a Windows machine:

D:\tools\eclipse\eclipse.exe -vm "C:\Program Files\Java\jdk1.5.0_10\jre\bin\javaw.exe"
-vmargs -Xmx512M

Quelle: http://my.safaribooksonline.com/9780596 ... 7_d1e27125

Dann muss ich wohl tatsächlich Java 5 zusätzlich installieren...

[Jonathan]

Anscheinend brauchen einige TPTP-Teile unter Linux eine C++-Runtime, die schon 2001(!) deprecated war. Das entsprechende compatibility-Paket ist jetzt bei diversen Distributionen, unter anderem Ubuntu, rausgeflogen. Wenn man ein 32-Bit-System hat, kann man sich mit diesem Trick behelfen: http://goodenoughjava.blogspot.com/2008 ... oblem.html

Ansonsten kann man es wohl ziemlich vergessen, den Schrott auf 64 Bit zum Laufen zu bekommen, es sei denn man holt sich ein 32-Bit Eclipse oder kompiliert es selber.

[Vockilein]

Bei mir kam dieser Fehler auch. Was kann ich da tun? Ich benutze Windows.

[nt4u]

Also bei mir funktioniert das Tool, danke für den Tipp.

Leider hab ich immer noch nicht rausgefunden, wie ich mein Programm verbessern kann. Gibts eigentlich ne spezielle Sprechstunde fürs Projekt? Oder soll ich da in die allgemeine Sprechstunde am Freitag?

Wies aussieht kostet mich BFS am meisten. 97% der Zeit gehen dafür drauf. Vielleicht rufe ichs zu oft auf? Zum Beispiel in augmentingPath(). Wie soll man das realisieren, ohne jedes mal BFS() aufzurufen? Der Graph könnte ja seine Gewichte geändert haben. augmentingPath() wird dann 2 mal in edmondsKarp() aufgerufen. Das ist ne "Teufelskette".

Gruß,
Moritz

[leviathan]

Dann muss ich wohl tatsächlich Java 5 zusätzlich installieren...

Läuft bei mir problemlos mit JDK 1.6.0_07... habe außer dem TPTP nichts sonst installieren müssen, lief einwandfrei. Vielleicht ist deine Eclipse-Installation nicht auf dem neuesten Stand?..

Will bei mir irgendwie nich.

IWAT0435E An error occured when connecting to the host.

[Monitor]: The launch requires at least one data collector to be selected.


Muss ich noch irgendwas einrichten/angeben/installieren?

Beim einrichten des Profiling Tests (in Profile Configurations) muss im "Monitor" Tab eins der Evaluierer ausgewählt werden. Ich nehme den einfachsten - "Java Profiling JRE 5 or newer"->"Execution Time Analysis". Der sollte aber beim korrekten Erstellen des Tests schon per default gewählt sein; ist er das nicht, mache es einfach per Hand rein.

Achja, und es gibt wohl einige Spezialfälle bei der Zusammenarbeit des JUnit mit dem Profiler. So startet z.B. ein Profiler, wenn man in der Java Perspektive auf "rerun" im JUnit View klickt, wenn man aber den vorherigen Test normal laufen lassen will. Und manche randomTests() terminieren bei mir nicht im Profiler, warum auch immer; man kann sie aber per Hand nach 10-15 Sekunden terminieren, die Daten werden trotzdem gesammelt und Optimierung lässt sich durchführen.

[robert.n]

Ui... ohne, dass ich etwas geändert hätte, funktioniert es jetzt. Seeeeeeeeeehr seltsam.

Was sich geändert hat, ist folgendes:
In der Monitor-Auswahl gab es bis gerade eben immer nur "PRE Java 5" o.ä. Jetzt gibt es "Java 5 or newer". Das stand da DEFINITIV vorher nicht drin...

(Dafür braucht der Profiler aber ne ganze Weile, wenn ich alle Tests profilen lasse.)