C++ 3-Dim Array, Elemente konstanter Manhatten Distanz indexieren.

[striker159]

Ich habe ein dynamisches Programm mit einem n-dimensionalen Array, das ich füllen will. Auf die genaue Dimension habe ich mich noch nicht festgelegt, wird aber wohl ca 5 sein.

Die Abhängigkeit ist durch die Manhatten Distanz zum Ursprung gegeben. Für Einträge mit Manhatten Distanz D müssen die Einträge mit Distanz D-1 bekannt sein.

Das Array fülle ich demnach in Ebenen mit gleicher Manhatten Distanz der Elemente.

Nun bin ich auf der Suche nach einem Weg, die Anzahl an Iterationen zu verringern. Denn zb mit einem 50x50x50 Array habe ich in der aktuellen Version 122500 unnötige Iterationen (misses im code), also knapp 50% overhead.

Wie kann das speziell bei 3 Dimensionen, oder auch allgemein bei n Dimensionen verbessert werden?
Kann es verbessert werden?

    const int MAX_X_DIM = 50;
    const int MAX_Y_DIM = 50;
    const int MAX_Z_DIM = 50;
    const int MAX_X_INDEX = MAX_X_DIM - 1;
    const int MAX_Y_INDEX = MAX_Y_DIM - 1;
    const int MAX_Z_INDEX = MAX_Z_DIM - 1;
    const int MAX_PLANE = MAX_X_INDEX + MAX_Y_INDEX + MAX_Z_INDEX;

    int misses = 0;

    int data[MAX_X_DIM][MAX_Y_DIM][MAX_Z_DIM];

    memset(&data,0,MAX_X_DIM*MAX_Y_DIM*MAX_Z_DIM);


    for(int plane = 0; plane <= MAX_PLANE; ++plane){

	int maxX = plane;
        maxX = min(maxX, MAX_X_INDEX);

        for(int x = 0; x <= maxX; ++x){

            int maxY = plane - x;
            maxY = min(maxY, MAX_Y_INDEX);

            for(int y = 0; y <= maxY; ++y){

                int z = plane - x - y;

                if(z <= MAX_Z_INDEX && x + y + z == plane){
                    //do stuff
                    // berechne data[x][y][z] aus data[x-1][y][z], data[x][y-1][z] und data[x][y][z-1]
                }else{
                    ++misses;
                }

            }
        }
    }

    cout << "misses : " << misses << endl;

 

[VikingGe]

Kannst du schreiben, was genau du machen willst, was "do stuff" etwa macht und wofür welche Variablen in deinem Code zuständig sind? Wie soll das Array nach der Befüllung etwa aussehen? Ich verstehe nicht ganz, was du vor hast.

    memset(&data,0,MAX_X_DIM*MAX_Y_DIM*MAX_Z_DIM);

Deswegen ist memset in C++ eine Scheißidee Du füllst damit nur ein Vierteil deines Arrays.
Würde einfach nen std::vector für die Struktur nehmen und die genauen Indizes von Hand ausrechnen. Wenn die Arraydimension dynamisch wird, wird das eh zwingend nötig sein.

 

[Grantig]

Ohne zu wissen was du bei "do stuff" vor hast würde ich sagen das:

for(int x = 0; x < MAX_X_DIM; x++) {
    for(int y = 0; y < MAX_Y_DIM; y++) {
        for(int z = 0; z < MAX_Z_DIM; z++) {
            //do stuff
        }
    }
}

macht das gleiche wie dein Code nur ohne Overhead.

 

[striker159]

stimmt, da habe ich ein sizeof unterschlagen. macht aber nichts, das memset kommt raus.

Ich möchte nicht einfach nur alle Elemente schreiben, sondern muss auch die Abhängigkeiten einhalten. Dazu muss ich das Array wie beschrieben Ebene für Ebene füllen.


Speziell brauche ich in doStuff die benachbarten Elemente der vorherigen Ebene, zB um (5,4,3) zu berechnen die Werte von (4,4,3) , (5,3,3) und (5,4,2). Später analog für weitere Dimensionen.

Die genaue Arbeitsweise von dostuff möchte ich hier eigentlich nicht beschreiben. Es geht mir wirklich nur um eine effiziente bestimmung der Indizes für die aktuelle Ebene.

Edit: Da es aus dem Code nicht klar wird. In dem do stuff wird schließlich data[x][y][z] berechnet.

 

[ph4nt0m]

Wenn ich striker159 richtig verstehe, geht es darum, das mehrdimensionale Array nicht klassisch (d.h. zeilen- oder spaltenweise) zu durchlaufen, sondern in einer Reihenfolge, welche die Ordnung der Elemente mittels der Manhattan-Metrik berücksichtigt. Es soll verhindert werden, dass Elemente mehrfach besucht werden, und vor allem sollen sie erst dann besucht werden, wenn alle vorherigen Elemente (d.h. solche mit einer kleineren Manhatten-Distanz zum Ursprung) bereits besucht wurden

Für ein zweidimensionales Array ist diese Aufgabe leicht: Hier müsste man lediglich durch die Diagonalen (das ist im Startpost mit "Ebenen" gemeint) iterieren, ähnlich wie bei der Cantor-Diagonalisierung:

Bild

