Eine Woche Programmierwettbewerb: Rechtecke

Ponto

Hallo,

ich habe 4 Einsendungen erhalten:

otze
Jens
TomasRiker
camper

Ich werde mich morgen an die Auswertung setzen.

Badestrand

Ach verflucht, ich hab irgendeinen doofen Fehler nicht rausgekriegt

rapso

Badestrand schrieb:

Ach verflucht, ich hab irgendeinen doofen Fehler nicht rausgekriegt

und mir klang das ein wenig spanish von den anforderungen her, als ob jemand gratis die optimierungsarbeit von anderen sehen moechte *hehe*

Ponto

rapso schrieb:

Badestrand schrieb:

Ach verflucht, ich hab irgendeinen doofen Fehler nicht rausgekriegt

und mir klang das ein wenig spanish von den anforderungen her, als ob jemand gratis die optimierungsarbeit von anderen sehen moechte *hehe*

Wenn du nicht völlig realitätsfremde Probleme sehen möchtest, hast du diese Gefahr immer. Dass du mir nicht vertraust, dass es hier nur um den Wettbewerb geht, kann ich verstehen. Warum sollte man das auch tun.

Ponto

Ich suche übrigends Ideen für einen folgenden Programmierwettbewerb. Wenn jemand eine interessante Problemstellung hat, kann er sich an die obige Adresse melden.

jenz

@rapso:

ich hatte ja mal wegen der threads nachgefragt.
warum meinst du, dass das "random" ist?
ich finde, dass sich das problem recht gut parallelisieren ließe.
einfach die plane aufteilen und wenn ein thread dann schneller fertig ist, als andere, dann bekommt er einen teil von dessen plane.

würde in mein verfahren recht gut reinpassen.

ich verstehe nicht, was daran dann nicht von vorteil sein sollte, natürlich nur bei mehreren kernen/prozessoren, aber das kann man im rahmen der optimierung ja anpassen.

@ponto:
optimieren auf mehrere threads/prozessoren vielleicht?

jenz

Ponto

jenz schrieb:

@ponto:
optimieren auf mehrere threads/prozessoren vielleicht?

jenz

Dazu bräuchte man aber auch eine andere Aufgabe.

rapso

Ponto schrieb:

rapso schrieb:

Badestrand schrieb:

Ach verflucht, ich hab irgendeinen doofen Fehler nicht rausgekriegt

und mir klang das ein wenig spanish von den anforderungen her, als ob jemand gratis die optimierungsarbeit von anderen sehen moechte *hehe*

Wenn du nicht völlig realitätsfremde Probleme sehen möchtest, hast du diese Gefahr immer. Dass du mir nicht vertraust, dass es hier nur um den Wettbewerb geht, kann ich verstehen. Warum sollte man das auch tun.

tja, am ende hast du selbst zugegeben dass du das nutzen moechtest (nutzen!=copy&paste), andere zahlen mir mein gehalt damit ich sowas fluessig auf dem schirm zaubere, da kann ich das ja nicht gratis hier machen (zumal das mein arbeitsvertrag auch verbietet, wie vielleicht von einigen anderen auch).

rapso

jenz schrieb:

@rapso:

ich hatte ja mal wegen der threads nachgefragt.
warum meinst du, dass das "random" ist?
ich finde, dass sich das problem recht gut parallelisieren ließe.
einfach die plane aufteilen und wenn ein thread dann schneller fertig ist, als andere, dann bekommt er einen teil von dessen plane.

würde in mein verfahren recht gut reinpassen.

ich verstehe nicht, was daran dann nicht von vorteil sein sollte, natürlich nur bei mehreren kernen/prozessoren, aber das kann man im rahmen der optimierung ja anpassen.

multithreading haengt oft stark von der architektur ab auf der es laeuft, manchmal kannst du cachetrasching produzieren die deine 4threads langsammer als einen machen, manchmal kann genau der selbe code fast 4mal schneller laufen, wenn man da nicht sehr genau weiss was man macht und auf welcher maschine koennen die resultate random sein.
natuerlich hat man im schnitt wenn alle hier teilnehmen ne bessere geschwindigkeit, aber es kann gut sein dass auf einer anderen maschine der letzte der erste wird.

Ponto

