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? 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.
-
Sehr interessant, und wirst du die beste Lösung dann in dein Programm einbauen (falls sie besser ist als deine)?
Hier übrigens mal ein Ruby-Script, das ganz viele zufällige Tests ausführt.
def exec(str) puts puts '****************************************' puts 'EXECUTING:' puts '----------------------------------------' puts str puts '****************************************' puts system str end while true do seed = 1 + rand(1000) plane_w = 1 + rand(256) plane_h = 1 + rand(256) mode = rand(4) if mode == 0 then max_size = 1 + rand(1024) num_rects = 1 + rand(100000) exec "contest p #{seed} #{plane_w}x#{plane_h} #{max_size} #{num_rects}" elsif mode == 1 then num_layers = 1 + rand(10) exec "contest d #{seed} #{plane_w}x#{plane_h} #{num_layers}" elsif mode == 2 then num_wires = 1 + rand(100000) exec "contest w #{seed} #{plane_w}x#{plane_h} #{num_wires}" elsif mode == 3 then max_size = 1 + rand(1024) num_rects = 1 + rand(100000) exec "contest r #{seed} #{plane_w}x#{plane_h} #{max_size} #{num_rects}" end end
-
TomasRiker schrieb:
Sehr interessant, und wirst du die beste Lösung dann in dein Programm einbauen (falls sie besser ist als deine)?
Die nehme ich höchstens als Inspiration den Viewer mal zu überarbeiten. Es fehlen ja noch viele andere Primitive wie Linien, Polygone, Text uns so weiter.
Und einfach so fremden Code einbauen lassen mich die Anwälte eh nicht.
-
Zur Erinnerung. Heute um 18 Uhr ist Einsendeschluss.
Sobald ich zurück bin, werde ich mich an die Auswertung machen.