WPC... geht weiter! -> wpc12
-
volkard schrieb:
haben jetzt alle den spaß verloren und ich bin der einzigste, der einsendet?
Hm, also ich werde sicher auch noch einsenden
Habe heute noch ein paar Millisekunden herausschlagen können, aber ich glaube, in der Optimierung des Algorithmus selbst kann ich mit meinem Wissen nicht mehr wirklich was erreichen. Das einzige, was jetzt nochmal einen echten Schub geben würde, wäre, wenn ich das Problem mit den zwei Wegen vorab entscheiden könnte... Ich glaube, wer das schafft (oder sogar schon geschafft hat), hat gute Karten auf den Sieg
-
kwaart schrieb:
Habe heute noch ein paar Millisekunden herausschlagen können, aber ich glaube, in der Optimierung des Algorithmus selbst kann ich mit meinem Wissen nicht mehr wirklich was erreichen. Das einzige, was jetzt nochmal einen echten Schub geben würde, wäre, wenn ich das Problem mit den zwei Wegen vorab entscheiden könnte... Ich glaube, wer das schafft (oder sogar schon geschafft hat), hat gute Karten auf den Sieg
Da ich bei der Bundeswehr bin und nur im Büro sitze, habe ich heute mal wieder sehr viel Zeit gehabt und meinen Algorithmus noch optimiert. Ich erreiche jetzt mit Dev-Cpp ca. 76 ms bei 1.000.002 Glühbirnen
-
TomasRiker schrieb:
kwaart schrieb:
Habe heute noch ein paar Millisekunden herausschlagen können, aber ich glaube, in der Optimierung des Algorithmus selbst kann ich mit meinem Wissen nicht mehr wirklich was erreichen. Das einzige, was jetzt nochmal einen echten Schub geben würde, wäre, wenn ich das Problem mit den zwei Wegen vorab entscheiden könnte... Ich glaube, wer das schafft (oder sogar schon geschafft hat), hat gute Karten auf den Sieg
Da ich bei der Bundeswehr bin und nur im Büro sitze, habe ich heute mal wieder sehr viel Zeit gehabt und meinen Algorithmus noch optimiert. Ich erreiche jetzt mit Dev-Cpp ca. 76 ms bei 1.000.002 Glühbirnen
Warum gerade 1.000.002 Glübirnen und nicht 1.000.000?
-
Ponto schrieb:
Warum gerade 1.000.002 Glübirnen und nicht 1.000.000?
weils durch 3 teilbar ist.
-
borg schrieb:
Ponto schrieb:
Warum gerade 1.000.002 Glübirnen und nicht 1.000.000?
weils durch 3 teilbar ist.
Kann es sein, dass die Eingabe immer um zwei Elemente erweitert wird?
-
1. Ich wollte mal fragen, wie weit man eigentlich gehen darf? std::vector<bool> ist nicht gerade der schnellste Container, wie hier schon festgestellt wurde. Wenn man jedoch auf seine interne Repräsentation zugreift, kann man einiges rausholen. Ich hab mal einen Test mit Intels 8.1 Compiler und der libstdc++ gemacht. Bei einer Eingabe von 50000000 Lampen konnte ich den Algorithmus von 1,81 auf 1,21 Sekunden beschleunigen. Deshalb meine Frage darf man sowas machen? Wenn ja, ist es natürlich notwendig zu wissen, welche STL Implementierung zum Auswerten verwendet wird. Aber eigentlich bin ich der Meinung, dass nur das im Standard festgelegte Interface verwendet werden darf.
2. Ich hab mal einen größeren Rechner mit der Aufgabe beauftragt und festgestellt, dass der Rückgabewert das Problem ist. Ich hab mal 2^32 Lampen verwendet. Die beiden Eingabestrings machen dann 2^33 Bits oder 2^30 Bytes oder 1GiB aus. Die Instanz hatte die optimale Lösung mit ungefähr 3000000000 Positionen. Ein size_t hat auf dem Rechner 8 Byte. Das machte also 24000000000 Byte oder 22,35 GiB. Meine Implementierung benötigte dafür übrigens 107 Sekunden. Ich konnte noch einen Test mit einer Eingabe von 2^33 Lampen machen, was ungefähr 48 GiB verbraucht hat. Bei 2^34 Lampen hat dann der Rechner angefangen zu swappen, so dass es sinnlos war. Das Ergebnis ist eigentlich, dass das Ergebnis verhältnismäßig sehr viel Speicher frisst und man bei einer anderen Darstellung oder bei der alleinigen Ausgabe der Schalteranzahl viel größere Instanzen rechnen könnte.
-
1. Die Lösung sollte standardkonform sein.
2. Jo, das ist klar. Aber letztlich geht es ja nicht drum riesige Instanzen zu berechnen, sondern einfach schneller zu sein als alle anderen. Natürlich ist die Rückgabe nicht optimal. Ein std::vector<bool> für welche Schalter werden gekippt, welche nicht wäre auch möglich gewesen. Das hätte aber einige Dinge, die ihr so noch rausfinden durftet vorausgesetzt. Und nur die Zahl schien mir doch fast ein bißchen wenig.
-
Du hast nicht gerade die Testumgebung, die ich mir wünschen würde.
Mein Algorithmus ist sehr platzsparend, braucht keinen zusätzlichen Speicher ausser für das Ergebnis und ein paar Variablen. Dafür hätte er gerne einen schnellen Prozessor und schnellen RAM.
Auf meinem durchschnitts PC sieht das so aus:
Pentium4 1.7GHz, 256MB DDR-SDRAMMit -march=pentium4 -O3 braucht mein Algo nur noch 15ms (Durchschnitt) für Blöcke der Grösse 1 000 002.
Ich weiss nicht genau, was du mit standardkonform meinst, aber mein Programm sollte auf jedem 32bit-x86 mit gcc >= 2.9 kompilieren und laufen.
-
Kannst Du uns sagen, in welcher Größenordnung die Ketten liegen, die Du zum Testen verwenden wirst? Am besten wäre es, wenn Du möglichst vielseitig testest, d.h. zufällige kleine/mittlere/lange Ketten der Länge 3n/3n+1/3n+2.
Nicht dass wir hier alle auf Millionen von Lämpchen optimieren und am Ende testest Du es immer nur mit 20 oder 30...Mit standardkonform meint er wohl, dass es nicht erlaubt ist, an der "inneren Repräsentation" von vector<bool> herumzuspielen.
Ich finde eigentlich Wettbewerbe, wo es um die Kürze des Programms geht, viel besser. Da kann man wenigstens sicher sein, dass das Ergebnis überall gleich ist. Hier hat derjenige einen großen Vorteil, der den gleichen Prozessor wie das Testsystem hat.
Vielleicht sollte man die Einsendungen auch auf mehreren Systemen testen (Celeron, Pentium 3, Pentium 4, Duron, Athlon XP, Athlon 64) und die Mittelwerte nehmen?
-
15ms! Meiner braucht selbst mit vector<char> noch doppelt so lange
Bei schnellerem Rechner... hm. Ich glaube, vom Siegercode werde ich noch einiges in Sachen Performance-Optimierung lernen können
-
d-f-g schrieb:
Du hast nicht gerade die Testumgebung, die ich mir wünschen würde.
Für den relativen Vergleich der Algorithmen würde es auch ein 486er tun. Die absolute Geschwindigkeit des Rechners ist vollkommen unerheblich.
@d-f-g: Solange ich es auch noch auf nem anderen Compiler als dem gcc übersetzen kann.
Ich möchte eigentlich keine gcc-spezifischen Hacks drinhaben.@ThomasRiker: Für den Speedtests werde ich vor allem auch große Lichterketten benutzen, damit gute Algos auch ne Chance haben sich abzusetzen.
MfG Jester
-
Jester schrieb:
d-f-g schrieb:
Du hast nicht gerade die Testumgebung, die ich mir wünschen würde.
Für den relativen Vergleich der Algorithmen würde es auch ein 486er tun. Die absolute Geschwindigkeit des Rechners ist vollkommen unerheblich.
tja, mathematiker eben.
mal was von O-notation gehört und nur alles gleichsetzen.problem ist folgendes: ich kann entweder
a) mit n durchläufen durch's array rasen, dabei feststellen, ob diese oder jene lösung ok ist und dann diese oder jene lösung langsam berechnen.
b) oder ich kann erst diese lösung berechnen, und wenn's nicht klappte, dann jene.ist jetzt das ram viel lahmer als der prozessor, dann ist b) besser. denn ich brauche 2*n mal op[] und zu 50% wahrscheinlichkeit nochmal 2*n mal op[]. bei a) brauche ich aber immer 2*n mal op[] und nochmal 2*n mal op[].
andererseits ist bei nem 486-er auf 33MhZ mit ebensoschnellem ram die lage vermutlich anders. da muss man echt rechentakte sparen und sicherlich bestimmt vermutlich ist a) viel besser.also wäre es schon nötig, daß du wenigstens ungefähr verrätst, welcher test-rechner genommen wird.
was ganz anderes wäre es, wenn dieses problem in der tat algorithmische vereinfachungen enthielte, die deutlich zwischen den ersten drei plätzen unterscheiden würden. ist aber nicht so.
@ThomasRiker: Für den Speedtests werde ich vor allem auch große Lichterketten benutzen, damit gute Algos auch ne Chance haben sich abzusetzen.
auch diese aussage ist enorm wichtig. die sagt, daß man durchaus mal nen operator new benutzen darf, wenn dafür das asymtotische verhalten besser wird. ich hab nämlich auch schon beide lösungsstränge in den selben ergebnis-vector geschrieben und dann einen teil wieder rausgelöscht, um new/delete zu sparen und um lieb zur RVO zu sein. muss man aber als dunklen hack bezeichnen, der da eigentlich nix zu suchen hat. mit echt großen eingaben fliegt die begründung für 95% der dunklen hacks weg, man kann einigermaßen auf dem eigenen rechner messen. und ich habe noch gar nix gemessen und beschränke mich drauf, mir zu überlegen, bei welcher version die maschine sich wohl am wohlsten fühlt. geht auch nur gescheit, wenn man einmalige aspekte wie ein new/delete außen vor lassen darf, weil die messwerte saugroß sind. nee, ich lassie sie gar nicht außen vor. natürlich nicht. aber wenn ich den eindruck habe, mit 3 new-aufrufen außen auch nur einen takt in der innersten schleife sparen zu können, tue ich es, da ist kein raten mehr, welche testmaschine, wie schnell da der op new ist und so.
-
Ich werde wohl den Celeron mit 475Mhz benutzen. Weil der einfach deutlich mehr RAM hat und ich dadurch größere Lichterketten fahren kann, ohne daß ich swappen muß. Der Speed-Unterschied zwischen den 475Mhz und den 650 ist ja nicht soo schrecklich riesig.
Der 475Mhz-Rechner hat 75Mhz Bustakt. Ihr könnt also getrost davon ausgehen, daß der Prozessor schneller ist als das RAM.
Ungefähr das System verraten hab ich schon vor ein paar Seiten als ich gesagt hab welche Rechner ich habe.
Ich bin mir ziemlich sicher, daß ihr Eure Meßergebnisse daher getrost übertragen könnt. Die Zahlen werden halt nur nicht ganz so groß.
-
Hm, ein bisschen konnte ich heute nochmal rauskitzeln, andererseits habe ich auch wieder ein bisschen was verloren, nachdem ich festgestellt habe, dass die rndBool() Funktion meines Messprogrammes unbefriedigende Resultate geliefert hat und ich sie etwas umgeschrieben habe... Vorher hat sie zu oft 'true' geliefert, auf ausgeglicheneren Ketten ist mein Algorithmus ein paar ms langsamer. Mist
Mal eine andere Frage, jester, auch wegen der Messung: Ist es wirklich klug, dass der Algorithmus bei Nichtlösbarkeit eine Exception wirft? Da ist zwar an und für sich nichts Verkehrtes dran, aber wenn während der Zeitmessung eine Exception geworfen wird, dann verfälscht das die Messung signifikant... andererseits sollen nicht lösbare Ketten ja sicher nicht ausgeklammert werden?
-
kwaart schrieb:
Ist es wirklich klug, dass der Algorithmus bei Nichtlösbarkeit eine Exception wirft? Da ist zwar an und für sich nichts Verkehrtes dran, aber wenn während der Zeitmessung eine Exception geworfen wird, dann verfälscht das die Messung signifikant... andererseits sollen nicht lösbare Ketten ja sicher nicht ausgeklammert werden?
bei langen ketten verfälscht die exception doch gar nicht messbar.
-
Hm, hast recht. Komisch, ich hatte einmal eine Messung, bei der die Exception über 100ms Verzögerung bewirkt hat, ehe der try/catch-Block fertig war, aber offenbar war das wohl mit deaktivierten Compileroptimierungen. Nichts für ungut, mein Fehler.
-
kwaart schrieb:
Mal eine andere Frage, jester, auch wegen der Messung: Ist es wirklich klug, dass der Algorithmus bei Nichtlösbarkeit eine Exception wirft? Da ist zwar an und für sich nichts Verkehrtes dran, aber wenn während der Zeitmessung eine Exception geworfen wird, dann verfälscht das die Messung signifikant... andererseits sollen nicht lösbare Ketten ja sicher nicht ausgeklammert werden?
Am besten wäre es, einen Vektor, dessen letztes Element N ist, zurückzugeben. Es stehen ja nur die Schalter 0...N-1 zur Verfügung.
-
Was genau wäre daran besser?
Kannst Du bei 1000002 Lichtern durch Messung rausfinden ob ne Excpetion fliegt?
Und bei 100000002?
-
Jester schrieb:
Kannst Du bei 1000002 Lichtern durch Messung rausfinden ob ne Excpetion fliegt?
Und bei 100000002?Da kann gar keine Exception geworfen werden
Es sei denn der Algorithmus ist fehlerhaft.
Selbst wenn Exceptions viel Zeit brauchen sollten, so ist es letztendlich doch egal, weil jeder der Teilnehmer in diesem Fall eine Exception werfen muss, also gleiche Bedingungen für alle.
-
Stimmt.
Da kann nix fliegen. Aber ich wollte ja nix verraten.
Wie auch immer, ich denke nicht, daß es meßbar ist wenn eine fliegt.MfG Jester