tja, am ende hast du selbst zugegeben dass du das nutzen moechtest (nutzen!=copy&paste), andere zahlen mir mein gehalt damit ich sowas fluessig auf dem schirm zaubere, da kann ich das ja nicht gratis hier machen (zumal das mein arbeitsvertrag auch verbietet, wie vielleicht von einigen anderen auch).

Wie gesagt habe ich Verständnis dafür, dass du deine Ideen für dich behalten möchtest oder gar musst. Andererseits wäre es dumm, nicht mit den anderen Ideen den eigenen Horizont zu erweitern. Das gilt für diesen und für alle folgenden Wettbewerbe. Es tut mir auch leid, dass du Zeit in diese Sache gesteckt hast, ohne etwas einsenden zu dürfen.

Ich denke jedoch, dass es nichts zuzugeben gab. Ich habe auf jede Frage zu der Aufgabe bereitwillig geantwortet. Wofür man eine Lösung der Aufgabe nutzen kann, ist auch nicht schwer zu erraten. Dann muss man sich von Anfang an fragen, ob man eine Lösung beisteuern kann oder nicht. Hättest du die Aufgabe anders bewertet, wenn ich gesagt hätte, dass mir kein praktischer Nutzen einfällt? Oder wenn keiner nach dem Ursprung gefragt hätte? Ich denke also, dass sich durch meine späteren Aussagen grundsätzlich nichts geändert hat.

jenz

okay, wenn die caches gemeinsam genutzt werden, dann kann ich mich darauf einlassen, dass es schief gehen kann. auch wenn die threads ja so ziemlich auf den gleichen daten arbeiten.
lesend auf den rechtecken, schreibend auf der plane. lesen muss man nicht kontrollieren, das schreiben in die plane bei meinem verfahren auch nicht.

jeder thread hätte dann noch eine eigene "verwaltugsstruktur", die könnte natürlich den cache durcheianderbringen...

bei getrennten caches sollte die geschwinigkeitssteigerung aber ziemlich deutlich sein. eben fast verdoppelt, wenn man 2 nimmt.

jenz

rapso

Ponto schrieb:

tja, am ende hast du selbst zugegeben dass du das nutzen moechtest (nutzen!=copy&paste), andere zahlen mir mein gehalt damit ich sowas fluessig auf dem schirm zaubere, da kann ich das ja nicht gratis hier machen (zumal das mein arbeitsvertrag auch verbietet, wie vielleicht von einigen anderen auch).

Wie gesagt habe ich Verständnis dafür, dass du deine Ideen für dich behalten möchtest oder gar musst. Andererseits wäre es dumm, nicht mit den anderen Ideen den eigenen Horizont zu erweitern. Das gilt für diesen und für alle folgenden Wettbewerbe. Es tut mir auch leid, dass du Zeit in diese Sache gesteckt hast, ohne etwas einsenden zu dürfen.

keine sorge, ich kann das ja nach dem release der resultate usw. mit meiner version vergleichen. Bisher hab ich nicht viel zeit reingesteckt, leidglich das framework gesetzt und jesters version umgestellt mit trivialoptimierungen. (da sind nichtmal deine generatoren integriert).
wobei es mich auch mehr reizt dann das ganze fluessig darzustellen (was du ja als eigentliche anwendung genannt hast) als punkte in nem vector<vector<>> zu setzen *hehe*.

Ich denke jedoch, dass es nichts zuzugeben gab. Ich habe auf jede Frage zu der Aufgabe bereitwillig geantwortet. Wofür man eine Lösung der Aufgabe nutzen kann, ist auch nicht schwer zu erraten. Dann muss man sich von Anfang an fragen, ob man eine Lösung beisteuern kann oder nicht. Hättest du die Aufgabe anders bewertet, wenn ich gesagt hätte, dass mir kein praktischer Nutzen einfällt?

wenn ich gesehen haette dass es keinen nutzen gibt, haette ich eventuell code eingesand, aber da ich die benches auch alleine fuer mich machen kann wenn die sources und resultate freigegeben sind...

Oder wenn keiner nach dem Ursprung gefragt hätte? Ich denke also, dass sich durch meine späteren Aussagen grundsätzlich nichts geändert hat.

es wirkte von anfang an sehr auf einen speziellen context bezogen, deine aufgabenstellung implizirte das (vielleicht deine wortwahl )

Ich finde es ja gut dass du nen contest hier machst, raetsel loesen macht ja auch spass selbst wenn man sich nicht oeffentlich mit anderen misst oder es grossartige preise gibt.

