Eine Woche Programmierwettbewerb: Rechtecke

Jester

otze:

Ja, das Problem hatte ich auch, danke für Deinen Code. Damit läuft's bei mir auch. Wir können auch gerne den Code den Du gepostet hast als Referenz nehmen. Die Wartezeiten sind ja schon enorm sonst...

Wie wär's wenn wir den Code noch auf rapsos twister umstellen. Der seed ist zwar schön und gut, aber woher weiß ich, dass unser rand damit das gleiche produziert?

otze

ja, können wir machen. ich editiere gleich den neuen code rein

//edit ist drin. hoffe ich hab keinen Fehler gemacht

Jester

Der algo heißt jetzt algorithmTest, Du rufst aber noch algorithmJester auf.

Jester

Und wenn Du grad dabei bist... Ausgabe in ms wäre nice. So sieht man fast nix.

otze

ist drin.

Jester

Ich forder jetzt einfach so lange Änderungen an, bis Du aus versehen mal Deinen algo mitpostest.

Ponto

Ich werde spätestens morgen meine Rechteckgeneratoren hier posten. Zur Zeit sind das ungefähr:

Dot-Generator: Jedes Rechteck ist ein Punkt
Wiring-Generator: Es wird ein VLSI-Routing mit sehr vielen Layern simuliert.
Placement-Generator: Es wird ein VLSI-Placmenet simuliert. Das heisst, dass es sehr viele kleine
Rechtecke gibt und die Anzahl der Großen logarithmisch oder so abfällt.

Anregungen, Wünsche dazu?

rapso

Time needed 0s
Jestertime 444575ms
speedup 444575.000000
Correct: yes

ich hoffe einfach ich hab irgendwo nen bug, weil ich eigentlich nur stupide optimierungen machte, aber trotzdem lustig

welche cpu(s) hat der testrechner?

otze

Jester schrieb:

Ich forder jetzt einfach so lange Änderungen an, bis Du aus versehen mal Deinen algo mitpostest.

kannste vergessen :D. der algo ist in ner anderen datei :p

@Ponto ist der dot generator ein generator der rechtecke der Form {minx,minx+1,miny,miny+1} erzeugt? oder {minx,minx,miny,miny}?

@rapso welche werte? 0-1 ticks hört sich schon ziemlich wenig an

Ponto

otze schrieb:

@Ponto ist der dot generator ein generator der rechtecke der Form {minx,minx+1,miny,miny+1} erzeugt? oder {minx,minx,miny,miny}?

Ersteres.

camper

rapso schrieb:

Time needed 0s
Jestertime 444575ms
speedup 444575.000000
Correct: yes

ich hoffe einfach ich hab irgendwo nen bug, weil ich eigentlich nur stupide optimierungen machte, aber trotzdem lustig

welche cpu(s) hat der testrechner?

Das sieht nach einer trivialen Optimierung aus, die sich einen grundlegenden Defekt der bisherigen Generatoren zu nutze macht... - ich hab das gleiche Problem

Ponto

rapso schrieb:

welche cpu(s) hat der testrechner?

8 AMD Opeterons 2.6GHz

otze

camper schrieb:

Das sieht nach einer trivialen Optimierung aus, die sich einen grundlegenden Defekt der bisherigen Generatoren zu nutze macht... - ich hab das gleiche Problem

gibt es zum defekt nähere auskunft? ich kenn mich mit der theorie net so aus, vorallem was generatoren etc angeht, und was hat das für auswirkungen? Muss ja nix genaues sein, schon garnet, welche optimierung das ist. Und was ist daran ein Problem?

Ponto

otze schrieb:

camper schrieb:

Das sieht nach einer trivialen Optimierung aus, die sich einen grundlegenden Defekt der bisherigen Generatoren zu nutze macht... - ich hab das gleiche Problem

gibt es zum defekt nähere auskunft? ich kenn mich mit der theorie net so aus, vorallem was generatoren etc angeht, und was hat das für auswirkungen? Muss ja nix genaues sein, schon garnet, welche optimierung das ist. Und was ist daran ein Problem?

