30 Sekunden Beschränkung ?!

[burgi]

nabend,

hab das ding jetzt endlich zum laufen gebracht brauche allerding für den letzten test (testBig) 31sekunden . . irgendwo im beipackzettel zu dieser aufgabe steht dass es eine 30 sekunden beschränkung gibt. weis jemand was es damit auf sich hat ?

[leviathan]

Ich glaube, es bezieht sich auf die automatische Testierung durch das Online-System bei der Abgabe. Ich vermute, der Test dort wird nach 30 Sekunden abbrechen und fehlschlagen; allerdings scheint die Rechenleistung dort recht gut zu sein. Du kannst auf jeden Fall versuchen, hochzuladen; sollte es nicht gehen, kannst du ja bis zum Abgebetermin nochmal optimieren und erneut hochladen, das System erlaubt es.

[Le_Coeur]

Und wie lange es muss normalerweise laufen?:) Denn ich bin jetzt bei 5 Teil, und wenn ich einfach durch "Components" iteriere, dann dauert bei mir testBig 71 Sekunden

[burgi]

danke für den tipp,

habs eben hochgeladen pass time:9.379

[leviathan]

Es kommt sehr auf den Rechner an.

Mein Samsung R700 mit Core2Duo 2.5GhZ hat die Tests (mit meinem Code, natürlich) in ca. 12 Sekunden durch.
Der Linux-Rechner zuhause (alter Athlon XP 2500+) braucht satte 38.
Der Netbook (Samsung NC10, Intel Atom N270) im Akkumodus braucht über 2 Minuten...

Der Server hat nach dem ersten Upload ziemlich genau die selben 12 Sekunden gebraucht, wie der "große" Laptop; nach einer geringen Codeumschreibung ist es auf 9 gesunken, ob eher durch Zufall (geringere Serverlast) oder wirkliche Verbesserung, kann ich nicht wirklich sagen.

[burgi]

das passt ganz gut mir meinen werten zusammen mein "mainframe" zuhause ist en athlon 2400+ und ahhte wie gesagt knappe 31seks

[empe]

Ich habe auch das Samsung NC10. Mein Algorithmus braucht darauf für den big-Test ca. 25 sek, für alle Tests zusammen knapp über 30 sek, auf dem Server ca. 9.
Großartig optimiert habe ich nichts, sondern mich ziemlich an der Aufgabenstellung orientiert... soweit das bei dieser Aufgabenstellung möglich war

Es sollte also auch auf einem älteren Rechner in <30 sek gehen. Der Atom N270 hat nicht gerade viel Rechenpower.

[Le_Coeur]

Jetzt hab ich Kode optimiert, und von 190 Sekunden hab ich 8 Sekunden bekommen:)! Einziges Problem war Reversierung von der Liste! Ich hab selbst irgendwie nicht so gut geschrieben, und es brauchte 3 Sek. pro Liste!!! Dann hab ich JAva-Methode gefunden Collections.reverse() , und 0 Sek

[leviathan]

Bei Java ist es immer wichtig zu gucken, ob es das Gewünschte nicht bereits irgendwo gibt Ist meistens besser, bereits existierenden Code zu verwenden, als selbst was zu basteln.

[grek40]

Bei mir hat es auch was geholfen, an der richtigen Stelle einfach mal HashSet durch LinkedHashSet zu ersetzen -> Zeit fast halbiert.

LinkedHashSet ist immer dann interessant, wenn man eigentlich die Set-Funktionalität braucht, aber auch durch das Set iterieren muss / will. Im Gegenzug zur wesentlich verbesserten iterationsfähigkeit wird die Einfügeoperation minimal konstant verlangsamt.

Man kann auch sonst noch einiges raus holen, wenn man einfach genau überlegt, wo man ArrayList und wo LinkedList verwendet usw...

[Miguel]

