Eine Woche Programmierwettbewerb: Rechtecke

TomasRiker

Werden die Algorithmen eigentlich mit verschiedenen Datensätzen getestet?
Also werden folgende Parameter bei den Tests variiert?

- Größe der Ebene (bis zu 4096x4096)
- Anzahl der Rechtecke (bis zu 50 Millionen)
- Durchschnittliche Größe der Rechtecke

Ponto

TomasRiker schrieb:

Werden die Algorithmen eigentlich mit verschiedenen Datensätzen getestet?
Also werden folgende Parameter bei den Tests variiert?

- Größe der Ebene (bis zu 4096x4096)
- Anzahl der Rechtecke (bis zu 50 Millionen)
- Durchschnittliche Größe der Rechtecke

Jo

Mehlvogel

Habe mal meinen Algorithmus in den von camper gegebenen Rahmen gebaut. Mein Algorithmus ist nach ~80 Sekunden (zumindest laut Ausgabe - ich war in der Zeit essen) mit einem Ergebnis für die 100M Rechtecke fertig. Der Default (nicht der von Jestern, sondern der andere), rechnet mittlerweile > 15 Minuten, so dass ich die Geschichte gleich abbreche und mich anderen Sachen widmen werde.

Ponto

Hallo,

die erste Version meiner Testumgebung gibt es auf:

Da sind drei Generatoren. Einer wird noch dazukommen. Alle fliessen in die Bewertung ein.

http://www.pontohonk.de/wpc/contest.tar.bz2

Hm, irgendwie ist das doof >90% der Rechenzeit hängt bei mir am "result[x][y] = z;"
Darf/Kann man das irgendwie optimieren? Blockschreiben geht ja eigentlich nicht, obwohl viele Compiler die Werte von einem Vector ja hintereinander ablegen...

Jester

BlaBlubb schrieb:

Hm, irgendwie ist das doof >90% der Rechenzeit hängt bei mir am "result[x][y] = z;"
Darf/Kann man das irgendwie optimieren?

Jo, mach das seltener.

'Tschuldigung für den Doppelpost, aber könnte man nicht die Aufgabe so abändern, dass beim result statt einem vector<vector<size_t>> dann einfach ein size_t** genommen wird? Und als Regel, dass man nicht blockschreiben darf, aber der doppelte vector ist so verflucht langsam!

Oder vielleicht, dass kein vector-Array übergeben wird, sondern man mit einem Aufruf an "SetResult( x, y, Wert)" das Dings für ein Ergebnis setzen kann?

Badestrand

Hat sich erledigt, ist gar nicht das Setzen der Werte, was so lahm ist, sondern der Rest von meinem Algorithmus
Und "result[x][y] = z;" mache ich eigentlich auch nur pro Feld 1 mal, jedenfalls in der Theorie, irgendwo steckt noch ein Fehler drin
Bin übrigens die registrierte Version von BlaBlubb, wusste nur mein Passwort nicht mehr

Ponto

BlaBlubb schrieb:

Hm, irgendwie ist das doof >90% der Rechenzeit hängt bei mir am "result[x][y] = z;"
Darf/Kann man das irgendwie optimieren? Blockschreiben geht ja eigentlich nicht, obwohl viele Compiler die Werte von einem Vector ja hintereinander ablegen...

Alle Compiler legen die Werte eines vectors im Block ab. Das ist garantiert.

Aber da result ein std::vector<std::vectorstd::size\_t > ist, sind zwei benachbarte x linien nicht nebeneinander. Du kannst dir aber ein std::vectorstd::size\_t(xdim * ydim) anlegen und das Ergebnis am Ende rüberkopieren.

camper

Ponto schrieb:

BlaBlubb schrieb:

Hm, irgendwie ist das doof >90% der Rechenzeit hängt bei mir am "result[x][y] = z;"
Darf/Kann man das irgendwie optimieren? Blockschreiben geht ja eigentlich nicht, obwohl viele Compiler die Werte von einem Vector ja hintereinander ablegen...

Alle Compiler legen die Werte eines vectors im Block ab. Das ist garantiert.

Aber da result ein std::vector<std::vectorstd::size\_t > ist, sind zwei benachbarte x linien nicht nebeneinander. Du kannst dir aber ein std::vectorstd::size\_t(xdim * ydim) anlegen und das Ergebnis am Ende rüberkopieren.

Andererseits ist es ja egal, ob nun x oder y zuerst kommt; du kannst sie ja genauso gut auch in deinem Algorithmus vertauschen.

Ponto

Es gibt ein Update meiner Testumgebung.

- Ein Randomblockgenerator ist drin
- Es wird jetzt das vollständige Bild in der GUI angezeigt
- Das ultimative Makefile ist jetzt dabei

http://www.pontohonk.de/wpc/contest.tar.bz2

camper

struct Rectangle {

   Rectangle(Coordinate minx, Coordinate maxx, Coordinate miny, Coordinate maxy)
    : minx(minx), maxx(maxx), miny(miny), maxy(maxy){}

