Schnelles Iterieren über "pyramidale" Matrix

[Eisflamme]

Hi,

ich habe eine Matrix, bei der nur bestimmte Felder interessant sind. Daher möchte ich auch nur diese speichern.

Sie hat 3 Dimensionen X1,X2,X3. X1,X3 spannen sich auf von 0-10, also 11 mögliche Werte je. X2 spannt sich auf von 0-20, also 21 Werte je. Jetzt gibt es aber eine Zusatzbedingung für x1 aus X1, x3 aus X3: x1 + x3 <= 10

Man braucht jetzt also keinen Vektor der Größe 21*11^2 mehr, sondern nur noch 21*(11+1)*11/2 = 21*66.

Jetzt möchte ich schnell über alle Einträge in der Matrix iterieren. Ich benötige aber in jeder Iteration auch x1,x2,x3, also die jeweilige Position in der Matrix.

Die zurzeit optimale Idee, die ich gerade habe, ist so:
- Iteration selbst einfach mit for(int n = 0; n < 21 * 66; ++n)
- In Schleifendurchläufen Ermittlung von x1,x2,x3 durch Formel

So, etwas weitergedacht merkt man, dass der Hase bei x1 im Pfeffer liegt. Die Ermittlung von x1,x2,x3 würde ich zurzeit so machen:
- Lookup-Table für die Indizes [x1=0][x2=0][x3=0], [x1=1][0][0], ... erstellen
- via Schleife (hier habe ich jetzt Performanceängste :() schauen, was die kleinste Zahl ist, welche durch n überschritten wird (sagen wir Mal 441)
- der Index der Lookup-Table ist jetzt einfach unser x1, in diesem Fall also z.B. 2
- Sagen wir, n = 500; dann können wir einfach 500-441=59 rechnen; da x1=2, gibt es für x3 9 mögliche Werte, also 59 / 9 = 6 = x2
- 59 % 9 = 5 = x3

Also x2 und x3 sind trivial zu berechnen. Bei x1 brauche ich aber so eine Lookup-Table und da habe ich echt Angst, dass mir das zu langsam wird. Ich könnte die natürlich noch beschleunigen, indem ich binär lookupe oder eine Heuristik verwende (im einfachsten Fall z.B. linear). Aber ist das optimal?

Die Iteration ist garantiert performancekritisch. Anwendungsgebiet ist dynamische Programmierung, ich muss also einen State Space durchlaufen und für jede Iteration dann einen "Transition State Space", aber ich glaube kaum, dass das für die Problemstellung hier relevant ist. Prinzipiell könnte die Matrix statt 3 sogar eine beliebige ungerade Anzahl an Dimensionen umfassen (mehr als 7 ist jedoch sehr unwahrscheinlich), wobei zwei Dimensionspaare dann immer die Bedingung haben in Summe 10 nicht zu überschreiten. Die Matrix könnte also auch viel größer sein, was vielleicht für Cache-Überlegungen relevant sein könnte - aber eins nach dem anderen.

Vielleicht hat ja jemand eine Idee, wie ich es noch beschleunigen kann.

Vielen Dank und beste Grüße,
Eisflamme

Edit: Eine wurzelförmige Heuristik trifft das Ding ziemlich genau. Das wird so ein Prozessor ja auf Hardware berechnen können. Viel schneller wird's dann wohl nicht gehen. Habe nur Angst vor Rundungsfehlern, wenn 1,9999 für 2 rauskommt und das Abrunden dann zu 1 führt. Oder ist mein Iterationsansatz generell nicht gut genug?

[Werner Salomon]

Hallo Eisflamme,

wähle zwei geschachtelte Schleifen, wobei die innere jeweils nur über die Dimension X2 läuft - X2, weil das die längste ist. Etwa so:

vector< Foo > all; // 66*21 Elemente
    for( auto i = begin(all); i!= end(all); ++i )
    {
        // berechne hier x1 und x3
        vector< Foo >::iterator i2 = f(all, x1, x3);
        vector< Foo >::iterator i2_end = i2 + 21;
        for( int x2 = 0; i2 != i2_end; ++i2, ++x2 )
        {
            // hier stehen jetzt x1, x2 und x3 zur Verfügung
            Foo& foo = *i2; // mache was mit dem aktuellen Element
        }
    }

Die Berechnung von x1 und x3 sollte von der Performance keine Rolle spielen, da diese ja nur alle 21 Elemente durchgeführt wird.
Das setzt natürlich voraus, dass die Elemente innerhalb des vectors auch in der Reihenfolge abgelegt sind.

Ich würde das ganze ja noch in einen 'schlauen' Iterator packen, dafür fehlt mit i.A. die Muße.

Gruß
Werner

[Eisflamme]

Die Idee gefällt mir super.

Aber jetzt haben wir insgesamt ja 66*21 * 21 Iterationen. Der äußere Iterator sollte doch nur über X1,X3 iterieren. Hast du vorausgesetzt, dass der äußere Iterator eine Spezialanfertigung ist, welche immer brav 21 Elemente springt? Oder man schreibt halt i += 21.

Den gesamten Algorithmus packe ich bei mir ohnehin ebenfalls in einen Iterator, wie von dir vorgeschlagen.

[Werner Salomon]

Eisflamme schrieb:

Aber jetzt haben wir insgesamt ja 66*21 * 21 Iterationen. Der äußere Iterator sollte doch nur über X1,X3 iterieren. Hast du vorausgesetzt, dass der äußere Iterator eine Spezialanfertigung ist, welche immer brav 21 Elemente springt? Oder man schreibt halt i += 21.

Ja klar - hast Recht.
Der äußere Iterator i muss nachgeführt werden. i+=21 wäre eine Option - oder i=i2_end .

Gruß
Werner

[Werner Salomon]

.. oder gleich i2 einsparen und nur i nehmen!

[knivil]

Die Iteration ist garantiert performancekritisch

Das bedeutet in Zahlen? Wieviel % vom Rest faellt allein der Iteration zu? Hast du verschiedene Varianten ausprobiert? Was sind die Ergebnisse deiner Zeitmessungen im Vergleich zur trivialen Implementierung?

Die Matrix könnte also auch viel größer sein

Optimierung fuer verschiedene Problemgroessen ist ebenfalls verschieden. Gib eine realistische Groesse an, denn 21*66 Elemente (von welchem Typ?) ist sehr klein!

Ansonsten: Gibt keine generellen Tips, da Speicherlayout deiner Matrix unbekannt ist.

[volkard]

Eisflamme schrieb:

Sie hat 3 Dimensionen X1,X2,X3. X1,X3 spannen sich auf von 0-10, also 11 mögliche Werte je. X2 spannt sich auf von 0-20, also 21 Werte je. Jetzt gibt es aber eine Zusatzbedingung für x1 aus X1, x3 aus X3: x1 + x3 <= 10

Man braucht jetzt also keinen Vektor der Größe 21*11^2 mehr, sondern nur noch 21*(11+1)*11/2 = 21*66.

Also nur 50%. Beachte, daß Du durch unordentliche Herumhüpferei im RAM evtl viel mehr bezahlen musst. Wäre schlichtes if angemessen, wieviel mal mehr kostet die eigentliche Berechnung? Das Muster in Iteratoren wegzustopfen macht evtl den Optimierer dafür blind.

Eisflamme schrieb:

Sie hat 3 Dimensionen X1,X2,X3. X1,X3 spannen sich auf von 0-10,

for(int x1=0;x1<=10;++x1)
   for(int x2;;)
      for(int x3=0;x3<=10;++x3)

also 11 mögliche Werte je. X2 spannt sich auf von 0-20, also 21 Werte je.

for(int x1=0;x1<=10;++x1)
   for(int x2=0;x2<=20;++x2)
      for(int x3=0;x3<=10;++x3)

Jetzt gibt es aber eine Zusatzbedingung für x1 aus X1, x3 aus X3: x1 + x3 <= 10

for(int x1=0;x1<=10;++x1)
   for(int x2=0;x2<=20;++x2)
      for(int x3=0;x1+x3<=10;++x3)

Um ehrlich zu sein verstehe ich die Frage nicht. Ging es nur darum, "x1 + x3 <= 10" aus Deinem Posting in den Code zu copy&pasten?
Oder fürchstest Du, daß ein + auf int mehr als eine Nanosekunde kostet? Eine Nanosekunde sind nur 20 Centimeter, das ist winzig.

[Eisflamme]

Werner Salomon:
Okay, danke

knivil:
So genau kann ich das nicht beantworten. Es gibt innerhalb der Schleifen nochmal 1-2 kleinere Schleifen, worin wiederum nur ein paar Multiplikationen ausgeführt werden. Ich habe ein paar unterschiedliche Varianten ausprobiert, nicht nachgemessen aber einen Unterschied gespürt. Daraus ergab sich für mich, dass man hier optimieren sollte - ist vom Aufwand gegenüber dem restlichen Programm über auch recht vertretbar. Die anderen Teile werde ich aber ebenfalls noch versuchen so weit wie möglich zu optimieren. Der eigentliche Algorithmus ist sehr simpel, wird nur auf einer großen Datenmenge ausgeführt, daher besteht das Programm fast nur aus "Mikro"optimierungen.

Es gibt zwei Anwendungsfälle, einmal enthält die Matrix 21*66 Elemente und einmal 21*66^2. 21*66^3 ist unwahrscheinlich, weil es zu groß wird. Die beiden Fälle würde ich optimierungstechnisch gerne erschlagen, im Zweifelsfall ist 21*66 aber interessanter.

Das sind dann noch nicht viele Iterationen, aber diese 21*66 Iterationen werden wiederum 20-50 Mal ausgeführt. Und im inneren der Schleife iteriere ich wiederum über dieselbe Matrix, also eigentlich (21*66)^2 (aber ich bin gerade dran, die Anzahl innerer Iterationen auch noch zu verbessern).

Das Matrixdesign bin ich bereit komplett für die Optimierung anzupassen. Zurzeit habe ich einen lineareneindimensionalen Vektor und X1,X2,X3 ist die Reihenfolge der Dimensionen. Was gibt es zum Speicherlayout noch zu wissen? Ich nutze MSVC12 und dessen STL-Vektor-Implementierung.

volkard:
Ungefähr 50%, ja.

Wenn ich es so wie du beschrieben mache, muss ich halt den Index innerhalb der Schleife jedes Mal berechnen, um auf das Objekt zuzugreifen. In einem anderen Thread, wo die pyramidale Anforderung noch nicht gegeben war, sprach sich Shade of Mine dafür aus von 0 bis N zu iterieren statt mehrere Schleifen zu nutzen: http://www.c-plusplus.net/forum/p2371119#2371119

Kann natürlich sein, dass ich da zu wenige Infos geliefert habe.

[volkard]

Eisflamme schrieb:

Wenn ich es so wie du beschrieben mache, muss ich halt den Index innerhalb der Schleife jedes Mal berechnen, um auf das Objekt zuzugreifen.

Nicht unbedingt.

for(int x1=0;x1<=10;++x1)
   for(int x2=0;x2<=20;++x2)
      for(int x3=0;x1+x3<=10;++x3)	
         tuwas(vec[x1][x2][x3]);

for(int x1=0;x1<=10;++x1)
   for(int x2=0;x2<=20;++x2){
      auto& zeile=vec[x1][x2];
      for(int x3=0;x1+x3<=10;++x3)	
         tuwas(zeile[x3]);
   }

Aber mir scheint, das Speicherlayout der Matrix bestimmt hier alles und das kenne ich nicht.

[Eisflamme]

Ich wiederhole die Frage Mal: Was gehört zum Speicherlayout der Matrix, was ich nicht beschrieben habe? Kann man das überhaupt wissen?

[noobexplainer]

Eisflamme schrieb:

Ich wiederhole die Frage Mal: Was gehört zum Speicherlayout der Matrix, was ich nicht beschrieben habe? Kann man das überhaupt wissen?

um die Pyramide zu speichern? Das ist grottenlahm.

Hast du ein vector<vector<vector<int>>> hast um die Pyramide zu speichern? Das ist noch grottiger.

Pyramiden speichert man in einem vector<int>.
Wenn ich auf x,y,z zugreifen will, berechnet man halt z*z + y*y_max + x (oder so, habs jetzt nicht genauer überlegt).

Der Iterator geht dann einfach von vector.begin() nach vector.end(). Das ist am schnellsten. Nicht, weil it++ so billig zu berechnen ist, sondern weil das perfect im Speicher liegt und ohne Cache-Misses drauf zugegriffen werden kann.

[Eisflamme]

Ich ging davon aus, dass das aus meinem Text hervorging, aber scheint doch nicht so klar:

vector<int> matrix;

ist so abgelegt. Aber, wie schon gesagt, ändere ich mein Speicherlayout gerne so, dass es optimal ist. Soweit ich das Speicherlayout beeinflussen kann jedenfalls. Die Reihenfolge der Dimensionen ist gerade wie gesagt X1,X2,X3 mit X3 am granularsten, d.h. über X3 kann man via +1 iterieren, das X2-Offset für den Index erhält man durch Multiplikation mit der möglichen Anzahl von X3, X1-Offset durch entsprechend größeren Multiplikator...

Werde ich aber dann so ändern wie es Werner Salomon vorgeschlagen hat, d.h. Reihenfolge zu X1,X3,X2 ändern.

[volkard]

Eisflamme schrieb:

Ich wiederhole die Frage Mal: Was gehört zum Speicherlayout der Matrix, was ich nicht beschrieben habe? Kann man das überhaupt wissen?

Werden die nichtbenötigten Plätze gespeichert oder nicht? Falls nicht, wie wird der Zugriff gemacht, Hashtable über Indextripel vielleicht? Werden alle nichtbenötigten Plätze gestrichen oder für mehr Performance eine Hybridform gewählt, wie könnte die aussehen? Sind die Indizes x1, x2, x3 sorum da oder lieber x2, x1, x3? Werden x1 und x3 zu einem n=66-(11-x1)*(12-x1)/2+x3 verrechnet? Soll die ganze x1-x3-Schleife, sind ja bloß 66 Durchläufe, normalerweise ausgerollt werden, dann darf die Index-Berechnung auch hübsch teuer sein, passiert ja zur Compilezeit. Warum der Versuch, aus n wieder x1 und x3 zu berechnen, andersrum ist doch viel einfacher. Und was soll überhaupt damit gemacht werden? Iterieren sagste. Wenn dabei x1, x2 und x3 gebraucht werden für eine Rechnung, dann bezweifle ich doch mal stark, daß der Indexzugriff das Teure ist. Noch weiter innere Schleifen voller Plutimikationen? Dann ist der Zugriff egal.

[Eisflamme]

Werden die nichtbenötigten Plätze gespeichert oder nicht?

Also das geht aber aus meinem OP alles hervor. Da sage ich ja genau, dass weniger gespeichert werden muss, eben 21*66. Und ich beschreibe auch genau, wie ich basierend auf der Zählvariable dann x1,x2,x3 bestimme. Also ja, es werden nur die benötigten Plätze gespeichert.

Sind die Indizes x1, x2, x3 sorum da oder lieber x2, x1, x3?

Siehe mein letzter Post, aber ich habe nun wirklich auch davor schon deutlich gesagt, dass X1,X2,X3 die Reihenfolge ist.

Werden x1 und x3 zu einem n=66-(10-x1)*(11-x1)/2+x3 verrechnet? Warum der Versuch, aus n wieder x1 und x3 zu berechnen?

Ich hab doch explizit dir bereits beantwortet, dass und warum ich von 0 bis N iteriere statt drei einzelne Schleifen zu nutzen: http://www.c-plusplus.net/forum/p2375528#2375528

Und was soll überhaupt damit gemacht werden? Iterieren sagste. Wenn dabei x1, x2 und x3 gebraucht werden für eine Rechnung, dann bezweifle ich doch mal stark, daß der Indexzugriff das Teure ist.

Damit werden Berechnungen angestellt, genau. Aber die sind auch recht trivial, deswegen werden die ebenfalls ziemlich stark optimiert. Teilweise steck ich die sogar in Lookup-Tables, soweit es geht, aber das ist auch schon ne echt feine Optimierung.

[knivil]

Ganz ehrlich: Ich glaube kaum, dass das Optimieren des Iterationsschema signifikante Verbesserungen bringt, jedenfalls nicht bei 1386 ints. Ausnahme: Man hat sich vorher dumm angestellt.

Desweiteren: Alles hier geschriebene ist Laber-Rhabarber. Nur Messwerte zaehlen.

[volkard]

Eisflamme schrieb:

Werden die nichtbenötigten Plätze gespeichert oder nicht?

Also das geht aber aus meinem OP alles hervor. Da sage ich ja genau, dass weniger gespeichert werden muss, eben 21*66. Und ich beschreibe auch genau, wie ich basierend auf der Zählvariable dann x1,x2,x3 bestimme. Also ja, es werden nur die benötigten Plätze gespeichert.

Sind die Indizes x1, x2, x3 sorum da oder lieber x2, x1, x3?

Siehe mein letzter Post, aber ich habe nun wirklich auch davor schon deutlich gesagt, dass X1,X2,X3 die Reihenfolge ist.

Werden x1 und x3 zu einem n=66-(10-x1)*(11-x1)/2+x3 verrechnet? Warum der Versuch, aus n wieder x1 und x3 zu berechnen?

Ich hab doch explizit dir bereits beantwortet, dass und warum ich von 0 bis N iteriere statt drei einzelne Schleifen zu nutzen: http://www.c-plusplus.net/forum/p2375528#2375528

Und was soll überhaupt damit gemacht werden? Iterieren sagste. Wenn dabei x1, x2 und x3 gebraucht werden für eine Rechnung, dann bezweifle ich doch mal stark, daß der Indexzugriff das Teure ist.

Damit werden Berechnungen angestellt, genau. Aber die sind auch recht trivial, deswegen werden die ebenfalls ziemlich stark optimiert. Teilweise steck ich die sogar in Lookup-Tables, soweit es geht, aber das ist auch schon ne echt feine Optimierung.

lol

[Eisflamme]

jedenfalls nicht bei 1386 ints

Ich habe schon ausführlich beschrieben, dass die nicht einmal iteriert werden.

Und wenn ich spürbar zwischen zwei Verfahren einen Unterschied merke, brauche ich nicht messen.

Nach Umsetzung Werners Lösung läuft es schneller. Dankeschön dafür. Was der Rest vom Schützenfest hier wieder fürn Problem hat, weiß ich nicht.

volkard:
?