Eine Woche Programmierwettbewerb: Rechtecke

rapso

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.

otze

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

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?

Ponto

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.

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.