3. Eine Woche Programmierwettbewerb: Rechtecke

Eine Woche Programmierwettbewerb: Rechtecke

  • O

    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 🙂

    0
  • T

    Bin jetzt auch mit dabei 🙂
    Ergebnis mit otzes Testcode:

    Generating rectangles ...
Executing naive algorithm ...
Executing David's algorithm ...
Correct? 1
Naive: 149298 ms
David: 21 ms

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

    😉

    (Naive ist Jesters Code)

    0
  • O

    welcher generator?

    //edit ok, ich teste grad meinen eigenen generator...und ich merke, dass ich für meinen Algo eine nemesis erschaffen hab...

    //edit2 ok, das war ernüchternd...

    nach 15min hab ich den durchgang abgebrochen, und dann mit anderen zahlen probiert...

    seed = 64027;
    plane ={0,2048,0,2048};
    generator: generate_points

    rectCount= 100000;
    default: 31ms
    mein : 4532ms

    rectCount=200000
    default:47ms
    mein :23453ms

    rectCount=300000
    default:63ms
    mein :65453ms

    und dabei dachte ich noch, dass mein Algo damit gut klar käme...verkehrte Welt

    //edit3 nochn paar mehr Werte...und inzwischen hab ich auch ne idee, woran es liegt.

    0
  • T

    OK, ich wollte euch nur ein wenig schocken 🤡

    0
  • M

    Bin ich der einzige bei dem Jesters Algorithmus und otzes Algorithmus (siehe http://www.c-plusplus.net/forum/viewtopic-var-p-is-1286040.html#1286040) unterschiedliche Ausgaben liefern? Welcher liefert das korrekte Ergebnis?

    Btw. dieser Thread hat mich dazu inspiriert, mich endlich mal mit C++ zu beschäftigen 😉

    0
  • O

    Mehlvogel schrieb:

    Bin ich der einzige bei dem Jesters Algorithmus und otzes Algorithmus (siehe http://www.c-plusplus.net/forum/viewtopic-var-p-is-1286040.html#1286040) unterschiedliche Ausgaben liefern? Welcher liefert das korrekte Ergebnis?

    Btw. dieser Thread hat mich dazu inspiriert, mich endlich mal mit C++ zu beschäftigen 😉

    benutzt du jesters algo aus rapsos testcode? dann ist es klar, weil rapso den algo nochmal angepasst hat(siehe jesters nachricht ein paar seiten vorher)

    //edit grad nochmal getestet: alles korrekt

    0
  • M

    Wer lesen kann ist klar im Vorteil -.-
    Danke.

    0
  • C

    hier mal meine Testcode mit Generator (nicht auf auf Schönheit getrimmt), der die Sache etwas schwieriger machen dürfte:

    #include <iostream>
#include <ctime>

#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>

using namespace std;

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

const int rectCount= 100000000;
const int seed     = 532117;
const Rectangle plane = { -3100, -3100+512, 3452, 3452+512 };

class CTwister
{
    int m_Seed;
public:
    CTwister(int Seed) : m_Seed( Seed ) {}

    int get()
    {
        m_Seed ^= ( m_Seed >> 11 );
        m_Seed ^= ( m_Seed <<  7 ) & 0x9d2c5680ul;
        m_Seed ^= ( m_Seed << 15 ) & 0xefc60000ul;
        return m_Seed ^ ( m_Seed >> 18 );
    }
} twister( time( 0 ) );

struct Overlaps : binary_function< Rectangle, Rectangle, bool >
{
    bool operator()(const Rectangle& lhs, const Rectangle& rhs) const
    {
        return lhs.minx < rhs.maxx
            && lhs.maxx > rhs.minx
            && lhs.miny < rhs.maxy
            && lhs.maxy > rhs.miny;
    }
};

void generate_rectangles(Rectangle plane, vector< Rectangle >& rectangles)
{
    int width = plane.maxx - plane.minx;
    int height = plane.maxy - plane.miny;

    const int max_spread_x = width / 2;
    const int max_spread_y = height / 2;
    const int min_spread_x = static_cast< int >( sqrt( static_cast< double >( max_spread_x ) ) );
    const int min_spread_y = static_cast< int >( sqrt( static_cast< double >( max_spread_y ) ) );

    int counter = 2;

    vector< Rectangle > holes;

    rectangles.reserve( rectCount + 1 );
    rectangles.push_back( plane );

    int min_origin_x = plane.minx - 2 * max_spread_x;
    int var_origin_x = width + 3 * max_spread_x;
    int min_origin_y = plane.miny - 2 * max_spread_y;
    int var_origin_y = height + 3 * max_spread_y;

    for ( int i = 0; i < rectCount; )
    {
        if ( i == counter )
        {
            cout << counter << '\t' << flush;
            counter += counter / 4 + 1;
            int minx = plane.minx + twister.get() % width;
            int miny = plane.miny + twister.get() % height;
            int maxx = minx + twister.get() % min_spread_x;
            int maxy = miny + twister.get() % min_spread_y;
            Rectangle r = { minx, maxx, miny, maxy };
            holes.push_back( r );
        }
        int minx = min_origin_x + twister.get() % var_origin_x;
        int miny = min_origin_y + twister.get() % var_origin_y;
        int maxx = minx + twister.get() % ( max_spread_x - min_spread_x + 1 );
        int maxy = miny + twister.get() % ( max_spread_y - min_spread_y + 1 );
        Rectangle r = { minx, maxx, miny, maxy };
        if ( find_if( holes.begin(), holes.end(), bind1st( Overlaps(), r ) ) == holes.end() )
        {
            rectangles.push_back( r );
            ++i;
        }
    }
    cout << endl;
}

void algorithm_baseline(Rectangle plane, const vector<Rectangle>& rectangles, vector< vector< size_t > >& result);
void algorithm(Rectangle plane, const vector< Rectangle >& rectangles, vector< vector< size_t > >& result);

int main()
{
    vector< vector< size_t > > result( plane.maxx - plane.minx );
    for ( int i = 0; i < plane.maxx - plane.minx; ++i )
    {
        result[ i ].reserve( plane.maxy - plane.miny );
        for ( int j = 0; j < plane.maxy - plane.miny; ++j )
            result[ i ].push_back( twister.get() );
    }
    vector< vector< size_t > > result2( result );

    twister = CTwister( seed );

    vector< Rectangle > rects;
    generate_rectangles( plane, rects );

    cout << "start baseline ";

    clock_t start = clock();
    algorithm_baseline( plane, rects, result2 );
    clock_t end = clock();

    cout << ( end - start ) << " ms\n";

    cout << "starting algo ";

    start = clock();
    algorithm( plane, rects, result );
    end = clock();

    cout << ( end - start ) << " ms\n";

    if ( result == result2 )
        cout << "keine fehler" << endl;
    else
    {
        int fehler=0;
        for( size_t i = 0; i < result.size(); ++i )
        {
            for( size_t j = 0; j < result[ i ].size(); ++j )
            {
                fehler += result[ i ][ j ] != result2[ i ][ j ];
            }
        }
        cout << "fehler: " << fehler << endl;
    }
    return 0;
}
    0
  • T

    Werden die Algorithmen eigentlich mit verschiedenen Datensätzen getestet?
    Also werden folgende Parameter bei den Tests variiert?

    - Größe der Ebene (bis zu 4096x4096)
    - Anzahl der Rechtecke (bis zu 50 Millionen)
    - Durchschnittliche Größe der Rechtecke

    0
  • P

    TomasRiker schrieb:

    Werden die Algorithmen eigentlich mit verschiedenen Datensätzen getestet?
    Also werden folgende Parameter bei den Tests variiert?

    - Größe der Ebene (bis zu 4096x4096)
    - Anzahl der Rechtecke (bis zu 50 Millionen)
    - Durchschnittliche Größe der Rechtecke

    Jo

    0
  • M

    Habe mal meinen Algorithmus in den von camper gegebenen Rahmen gebaut. Mein Algorithmus ist nach ~80 Sekunden (zumindest laut Ausgabe - ich war in der Zeit essen) mit einem Ergebnis für die 100M Rechtecke fertig. Der Default (nicht der von Jestern, sondern der andere), rechnet mittlerweile > 15 Minuten, so dass ich die Geschichte gleich abbreche und mich anderen Sachen widmen werde.

    0
  • P

    Hallo,

    die erste Version meiner Testumgebung gibt es auf:

    Da sind drei Generatoren. Einer wird noch dazukommen. Alle fliessen in die Bewertung ein.

    http://www.pontohonk.de/wpc/contest.tar.bz2

    0
  • ?

    Hm, irgendwie ist das doof 😞 >90% der Rechenzeit hängt bei mir am "result[x][y] = z;" 😕
    Darf/Kann man das irgendwie optimieren? Blockschreiben geht ja eigentlich nicht, obwohl viele Compiler die Werte von einem Vector ja hintereinander ablegen...

    0
  • J

    BlaBlubb schrieb:

    Hm, irgendwie ist das doof 😞 >90% der Rechenzeit hängt bei mir am "result[x][y] = z;" 😕
    Darf/Kann man das irgendwie optimieren?

    Jo, mach das seltener. 🙂

    0
  • ?

    'Tschuldigung für den Doppelpost, aber könnte man nicht die Aufgabe so abändern, dass beim result statt einem vector<vector<size_t>> dann einfach ein size_t** genommen wird? Und als Regel, dass man nicht blockschreiben darf, aber der doppelte vector ist so verflucht langsam!

    Oder vielleicht, dass kein vector-Array übergeben wird, sondern man mit einem Aufruf an "SetResult( x, y, Wert)" das Dings für ein Ergebnis setzen kann?

    0
  • B

    Hat sich erledigt, ist gar nicht das Setzen der Werte, was so lahm ist, sondern der Rest von meinem Algorithmus 😞
    Und "result[x][y] = z;" mache ich eigentlich auch nur pro Feld 1 mal, jedenfalls in der Theorie, irgendwo steckt noch ein Fehler drin 🙂
    Bin übrigens die registrierte Version von BlaBlubb, wusste nur mein Passwort nicht mehr 😃

    0
  • P

    BlaBlubb schrieb:

    Hm, irgendwie ist das doof 😞 >90% der Rechenzeit hängt bei mir am "result[x][y] = z;" 😕
    Darf/Kann man das irgendwie optimieren? Blockschreiben geht ja eigentlich nicht, obwohl viele Compiler die Werte von einem Vector ja hintereinander ablegen...

    Alle Compiler legen die Werte eines vectors im Block ab. Das ist garantiert.

    Aber da result ein std::vector<std::vectorstd::size\_t > ist, sind zwei benachbarte x linien nicht nebeneinander. Du kannst dir aber ein std::vectorstd::size\_t(xdim * ydim) anlegen und das Ergebnis am Ende rüberkopieren.

    0
  • C

    Ponto schrieb:

    BlaBlubb schrieb:

    Hm, irgendwie ist das doof 😞 >90% der Rechenzeit hängt bei mir am "result[x][y] = z;" 😕
    Darf/Kann man das irgendwie optimieren? Blockschreiben geht ja eigentlich nicht, obwohl viele Compiler die Werte von einem Vector ja hintereinander ablegen...

    Alle Compiler legen die Werte eines vectors im Block ab. Das ist garantiert.

    Aber da result ein std::vector<std::vectorstd::size\_t > ist, sind zwei benachbarte x linien nicht nebeneinander. Du kannst dir aber ein std::vectorstd::size\_t(xdim * ydim) anlegen und das Ergebnis am Ende rüberkopieren.

    Andererseits ist es ja egal, ob nun x oder y zuerst kommt; du kannst sie ja genauso gut auch in deinem Algorithmus vertauschen.

    0
  • P

    Es gibt ein Update meiner Testumgebung.

    - Ein Randomblockgenerator ist drin
    - Es wird jetzt das vollständige Bild in der GUI angezeigt
    - Das ultimative Makefile ist jetzt dabei

    http://www.pontohonk.de/wpc/contest.tar.bz2

    0
  • C
     

    struct Rectangle {

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

   Rectangle(Coordinate x, Coordinate y)
    : minx(x), maxx(x+1), miny(y), maxy(y+1) {}

   Rectangle() {}

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

    Bleibt das jetzt dabei oder gilt die Definition im ersten Posting?
    Es ist ja denkbar, dass der Compiler mit PODs noch etwas besser optimieren kann, und nur der bequemen Erzeugung wegen brauchen wir hier eigentlich keine Konstruktoren. Man könnte ja genauso gut nehmen:

    struct Rectangle {

   static Rectangle make(Coordinate minx, Coordinate maxx, Coordinate miny, Coordinate maxy) {
       Rectangle r = { minx, maxx, miny, maxy };
       return r;
   }

   static Rectangle make(Coordinate x, Coordinate y) {
       Rectangle r = { x, x+1, y, y+1 };
       return r;
   }

   Coordinate minx;
   Coordinate maxx;
   Coordinate miny;
   Coordinate maxy;
};
    0
Anmelden zum Antworten