3. Eine Woche Programmierwettbewerb: Rechtecke

Eine Woche Programmierwettbewerb: Rechtecke

  • J

    über threads haben wir noch gar nicht gesprochen....

    sollen wir einfach mal von einer maschine mit mehreren kernen ausgehen?

    oder als parameter?

    jenz

    0
  • P

    jenz schrieb:

    über threads haben wir noch gar nicht gesprochen....

    sollen wir einfach mal von einer maschine mit mehreren kernen ausgehen?

    oder als parameter?

    jenz

    Nein, für den Wettbewerb hast du nur einen Prozessor.

    Wenn du möchtest, kannst du jedoch deinen Code außer Konkurrenz multithreaded machen, und ich lass es mal auf bis zu 8 Prozessoren laufen. Dann muss es aber auf PThreads oder Qt Threads basieren.

    0
  • R

    lieber nicht, wenn du nicht gerade die selbe maschine hast, ist das verhalten sehr zufaellig. was bei einer mit mehreren threads super laufen kann wird dir bei einer anderen maschine das genick brechen... und wie gesagt, das ist random.

    0
  • O

    ok, da das mit dem vergleichen irgendwie net klappt(rapsos gepostete datei lässt leider meinen algo beim kopieren ins result array abstürzen), update ich einfach mal meinen letzten wert:

    Seed:6432567
    Ebene: 4096x4096
    Anzahl: 15000000

    alter Wert(seite 4): 2min 45sec
    neuer Wert: 14sec

    anbei post ich nochmal die datei, mit der ich teste:

    #include <iostream>
#include <ctime>

#include <vector>

struct Rectangle
{
   short minx;
   short maxx;
   short miny;
   short maxy;
};

const int       rectCount= 15000000;
const int       seed     = 6432567;
const Rectangle plane    ={0,100,0,100};

class CTwister
{
    static int m_Seed;
public:
    static void Init(int Seed){m_Seed=Seed;}

    static int Rand()
    {
        m_Seed ^= (m_Seed>>11);
        m_Seed ^= (m_Seed<<    7)&0x9d2c5680UL;
        m_Seed ^= (m_Seed<<15)&0xefc60000UL;
        return (m_Seed^(m_Seed>>18)); //frac to 12bit?
    }
};

int CTwister::m_Seed;

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

//vergleich Algo
void algorithmTest(Rectangle plane, std::vector<Rectangle> const & rectangles, std::vector<std::vector<std::size_t> > & result)
{
    for(int i=0;i!=rectangles.size();++i)
    {
        for(int x=rectangles[i].minx;x<rectangles[i].maxx;++x)
        {
            for(int y=rectangles[i].miny; y<rectangles[i].maxy; ++y)
            {
                if((x>=plane.minx) &&(x<plane.maxx) &&(y>=plane.miny) && (y<plane.maxy))
                {
                    result[x-plane.minx][y-plane.miny]=i;
                }
            }
        }
    }
}

void algorithm(Rectangle plane, std::vector<Rectangle> const & rectangles, std::vector<std::vector<std::size_t> > & result)
{
    //schreibt da euren Algo rein
}
int main()
{
    CTwister::Init(seed);
    std::vector<Rectangle> rects;
    generate_rectangles(plane,rects);

    std::vector<std::vector<std::size_t> > result(plane.maxx-plane.minx,std::vector<std::size_t>(plane.maxy-plane.miny));
    std::vector<std::vector<std::size_t> > result2(plane.maxx-plane.minx,std::vector<std::size_t>(plane.maxy-plane.miny));

    std::cout<<"start ";

    std::clock_t start=std::clock();
    algorithm(plane,rects, result2);
    std::clock_t end=std::clock();

    std::cout<<(end-start)/(CLOCKS_PER_SEC/1000)<<"\n";

    std::cout<<"starting Default algo ";

    start=std::clock();
    algorithmTest(plane,rects, result);
    end=std::clock();

    std::cout<<(end-start)/(CLOCKS_PER_SEC/1000)<<"\n";

    int fehler=0;
    for(std::size_t i=0;i<result.size();++i)
    {
        for(std::size_t j=0;j<result[i].size();++j)
        {
            fehler+=result[i][j]!=result2[i][j];
        }
    }
    std::cout<<"fehler:"<<fehler<<"\n";
	return 0;
}

    dann nochmal ein anderer Wert, bei dem man nicht 3 jahre auf Jesters Algo warten muss:

    Seed:6432567
    Ebene: 100x100
    Anzahl: 1500000

    mein Algo: 1406
    Jester: 72500 😃

    //edit bissl schnellerer default algo drin
    //edit1 fehler entfernt
    //edit2 so, ausgabe nun auch in ms

    0
  • ?

    Darf man aus der "algorithm"-Funktion heraus auch noch andere selbstgeschriebene Funktionen aufrufen? Falls man evtl Rekursivität braucht? Und darf man (kleine) selbstgeschriebene Klassen einbringen?

    0
  • P

    BlaBlubb schrieb:

    Darf man aus der "algorithm"-Funktion heraus auch noch andere selbstgeschriebene Funktionen aufrufen? Falls man evtl Rekursivität braucht? Und darf man (kleine) selbstgeschriebene Klassen einbringen?

    Klar. Du gibst mir einfach eine .C++ Datei ab, und da können eigene Funktionen oder Klassen drin stecken. Die Endung des Dateinamens ist nich verbindlich.

    0
  • J

    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?

    0
  • O

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

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

    0
  • J

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

    0
  • J

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

    0
  • O

    ist drin.

    0
  • J

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

    0
  • P

    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?

    0
  • R

    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?

    0
  • O

    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 😉

    0
  • P

    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.

    0
  • C

    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 🙂

    0
  • P

    rapso schrieb:

    welche cpu(s) hat der testrechner?

    8 AMD Opeterons 2.6GHz

    0
  • O

    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? 😉

    0
  • P

    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.

    0
Anmelden zum Antworten