Optimales Array für Datensatz

Shor-ty

Hallo zusammen,

danke für eure Antworten. Ich hab das mal kurz, schlicht und simple hier dargestellt: http://www.holzmann-cfd.de/cppForum/Extraction.pdf

Also ich habe wirklich eine vier-dimensionales Array und ich mach auch eine 4d-Interpolation. Jedoch macht das mit der Struct wesentlich mehr Sinn und scheint einfacher zu sein.

Shor-ty

Wie die Sturktur gerade ist:

[code]

├── LUT0
│   ├── LookUpTable.out
│   ├── SR_10.bin
│   ├── SR_11.bin
│   ├── SR_12.bin
│   ├── SR_13.bin
│   ├── SR_14.bin
│   ├── SR_15.bin
│   ├── SR_16.bin
│   ├── SR_17.bin
│   ├── SR_18.bin
│   ├── SR_1.bin
│   ├── SR_2.bin
│   ├── SR_3.bin
│   ├── SR_4.bin
│   ├── SR_5.bin
│   ├── SR_6.bin
│   ├── SR_7.bin
│   ├── SR_8.bin
│   └── SR_9.bin
├── LUT-100
│   ├── LookUpTable.out
│   ├── SR_10.bin
│   ├── SR_11.bin
│   ├── SR_12.bin
│   ├── SR_13.bin
│   ├── SR_14.bin
│   ├── SR_15.bin
│   ├── SR_16.bin
│   ├── SR_17.bin
│   ├── SR_18.bin
│   ├── SR_1.bin
│   ├── SR_2.bin
│   ├── SR_3.bin
│   ├── SR_4.bin
│   ├── SR_5.bin
│   ├── SR_6.bin
│   ├── SR_7.bin
│   ├── SR_8.bin
│   └── SR_9.bin
└── LUT+100
├── LookUpTable.out
├── SR_10.bin
├── SR_11.bin
├── SR_12.bin
├── SR_13.bin
├── SR_14.bin
├── SR_15.bin
├── SR_16.bin
├── SR_17.bin
├── SR_18.bin
├── SR_1.bin
├── SR_2.bin
├── SR_3.bin
├── SR_4.bin
├── SR_5.bin
├── SR_6.bin
├── SR_7.bin
├── SR_8.bin
└── SR_9.bin
[/code]

LUT -> $\zeta_x$
SR_x -> $\chi_x$
und in den Dateien ist dann jede Größe $\phi = f(Z,Zvar)$

mgaeckler

Nach dem Bild in deinem pdf schätze ich, daß eine map wohl ne gute Lösung wäre.

Mfg Martin

Shor-ty

Hallo Martin,

also mit dem vector<vector<vector<vector<double> > > > funktioniert es ja, wollte aber mal nachfragen ob es eine schönere Lösung gibt. Ich schau mir das mit der "map" mal an. Dankeschön für das Feedback.

SeppJ

Ist das eine gute Idee, die Werte überhaupt zu speichern? Wenn du interpolieren willst, brauchst du schließlich nicht alle Werte gleichzeitig, sondern bloß ein paar Nachbarn. Deren Werte berechnest du, machst, was auch immer du mit diesen Werten machen möchtest, und merkst dir am Ende ein paar der Werte am Rand. Dann berechnest du die Werte von deren Nachbarn. Und so weiter.

hustbaer

@Shor-ty
Möglichkeiten gibt es viele.
Um hier die "optimale" zu finden, müsste man wissen wie auf die Daten zugegriffen werden soll.
Also z.B. wie viele Lookups du machst, und ob es Muster gibt - also z.B. ob sich die "Koordinaten" der Zugriffe von einem zum nächsten nach einem bestimmten Schema ändern.

Bzw. genau so ob die Sample-Abstände der einzelnen Dimensionen immer gleich sind. Also ob der Abstand auf der "Zvar" Achse zwischen zwei Samples immer 0.1 ist.
Dann müsste man die Parameter nämlich z.B. überhaupt nicht speichern, bzw. nur die Parameter für das Sample (0,0,0,0) + halt die Deltas für die 4 Parameter.

