spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Kommt ja auch drauf an was du nebenbei machst. Wenn du immer dann viel Action machst wenn der Greedy dran ist, dann hat man einen klaren Vorteil.

2.75, wo seid ihr ?

Ich bin bei 1,82. Nun muss ich aber die Geschwindigkeit verbessern.

Ich schaffe nur 87504 task/sec

Wo liegt ihr bei der Geschwindigkeit?


EDIT: Das ist ja mal sehr komisch, im release habe ich nur 0,5 statt wie im debug 1,8. Da muss ich wohl selbst optimieren

Zitat von »"marfi"«

Ich schaffe nur 87504 task/sec

Wo liegt ihr bei der Geschwindigkeit?

... mit dieser Zahl kann man so erstmal nix anfangen. Setz die Zahl mal in's Verhältnis mit der Anzahl tasks/sec vom greedy.

Bei mir sind das im Moment ca.
Verhaeltnis der Gesamtpunktzahlen: ...... ~1.5
Verhaeltnis der Tasks pro Sekunde: ...... ~0.7

Verfolge gerade eine neue Strategie. Mein Code ist noch provisorisch und nicht optimiert... Da geht noch was

Achso ja Hab da gar nicht dran gedacht.

Verhältnis tasks pro sec.
my : greedy = 0,61

Kann mal jemand vllt einen Umsetzungstipp geben? Mache zum ersten Mal bei diesem Contest mit und bin jenseits von Gut und Böse (mein Verhaeltnis der Gesamtpunktzahlen dümpelt bei 0,2 rum ).

Mein Ansatz ist auch wirklich blöde (nutzte dazu noch Vektoren und sortier-Funktionen -> langsam). Habe aber momentan echt keinen Ansatz.

Erstmal in eigener Sache: Wenn es bei den naechsten Contests um Geschwindigkeit wie hier geht, die Zeitmessung ohne Floating Point zu machen ( zu mindestens wenn man wie hier so oft misst ). Eine Optimierung mittels MMX / SSE/ SSE2 im Integerbereich ist dann nicht zum scheitern verurteilt. Aktuell hilft es mir aber nichts, bin noch bei reinem C/C++ :-).

@spacegaier: Naja, du faengst an, erstmal den Dummy-Algorithmus zu implementieren (exakter Loeser) und schaust dann weiter. Mein zweiter war dann Meet-in-the-middle. Dann schaust du wie sich der Algorithmus verhaelt, wann und wo er langsam ist. Dann kannst du weiter schauen: Approximationsalgorithmen etc. ... und schaust, wann und wo sie langsam sind. Und dann kannst du sie optimieren. Ich glaube ich habe den schnellsten Meet-in-the-middle Algorithmus, den man mit "C" hinkriegen kann zumindestens bis Laenge 40 oder so), leider ist er immer noch nicht gut genug. Der andere Weg ist, sich zu fragen, warum greedy so gut ist, wann und wo das passiert und dort optimieren, mein eigener greedy lag bei 1.33 Vergleich. Dann kannst du weggehen vom allgemeinem Ansatz und der Aufgabenstellung angepasst, dich nur auf Probleme der Groesse 50 oder weniger beschraenken. Und vieles mehr ...... Btw. ich mag die Aufgabenstellung.

Da es ein NP-vollstaendiges Problem ist, solltest du nicht zu viel erwarten, ein Faktor 2 ist da schon gigantisch. Btw. sortieren muss ich auch mal, nutze sogar die STL dafuer :-).

Zitat von »"knivil"«

2.75, wo seid ihr ?

2,75?? im release-mode? nicht schlecht!

Bin jetzt bei ~2.3

Etwas C++ brauche ich da schon noch. Konkret: g++ -O3. Mein Fedora kann kein Visual Studio starten. Jaja, alles in der GNU Compiler Collection drin ...