Vielleicht meint er, dass man sich recht sicher sein, kann, dass die Lösung der Generatoren hohe Zahlen haben wird.

otze

Ponto schrieb:

Vielleicht meint er, dass man sich recht sicher sein, kann, dass die Lösung der Generatoren hohe Zahlen haben wird.

davon kann man ja unabhängig vom generator ausgehen :). Zumindest, solang die chance, dass ein großes oder kleines rechteck ausgespuckt wird, über die ganze Verteilung hinweg konstant bleibt. das würde sich nur ändern, wenn man zb nach der generierung die elemente nochmal sortiert...die großen am anfang, die kleinen am Ende.

Jester

Oder sie gleich entsprechend generiert.

otze

Jester schrieb:

Oder sie gleich entsprechend generiert.

Das reicht dabei leider nicht.
ich werd dazu nochwas schreiben, nachdem die algorithmen abgegeben wurden, imho würde eine diskussion darüber momentan zuviele hinweise geben.

Jester

otze schrieb:

Jester schrieb:

Oder sie gleich entsprechend generiert.

Das reicht dabei leider nicht.

Huh? Es reicht nicht sie so zu generieren, dass es nicht passiert damit's nicht passiert? Da bin ich aber mal gespannt was Du da schreiben willst.

Ponto

So stelle ich mir ungefähr den Placement-Generator vor:

typedef short Coordinate;

struct Rectangle { 

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

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

Coordinate random(Coordinate begin, Coordinate end) {
   return random() % (end - begin) + begin;
}

void generate_rectangles(std::size_t count, 
                         Rectangle plane,
                         std::vector<Rectangle> & rectangles) 
{ 
   rectangles.clear();
   rectangles.reserve(count + 1);
   rectangles.push_back(plane);

   int freex = random(plane.minx, plane.maxx);
   int freey = random(plane.miny, plane.maxy);

   for (std::size_t i = 0; i < count; ++i) {
      Coordinate max = (6 - static_cast<Coordinate>(log2(random() % 127 + 1)));
      max = (1 << max);
      Coordinate width = random() % max + 1; 
      Coordinate height = random() % max + 1;

      Coordinate minx = random(-256, 4096 + 256 - width) + plane.minx;
      Coordinate miny = random(-256, 4096 + 256 - width) + plane.miny;

      if (minx <= freex and (minx + width) > freex and miny <= freey and (miny + height) > freey) {
         --i;
         continue;
      }

      rectangles.push_back(Rectangle(minx, minx + width, miny, miny + height));
   }
}

otze

ich hab auch mal nen kleinen Punktgenerator gebastelt.

ihr könnt mal testen, was ihr damit so an zeiten zu stande bringt

void generate_points(Rectangle plane,std::vector<Rectangle> &rectangles)
{
    const int width  = plane.maxx-plane.minx;
    const int height = plane.maxy-plane.miny;
    std::vector<Rectangle> maxima;
    int maximaCount=CTwister::Rand()%9+2;//2-10 maxima

    for(int i=0;i<maximaCount;++i)
    {
        Rectangle rect;
        rect.minx=plane.minx-width/2+width*((CTwister::Rand()%200)/100.0);
        rect.miny=plane.miny-height/2+height*((CTwister::Rand()%200)/100.0);
        maxima.push_back(rect);
    }
    rectangles.resize(rectCount+1);
    rectangles[0] = plane;
    for(int i=0;i<rectCount;++i)
    {
        Rectangle maximum=maxima[CTwister::Rand()%maximaCount];
        double ratio=i/double(rectCount);

        Rectangle& rect=rectangles[i+1];
        rect.minx=maximum.minx-width/2+width*((CTwister::Rand()%200)/100.0*ratio);
        rect.maxx=rect.minx+1;
        rect.miny=maximum.miny-height/2+height*((CTwister::Rand()%200)/100.0*ratio);
        rect.maxy=rect.miny+1;
    }
}

hier empfiehlt es sich btw, auch mal mit den rechteckzahlen richtig hoch zu gehen