Eine Woche Programmierwettbewerb: Rechtecke

Ponto

otze schrieb:

ahh ok, danke

noch eine Frage:

Der Parameter rectangles bezeichnet die Menge der eingegebenen Rechtecke. Diese müssen nicht vollständig in der Ebene plane liegen.

bedeuted dass, dass jedes rechteck midnestens einen Punkt mit der Grundebene gemeinsam haben muss? so les ich das nämlich da heraus. Oder ist zb das verhalten von jenz generator richtig?

Die können ganz außerhalb liegen.

otze

dann entfern besser das Wort "vollständig". das verwirrt leute wie mich

ok, keine Fragen mehr

//edit erstes Ergebnis: eine 4096x4096 große ebene mit 15 millionen rechtecken in 2min, 45sec durchgerechnet :). Viel mehr geht im moment nicht, weil ich zwischendurch bedrohlich nah an die 2GB speichergrenze komme ;). Aber das undn bissl mehr speed krieg ich noch hin, bzw wenn ich mehr zeit hätte

habt ihr schon Ergebnisse?

ca. 40 Sekunden bei 4096² und 50M Rechtecken, 915MB Speicherverbrauch
A64 3200+ Venice, Vista x64 (2GB Grenze, wasn des? :D)
muss aber noch Korrektheitstests durchführen

Der Wettbewerb ist IMO etwas ungünstig angesetzt, ich fahre morgen über verlängertes WE Eltern besuchen und möchte die Zeit eigentlich nicht vor dem Rechner verbringen. Ansonsten coole Optimierungsaufgabe, Respekt.

Jester

Ich komme wohl nicht vor Freitag zum Implementieren :(. Könnt ihr die Generatoren die ihr verwendet mal posten?

Ponto

Verwirrt die Teilnehmer nicht durch irgendwelche erfundenen Zwischenergebnisse!

Es soll ja keiner abgeschreckt werden.

otze

Jester schrieb:

Ich komme wohl nicht vor Freitag zum Implementieren :(. Könnt ihr die Generatoren die ihr verwendet mal posten?

ich hab den von jenz benutzt

@Ponto ich bin eh für niemanden ne Konkurrzenz, weil das Programm das bei mir fehlerfrei läuft, bei dir wahrscheinlich nichtmal compilieren wird

camper

Eigentlich die ideale Aufgabe, um Grafikprozessoren zu beschäftigen. Fütter den Prozessor mit den Rechtecken, der Index dient für die Tiefe und Farbe und lass es ihn einfach malen. Anschließend untersucht man einfach die Farbe für jedes Pixel. ist aber wohl nicht portabel hinzukriegen

otze

camper schrieb:

Eigentlich die ideale Aufgabe, um Grafikprozessoren zu beschäftigen. Fütter den Prozessor mit den Rechtecken, der Index dient für die Tiefe und Farbe und lass es ihn einfach malen. Anschließend untersucht man einfach die Farbe für jedes Pixel. ist aber wohl nicht portabel hinzukriegen

ginge schon. opengl is ja ziemlich portabel

Ponto

Wenn Ihr das mit der OpenGL Unterstützung von Qt so hinkriegt, dass es hier kompiliert, soll es mir recht sein. Aber wie bekommt ihr die Daten aus der Graphikkarte? Und wenn man den Index als Farbe kodiert, reichen da die Werte?

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