Eine Woche Programmierwettbewerb: Rechtecke

jenz

ein neuer generator, der geht auch über die begrenzung.

void generate_rectangles(Rectangle plane,std::vector<Rectangle> &rectangles) {
  unsigned int width(plane.maxx-plane.minx);
  unsigned int height(plane.maxy-plane.miny);
  unsigned int number(rand() & 10000);
  rectangles.resize(number+1);
  rectangles[0] = plane;
  for (int i(0);i<number;++i) {
    Rectangle &r(rectangles[i+1]);
    r.minx = rand()%(2*width)-(width/2);
    r.maxx = r.minx+rand()%(2*width)+1;
    r.miny = rand()%(2*height)-(height/2);
    r.maxy = r.miny+rand()%(2*height)+1;
  }
}

jenz

edit: nach jesters nettem hinweis, habe ich die plane noch als erstes Recteck hinzugefügt.
und jetzt ist max immer größer als min

Jester

Die erste Ebene ist mit der Grundebene identisch -- vielleicht doch mal die Aufgabenstellung lesen?

otze

desweiteren erzeugt der algo rechtecke die komplett ausserhalb der ebene liegen. und er erzeugt rechtecke, wo min=max ist.

ich war grad mal auf fehlersuche in meinem algo, und hab deswegen zwecks debugging die rechteckzahl auf 10 limitiert, heraus kamen als rechtecke:

Grundebene [15,25)x[15,25)

erzeugte Ebenen:
[0,19)x[1,6)
[-1,14)x[11,11)

und da wunder ich mich noch, dass der output aus lauter Nullen besteht

ps: muss man auch mit negativen zahlenwerten fertig werden?

pps: jenz, nichts gegen dich ;), auf solche werte wär ich alleine aber wohl net gekommen, und nun kann ich das mal testen

jenz

@otze, kein problem.

ich werde den jetzt gleich mal ausführlich testen.

rechtecke ausserhalb der ebene sollten berücksichtigt (bzw. verworfen) werden.

jenz

edit: ich habe den generator noch mal geändert.
soweit ich jetzt probiert habe scheint es zu passen.

Ponto

otze schrieb:

ps: muss man auch mit negativen zahlenwerten fertig werden?

Die Koordinaten sind int und können als 32-bit 2-Komplement angenommen werden. Also können die auch negativ werden.

otze

ahh ok, danke

noch eine Frage:

Der Parameter rectangles bezeichnet die Menge der eingegebenen Rechtecke. Diese müssen nicht vollständig in der Ebene plane liegen.

bedeuted dass, dass jedes rechteck midnestens einen Punkt mit der Grundebene gemeinsam haben muss? so les ich das nämlich da heraus. Oder ist zb das verhalten von jenz generator richtig?

Ponto

otze schrieb:

ahh ok, danke

noch eine Frage:

Der Parameter rectangles bezeichnet die Menge der eingegebenen Rechtecke. Diese müssen nicht vollständig in der Ebene plane liegen.

bedeuted dass, dass jedes rechteck midnestens einen Punkt mit der Grundebene gemeinsam haben muss? so les ich das nämlich da heraus. Oder ist zb das verhalten von jenz generator richtig?

Die können ganz außerhalb liegen.

otze

dann entfern besser das Wort "vollständig". das verwirrt leute wie mich

ok, keine Fragen mehr

//edit erstes Ergebnis: eine 4096x4096 große ebene mit 15 millionen rechtecken in 2min, 45sec durchgerechnet :). Viel mehr geht im moment nicht, weil ich zwischendurch bedrohlich nah an die 2GB speichergrenze komme ;). Aber das undn bissl mehr speed krieg ich noch hin, bzw wenn ich mehr zeit hätte

habt ihr schon Ergebnisse?

ca. 40 Sekunden bei 4096² und 50M Rechtecken, 915MB Speicherverbrauch
A64 3200+ Venice, Vista x64 (2GB Grenze, wasn des? :D)
muss aber noch Korrektheitstests durchführen

Der Wettbewerb ist IMO etwas ungünstig angesetzt, ich fahre morgen über verlängertes WE Eltern besuchen und möchte die Zeit eigentlich nicht vor dem Rechner verbringen. Ansonsten coole Optimierungsaufgabe, Respekt.