toll, meine testRandom braucht normalerweise 18 sekunden auf meinem laptop (nur irgendwie hat es sich jetzt entschieden 13 sekunden zu dauern) und testBig scheint kein ende zu nehmen.
irgendwo werd ich optimisieren müssen

und ich probier mal auf meinem quad 2,8ghz, auch nicht besser, 8 sekunden für testrandom und keine ahnung wie lang für testBig

anscheinend braucht die components() ewig und da hakts

edit: ...


...


...

ouch, das tut echt echt weh. Ich hab jedes einzelne mal in der for schleife den originalen graphen neu umgekehrt ... und wenn man das eine million mal (oder wie viel mal auch immer der das im testBig macht) hintereinander macht ... tja das dauert

[d3non]

Also allen die noch Zeitprobleme haben, kann ich nur raten, mal die for-Schleife mit einem Iterator zu verwenden, anstatt immer selber zu zählen - das sollte durchaus noch was an geschwindigkeit bringen...

Bei mir auf meinem Laptop(Intel T5750/2GHz, ubuntu8.04, SUN java 1.6 patchlevel 7) laufen die gesammten Tests in 6,4sec durch. Auf dem server immerhin in 8,5sec (wer weiß, was da momentan für ein Load drauf ist; ich dachte, der wäre eher schneller als mein kleiner Lappi^^)

[dalinger]

Ich brauche für alle Tests ~ 600 Sekunden. Der Grund ist wohl die StrikeForce.components, in der ich removeAll benutzer um die Liste mit den top. sortierten Knoten zu reduzieren. Im Moment sehe ich leider keine Alternative dazu. Hier ein Auszug aus meine java.hprof.txt:

rank self accum count trace method
1 50,00% 50,00% 63576 300140 java.net.SocketInputStream.socketRead0
2 48,46% 98,46% 61627 300396 java.util.ArrayList.contains
3 0,65% 99,11% 832 300397 java.util.AbstractList$Itr.remove
4 0,05% 99,16% 61 300411 java.util.HashMap.put

TRACE 300140:
java.net.SocketInputStream.socketRead0(SocketInputStream.java:Unknown line)
java.net.SocketInputStream.read(SocketInputStream.java:129)
sun.nio.cs.StreamDecoder.readBytes(StreamDecoder.java:264)
sun.nio.cs.StreamDecoder.implRead(StreamDecoder.java:306)
sun.nio.cs.StreamDecoder.read(StreamDecoder.java:158)
java.io.InputStreamReader.read(InputStreamReader.java:167)
java.io.BufferedReader.fill(BufferedReader.java:136)
java.io.BufferedReader.readLine(BufferedReader.java:299)
java.io.BufferedReader.readLine(BufferedReader.java:362)
org.eclipse.jdt.internal.junit.runner.RemoteTestRunner$ReaderThread.run(RemoteTestRunner.java:140)
TRACE 300396:
java.util.ArrayList.contains(ArrayList.java:199)
java.util.AbstractCollection.removeAll(AbstractCollection.java:336)
StrikeForce.components(StrikeForce.java:126)
StrikeForce.solve(StrikeForce.java:182)
StrikeForceTest.testBig(StrikeForceTest.java:161)
sun.reflect.NativeMethodAccessorImpl.invoke0(NativeMethodAccessorImpl.java:Unknown line)
sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
java.lang.reflect.Method.invoke(Method.java:597)
junit.framework.TestCase.runTest(TestCase.java:168)
junit.framework.TestCase.runBare(TestCase.java:134)
junit.framework.TestResult$1.protect(TestResult.java:110)

[Jonathan]

Normalerweise kann man statt removeAll auf einer Liste auch ein Set entfernter Elemente anlegen, und dann für jedes Element dass der Liste entnommen wird schauen ob es in diesem Set ist.

[dalinger]

Ok. Hat sich geklärt. Ich habe das removeAll gebraucht weil in meine topo. Sortierung manche Knoten mehrfach vorgekommen sind. Jetzt kann eine Schleife benutzen und bin damit in der Zeit.