Besonderheit im Testfall "testBig"?

Trillium
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 1. Jul 2007 16:05

Besonderheit im Testfall "testBig"?

Beitrag von Trillium »

Ich habe mein Programm mittlerweile soweit, dass alle Tests, bis auf testBig, durchlaufen. Habt ihr irgendwelche Tipps, woran das liegen könnte? Hat der Testfall irgendwelche besonderen Konstellationen von Constraints, die in den anderen Testfällen nicht abgedeckt wurden? testBig ist ja zum Debuggen leider etwas zu big ;-). Die Graphen sind ja riesig …

Benutzeravatar
leviathan
Computerversteher
Computerversteher
Beiträge: 307
Registriert: 30. Jul 2008 14:26
Wohnort: Darmstadt
Kontaktdaten:

Re: Besonderheit im Testfall "testBig"?

Beitrag von leviathan »

Während meiner Entwicklung hatte ich eine Zeit, wo alles bis auf die letzten zwei Tests grün war - testRandom und testBig. Der Fehler war letztendlich in der components(), die die gefundenene Komponenten nicht richtig erkannt bzw. angeordnet hat (man beachte - die componentsTests liefen alle korrekt, aber das hieß nicht, dass die Funktion korrekt war).

Das Umschreiben von components() und im Endeffekt auch topologicalSort() hat aber beide Tests gleichzeitig zum Laufen gebracht, ich habe darunter auch keinen entscheidenden Unterschied (außer Anzahl der Constraints) in der Testdefinitioon gefunden.
Ein Programmierer hat immer eine Lösung. Die passt nur nicht immer zum Problem.

Hiwi für Weiterentwicklung des Lernportals (Moodle).

Trillium
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 1. Jul 2007 16:05

Re: Besonderheit im Testfall "testBig"?

Beitrag von Trillium »

Das Problem hatte ich auch. Alle Testfälle, bis auf die letzten 2, liefen fehlerfrei durch. Nach umschreiben von components und einer kleinen Änderung in dfsVisit läufts immerhin schon mal bis auf den Letzten 8).

Ich habe aber irgendwie das Gefühl, dass ich in der Klasse solve noch nen Fehler habe. Nur komisch, dass der erste Random-Test durchläuft ...

empe
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 118
Registriert: 14. Jan 2008 14:24

Re: Besonderheit im Testfall "testBig"?

Beitrag von empe »

Trillium hat geschrieben:Das Problem hatte ich auch. Alle Testfälle, bis auf die letzten 2, liefen fehlerfrei durch. Nach umschreiben von components und einer kleinen Änderung in dfsVisit läufts immerhin schon mal bis auf den Letzten 8).
Dito. Ich beschuldige da die Aufgabenstellung und die entsprechenden Tests. Es werden Hinweise gegeben, die einen zu einer "richtigen Lösung" führen. Richtig in dem Sinn, dass die Tests für die Teilaufgabe erstmal alle funzen. Die Lösung ist dann aber nicht unbedingt tatsächlich richtig. Später kriegt man dann Probleme, wenn man die fertigen Methoden benutzen muss, um die letzte Aufgabe zu lösen.

Ich war irgendwann soweit, dass alle Tests durchgelaufen sind. Ich wusste allerdings nicht warum. War mir auch erstmal egal. Inzwischen weiß ich: Ich hatte den Algorithmus richtig programmiert ohne ihn verstanden zu haben. Was ich bisher von anderen gehört habe, ging es vielen genauso. Sowohl bei der letzten Aufgabe, als auch bei anderen Teilaufgaben.

Trillium
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 1. Jul 2007 16:05

Re: Besonderheit im Testfall "testBig"?

Beitrag von Trillium »

Habe den Fehler nun gefunden. War etwas richtig dummes. Ich habe nicht bedacht, dass im letzten Testfall die Knoten durch Zahlen dargestellt werden. Wenn man von z.B. 4204 das erste Zeichen abschneidet, hat man immer noch einen gültigen Knoten, nämlich 204 …

Aber ich glaube ich habe noch gewaltiges Optimierungspotenzial. Ich brauche für den letzten Test schlappe 650s … :roll:

Abgesehen von meinem Fehler, sollten die Testfälle der einzelnen Module zukünftig allerdings schon so gewählt werden, dass alle für spätere Tests relevanten Fälle abgedeckt werden. Sonst stolpert man in den letzten Testfällen über Probleme, die man sich erstmal nicht erklären kann …

Benutzeravatar
m_stoica
Kernelcompilierer
Kernelcompilierer
Beiträge: 473
Registriert: 5. Dez 2008 20:19
Wohnort: Zuhause

Re: Besonderheit im Testfall "testBig"?

Beitrag von m_stoica »

Bei mir laufen auch nur die letzten zwei Tests nicht. Ich finde, aber dass ich components() wirklich so, wie auf dem Aufgabenblatt beschrieben implementiert habe. Was war den ursprünglich, an components() falsch? Ich bekomme außerdem die Fehlermeldung: "too many random constraints rejected expected:<502> but was:<645>". Sieht so auß alls ob ich zu oft null zurückgebe, aber ich weiß auch nicht woran dasliegt. Ich gebe einfach nur dann null zurück, wenn die gleiche Variable in einer Komponente vorkommt.

Gruß, Michael

Trillium
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 1. Jul 2007 16:05

Re: Besonderheit im Testfall "testBig"?

Beitrag von Trillium »

Die Methode components ist schon richtig auf dem Aufgabenblatt beschrieben. Das Problem ist, dass die Hinweise von einem zyklenfreien Graphen ausgehen. Während der Tests triffst du aber auf Zyklen in den Graphen und schon kann man keine topologische Sortierung mehr anwenden …

