3. Eine Woche Programmierwettbewerb: Rechtecke

Eine Woche Programmierwettbewerb: Rechtecke

  • J

    Aber selbst dann erzeugst Du eine gewisse Verzerrung des Lösungsspektrums. Wer sich lieber das 25. Rechteck vor dem 3. anschaun will, der muß Daten zwischenspeichern, was Zeit kostet. Im anderen Fall kann ich aber problemlos an Stelle 25 einsteigen.

    0
  • J

    rapso: mein algorithmus ist in deinem code falsch. Die Konvention lautet [x][y].

    0
  • O

    Jester schrieb:

    Aber selbst dann erzeugst Du eine gewisse Verzerrung des Lösungsspektrums. Wer sich lieber das 25. Rechteck vor dem 3. anschaun will, der muß Daten zwischenspeichern, was Zeit kostet. Im anderen Fall kann ich aber problemlos an Stelle 25 einsteigen.

    richtig, aber ich denk, das ist zu verschmerzen. ich denk mal, das wird den algo der kopieren muss, maximal eine halbe sekunde zurückwerfen und ich denk, dass dies zu verschmerzen ist.
    Bislang müssen halt alle anderen algos diese halbe sekunde aufbringen UND verlieren noch 400mb speicher, wodurch sie im zweifelsfall das BS dazu zwingen, daten auf die festplatte zu schreiben, und damit werden sie gleich 3fach bestraft 😉

    0
  • P

    Also, die einzige Änderung mit der ich leben kann, ist die freie Auswahl zwischen short und int bei den Rechtecken. Für den Rest ist es zu spät.

    Ich werde die Programme übrigends auf einer Maschine mit 128GB RAM testen und die größten Instanzen bei 16GB ansetzen, so dass die Programme bis zum 8fachen Overhead haben können. Reicht das?

    Bei short Koordinaten wären dass dann Instanzen mit ungefähr 2 Milliarden Rechtecke, wenn ich mich nicht verrechnet habe. Bei int sind es dann ungefähr 1 Milliarde Rechtecke.

    0
  • O

    ok, damit kann man leben :). Das kopieren fällt ja nicht so sehr ins Gewicht, vorallem wenn man eh die daten anpassen muss, aber die ram limitierung war schon sehr ärgerlich 🙂

    woher haste denn sone Kiste her? Gibts Bilder? hat sie schon nen Freund? 😃

    0
  • P

    otze schrieb:

    ok, damit kann man leben :). Das kopieren fällt ja nicht so sehr ins Gewicht, vorallem wenn man eh die daten anpassen muss, aber die ram limitierung war schon sehr ärgerlich 🙂

    woher haste denn sone Kiste her? Gibts Bilder? hat sie schon nen Freund? 😃

    Manchmal braucht man solche Kisten.

    0
  • R

    hmm.. ich denke wir sollten das interface so lassen wie es ist, ist zwar fuer die meisten suboptimal, aber es ist nunmal die anforderung und ein interface zu finden das allen gefaellt wird schwer.
    einzig das mit den shorts waere ne erwegung wert, da der speicherverbrauch doch imens ist.

    0
  • 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
Anmelden zum Antworten