   Rectangle(Coordinate x, Coordinate y)
    : minx(x), maxx(x+1), miny(y), maxy(y+1) {}

   Rectangle() {}

   Coordinate minx;
   Coordinate maxx;
   Coordinate miny;
   Coordinate maxy;
};

Bleibt das jetzt dabei oder gilt die Definition im ersten Posting?
Es ist ja denkbar, dass der Compiler mit PODs noch etwas besser optimieren kann, und nur der bequemen Erzeugung wegen brauchen wir hier eigentlich keine Konstruktoren. Man könnte ja genauso gut nehmen:

struct Rectangle {

   static Rectangle make(Coordinate minx, Coordinate maxx, Coordinate miny, Coordinate maxy) {
       Rectangle r = { minx, maxx, miny, maxy };
       return r;
   }

   static Rectangle make(Coordinate x, Coordinate y) {
       Rectangle r = { x, x+1, y, y+1 };
       return r;
   }

   Coordinate minx;
   Coordinate maxx;
   Coordinate miny;
   Coordinate maxy;
};

Ponto

camper schrieb:

Bleibt das jetzt dabei oder gilt die Definition im ersten Posting?
Es ist ja denkbar, dass der Compiler mit PODs noch etwas besser optimieren kann, und nur der bequemen Erzeugung wegen brauchen wir hier eigentlich keine Konstruktoren. Man könnte ja genauso gut nehmen:
struct Rectangle {

   static Rectangle make(Coordinate minx, Coordinate maxx, Coordinate miny, Coordinate maxy) {
       Rectangle r = { minx, maxx, miny, maxy };
       return r;
   }

   static Rectangle make(Coordinate x, Coordinate y) {
       Rectangle r = { x, x+1, y, y+1 };
       return r;
   }

   Coordinate minx;
   Coordinate maxx;
   Coordinate miny;
   Coordinate maxy;
};

Ok, da ich es im ersten Posting nicht gemacht habe, einige ich mich auf die letztere Form. Sollte dank RVO nicht langsamer als die Konstruktorform sein.

Ponto

Es gibt ein zweites Update meiner Testumgebung.

- Rechtecke sind so wie im ersten Post beschrieben. Die Konstruktoren sind weg und dafür make() Methoden reingekommen.
- Das ultimative Makefile benutzt jetzt ein Buildverzeichnis.
- Ein "make" erzeugt optimierten Code ohne GUI.
- Ein "make debug" erzeugt debug Code.
- Ein "GUI=1" hinter eins der beiden Makecommandos erzeugt die Qt-Gui. Dazu muss im Makefile der QTDIR gesetzt werden.

http://www.pontohonk.de/wpc/contest.tar.bz2

Ponto

Ich werde übrigends keine anderen Generatoren mehr schreiben. Ihr könnt also auf die bestehenden hin optimieren.

TomasRiker

Schon fies, dass bei 3 von 4 Generatoren immer mindestens 1 Pixel frei bleibt ...

Ponto

Es gibt ein drittes Update meiner Testumgebung.

- Ich habe den Timer für den Algorithmus nicht neu gestartet. Es wurde die Zeit für die Generierung und die Zeit für den Algorithmus gemessen.

http://www.pontohonk.de/wpc/contest.tar.bz2

TomasRiker

Ja, das hab ich auch schon gemerkt (und bei mir korrigiert).
Da ich unter Windows arbeite, musste ich den Timer durch timeGetTime() ersetzen.
Bei der Erstellung des distribution[]-Arrays ist auch noch ein Fehler drin (jedenfalls in der Version, die ich jetzt grade habe). Es kann passieren (und tut es auch), dass ein Rechteck dort eingetragen wird, obwohl es durch einen der nachfolgenden Tests rausfliegt.

Wie lange braucht ihr für:
> contest p 12345 4096x4096 4096 100000000 (100 Millionen)?

Ich bin mittlerweile bis auf 25 Sekunden runter

Ponto

TomasRiker schrieb:

Ja, das hab ich auch schon gemerkt (und bei mir korrigiert).
Da ich unter Windows arbeite, musste ich den Timer durch timeGetTime() ersetzen.
Bei der Erstellung des distribution[]-Arrays ist auch noch ein Fehler drin (jedenfalls in der Version, die ich jetzt grade habe). Es kann passieren (und tut es auch), dass ein Rechteck dort eingetragen wird, obwohl es durch einen der nachfolgenden Tests rausfliegt.

Wie lange braucht ihr für:
> contest p 12345 4096x4096 4096 100000000 (100 Millionen)?

Ich bin mittlerweile bis auf 25 Sekunden runter

Die distribution map ist nur ein einfacher Check, dass die Größen auch logarithmisch abnehmen.

Mach deine Rechtecke nicht so groß. Je größer desto einfacher. für 4096x4096 würde ich eher 512 als maxsize nehmen.

TomasRiker

Ponto schrieb:

Mach deine Rechtecke nicht so groß. Je größer desto einfacher. für 4096x4096 würde ich eher 512 als maxsize nehmen.

Sehr gut. Dafür brauche ich dann nur knappe 15 Sekunden.