Eine Woche Programmierwettbewerb: Rechtecke

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

TomasRiker

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)

otze

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.

TomasRiker

OK, ich wollte euch nur ein wenig schocken

Mehlvogel

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

otze

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

Mehlvogel

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

camper

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;
}

TomasRiker

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

Ponto

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

Mehlvogel

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.

Ponto

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