Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Wahnsinnige Vegetarier
Ich wollte mich wegen 3 Punkten vergewissern bezüglich der Klasse Veggiewahn im Public-Test:
-
der Test(4) unter 666ms geschafft wurde
und zweitens der wichtige allgemeine Test (if this fails, you get no points at all…) auch bestanden wird mit 1 Sekunde. -
Wenn ich das richtig verstehe, muss der Test(4) unter 1 MILLISEKUNDE geschafft werden, weil er dann im allgemeinen performance-Test mit (if this fails…) 1000 mal wiederholt wird, was zusammen knapp unter 1 Sekunde
ausmacht.
Bei mir ist der Test(4) mit knapp 1 Sekunde allein das ganze zum Scheitern verurteilt. Ich habe aber auch nicht gesehen, wo meine Memoization falsch oder ineffizient wäre.
- Memoization ist doch der rekursive Aufruf mit berücksichtigung bereits berechneter werte und NICHT iterativ, sprich bottom-up mit Tabulation.
Verstehe ich das richtig?
Der Test braucht bei dir 1 Sekunde wenn er einmal ausgeführt wird und Weniger als eine wenn er 1000 ausgeführt wird?
Das macht ehrloch gesagt wenig sinn, selbst wenn man bedenkt, dass men evtl. statisch ist, denn es werden ja keine weiteren Tests ausgeführt, wenn ein Test fehlschlägt, sprich es kann nicht sein, dass der 1000x-Test nur so schnell ist, da er nur das Ergebnis, das im einzeltest berechnet wurde plumb abruft.
Bei mir brauchen übrigens Alle test bis auf der 1000x-Test 0,000s und der 1000x-Test 0,001s und mein rechner ist ca. 4 Jahre alt…
der Test mit 106 Gerichten und 111 Gewürzen (Public Test 4) braucht knapp 1 Sekunde(und ein paar Millisekunde mehr oder weniger).
Ich habe nur geschlussfolgert, wenn man den 1000er Test bestehen möchte, so sollte der Test-4 unter 1 Millisekunde liegen, weil Test 4 1000 mal hintereinander durchgeführt wird.
Das bedeutet, dass der 1000er Test über 1000 Sekunden bräuchte, bei meiner Implementierung.
Benutzt du irgendwo Methoden die an sich nicht erlaubt sind (eg. [m]java.lang.Math[/m]) oder berechnest du irgendwas doppelt? Wenn du genauer sehen willst was deine Rechnerzeit verschwendet, kannst du dir einen Profiler wie VisualVM anschauen.
An sicht, ist „Memoization“ und „Tabulation“ (als zumindest Konzept wie es in den Übungen besprochen wird) nicht strikt an Rekursion und Iteration gebunden. Man kann per se, auch Tabulation rekursiv umsetzen. Aber das ist nun eher Pedantik.
Ja, das würde es theoretisch bedetuten, wenn du keine globale Memoization-Variable hättest, die nach dem ersten Durchlauf das Ergebniss für die anderen Durchläufe gespeichert hat und somit dort das Ergebniss nur noch aufgerufen werden muss.
Allerdsing sollte der 1000er Test mindestens so lange brauchen wie der Einzel Test 4, was beid dir laut deiner Schilderung nicht der Fall ist, was höchst merkwürdig ist…
Der Bug ist gefunden. Im Grunde genommen wurde entweder FALSCH memoisiert oder gar nicht (was in dem Fall zu dem richtigen Ergebnis führte, aber erwartungsgemäß langsamer). Danke für das Feedback!