Eine Woche Programmierwettbewerb: Rechtecke

[rapso]

ich hab mal was waehrend meiner 10min linker-time verwurschtelt:

#include <stdio.h>
#include <vector>
//#include <iostream>
#include <ctime>

#define USE_SAMPLE
#define USE_VERIFY
#define USE_OUTPUT
#define USE_BENCH

const size_t	MAX_PLANE_SIZE	=	4096;
const int			MAX_RECTS				=	1000;
const	int			DEFAULT_SEED		=	0xDeadFace;

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;

struct Rectangle
{
	int minx, maxx, miny, maxy;
	Rectangle(){};
	Rectangle(int x1,int x2,int y1,int y2):minx(x1),maxx(x2),miny(y1),maxy(y2){}
};

void GenRects(Rectangle plane,std::vector<Rectangle> &rectangles,int MaxSize)
{
	const int width		=	plane.maxx-plane.minx;
	const int height	=	plane.maxy-plane.miny;
	const int Count		=	CTwister::Rand() % MaxSize;
	rectangles.resize(Count+1);
	rectangles[0] = plane;
	for(int a=0;a<Count;a++)
	{
		Rectangle &r	=	rectangles[a+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;
	}
}

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

void algorithm(Rectangle plane, std::vector<Rectangle> const & rectangles, std::vector<std::vector<std::size_t> > & result)
{
	//yours
}

int main(int argc,char* argv[])
{
#if defined(USE_SAMPLE)
	Rectangle Plane(3,8,3,8);
	std::vector<Rectangle> Rects;
	Rects.push_back(Plane);
	Rects.push_back(Rectangle(5,9,2,6));
	Rects.push_back(Rectangle(4,6,5,7));
	Rects.push_back(Rectangle(3,4,3,7));
#else
	CTwister::Init(DEFAULT_SEED);
	Rectangle Plane;
	Plane.minx	=
	Plane.maxx	=		CTwister::Rand()%(MAX_PLANE_SIZE-1);
	Plane.miny	=
	Plane.maxy	=		CTwister::Rand()%(MAX_PLANE_SIZE-1);
	Plane.maxx	+=	CTwister::Rand()%(MAX_PLANE_SIZE-Plane.minx);
	Plane.maxy	+=	CTwister::Rand()%(MAX_PLANE_SIZE-Plane.miny);
	std::vector<Rectangle> Rects;
	GenRects(Plane,Rects,MAX_RECTS);
#endif

	std::vector<std::vector<std::size_t> > Result;
	Result.resize(Plane.maxy-Plane.miny+1);
	for(size_t a=0,Size=Plane.maxy-Plane.miny;a<=Size;a++)
		Result[a].resize(Plane.maxx-Plane.minx+1);

#if defined(USE_BENCH)
	clock_t T1=clock();
#endif
	algorithm(Plane,Rects,Result);
#if defined(USE_BENCH)
	clock_t T2=clock();
#endif

#if defined(USE_VERIFY)
	std::vector<std::vector<std::size_t> > ResultJester;
	ResultJester.resize(Plane.maxy-Plane.miny+1);
	for(size_t a=0,Size=Plane.maxy-Plane.miny;a<=Size;a++)
		ResultJester[a].resize(Plane.maxx-Plane.minx+1);

#if defined(USE_BENCH)
	clock_t J1=clock();
#endif
	algorithmJester(Plane,Rects,ResultJester);
#if defined(USE_BENCH)
	clock_t J2=clock();

	printf("Time needed %ds\nJestertime %ds\nspeedup %f\n",(T2-T1)/CLOCKS_PER_SEC,
																												(J2-J1)/CLOCKS_PER_SEC,
																												(static_cast<float>(J2-J1)/static_cast<float>(T2-T1>0?T2-T1:1)));
#endif

	bool Correct=true;
	for(size_t y=0,SizeY=Plane.maxy-Plane.miny;y<SizeY;y++)
		for(size_t x=0,SizeX=Plane.maxx-Plane.minx;x<SizeX;x++)
			Correct&=(Result[y][x]==ResultJester[y][x]);

	printf("Correct: %s\n",Correct?"yes":"no");
	//std::cout << "Correct: " << (Correct?"yes":"no") << std::endl;

#endif

#if defined(USE_OUTPUT)
	for(size_t y=0,SizeY=Plane.maxy-Plane.miny;y<SizeY;y++)
	{
		for(size_t x=0,SizeX=Plane.maxx-Plane.minx;x<SizeX;x++)
			printf("%d",ResultJester[SizeY-y-1][x]);
		printf("\n");
//			std::cout	<<	Result[y][x];
//		std::cout << std::endl;
	}
#endif

	return 0;
}

damit wir ne gemeinsame basis haben zum verifizieren und benchen. eventuell findet ihr ja noch ein paar bugs (btw sorry fuers layout, hier in der arbeit hab ich tab2)

edit: timer eingebaut

[rapso]

otze schrieb:

mit jesters code braucht man wohl nicht zu testen, der skaliert so schlecht, dass man große daten(und da wirds erst richtig interessant), vergessen kann zu berechnen.

naja, ne referenz brauchen wir.

[Ponto]

Da die Plane maximal 4096x4096 groß werden kann, ist es denke ich keine Einschränkung short für die Rechtecke zu nehmen. Deshalb würde ich jedem freistellen, ob er Rechtecke mit short oder int haben möchte.

Ist das ok?

Den Typ von result ändern wir nicht mehr.

[rapso]

ich glaube es waere noch wichtig irgendwie festzulegen wo die rects liegen. in dem sample oben sind alle ausserhalb (zufaelligerweise), ist es legitim dass es Rectangle gibt die nicht in der plane liegen?

[otze]

vielleicht sollte man lieber, anstatt ein zufällige anzahl von rects eine konstante anzahl nehmen, denn was bringt ein maxrect=50000000 wenn der algo nur 10 rects am ende ausspuckt?

also:

void GenRects(Rectangle plane,std::vector<Rectangle> &rectangles,int MaxSize)
{
    const int width        =    plane.maxx-plane.minx;
    const int height    =    plane.maxy-plane.miny;
    const int Count        =   MaxSize;//kein rand hier
    rectangles.resize(Count+1);
    rectangles[0] = plane;
    for(int a=0;a<Count;a++)
    {
        Rectangle &r    =    rectangles[a+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;
    }
}

und der algo war bei mir bei einem test mit 300000 rects und einem 100x100 feld 3x so schnell, könnte man vielleicht verwenden

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

@rapso ja, die rects dürfen ausserhalb liegen, hab ich schon gefragt

[Ponto]

rapso schrieb:

ich glaube es waere noch wichtig irgendwie festzulegen wo die rects liegen. in dem sample oben sind alle ausserhalb (zufaelligerweise), ist es legitim dass es Rectangle gibt die nicht in der plane liegen?

Ja, das ist nach Aufgabenstellung explizit legitim.

[Ponto]

otze schrieb:

vielleicht sollte man lieber, anstatt ein zufällige anzahl von rects eine konstante anzahl nehmen, denn was bringt ein maxrect=50000000 wenn der algo nur 10 rects am ende ausspuckt?

also:

und der algo war bei mir bei einem test mit 300000 rects und einem 100x100 feld 3x so schnell, könnte man vielleicht verwenden

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

@rapso ja, die rects dürfen ausserhalb liegen, hab ich schon gefragt

Das ist der zweite Algorithmus hier. Der ist nicht so einfach zu schlagen wie der erstere. Aber dennoch ist Raum für bessere Implementierungen.

[Ponto]

#include <iostream>
#include <vector>

#include <QtGui>

int main() {
   std::vector<std::vector<std::size_t> > vec(4096, std::vector<std::size_t>(4096, 0));
   std::vector<std::size_t> vec2(4096*4096, 10);

   QTime time;
   time.start();
   for (int i = 0; i < 4096; ++i) {
       vec[i].assign(&vec2[0] + i*4096, &vec2[0] + (i+1)*4096);
   }
   std::cout << time.elapsed() << "\n";
}

Das Kopieren eines kontinuierlichen Feldes in das result Array benötigt hier 0.156 Sekunden. Wenn man also durch die Verwendung soviel sparen kann.

[rapso]

3x so schnell im debug und

Time needed 0s
Jestertime 0s
speedup 1.284404
Correct: yes

im release.

[otze]

@rapso hmm bei mir war er im release 3x so schnell. vielleicht optimiert dein compiler da wesentlich besser.

btw: wie wollen wir das vergleichen, wenn alle unterschiedliche std implementationen und compiler haben?

@Ponto den algo hab ich nur gepostet, um was besseres zum vergleichen zu haben. glaub niemand hier, würde wirklich etwas in der richtung versuchen.

btw: das kopieren des arrays wäre kein problem, ich mach das zb auch, weil das Rectangle meinen anforderungen nicht genügt, aber das bringt enorme speicherverluste mit sich.

bei 50 millionen rechtecken ist das array 381MB groß. nach dem kopieren sind also schonmal 762 MB übern Jordan. Und das array was man als input kriegt, kann man nicht mehr freigeben.

Ich weis, das istn bissl ketzerisch, aber vielleicht...

class Algorithm
{
    private:
        //user defined
    public:
        void setPlane(Rectangle Plane)
        {
             //user defined
        }
        void insertData(const Rectangle& rectangle)
        {
             //user defined
        }
        void calculate(std::vector<std::vector<std::size_t> >& result)
        {
             //user defined
        }
};

dann in der main:
std::vector<Rectangle> array;
Algorthm test;
//werte berechnen..
test.setPlane(array[0]);
foreach(Rectangle& rect,array)//das neue boost foreach ist cool
{
    test.insertData(rect);
}
array.clear();
test.calculate(result);

so wär viel mehr freiraum für alle geschaffen. natürlich muss dann insert+calculate gemessen werden, aber danach kann man theoretisch alle algorithmen fair vergleichen. Nurn vorschlag, denke nicht, dass du da nochmal was ändern willst, aber wollte ich nur mal gesagt haben.

so, ich geh malwieder Kisten packen *seufz*

[Jester]

otze schrieb:

so wär viel mehr freiraum für alle geschaffen.

Dann müßte zu Beginn mindestens noch die Rechteckanzahl übergeben werden. Sonst hat man weniger Information zur Verfügung.

[otze]

Jester schrieb:

otze schrieb:

so wär viel mehr freiraum für alle geschaffen.

Dann müßte zu Beginn mindestens noch die Rechteckanzahl übergeben werden. Sonst hat man weniger Information zur Verfügung.

stimmt. ganz vergessen, guter Einwand

[Jester]

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.

[Jester]

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

[otze]

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

[Ponto]

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.

[otze]

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?

[Ponto]

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.

[rapso]

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.

[jenz]

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

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

oder als parameter?

jenz