Und auch: auf was genau willst du optimieren? Auf einfach & übersichtlich, oder auf schnelle Zugriffe?
(Falls auf einfach & übersichtlich entfällt natürlich die Frage nach dem Zugriffsmuster oben)

Shor-ty

Hallo,

danke für deine Antwort. Zu deinen Fragen. Wir bewegen uns in der numerischen Strömungsmechanik, bei der je nach Problemstellung und Design mehrere Millionen Zellen vorhanden sein können. Für jede Zelle wird bei jedem Zeitschritt über Erhaltungsgleichungen (Transportgleichungen) der Wert von

Z
Zvar
Zeta
Chi

geändert. Diese Werte sind willkürlich (natürlich mit Beschränktheiten wie bspw. Z und Zvar definiert zwischen [0:1] wobei alle Werte vorkommen. Mit diesen Werten extrahiere ich dann thermodynamische Eigenschaften, die ich vorher Berechnet habe (das Modell ist bereits vorliegend, jedoch nicht sauber implementiert).

Die thermodynamischen Eigenschaften sind natürlich nur an diskteten Stellen vorhanden. Für jede Zelle muss dann ein Interpolationsverfahren durchgeführt werde. Somit muss sehr häufig auf dieses Array zugegriffen werden. Wenn es interessiert kann nachfolgend die Interpolationshierarchie einsehen: http://www.holzmann-cfd.de/images/openfoam/softwareentwicklung/flameletModell/Extraktionsverfahren.png

Soweit dazu.
Anzumerken ist, dass dieses Modell (auch wenn mit vielen Zugriffen auf die Thermodynamischen Datenbanken) bereits um ein vielfaches schneller ist als normale Modelle. Ist nämlich ein Verbrennugnsmodell und die komplexen chemischen Gleichungen zu berechnen kostet wesentlich mehr als mit den Tabellen.

Die Abstände sind nicht einheitlich (sondern nur in meinem Beispiel fiktiv angenommen). Bspw. kann sich die Z Achse [0:1] wie folgt verhalten:

.       .     .     .  .  . ... . . .    .    .      .       .      .

Hier soll der Abstand der Punkte die Intervallgröße darstellen (nur zur Vorstellung).

Zu Beginn möchte ich sehr sauber und übersichtlich Programmieren, dass ggf. im späteren Verlauf mit einer Optimierung versehen wird (aus reinem Interesse und wenn mir die Zeit dazu bleibt).

Zudem möchte ich so viel wie möglich von der namespace FOAM verwenden, da ich bei den Programmierern anfragen möchte, ob dieses Modell als offizielles Modell implementiert wird.

Hoffe deine Fragen beantwortet zu haben.

hustbaer

Die Abstände sind nicht einheitlich (sondern nur in meinem Beispiel fiktiv angenommen). Bspw. kann sich die Z Achse [0:1] wie folgt verhalten: (...)

OK. Verstanden soweit. Das führt zur nächsten Frage:
Liegen die Samples auf einem "rechtwinkeligen" Grid, wobei jeder Grid-Punkt auch "ausgefüllt" ist?
(Weiss nicht wie ich das anders beschreiben soll, mir fehlen da die nötigen mathematischen/physikalischen Fachausdrücke)

Also...
Wenn es einen Punkt mit Z = 0.1 gibt, und einen anderen Punkt mit Chi = 42, gibt es dann auch immer einen Punkt mit Z = 0.1 und Chi = 42? Und das für alle möglichen Werte aller vier Parameter? (Anhand deines PDFs vermute ich mal: ja, gibt es.)
Bzw. man könnte das auch einfach als 4-dimensionalen "Daten-Cube" bezeichnen.

Oder ist es eine komplett freie Punktwolke?

Grund der Frage: wenn ich dich richtig verstanden habe, dann willst (musst) du zu einem Koordinaten-Quadruple die nächstgelegenen 4 Samples finden. Und das bei mehreren Millionen einträgen und sehr sehr oft.

Wenn man das für eine "komplett freie Punktwolke" straight-forward implementiert, dann ist das reichlich langsam. Dazu müsstest du nämlich die Distanz jedes Samples zum gegebenen Koordinaten-Quadruple berechnen (für alle Samples!), und dann die vier Samples mit dem kleinsten Abstand raussuchen. Das wäre O(N). Und das für jedes Koordinaten-Quadruple. Also sehr sehr oft. Also sehr sehr langsam.

Um sowas schnell zu bekommen bräuchtest du nen "spatial index" - also z.B. nen Octree (bzw. bei dir dann 16-Tree).

Wenn es aber ist wie ich vermute, dann wäre mMn. eine gute Darstellung im Speicher:

vector<double> z_values;      // Werte entlang der Z-Achse des Cubes (sortiert)
vector<double> zvar_values;   // Werte entlang der Zvar-Achse des Cubes (sortiert)
vector<double> zeta_values;   // Werte entlang der Zeta-Achse des Cubes (sortiert)
vector<double> chi_values;    // Werte entlang der Chi-Achse des Cubes (sortiert)
vector<double> values;        // Samples im Cube

values würde dabei dann z_values.size() * zvar_values.size() * zeta_values.size() * chi_values.size() Einträge enthalten.

Den Messwert zu z_values[A] , zvar_values[B] , zeta_values[C] und chi_values[D] legst du dann unter index = A + (B * z_values.size()) + (C * z_values.size() * zvar_values.size()) + (D * z_values.size() * zvar_values.size() * zeta_values.size()) ab.

Das ist halbwegs einfach und spart Speicher.

Zum Raussuchen eines Werts würdest du über ne binäre Suche erstmal die z_values Indexe der beiden benachbarten Z-Werte raussuchen,
dann die zvar_values Indexe der beiden benachbarten Zvar Werte, und das selbe für Zeta und Chi.
Dann hast du 8 Indexe mit denen du dir die 16 Nachbarn aus dem values Vektor rausholen kannst.

Also im Prinzip sehr ähnlich zu deiner vector<vector<vector<vector<double> > > > Variante. Nur halt mit einem einzigen nicht verschachtelten vector . Weil verschachtelte Vektoren pfui sind (und auch ein Stück langsamer als die von mir skizzierte Variante)

@manni66
Ist ne 4-Dimensionale Tabelle. Nicht Tabelle im Sinn von Datenbank-Tabelle, sondern im Sinn von ... naja, "Tabelle" halt

@mgaeckler
Wieso ne map?
Wie willst du darin vernünftig nen Lookup machen?

Shor-ty

Hey,

also so wie ich dich verstanden habe, läuft es eigentlich fast schon so hinaus, wie ich da gerade dabei bin das zu implementieren. Es ist halt immer etwas schwer sich das vorzustellen 4d - Raum (für andere). Da ich darin schon länger arbeite ist das klar. Wenn es interessiert: Die Z und Zvar spannen eine Oberfläche im 3D - Raum auf. Somit gilt:
$\phi = f(Z,Zvar)$
Stichwort hier ist eine $\beta$ -PDF. Chi ist zusammenhängend über eine Log-Normal-PDF und Zeta eine Delta Function (nur wen es interessiert).

"Grob" gesagt sieht das wie folgt aus: http://www.holzmann-cfd.de/images/openfoam/softwareentwicklung/flameletModell/Interpolationsverfahren.png.

Z definiert [0:1]
Zvar definiert [0:0,25] bzw. normiert auch [0:1]
Chi definiert [0: $\infty$ ]
zeta definiert [ $-\infty$ : $\infty$ ]

Zurück zum eigentlichen Thema
Also dein Vorschlag ähnelt meinem mit dem "vector<vector<vector<vector<double> > > >", also war das von mir schon mal gar kein » soo « schlechter Ansatz. Ich werde mir morgen das von dir nochmals durchsehen, da es jetzt schon etwas spät geworden ist und ich nicht mehr wirklich aufnahmefähig bin

Grüße Tobi

mgaeckler

hustbear schrieb:

@mgaeckler Wieso ne map? Wie willst du darin vernünftig nen Lookup machen?

Ich habe die grafik in der pdf so verstanden, dass zu jeden Messwert n Messwerte der Spalte rechts daneben ist. Das kann mit einer map modeliert werden. Key ist double und die werte sind vector. Darfst halt kein unorderd map nehmen. Sonnst wirds langsam.

Map <double, vector < map < double ...

Mfg Martin