Ponto

jenz schrieb:

okay, wenn die caches gemeinsam genutzt werden, dann kann ich mich darauf einlassen, dass es schief gehen kann. auch wenn die threads ja so ziemlich auf den gleichen daten arbeiten.
lesend auf den rechtecken, schreibend auf der plane. lesen muss man nicht kontrollieren, das schreiben in die plane bei meinem verfahren auch nicht.

jeder thread hätte dann noch eine eigene "verwaltugsstruktur", die könnte natürlich den cache durcheianderbringen...

bei getrennten caches sollte die geschwinigkeitssteigerung aber ziemlich deutlich sein. eben fast verdoppelt, wenn man 2 nimmt.

Nehmen wir mal an, dass du folgendermaßen parallelisierst:

Jeder Thread bekommt einen Teil der plane. Dann geht er durch die Rechteckliste und aktualisiert seinen Planeanteil, wenn das Rechteck darin liegt.

Wir können leicht dafür sorgen, dass die Planeteile, in die die Threads schreiben sich Cachemässig nicht in die Quere kommen. Dennoch wird man keinen Faktor 2 bei 2 Threads erhalten, denn wir machen jetzt manche Arbeit doppelt.

Nehmen wir an die Gesamtarbeit ist GA und der Anteil für das Schreiben in die Plane ist x*GA. Dann haben wir noch (1-x)*GA an Arbeit, die für das Durchlaufen der Rechteckliste und für die Bestimmung, ob die Rechecke in die Plane passen, draufgehen. Den ersten Teil kann man parallelisieren, den zweiten macht man jedoch doppelt.

Damit steigt die Arbeit im Falle zweier Threads auf x*GA + 2*(1-x)*GA und mit perfekter parallelisierung macht dann jeder Thread: 0.5*x* GA + (1-x)*GA

Der Speedupfaktor gegenüber der seriellen Lösung ist dann GA/(0.5*x* GA + (1-x)*GA) = 1 /(0.5*x + (1-x)) = 1/(1 - 0.5x).

Je näher also das x an 1 ist, desto näher ist der Speedup bei 2. Aber wenn x klein ist, können wir nur ganz geringe Speedups erwarten.

rapso

jenz schrieb:

okay, wenn die caches gemeinsam genutzt werden, dann kann ich mich darauf einlassen, dass es schief gehen kann. auch wenn die threads ja so ziemlich auf den gleichen daten arbeiten.

du kannst pech haben und jeder thread hat seine daten so, dass sie sich im cache ueberlagern, sodass sich die threads gegenseitig die daten "wegschmeissen" aus dem cache.

lesend auf den rechtecken, schreibend auf der plane. lesen muss man nicht kontrollieren, das schreiben in die plane bei meinem verfahren auch nicht.

das ist dem cache relativ egal beim mappen von cache-adress-space auf den echten addressspace.

jeder thread hätte dann noch eine eigene "verwaltugsstruktur", die könnte natürlich den cache durcheianderbringen...

koennte, koennte auch ein gewinn sein, je nach architektur.

bei getrennten caches sollte die geschwinigkeitssteigerung aber ziemlich deutlich sein. eben fast verdoppelt, wenn man 2 nimmt.

koennte aber auch doppelte belastung des rams sein, was wenn das ram das limitierende in dem fall ist? dann zerschiessen sich die threads die sequential reads?

was ist bei nem intel quadcore, 2cores teilen sich jeweils den cache, greifen die cores in der falschen combination auf die daten zu, muessen die daten aus dem einen cache ueber den FSB ins ram geschrieben werden und dann in den anderen cache....

klar, am ende hat man irgend ne beschleunigung, einer hat eventuell ne arschkarte und die ergebnisse sehen auf jeder maschine aus wie anders ausgewuerfelt

mag sein dass ich hier zu sehr schwarzmale, aber ich hab schon erlebt, dass je besser eine optimierung fuer threads ist, desto anfaelliger ist sie auf anderen architekturen.

jenz

nun gut, ich nehme das mal so hin...

@ponto:
eins aber noch
vielleicht kannst du ja in deinen vergleich die fläche der plane einfach mal ein paar mal verdoppeln, dann kann man den speedup vielleicht ein bisschen abschätzen.

ich habe das gerade auch ein bisschen gemacht und das ergebnis sieht wirklich nicht so erfolgversprechend aus...schade

