[C++] 3D-Iterator

Programmiersprachen, APIs, Bibliotheken, Open Source Engines, Debugging, Quellcode Fehler und alles was mit praktischer Programmierung zu tun hat.
Antworten
Benutzeravatar
Jonathan
Establishment
Beiträge: 2352
Registriert: 04.08.2004, 20:06
Kontaktdaten:

[C++] 3D-Iterator

Beitrag von Jonathan »

Ich muss gerade über mehrere Dimensionen iterieren. Der naheliegende Ansatz wäre:

Code: Alles auswählen

for(auto x=0u; x<X; ++x)
	for(auto y=0u; y<Y; ++y)
		for(auto z=0u; z<Z; ++z)
			Something(x,y,z);
Was ich aber gerne hätte, wäre eine Lösung mit range-based for loops:

Code: Alles auswählen

for(auto& i : Range3d(2, 2, 2))
{
	cout << i.x << "/" << i.y << "/" << i.z << endl;
}
Ich habe spontan dazu nichts fertiges gefunden (kennt jemand was?), und mir als kleine Fingerübung selber was geschrieben: (Der Code benutzt glm::uvec3 als Hilfsklasse).

Code: Alles auswählen

class Range3d
{
public:
	Range3d(unsigned int x, unsigned int y, unsigned int z):
		Range3d(uvec3(x, y, z)) {};
	Range3d(uvec3 range):
		range(range),
		position(0, 0, 0)
	{
	}

	Range3d begin()
	{
		return *this;
	}
	Range3d end()
	{
		return *this;
	}

	bool operator!= (Range3d r)
	{
		// r should always be *this
		return uvec3(position.x+1, position.y+1, position.z+1) != r.range;
	}
	Range3d& operator++ ()
	{
		position.x++;
		if(position.x==range.x)
		{
			position.x=0;
			position.y++;
			if(position.y==range.y)
			{
				position.y=0;
				position.z++;
				// z should never overflow due to loop exit condition
			}
		}
		return *this;
	}
	uvec3 operator* ()
	{
		return position;
	}
private:
	uvec3 range;
	uvec3 position;
};
Was haltet ihr davon? Das ganze ist etwas kompakt geschrieben, weswegen einige Operatoren teilweise etwas pervers sind. Semantisch hätte man vermutlich gerne ein Range und eine Iteratorklasse gehabt, aber so ist halt kompakter. Ein paar Kopien werden im Hintergrund gemacht, aber wenn man sich die Referenzimplementierung ansieht, ist das wohl auch nicht zu vermeiden. Ich hoffe einfach mal, dass der Kompiler seinen Job macht, und die wegoptimiert.Falls ja, bin ich eigentlich halbwegs zuversichtlich, dass da ähnlicher Code wie bei der naiven Implementierung rauskommen könnte.
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Benutzeravatar
Schrompf
Moderator
Beiträge: 4838
Registriert: 25.02.2009, 23:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: [C++] 3D-Iterator

Beitrag von Schrompf »

Joa, so in etwa sieht meiner auch aus. Ich würde aber noch zu einem Prä-Inkrement-Operator raten. Du hast bisher nur Post-Increment implementiert, und den falsch, denn eigentlich gibt der Post Increment den vorherigen Wert zurück. Und das braucht ein Temporary, weswegen man in inneren Schleifen eigentlich darauf achtet, immer Preincrement zu nutzen.

Optimierungsidee: Zählervariable von 0 bis x*y*z laufen lassen, und xyz per Modulo berechnen lassen. Vermeidet dynamisches Branching, kostet dafür Integer-Divisionen... könnte auf aktuellen x86-CPUs also schneller sein, auf ARM oder sowas dagegen schmerzhaft langsam.
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
Benutzeravatar
Jonathan
Establishment
Beiträge: 2352
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: [C++] 3D-Iterator

Beitrag von Jonathan »

Schrompf hat geschrieben:Ich würde aber noch zu einem Prä-Inkrement-Operator raten. Du hast bisher nur Post-Increment implementiert, und den falsch, denn eigentlich gibt der Post Increment den vorherigen Wert zurück. Und das braucht ein Temporary, weswegen man in inneren Schleifen eigentlich darauf achtet, immer Preincrement zu nutzen.
Bist du dir da sicher?

