Eine Woche Programmierwettbewerb: Rechtecke

rapso

opengl ist bei so ziemlich jedem compiler dabei, es duerfte kein problem sein das auf jeder plattform zu nutzen. als farbinformationen solltest du durchaus 4mrd farben (32bit) annehmen duerfen, man muss nur das richtige format setzen. du kannst nen buffer mit 4096*4096 als rendertarget setzen und rauslesen ist auch kein problem.

jenz

ich habe noch mal eine frage,
dürfen wir die obersten beiden bits im result jeweils benutzen...

so viele rechtecke wird es ja wohl nie geben, oder?

jenz

rapso

jenz schrieb:

ich habe noch mal eine frage,
dürfen wir die obersten beiden bits im result jeweils benutzen...

so viele rechtecke wird es ja wohl nie geben, oder?

jenz

dann wuerd ich auch requesten ob wir statt int dann short benutzen koennen im Rectangle und ob wir statt dem vector<vector> nicht lieber nur vector nehmen koennten der halt size*size gross ist(wenn wir schon performance messen wollen, waere es bloed diesen overhead zu haben).

btw. hat jemand Jesters loesung auf das beispiel angewand?

Ponto

jenz schrieb:

ich habe noch mal eine frage,
dürfen wir die obersten beiden bits im result jeweils benutzen...

so viele rechtecke wird es ja wohl nie geben, oder?

jenz

Warum brauchst du dazu result? Warum kein eigenes Array, das die Daten vorhält.

Es werden wahrscheinlich nicht so viele Elemente sein, aber ich denke, dass ich die Aufgabe aus Fairness jetzt nicht mehr ändern kann. Es sei, denn jeder stimmt zu?

Ponto

dann wuerd ich auch requesten ob wir statt int dann short benutzen koennen im Rectangle und ob wir statt dem vector<vector> nicht lieber nur vector nehmen koennten der halt size*size gross ist(wenn wir schon performance messen wollen, waere es bloed diesen overhead zu haben).

btw. hat jemand Jesters loesung auf das beispiel angewand?

Stimmt was mit Jesters Lösung nicht? Oder mit dem Beispiel?

Für die Änderung ist es denke ich auch zu spät. Ich hab zuerst überlegt, nur ein std::vectorstd::size_t zu nutzen, aber dann wäre die Erklärung nicht so einfach gewesen.

Vieviel Zeit würde verloren gehen, die Daten von einem eigenen Vektor nach result zu kopieren?

jenz

okay, kein problem.
ich kann auch ohne die bits auskommen...

jenz

hat jemand lust meine lösung mal auszuprobieren?

ich würde gerne mal einen anderen ausprobieren...

natürlich jeweils als quellcode...

falls jemand schicken möchte:

wienoebst at yahoo.de

jenz

rapso

emm... vorher die quellcodes auszutauschen entgeht irgendwie dem wettbewerbs geist, oder?

ich schlage vor wir uppen irgendwo standard testdaten, testen mit Jesters code und schauen dann wieviel % schneller man ist, so zum vergleichen.

otze

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. Vielleicht kann man sich ja so einigen, dass man jenz generator so verändert, dass er statt rand() die boost lösung nutzt, und geben dann bei unseren testzeiten den jeweiligen seed mit an. So hat jeder den gleichen zufallsgenerator und den gleichen seed, und dann kann man auch große testdaten vergleichen.

btw: 50 mio rectangles sind mal ne richtige herausforderung. ich denke, Geschwindigkeit wird nicht das problem sein, aber der Speicherverbrauch...(insofern find ichs schon interessant, dass ich nicht der einzige mit solchen platzproblemen bin :D).

Weis auch inzwischen nicht mehr, wie ich mehr als 25mio rects sicher berechnen kann, vorhin hab ich zum ersten mal 30mio rects geschafft, dann hab ich nen andren seed für rand genommen, und aus wars ;).

ps: bin auch für short im Rectangle
pps: meinetwegen kann man auch ein paar bytes aus result nutzen, mich störts nicht(hilft mir aber auch leider nicht weiter :D)
ppps: benutzt niemals vector in Code, wo ihr große datenschwankungen habt, der expandiert euch mal locker den halben speicher weg, ohne ihn jemals zu brauchen *seufz*. Andererseits is es mit der std::list auch net wirklich besser, durch die 8Byte zusätzlichen speicher pro element...
pppps: Jesters Code ist korrekt

Jester

otze schrieb:

So hat jeder den gleichen zufallsgenerator und den gleichen seed, und dann kann man auch große testdaten vergleichen.

Wie vergleichen wir die Laufzeiten, wenn wir alle verschieden schnelle Rechner haben? -- Irgendein Vergleichsalgorithmus muss da schon her. Vielleicht mag ja jemand den Algorithmus ein bißchen umstricken? Allein das Vertauschen einiger Schleifen dürfte da ja schon einiges bringen.

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*