Jester

Ich komme wohl nicht vor Freitag zum Implementieren :(. Könnt ihr die Generatoren die ihr verwendet mal posten?

Ponto

Verwirrt die Teilnehmer nicht durch irgendwelche erfundenen Zwischenergebnisse!

Es soll ja keiner abgeschreckt werden.

otze

Jester schrieb:

Ich komme wohl nicht vor Freitag zum Implementieren :(. Könnt ihr die Generatoren die ihr verwendet mal posten?

ich hab den von jenz benutzt

@Ponto ich bin eh für niemanden ne Konkurrzenz, weil das Programm das bei mir fehlerfrei läuft, bei dir wahrscheinlich nichtmal compilieren wird

camper

Eigentlich die ideale Aufgabe, um Grafikprozessoren zu beschäftigen. Fütter den Prozessor mit den Rechtecken, der Index dient für die Tiefe und Farbe und lass es ihn einfach malen. Anschließend untersucht man einfach die Farbe für jedes Pixel. ist aber wohl nicht portabel hinzukriegen

otze

camper schrieb:

Eigentlich die ideale Aufgabe, um Grafikprozessoren zu beschäftigen. Fütter den Prozessor mit den Rechtecken, der Index dient für die Tiefe und Farbe und lass es ihn einfach malen. Anschließend untersucht man einfach die Farbe für jedes Pixel. ist aber wohl nicht portabel hinzukriegen

ginge schon. opengl is ja ziemlich portabel

Ponto

Wenn Ihr das mit der OpenGL Unterstützung von Qt so hinkriegt, dass es hier kompiliert, soll es mir recht sein. Aber wie bekommt ihr die Daten aus der Graphikkarte? Und wenn man den Index als Farbe kodiert, reichen da die Werte?

rapso

opengl ist bei so ziemlich jedem compiler dabei, es duerfte kein problem sein das auf jeder plattform zu nutzen. als farbinformationen solltest du durchaus 4mrd farben (32bit) annehmen duerfen, man muss nur das richtige format setzen. du kannst nen buffer mit 4096*4096 als rendertarget setzen und rauslesen ist auch kein problem.

jenz

ich habe noch mal eine frage,
dürfen wir die obersten beiden bits im result jeweils benutzen...

so viele rechtecke wird es ja wohl nie geben, oder?

jenz

rapso

jenz schrieb:

ich habe noch mal eine frage,
dürfen wir die obersten beiden bits im result jeweils benutzen...

so viele rechtecke wird es ja wohl nie geben, oder?

jenz

dann wuerd ich auch requesten ob wir statt int dann short benutzen koennen im Rectangle und ob wir statt dem vector<vector> nicht lieber nur vector nehmen koennten der halt size*size gross ist(wenn wir schon performance messen wollen, waere es bloed diesen overhead zu haben).

btw. hat jemand Jesters loesung auf das beispiel angewand?

Ponto

jenz schrieb:

ich habe noch mal eine frage,
dürfen wir die obersten beiden bits im result jeweils benutzen...

so viele rechtecke wird es ja wohl nie geben, oder?

jenz

Warum brauchst du dazu result? Warum kein eigenes Array, das die Daten vorhält.

Es werden wahrscheinlich nicht so viele Elemente sein, aber ich denke, dass ich die Aufgabe aus Fairness jetzt nicht mehr ändern kann. Es sei, denn jeder stimmt zu?

Ponto

dann wuerd ich auch requesten ob wir statt int dann short benutzen koennen im Rectangle und ob wir statt dem vector<vector> nicht lieber nur vector nehmen koennten der halt size*size gross ist(wenn wir schon performance messen wollen, waere es bloed diesen overhead zu haben).

btw. hat jemand Jesters loesung auf das beispiel angewand?

Stimmt was mit Jesters Lösung nicht? Oder mit dem Beispiel?

Für die Änderung ist es denke ich auch zu spät. Ich hab zuerst überlegt, nur ein std::vectorstd::size_t zu nutzen, aber dann wäre die Erklärung nicht so einfach gewesen.

Vieviel Zeit würde verloren gehen, die Daten von einem eigenen Vektor nach result zu kopieren?