http://en.cppreference.com/w/cpp/langua ... tor_incdec

Eigentlich sollte es ohne dummy-int der pre-increment operator sein. Aber eigentlich sollte es auch keinen Unterschied machen, nur ein Wahnsinniger würde den Operator (wie auch alle anderen Funktionen) von Hand (außerhalb einer range-based-for Schleife) aufrufen.
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Benutzeravatar
Schrompf
Moderator
Beiträge: 4838
Registriert: 25.02.2009, 23:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: [C++] 3D-Iterator

Beitrag von Schrompf »

Hm, kann sein, dass ich mich verguckt habe. Dann bleibt nur noch, mal den linearen Betriebsmodus auszuprobieren. Damit könnte vor allem der Comparator deutlich fixer werden. Ob und wie Dein bisheriger Abschluss-Vergleich funktioniert, habe ich ehrlich gesagt nicht durchschaut.
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] 3D-Iterator

Beitrag von Krishty »

Was machst du denn mit X, Y, und Z? Falls du jeweils an jeder Position Daten verarbeiten willst, liegen die doch sicher in einem Container, und der hat bestimmt eine 1D-Iterationsfunktion …
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Jonathan
Establishment
Beiträge: 2352
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: [C++] 3D-Iterator

Beitrag von Jonathan »

jup. Aber ich muss aus den x,y,z Indexen eine 3D Position ausrechnen, und das geht mit 2 Zeilen weniger als wenn ich nicht nur einen 1D-Index habe. Aber jetzt da es läuft, würde ich es gerne mit OpenMP beschleunigen, und werde es der Einfachheit halber deshalb vermutlich doch wieder umschreiben...
(Zu gut 50% war das aber eh nur ein Experiment, ob man das mit C++ nicht irgendwie schön machen kann).
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] 3D-Iterator

Beitrag von Krishty »

Wenn man das schön macht, wird es automatisch langsam. Falls deine Datenstruktur irgendwie hierarchisch oder räumlich ist, ist for(x, y, z) das Schlimmste, das du der CPU antun kannst …
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Jonathan
Establishment
Beiträge: 2352
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: [C++] 3D-Iterator

Beitrag von Jonathan »

Im wesentlichen ist im Hintergrund ein 1D-Vector und ich achte schon darauf, dass der beim iterieren schrittweise durchlaufen wird. Ob der Compiler von dem (x,y,z) verwirrt wird und nicht die selben Optimierungen vornimmt, wie im flachen Fall, weiß ich nicht - wäre unschön aber denkbar.
In der Schleife benötige ich auf jeden Fall die (x,y,z) Werte. Dann stellt sich also nur noch die Frage, welche Variante (wie von Schrompf auch schon vorgeschlagen) schneller ist. Vielleicht steige ich tatsächlich auf 1D Iteration um, immerhin spart man sich damit die ganze Iterator-Hilfsklasse und braucht nur eine Get3dIndexFrom1dIndex(int i, vec3 range) Funktion, die dann halt zwei Divisionen durchführt.

Aber es war auf jeden Fall nochmal eine nette Fingerübung. Ich habe zuletzt einiges in Python gemacht, wo man ja oft eine nette und kompakte Syntax hat (was zu den Dingen gehört, die mich an Python nicht nerven) und wollte mal schauen, inwieweit das auch in C++ geht. Tut es also, aber ob es dadurch wirklich besser wird - naja.

@Schrompf:
Zum Abbruchkriterium: Wenn die Range (128,96,32) ist, ist der letzte Index(127,95,31) - daher das +1 im Vergleich. Das rechte Argument des Operators braucht man ansich nicht, weil im linken auch schon die range steht.
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] 3D-Iterator

Beitrag von Krishty »

Jonathan hat geschrieben:Ob der Compiler von dem (x,y,z) verwirrt wird und nicht die selben Optimierungen vornimmt, wie im flachen Fall, weiß ich nicht - wäre unschön aber denkbar.
So lange du nicht Clang mit Polly nutzt, ist es höchstwahrscheinlich. Divisionen als Index für indirekten Speicherzugriff, mit drei zu verschmelzenden Schleifen, ist schon hart. An Visual C++ würde es allein deshalb scheitern, weil dein Iterator X/Y/Z als Member speichert und dann grundsätzlich nichts optimiert wird.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Antworten