Um dieses Prinzip auf mehr als zwei Dimensionen zu verallgemeinern, müssten im Grunde Zerlegungen von ganzen Zahlen in eine Summe aus k Zahlen (sog. Partitionierungen) berechnet werden, wobei k die Anzahl der Dimensionen ist. Dies ist zweifelsfrei möglich, aber ich vermute, dass der dazu erforderliche Aufwand so groß wäre, dass er den Vorteil des einmaligen Durchlaufens aufhebt. Natürlich führst du momentan viele unnötige Iterationen aus, aber dafür ist die Prüfung, ob das aktuelle Element teil der momentanen Ebene ist (Zeile 30), relativ günstig.

 

[VikingGe]

Also im Grunde suchst du alle Felder mit der Manhattan-Distanz D zum Ursprung. Manhattan-Metrik ist im Dreidimensionalen bekanntlich folgende (wenn U=(ux,uy,uz) der Ursprung ist und P=(x, y, z) eine Feldposition):

d(U, P) = |ux-x| + |uy-y| + |uz-z|

d.h. du suchst in Schritt D alle Felder P, für die d(U, P)=D.

Wenn du jetzt jede Ebene einzeln durchgehst, kennst du deren minimale Distanz zum Ursprung (wenn z dein Ebenen-Index ist, ist das einfach |z-uz|), sowie das Feld mit dieser minimalen Distanz (das ist dann (ux,uy) in der Ebene). Du weißt also, dass die gesuchten Felder D-|uz-z| Felder von (ux,uy,z) entfernt sein müssen, d.h. wir reduzieren das Problem einfach auf den zweidimensionalen Fall:

Nun erhöht sich die Distanz ja mit jedem Schritt, den du dich vom Ursprung entfernt, um 1. Will heißen: Du kannst um D-|uz-z| Felder in positiver X-Richtung gehen und hast eins gefunden. Du kannst um D-|uz-z| Felder in positiver Y-Richtung gehen und hast wieder eins gefunden. Dann das ganze noch in negativer X- und Y-Richtung und du hast insgesamt vier Felder. Alle anderen Felder, die das Kriterium erfüllen, liegen auf der "Diagonalen" (wenn man das im Diskreten denn so nennen mag) zwischen diesen Punkten.

Also:

      x
    x o x
  x o U o x
    x o x
      x

x: Gesuchte Felder
o: Bekannte Felder
U: Ursprung, bzw. Feld mit minimaler Distanz zum Ursprung in der aktuellen Ebene.

Mit N Dimensionen müsste das eigentlich ähnlich gehen (also Zurückführen auf den N-1-dimensionalen Fall, bis man bei 2 angekommen ist), aber nagelt mich bitte nicht darauf fest, ich habe da jetzt nicht großartig drüber nachgedacht.

 

[kuddlmuddl]

Hier ist die Lösung für 2D:
http://stackoverflow.com/questions/1779199/traverse-matrix-in-diagonal-strips

Wenn es kein mehrdimensionaler Würfel ist sondern ein Quader dann ist hier die Erweiterung (allerdings auch erstmal nur für 2D):
http://stackoverflow.com/questions/2112832/traverse-rectangular-matrix-in-diagonal-strips

 

[Miuwa]

Geht's nur um die Manhattendistanz von positiven Indices zum Ursprung? Oder können einzelne Komponenten auch negativ werden?

 

[striker159]

ja, die Indices sind alle >= 0.

Dank dem 2d Bsp für ein Rechteck habe ich nun eine Lösung für ein 3d Quader. (Code habe ich gerade nicht da. Ich lasse für alle 2d Ebenen jeweils den 2d Code laufen, und rechne bei der n-ten 2d Ebene mit (slice - n) an Stelle von slice.)

Für höhrere Dimensionen muss ich mir mehr Gedanken machen.

 

[Miuwa]

Rekursiv lässt sich das ziemlich leicht lösen:

constexpr size_t DIMS = 2; //number of dimensions
using Indexes = std::array<int, DIMS>;

void doSomething(const Indexes& idx) {
	for (auto i : idx) {
		std::cout << std::setw(4) << i << " ";
	}
	std::cout << "\n";
}

void iterateRecursive(Indexes& idxs, const Indexes& max, size_t pos, int remainder) {
	if (pos < DIMS - 1 ) {
		for (size_t i = 0; i <= std::min(remainder , max[pos]); ++i) {
			idxs[pos] = i;
			iterateRecursive(idxs, max, pos + 1, remainder - i);
		}
	} else {
		if (remainder <= max.back()) {
			idxs.back() = remainder;
			doSomething(idxs);
		}
	}
}
int main()
{
	const Indexes maxidx{7,7,3,3};
	const size_t ManhattenDistance=10;
	Indexes idx{};
	iterateRecursive(idx, maxidx, 0, ManhattenDistance);
}

Ergänzung (23. April 2016)

Oder mit Templates:

template<size_t POS>
void iterateRecursive(Indexes& idxs, const Indexes& maxidx, int remainder) {	
	for (size_t i = 0, max= std::min(remainder, maxidx[POS]); i <= max; ++i) {
		idxs[POS] = i;
		iterateRecursive<POS+1>(idxs, maxidx, remainder - i);
	}	
}

template<>
void iterateRecursive<DIMS-1>(Indexes& idxs, const Indexes& max, int remainder) {
	if (remainder <= max.back()) {
		idxs.back() = remainder;
		doSomething(idxs);
	}
}


int main()
{
	Indexes idx{};
	Indexes maxidx{7,7,3,3};
	size_t ManhattenDistance=10;
	iterateRecursive<0>(idx, maxidx,ManhattenDistance);
}