jenz

rapso

jenz schrieb:

nun gut, ich nehme das mal so hin...

http://www.xbitlabs.com/articles/cpu/display/3dmax5-p4-ht.html

da sieht man ein wenig wie random die resultate sein koennen, einige benches bei denen singlethreaded 10% schneller ist, auf der zweiten seite ist dann der p4 mit HTT 5mal schneller...

jenz

schon interessant, aber da haben wir ja nicht wirklich getrennte rechner, sondern eben hyperthreading...

aber ich erkenne den punkt, dass es auch da schwankt.

gut, dann machen wir mal weiter unsere eigenen erfahrungen

@ponto:
wie sieht es denn mit den ergebnissen aus?

Badestrand

Und wäre auch interessant, wenn der Gewinner seine Herangehensweise schildern könnte; könnte man ja noch was von lernen
Muss ja nicht der Code sein, aber evtl das Prinzip, wie es gelöst wurde. Falls der Gewinner damit einverstanden ist, natürlich.

Ponto

Hier kommt meine Auswertung:

Es gab vier Einsendungen: otze, Jens, camper und TomasRiker

Jens hatte zwei Algorithmen abgegeben, die ich beide getestet habe, weil noch genug Kapazität da war.
Da aber jeder nur einen Algorithmus in den Contest schicken kann, gilt nur der, der hier als Jens-1 bezeichnet ist. Der andere läuft außer Konkurrenz.

Ebenso wird mein Algorithmus nicht berücksichtigt, der hier als Ponto bezeichnet wird. Zusätzlich taucht in den Tabellen noch der Algorithmus "TomasRiker Mod" auf. Diesen habe ich aufgenommen, weil TomasRiker in seiner Originallösung die Generatoren stark berücksichtigt.

Insgesamt tauchen hier also 7 Algorithmen auf.

Ich habe die Generatoren mit verschiedenen Parametern gefüttert und die Laufzeiten der Algorithmen aufsummiert. Damit denke ich den Algorithmus zu erhalten, der über einen breiten Anwendungsbereich am besten arbeitet.

Die Tests liefen auf einer Maschine mit 8 Prozessoren von AMD: "AMD Opteron(tm) Processor 852". Die Taktrate ist 2.6GHz. Die Testmaschine hat 64GB Hauptspeicher, welcher von keinem Programm ausgenutzt wurde.
Für jeden Test habe ich den Programmen 120 Sekunden CPU-Zeit gegeben. Testläufe, die länger benötigten wurden mit 130 Sekunden bewertet. Für die anderne Läufe gelten die tatsächlichen Sekunden.

Hier die Laufzeiten in Sekunden:

User:     camper  Jens-1  Jens-2   otze  TomasRiker  TomasRiker  Ponto
                                                        Mod
Dot:          86     783    2194   2507          38          42     61
Wiring:     1104    2392    1965   2686         114         924    757
Placement   1708    3566    5711   6906         255         516    986
Random:     2248    5107     884   5331          28        1472    771
           -----   -----   -----  -----       -----       -----  -----
Gesamt:     5146   11848   10754  17430         435        2954   2574

Damit ergibt sich die folgende Reihenfolge:

4. otze
3. Jens
2. camper
1. TomasRiker

Man sieht, dass TomasRiker auch ohne seine Optimierung auf die Generatoren hin gewonnen hätte.

Herzlichen Glückwunsch an den Gewinner.

Alle Testläufe sind in der folgenden Tabelle eingetragen: http://www.pontohonk.de/wpc/Contest.ods

Die Rohdaten sind in http://www.pontohonk.de/wpc/Contest.txt zu finden. Die Laufzeitspalten sind sortiert nach camper, Jens-1, Jens-2, otze, TomasRiker Mod, Ponto, TomasRiker, Ponto (mit TomasRiker optimierungen)

Ponto

Hier ist mein eigener Code:

Grob gesagt, wird hier ein Quadtree aufgebaut, der an jedem Knoten abspeichert, ob dieser und die gesamte
Fläche darunter schon belegt sind.

Der erste Knoten (layer0[0]) repräsentiert die gesamte Ebene. In jedem weiteren Layer werden die darüberliegenden Flächen in vier gleich große Quadrate aufgeteilt.

