Polydimensionales Array in Monodimensionales

  • C#
  • .NET (FX) 4.5–4.8

Es gibt 13 Antworten in diesem Thema. Der letzte Beitrag () ist von φConst.

    Polydimensionales Array in Monodimensionales

    Guten Abend,
    ich versuche ein drei dimensionales Array in ein ein-dimensionales Array zu konvertieren.

    Problematisch ist jedoch dass ich drei Index-Formeln habe.
    Dieser ist bedingt dadurch, wie ich das drei dimensionale Array fülle. (Reihenfolge der For-Schleife : Erst X, dann Y, abschließend Z, oder Y, X, Z, et cetera)

    C#-Quellcode

    1. Func<int, int, int, int> getFirstX = (int x, int y, int z) =>
    2. {
    3. return z * HEIGHT + y + x * HEIGHT * DEPTH;
    4. };
    5. Func<int, int, int, int> getFirstY = (int x, int y, int z) =>
    6. {
    7. return z + y * WIDTH * DEPTH + x * DEPTH;
    8. };
    9. Func<int, int, int, int> getFirstZ = (int x, int y, int z) =>
    10. {
    11. return z * WIDTH * HEIGHT + y * WIDTH + x;
    12. };


    Das 3d-Array fülle ich folgendergestalt:

    C#-Quellcode

    1. int[, ,] b = new int[5, 6, 7];
    2. int WIDTH = 5;
    3. int HEIGHT = 6;
    4. int DEPTH = 7;
    5. int counter3d = 0;
    6. for (int z = 0; z < b.GetLength(2); z++)
    7. {
    8. for (int y = 0; y < b.GetLength(1); y++)
    9. {
    10. for (int x = 0; x < b.GetLength(0); x++)
    11. {
    12. b[x, y, z] = counter3d++;
    13. }
    14. }
    15. }



    Um auf den 1D-Index zuzugreifen wird hierfür die Methode getFirstZ gebraucht ( denn zuerst wird X, dann Y, dann Z iteriert.)

    Gibt es eine allgemeine Form?
    Scheint es ja, denn das .NET Framework kann immer korrekt auf den Index zugreifen.(Wenn ich mich recht entsinne konvertiert CSharp ein polydimensionales Array immer in ein ein Dimensionales).

    Liebe Grüße.
    Und Gott alleine weiß alles am allerbesten und besser.
    Die Reihenfolge ist grundsätzlich egal, du musst dich nur für eine feste Entscheiden. Dann kannst du auch eine der Formeln nehmen.
    Ich verwende z.B. immer

    Quellcode

    1. z*WIDTH*HEIGHT+y*WIDTH+x


    Aber der Hauptunterschied dabei liegt darin, wenn du dein Array dann mit den drei schleifen durchläufst, dass du den index nicht mittels Multiplikationen sondern eines einfachen Increments hinbekommst:

    C#-Quellcode

    1. for (int z=0;z<DEPTH;z++)
    2. {
    3. for(int y=0;y<HEIGHT;y++)
    4. {
    5. for (int x=0;x<WIDTH;x++,index++)
    6. {
    7. }
    8. }
    9. }

    Dann ist keine multiplikation nötig, noch besser ist das ganze natürlich, wenn du weder x/y noch z benötigst, dann kannst du einfache eine einzige Schleife verwenden.
    Ich wollte auch mal ne total überflüssige Signatur:
    ---Leer---
    Danke vielmals für Eure Antworten.

    jvbsl schrieb:

    dass du den index nicht mittels Multiplikationen sondern eines einfachen Increments hinbekommst

    Das ist richtig, nur muss ich ja trotzdem dann mit der Index-Formel auf die Elemente des 1D-Arrays zugreifen können.

    ~blaze~ schrieb:

    verwende doch unsafe und Zeiger für das Problem


    Mit Zeigern habe ich selten gearbeitet.

    ~blaze~ schrieb:

    Verwende direkt nur 1D-Arrays und wrappe diese in einer Struktur


    Das klingt interessant.
    Meinst du etwa marshallen?
    Und Gott alleine weiß alles am allerbesten und besser.
    Hallo,
    ja du hast ja recht, eben darin liegt ja das Problem.
    Ich muss mich dann für eines der Index-Formeln entscheiden.

    Für die Index-Formel ,

    Quellcode

    1. z * WIDTH * HEIGHT + y * WIDTH + x
    iterierst du als letztes Z.
    Wenn jedoch Z als erstes iteriert wird, funktioniert nicht diese Index Formel und man muss eine andere nutzen.
    Und ich habe mich gefragt ob es eine universelle gibt.
    Und Gott alleine weiß alles am allerbesten und besser.

    C#-Quellcode

    1. for (int z=0;z<DEPTH;z++)
    2. {
    3. for(int y=0;y<HEIGHT;y++)
    4. {
    5. for (int x=0;x<WIDTH;x++,index++)
    6. {
    7. int index2 = z*WIDTH*HEIGHT+y*WIDTH+x;
    8. if (index2 != index)
    9. Console.WriteLine(index.ToString() + ";" + index2.ToString());
    10. }
    11. }
    12. }

    Dabei dürftest du keine Konsolenausgabe bekommen. Also stimmt die Formel mit dieser Iterationsreihenfolge überein.

    Oder ich verstehe nicht so ganz was dein Problem ist :D
    Ich wollte auch mal ne total überflüssige Signatur:
    ---Leer---

    C#-Quellcode

    1. int index = 0;
    2. for (int z = 0; z < DEPTH; z++)
    3. {
    4. for (int y = 0; y < HEIGHT; y++)
    5. {
    6. for (int x = 0; x < WIDTH; x++, index++)
    7. {
    8. int index2 = z * WIDTH * HEIGHT + y * WIDTH + x;
    9. if (index2 != index)
    10. Console.WriteLine(index.ToString() + ";" + index2.ToString());
    11. }
    12. }
    13. }


    Und das mach mal für

    C#-Quellcode

    1. int index = 0;
    2. for (int y = 0; y < HEIGHT; y++)
    3. {
    4. for (int z = 0; z < DEPTH; z++)
    5. {
    6. for (int x = 0; x < WIDTH; x++, index++)
    7. {
    8. int index2 = z * WIDTH * HEIGHT + y * WIDTH + x;
    9. if (index2 != index)
    10. Console.WriteLine(index.ToString() + ";" + index2.ToString());
    11. }
    12. }
    13. }
    Und Gott alleine weiß alles am allerbesten und besser.
    ja da kann man tatsächlich etwas machen, mit mehreren Variablen und zurücksetzen und was der Geier, oder einfach der "Formel"

    Die Frage ist eher, wann sollte es einen Grund dafür geben, dass die Schleifenreiheinfolge genau so fest sein muss?
    Ich wollte auch mal ne total überflüssige Signatur:
    ---Leer---
    "Die Frage ist eher, wann sollte es einen Grund dafür geben, dass die Schleifenreiheinfolge genau so fest sein muss?"
    richtig, nie.
    Deswegen suchte ich nach einer universellen Formel.
    Aber naja, dann muss die Reihenfolge fixiert sein.
    Und Gott alleine weiß alles am allerbesten und besser.
    Ums mal mit Zeigern zu demonstrieren: Entsprechendes Unsafe-Flag in den Projekt-Einstellungen setzen, danach könnte das z.B. so aussehen.

    C#-Quellcode

    1. int[...] values;
    2. int[] target = new int[values.Length];
    3. unsafe
    4. {
    5. fixed(int* srch = values)
    6. fixed(int* dsth = target)
    7. {
    8. int* srcend = srch + values.Length;
    9. int dst = dsth;
    10. for(int* src = srch; src < srcend; src++, dst++)
    11. *dsth = *src;
    12. }
    13. }

    Oder aber über Marshal:

    C#-Quellcode

    1. int[...] values;
    2. int[] target = new int[values.Length];
    3. unsafe
    4. {
    5. fixed(int* srch = values)
    6. {
    7. System.Runtime.InteropServices.Marshal.Copy(srch, target, 0, values.Length);
    8. }
    9. }


    Alternativ wäre der Zugriff auf ein direkt eindimensionales Array recht einfach:
    Du erzeugst ein Array mit Width * Height * Depth Elementen. Der Index i der Position (x, y, z) wird dann durch
    i = x + Width * y + Width * Height * z
    ermittelt.

    I.A. ist es sinnvoll, Daten in einem Rutsch zu kopieren, d.h. mein Programmbeispiel z.B. ist nicht unbedingt so optimal, sofern der JITC es nicht auf die modernsten Prozessoren abstimmt. Bspw. Vektoroperationen können vermutlich einiges an Performance herausschlagen, d.h. es wäre eine Überlegung wert, direkt Marshal.Copy zu verwenden, was hoffentlich einiges an Performance rausholt.
    Zudem ist es sinnvoll, Daten in der Reihenfolge anzusprechen, in der sie im Speicher stehen. Afaik wird in den CPU Caches ein Speicherblock, d.h. aufeinanderfolgende Daten, gepuffert, auf den der Zugriff dann effizient stattfindet. Bei zu vielen Sprüngen durch den Speicher, wie bei nicht-sequentiellen Speicheraufrufen, dürfte das daher, so meine Vermutung, weniger effizient sein. Wie das mit Compileroptimierung und CPU-Optimierung aussieht, weiß ich aber nicht.

    Das mit der Schleifenreihenfolge habe ich übrigens nicht berücksichtigt. Für ein effizientes System wäre es wohl die beste Lösung, eine Methode für jeden Case zu haben.

    Viele Grüße
    ~blaze~

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „~blaze~“ ()

    Na wie dem auch sei, habe mich einfach dafür entschieden

    C#-Quellcode

    1. private int From3Dto1D(int x, int y, int z)
    2. {
    3. return z * Height + y + x * Height * Depth; ;
    4. }
    5. private int From4Dto1D(int x, int y, int z, int slot)
    6. {
    7. return slot + Height * 12 * z + y * 12 + x * Height * 12 * Depth;
    8. }


    klappt perfekt ^^+.


    Hat mit meiner eingangs erwähnten Fragen nichts zu tun:

    Habe mich entschieden Listen zu verwenden für das Hinzufügen von Vertices, weil Arrays einfach arge Redundanzen generieren.
    Nämlich diese, dass ich für einen Chunk (16x16x256) jeweils zwei eindimensionale Arrays generieren muss.

    Eines dieser zwei Array muss jedoch quasi vierdimensional sein, also WIDTH * DEPTH * HEIGHT * K.

    Denn ein Vertex kann jeweils von K = 12 anderen Triangles gebraucht werden.

    Bei 16x16x256 sind das immerhin 786432 Vertices und gar 393216 Indices ...
    Mit Listen werden jedoch aber nur die Vertices hinzugefügt die auch gebraucht werden.

    Einziges Problem: 10 Sekunden ( noch immer besser als mit Arrays , OutOfMemoryException und PC-Crash).
    Was ist die effizienteste Variante um ein solches Problem zu lösen?
    Und Gott alleine weiß alles am allerbesten und besser.

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „φConst“ ()