Benutzeravatar
m_stoica
Kernelcompilierer
Kernelcompilierer
Beiträge: 473
Registriert: 5. Dez 2008 20:19
Wohnort: Zuhause

Re: Besonderheit im Testfall "testBig"?

Beitrag von m_stoica »

Das Problem habe ich so gelöst, dass ich für die topologische Sortierung von jedem Knoten aus eine dfs starte. Sollte das nicht in Ordnung gehen?

Trillium
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 1. Jul 2007 16:05

Re: Besonderheit im Testfall "testBig"?

Beitrag von Trillium »

Doch, das passt. Glaube ich jedenfalls. Ich mache das im ersten Schritt zur Komponentenfindung genauso. Ich verwende in meiner Methode components die Methode topologicalSort mittlerweile überhaut nicht mehr und habe soweit den Algorithmus aus dem Cormen implementiert.
So konnte ich die Laufzeit immerhin von 650s auf 240s drücken. Aber das ist irgendwie immer noch viel zu langsam … :cry:

linn
Mausschubser
Mausschubser
Beiträge: 77
Registriert: 15. Okt 2008 21:16

Re: Besonderheit im Testfall "testBig"?

Beitrag von linn »

ja, das war nervig den testfall auf <30 sek zu kriegen, vorallem weil die spezifikationen der funktionen ziemlich kontraproduktiv sind...
mit nem dfs, das direkt ne methode auf den knoten ausführen könnte, nen graphen der mehr is als ne einfache HashMap, etc könnte man die zeit sicherlich leichter packen, aber es geht auch so.

Hier mal nen paar Sachen die mir weitergeholfen haben:
1. counter für funktionsaufrufe, beim bigTest wurd bei mir glaub ich jede funktion 1x aufgerufen ausser dfsVisit mit ~ 35000x pro solve().

2. Zeit messen :
long time_start;
long time_end;

time_start=System.currentTimeMillis();
funktionsaufruf();
time_end=System.currentTimeMillis();
System.out.println("Funktionsaufruf(): "+time_end-time_start+" ms");

Das erst für alle funktionen komplett machen, und bei der/den langsamen dann nochmal genau schaun was da soviel zeit kostet.

3. besondere Zeitfresser sind, die listen und sets.
.contains(), .remove(), .add(), .get() etc immer hinterfragen:
bsp.
for (i=arrayList.size()-1; i>0, i--) // lieber reverse(arrayList) machen und ne for-each-schleife nehmen
list.contains(vector) // gibt es vielleicht ein HashSet mit dem gleichen inhalt? wenn nicht lohnt es sich vielleicht eins zu erstellen?
list.remove(0); // wenn möglich ne linkedList nehmen und removeFirst() benutzen
for (string vector : vectors) { graph.remove(vector) } // lieber ein set erstellen und die vectors per addAll ins set einfügen und die knoten dann ignorieren wenn sie im set stehn

auch operationen die auf der benutzten datenstruktur eigentlich schnell/konstant gehen, können wahre zeitfresser sein.
set.contains() z.B.:
wenn tu testest ob bob in der selben komponente wie !bob ist musst du nicht auch noch testen ob !bob in der selben komponente wie bob ist.
überhaupt reicht es sich gegenseitig ausschliessende sccs anhand von einem .contains() zu überprüfen

Ein Patzer bei den listenoperationen wirkt sich meist stärker aus, als nen schwacher algorithmus!

Jonathan
Mausschubser
Mausschubser
Beiträge: 47
Registriert: 10. Okt 2008 13:37

Re: Besonderheit im Testfall "testBig"?

Beitrag von Jonathan »

Besser als sich selber irgendwelche unzuverlässigen Zeitmessungen zu basteln, die entweder ungenau sind oder die Laufzeit selbst beeinflussen, ist es besser den statistischen Java-Profiler zu verwenden. 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-\ .
In der java.hprof.txt steht dann unten eine Auflistung der zeitintensivsten Funktionen, mit den Trace-Nummern kann man sich den genauen Kontext raussuchen.
Mir hat das jedenfalls sehr geholfen, rauszufinden dass ich versehentlich in einer inneren Schleife suchend auf eine Liste zugegriffen hab.

Trillium
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 1. Jul 2007 16:05

Re: Besonderheit im Testfall "testBig"?

Beitrag von Trillium »

Danke für eure Tipps! Ich konnte den Übeltäter ausfindig machen … contains() auf einer Liste auszuführen ist sehr böse und get() auf einer sehr großen Liste ist zwar nicht ganz so böse, aber dennoch nicht ratsam.

Schlussendlich hab ich den Test mit einer Laufzeit von 9,259s bestanden :D

Benutzeravatar
glowhand
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 128
Registriert: 23. Okt 2008 22:23
Wohnort: Darmstadt

Re: Besonderheit im Testfall "testBig"?

Beitrag von glowhand »

38,5 Sekunden auf dem Eee PC.

Also, ohne Gamer PC schafft man das Studium wohl nicht in der Regelstudienzeit, wenn das so weitergeht :P

tanne
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 162
Registriert: 30. Sep 2008 16:05

Re: Besonderheit im Testfall "testBig"?

Beitrag von tanne »

38,5 ? :O oha ^^ krass

hab 7.1secs :)

Trillium
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 1. Jul 2007 16:05

Re: Besonderheit im Testfall "testBig"?

Beitrag von Trillium »

Die 9,259s brauchte der Rechner in der Uni, um die Testfälle durchzurechnen. Auf nem EEE braucht mein Programm gute 44s :lol:

Antworten

Zurück zu „Archiv“