Eine Woche Programmierwettbewerb: Rechtecke
-
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?
-
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
-
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.
-
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.
-
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
-
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; };
-
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.
-
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.
-
Ich werde übrigends keine anderen Generatoren mehr schreiben. Ihr könnt also auf die bestehenden hin optimieren.
-
Schon fies, dass bei 3 von 4 Generatoren immer mindestens 1 Pixel frei bleibt ...
-
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.
-
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
-
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.
-
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.
-
TomasRiker schrieb:
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.
Hui. Naja. Ich muss eh verschiedene Größen testen.
-
In der Aufgabenstellung heißt es, dass die Rechtecke auch teilweise außerhalb des plane-Rechtecks liegen können. Allerdings liefern die Generatoren nie solche Rechtecke.
Darf man den Test nun weglassen?
-
TomasRiker schrieb:
In der Aufgabenstellung heißt es, dass die Rechtecke auch teilweise außerhalb des plane-Rechtecks liegen können. Allerdings liefern die Generatoren nie solche Rechtecke.
Darf man den Test nun weglassen?Nein. Vor allem, weil ich schon Abgaben mit dem Test habe.
Die Korrektheit wird mit handverlesenen Instanzen getestet, bei denen auch mal ein Rechteck außerhalb liegt.
Geht denn dafür soviel Laufzeit verloren?
Im echten Leben gibt es immer mal Rechtecke außerhalb, vor allem, wenn man in Bilder reinzoomt.
-
Ponto schrieb:
Geht denn dafür soviel Laufzeit verloren?
Im echten Leben gibt es immer mal Rechtecke außerhalb, vor allem, wenn man in Bilder reinzoomt.
Ohne den Test wäre mein Algorithmus teilweise ca. 10% schneller, aber egal.
Hat diese Aufgabe etwa eine praktische Anwendung?
-
TomasRiker schrieb:
Ponto schrieb:
Geht denn dafür soviel Laufzeit verloren?
Im echten Leben gibt es immer mal Rechtecke außerhalb, vor allem, wenn man in Bilder reinzoomt.
Ohne den Test wäre mein Algorithmus teilweise ca. 10% schneller, aber egal.
Hat diese Aufgabe etwa eine praktische Anwendung?Ich musste das Problem selbst lösen, als ich einen Viewer für VLSI Daten geschrieben habe. Da hat man ungefähr 10-20 Mio Rechtecke, die man anzeigen möchte. Da man nur ungefähr 1 Mio Pixel im Fenster hat,
gibt es zwangsläufig Überlappungen. Das löst man, indem das letzte Rechteck gewinnt. Zoomt man rein, lösen sich die Überlappungen auf, und man muss sich nur um einen Ausschnitt kümmern.Der Wiringgenerator erzeugt Bilder, die auch ungefähr der Realität entsprechen. In der Realität sind die Drähte aber nur auf bis zu 10 Lagen verteilt. Das macht der Generator nicht.
Der Placementgenerator erzeugt Bilder, die einem nicht legalen Placement entsprechen. (Legal bedeutet, dass sich keine zwei Rechtecke überlappen) Die Verteilung der Rechteckgrößen ist auf echten Chips ähnlich. Es gibt wenige große und sehr viele kleine.