Der Algorithmus läuft dann rekursiv. Es wird das Rechteck in das kleinste Quadrat gelegt, in das das Rechteck passt. Dann wird Anhand der Viertelung aufgeschnitten und die nächste Ebene aufgerufen. Ist eine Ebene schon belegt, kann abgebrochen werden.

#include <cmath>
#include <vector>

#include "rectangle.hpp"

char layerC[4096*4096/8];
char layerB[2048*2048/8];
char layerA[1024*1024/8];
char layer9[512*512/8];
char layer8[256*256/8];
char layer7[128*128/8];
char layer6[64*64/8];
char layer5[32*32/8];
char layer4[16*16/8];
char layer3[8*8/8];
char layer2[4*4/8];
char layer1[1];
char layer0[1];

char * layer[] = { layer0, layer1, layer2, layer3, layer4, layer5, layer6,
                   layer7, layer8, layer9, layerA, layerB, layerC };

inline bool get(int l, int x, int y) {
   unsigned int pos = (x * (1 << l) + y);
   unsigned int byte = pos / 8;
   unsigned int bit = pos % 8;
   return (layer[l][byte]) & (1 << bit);
}

inline void set(int l, int x, int y) {
   unsigned int pos = (x * (1 << l) + y);
   unsigned int byte = pos / 8;
   unsigned int bit = pos % 8;
   layer[l][byte] |= (1 << bit);
}

static int pixel = 0;

static std::vector<std::vector<std::size_t> > * res;

inline unsigned int floor_log2_p1(unsigned int v)
{
   if (v <= 2) return v;

   unsigned int b = 17U;
   if (v <   1U<<16U)       b  = 1U;
   if (v >= (1U<< 7U) << b) b += 8U;
   if (v >= (1U<< 3U) << b) b += 4U;
   if (v >= (1U<< 1U) << b) b += 2U;
   return(b + (v >= (1U<<0U) << b));
}

inline void draw(int l, int x, int y, int minx, int maxx, int miny, int maxy, std::size_t idx) {
   if (minx >= maxx or miny >= maxy) return;
   if (get(l, x, y)) return;

   int size = (4096U >> l);

   if (size == 1) {
      ++pixel;
      set(l, x, y);
      (*res)[x][y] = idx;
      return;
   }

   int half = size/2;

   int startx = x * size;
   int midx = startx + half;
   int starty = y * size;
   int midy = starty + half;

   draw(l+1, 2*x,   2*y,   minx, std::min(maxx, midx), miny, std::min(maxy, midy), idx);
   draw(l+1, 2*x+1, 2*y,   std::max(minx, midx), maxx, miny, std::min(maxy, midy), idx);
   draw(l+1, 2*x,   2*y+1, minx, std::min(maxx, midx), std::max(miny, midy), maxy, idx);
   draw(l+1, 2*x+1, 2*y+1, std::max(minx, midx), maxx, std::max(miny, midy), maxy, idx);

   if (get(l+1, 2*x, 2*y) and get(l+1, 2*x+1, 2*y) and get(l+1, 2*x, 2*y+1) and get(l+1, 2*x+1, 2*y+1)) {
      set(l, x, y);
      return;
   }
}

void algorithm(Rectangle plane,
               std::vector<Rectangle> const & rectangles,
               std::vector<std::vector<std::size_t> > & result)
{
   res = &result;

   Coordinate width  = plane.maxx - plane.minx;
   Coordinate height = plane.maxy - plane.miny;

   for (std::size_t i = rectangles.size(); i > 0; --i) {

      Rectangle rect = {rectangles[i-1].minx - plane.minx,
                        rectangles[i-1].maxx - plane.minx,
                        rectangles[i-1].miny - plane.miny,
                        rectangles[i-1].maxy - plane.miny };

      rect.minx = std::max(Coordinate(0), rect.minx);
      rect.miny = std::max(Coordinate(0), rect.miny);

      rect.maxx = std::min(width, rect.maxx);
      rect.maxy = std::min(height, rect.maxy);

      if (rect.minx >= rect.maxx or rect.miny >= rect.maxy) continue;

      int layer = floor_log2_p1(std::max(((rect.maxy-1) ^ rect.miny), ((rect.maxx-1) ^ rect.minx)));

      draw(12 - layer, (rect.minx >> layer) , (rect.miny >> layer),
           rect.minx, rect.maxx, rect.miny, rect.maxy, i-1);
      if (pixel == width * height) break;
   }
}