Arrayliste mit Arrayliste realisieren

[kodela]

Hallo,
um die Zellen eines zweidimensionalen Feldes (Str8ts) mit 9 Zeilen und 9 Spalten möglichst effizient ansprechen zu können, suche ich nach einer besseren Lösung.

Derzeit verwende ich für die Auswertung von Zeilen und Spalten folgende Konstruktion:

    for (int r = 0; r < 18; r++) {          
        int z = r;
        // zuerst die die 9 Zeilen, dann die Spalten
        for (int h = 0; h < 9; h++) {
            int s = h;
            if (r >= 9) {
                s = z - 9;
                z = s;
            }
            // hier kann auf einzelne Zellen einer
            // Reihe (Zeile oder Spalte) zugegriffen werden
        }
        // hier "kennt" man alle Werte der Reihe
        // und kann eine Auswertung vornehmen
    }

Statt dessen möchte ich eine Liste mit 18 Einträgen erstellen, für jede Reihe, also Zeile und Spalte, einen Eintrag, welcher selbst wiederum eine Liste mit 9 Punkt Objekten darstellt.

Ich könnte natürlich Zeilen und Spalten getrennt behandeln und damit den Zugriff vereinfachen. Das würde aber bedeuten, dass der relativ umfangreiche Code für die Auswertung doppelt geschrieben werden muss, was ich nicht besonders gut finde.

Im Endeffekt hätte ich gerne die beiden Koordinaten für jede Zelle einer Reihe in einer Array-Liste mit neun Punkten und alle 18 dieser Listen in einer weiteren Array-Liste.

Kennt sich hier jemand mit solchen Listen aus und kann mir beim Erstellen meines Vorhabens behilflich sein. Ich sage auf jeden Fall schon einmal Danke.

MfG, kodela

 

[mrBrown]

Ehrlich gesagt ist mir noch nicht ganz klar, was du eigentlich suchst.

Du hast ein 9*9 Feld, und möchtest effizient auf alle Spalten- und Zeilen-Werte zugreifen?

Dann würde ich einfach bei einem 9*9 Array (uU als 81*1 Array) bleiben und ein passendes Interface drüber legen, was entsprechend abstrahierte Methoden mit passenden Parametern und Rückgabetype liefert.

Warum man stattdessen eine 18*9-Liste nutzen sollte, erschließt sich mir noch nicht ganz - das dürfte sowohl Speicher als auch Laufzeittechnisch ineffizienter sein. (Und ganz generell finde ich List<List<...>> grausam)

 

[kodela]

Hallo mrBrown,

ja, es ist schon so, wie Du schreibst. Bei bestimmten immer nach dem selben Schema ablaufenden Auswertungen der 18 Reihen möchte ich Zeilen und Spalten gleich behandeln können. Wenn zum Beispiel die erste Zeile in Bearbeitung ist, dann bleibt die X-Koordinate für alle Zellen der Zeile gleich, es ändert sich nur die Koordinate für die Spalten. Bei der Bearbeitung einer Spalte bleibt dagegen die Koordinate für die Spalte gleich und die für die Zeile muss incrementiert werden. Ich müsste für Zeilen und Spalten einen eigenen Code schreiben.

Will man das vermeiden, müssen die Koordinaten entweder umgerechnet oder in einer Liste für jede Reihe vorgehalten werden, aus der sie problemlos abgerufen werden können. Bei Str8ts ist das Umrechnen noch relativ einfach, da gibt es neben den Straßen, die sowieso anders behandelt werden müssen, nur Zeilen und Spalten. Bei Sudokus kommen noch die Blöcke hinzu. Da die berechnende Festlegeung der Koordinaten für Blöcke doch sehr umständlich ist, verwende ich dafür ein zweidimensionales Integerarray mit allen Koordinaten für alle Zeilen, Spalten und Blöcke. Das lässt sich sehr einfach realisieren, da bei Sudokus das Feld als 81*1 Array geführt wird, für jede Zelle also auch nur eine Koordinate benötigt wird. Bei Str8ts arbeite ich mit gemischten Feldern, je was im Einzelfall günstiger ist.

Was meinst Du mit "ein passendes Interface drüber legen"?

MfG, kodela

 

[kodela]

Hallo,

vielleicht kann ich mein Vorhaben mit folgendem kleinen Codeschnipsel etwas konkretisieren:

    for (int i = 0; i < 9; i++) {
        int zelle = ZELLNDX[b][i];
        if ((sudoku[zelle] & mGruppe) > 0) {
            // tu etwas
        }
        // tu auch hier etwas
    }

Es stammt aus meinem Sudoku Programm, ist eingebettet in einer for-Schleife mit der Variable b für alle 27 Bereiche, 9 Zeilen, 9 Spalten und 9 Blöcke, und überprüft für jeden dieser Bereiche, ob eine bestimmte Konstellation gegeben ist, die ausgewertet werden kann. In dem zweidimensionalen Array ZELLNDX[27][9] sind für alle 27 Bereiche die Indizien für jede Zelle eines jeden Bereiches gespeichert. Damit kann von diesem Codeschnipsel ohne besondere bereichsbezogene Anpassung jeder Bereich, egal ob Zeile, Spalte oder Block, bearbeitet werden.

Bei meinem Str8ts Programm möchte ich für eine Klasse im Prinzip in gleicher Weise vorgehen. Das Problem: In meinem Str8ts Programm werdem zwar alle lösungsbezogenen Auswertungen fast ausschließlich über ein eindimensionales Feld-Array vorgenommen. Für eine Klasse wird das eindimensionale Feld-Array jedoch in ein zweidimensionales konvertiert.

Die Gründe dafür waren für mich gewichtig. Bei Sudokus sind ausschließlich Bereiche mit der selben Größe und den selben Bedingungen auszuwerten, jeder Bereich jat neun Zellen und in jedem gelösten Bereich müsse die Ziffern 1 bis 9 vertreten sein. Dies ist bei Str8ts ganz anders, daher unterscheidet sich das Vorgehen beim Auswerten der Bereiche, meistens Straßen und nur in wenigen Fällen Zeilen und Spalten. Für die Auswertung der Straßen bringt ein zweidimensionales Feld-Array deutliche Vorteile gegenüber einem eindimensionalen. Das Problem bei der Auswertung der Reihen habe ich in Kauf genommen, suche aber nun eine Möglichkeit, wie ich auch dafür mit ein und dem selben Code die Auswertung für Zeilen und Spalten vornehmen kann.

MfG, kodela

 

[Meniskusschaden]

Für die Auswertung der Straßen bringt ein zweidimensionales Feld-Array deutliche Vorteile gegenüber einem eindimensionalen. Das Problem bei der Auswertung der Reihen habe ich in Kauf genommen, suche aber nun eine Möglichkeit, wie ich auch dafür mit ein und dem selben Code die Auswertung für Zeilen und Spalten vornehmen kann.

Bin ehrlich gesagt nicht sicher, ob ich deine Anforderungen richtig verstanden habe, aber wenn du es analog zu deinem Sudoku-Beispiel machen willst, müsstest du in deinem Index-Array doch eigentlich nur eine Dimension hinzufügen, um Zeilen- und Spalten-Indizes speichern zu können, also ZELLNDX[18][9][2].

 

[mrBrown]

Was meinst Du mit "ein passendes Interface drüber legen"?

Du greifst niemals direkt auf die Darstellung des Feldes zu, sondern schreibst dir ein entsprechendes Interface dafür. Das kann dann zB eine Methode bieten, um alle Spalten und Zeilen auf einmal zu bekommen

 

[kodela]

Hallo Meniskusschaden,

das war auch mein erster Gedanke, einfach eine Dimension hinzufügen, also einfach ZELLNDX[18][9][2]. Wie sieht dann aber die Initialisierung dieses dreidimensionalen Arrays aus. Hier, wie ich das zweidimensionale Array initialisiere:

    public static final int[][] ZELLNDX = {
        // für die Zeilen
        {0, 1, 2, 3, 4, 5, 6, 7, 8},
        {9, 10, 11, 12, 13, 14, 15, 16, 17},
        {18, 19, 20, 21, 22, 23, 24, 25, 26},
        {27, 28, 29, 30, 31, 32, 33, 34, 35},
        {36, 37, 38, 39, 40, 41, 42, 43, 44},
        {45, 46, 47, 48, 49, 50, 51, 52, 53},
        {54, 55, 56, 57, 58, 59, 60, 61, 62},
        {63, 64, 65, 66, 67, 68, 69, 70, 71},
        {72, 73, 74, 75, 76, 77, 78, 79, 80},
        // für die Spalten
        {0, 9, 18, 27, 36, 45, 54, 63, 72},
        {1, 10, 19, 28, 37, 46, 55, 64, 73},
        {2, 11, 20, 29, 38, 47, 56, 65, 74},
        {3, 12, 21, 30, 39, 48, 57, 66, 75},
        {4, 13, 22, 31, 40, 49, 58, 67, 76},
        {5, 14, 23, 32, 41, 50, 59, 68, 77},
        {6, 15, 24, 33, 42, 51, 60, 69, 78},
        {7, 16, 25, 34, 43, 52, 61, 70, 79},
        {8, 17, 26, 35, 44, 53, 62, 71, 80}
    };

Und dann erst der Zugriff. Wie würde der aussehen. Wie könnte man mit einer Abfrage auf die beiden Koordinaten für Zeile und Spalte gleichzeitig zugreifen. Mir ist dazu einfach nichts eingefallen.

MfG, kodela

 

[mrBrown]

Ich halte immer noch ein simples 2D-Array für die einfachste Variante.

Ein extra Array, was nur die Indizes beinhaltet, halte ich für überflüssig - das kann man wesentlich eleganter mit einer passenden Schleife lösen.
Und ja, auch so, das man weiterhin Spalten und Zeilen gleich behandeln kann - zB wenn das Feld eine einfache List<int[]> getRowsAndColumns() hat.

 

[Meniskusschaden]

Das:

das war auch mein erster Gedanke, einfach eine Dimension hinzufügen, also einfach ZELLNDX[18][9][2]. Wie sieht dann aber die Initialisierung dieses dreidimensionalen Arrays aus.

könnte dann so aussehen:

    public static final int[][][] ZELLNDX = {
            { {0, 0},  {0, 1} , {0, 2},  {0, 3}, ... },
            { {1, 0},  {1, 1} , {1, 2},  {1, 3}, ... },
            ...
        };

Und das:

Und dann erst der Zugriff. Wie würde der aussehen. Wie könnte man mit einer Abfrage auf die beiden Koordinaten für Zeile und Spalte gleichzeitig zugreifen. Mir ist dazu einfach nichts eingefallen.

so:

        for (int i = 0; i < 9; i++) {
            int zeile = ZELLNDX[b][i][0];
            int spalte = ZELLNDX[b][i][1];
            if ((sudoku[zeile][spalte]) > 0) {
                // ...
            }
        }

 

[kodela]

Hallo Meniskusschaden,

danke für Deine Hilfe. Ja so geht es mit der Initialisierung. Auch für den Zugriff ist die vorab durchgeführte Festlegung der beiden Koordinaten eine gute Lösung.

Ich habe mir zwischenzeitlich auch Gedanken gemacht, bin aber einen anderen Weg gegangen und habe beide Koordinaten für eine Zelle in einen Integer gepackt, in die Bits 0 - 3 den Zeilenindex und in die Bits 4 - 7 den Spaltenindex.

Das sieht dann für die Initialisierung so aus:

    public static final int[][] ZELLNDX = {
        // für Zeilen
        {0, 16, 32, 48, 64, 80, 96, 112, 128},
        {1, 17, 33, 49, 65, 81, 97, 113, 129},
        {2, 18, 34, 50, 66, 82, 98, 114, 130},
        {3, 19, 35, 51, 67, 83, 99, 115, 131},
        {4, 20, 36, 52, 68, 84, 100, 116, 132},
        {5, 21, 37, 53, 69, 85, 101, 117, 133},
        {6, 22, 38, 54, 70, 86, 102, 118, 134},
        {7, 23, 39, 55, 71, 87, 103, 119, 135},
        {8, 24, 40, 56, 72, 88, 104, 120, 136},
        // für Spalten
        {0, 1, 2, 3, 4, 5, 6, 7, 8},
        {16, 17, 18, 19, 20, 21, 22, 23, 24},
        {32, 33, 34, 35, 36, 37, 38, 39, 40},
        {48, 49, 50, 51, 52, 53, 54, 55, 56},
        {64, 65, 66, 67, 68, 69, 70, 71, 72},
        {80, 81, 82, 83, 84, 85, 86, 87, 88},
        {96, 97, 98, 99, 100, 101, 102, 103, 104},
        {112, 113, 114, 115, 116, 117, 118, 119, 120},
        {128, 129, 130, 131, 132, 133, 134, 135, 136}      
    };

und für den Zugriff so:

    for (int i = 0; i < 9; i++) {
        int zelle = ZELLNDX[b][i];
        if ((sudoku[zelle & 15][zelle >>> 4]) > 0) {
            // ...
        }
    }

Die beiden erforderlichen Bitoperationen bei jedem Zugriff auf einen Zellwert verbrauchen sicher nicht mehr Zeit, als der ansonsten erforderliche zweite Lesezugriff.

MfG, kodela

 

[mrBrown]

Meine Variante:

Spoiler: Code

public class Field {
    private final static int SIZE = 9;

    private int[][] field = new int[SIZE][SIZE];

    Field() {
        field[0][0] = 1;
        field[1][0] = 2;
        field[2][0] = 3;
        field[0][1] = 4;
        field[1][1] = 5;
        field[2][1] = 6;
        field[0][2] = 7;
        field[1][2] = 8;
        field[2][2] = 9;
    }

    public static void main(String[] args) {
        new Field().getBlocks().forEach(a -> System.out.println(Arrays.toString(a)));
        System.out.println("##");
        System.out.println(Arrays.toString(new Field().get(Type.BLOCK, 0)));
        System.out.println("##");
        System.out.println(Arrays.toString(new Field().get(Type.COLUMN, 0)));
        System.out.println("##");
        System.out.println(Arrays.toString(new Field().get(Type.ROW, 0)));
    }

    List<int[]> getAll() {
        ArrayList<int[]> all = new ArrayList<>();
        for (int i = 0; i < SIZE; i++) {
            all.add(Type.BLOCK.get(i, field));
            all.add(Type.ROW.get(i, field));
            all.add(Type.COLUMN.get(i, field));
        }

        return all;
    }

    int[] get(Type type, int i) {
        return type.get(i, field);
    }

    enum Type {
        BLOCK {
            @Override
            int get(int i, int j, int[][] field) {
                int blockColumn = i / 3;
                int blockRow = i % 3;

                int columnInBlock = j % 3;
                int rowInBlock = j / 3;

                return field[blockColumn * 3 + columnInBlock][blockRow * 3 + rowInBlock];
            }
        }, ROW {
            @Override
            int get(int i, int j, int[][] field) {
                return field[j][i];
            }
        }, COLUMN {
            @Override
            int get(int i, int j, int[][] field) {
                return field[i][j];
            }
        };

        int[] get(int i, int[][] field) {
            int[] ret = new int[SIZE];
            for (int j = 0; j < SIZE; j++) {
                ret[j] = get(i, j, field);
            }
            return ret;
        }

        abstract int get(int i, int j, int[][] field);
    }

}

Spart man sich im wesentlichen das Bitshifting und das händische Aufschreiben der Werte. Legt man noch ein vernünftiges Interface drüber, kann man das zT auch für andere Arten verwenden.

 

[kodela]

Hallo mrBrown,

Spart man sich im wesentlichen . . . das händische Aufschreiben der Werte.

Was ist damit gemeint?

Danke für Deine Variante. Ich muss mich aber erst noch näher mit ihr beschäftigen.

MfG, kodela

 

[mrBrown]

Was ist damit gemeint?

Du musst die Tabelle mit den 243*2 Werten nicht aufschreiben^^

 

[kodela]

Du musst die Tabelle mit den 243*2 Werten nicht aufschreiben^^

Die habe ich nicht geschrieben, zumindest nicht direkt. Ich habe mir für die Ausgabe der Werte eine kleine Methode geschrieben. Nur das "Drumherum" musste ich schreiben. Übrigens sind es für Str8ts nicht 2*243 sondern 2*81 Werte. Die Tabelle ist so, wie ich sie im Beitrag #10 gezeigt habe, vollständig. Nicht vergessen, die beiden Koordinaten für eine Zelle im zweidimensionalen Array habe ich in einen Wert gepackt.

 

[mrBrown]

Die habe ich nicht geschrieben, zumindest nicht direkt. Ich habe mir für die Ausgabe der Werte eine kleine Methode geschrieben. Nur das "Drumherum" musste ich schreiben. Übrigens sind es für Str8ts nicht 2*243 sondern 2*81 Werte. Die Tabelle ist so, wie ich sie im Beitrag #10 gezeigt habe, vollständig. Nicht vergessen, die beiden Koordinaten für eine Zelle im zweidimensionalen Array habe ich in einen Wert gepackt.

Das Beispiel von mir ist ja auch für Sudoku, was du angesprochen hattest.
Ob man die beiden Werte in einem Integer speichert (was ich ausgesprochen unschön finde), ändert ja nichts daran, das es 2 Werte sind

Und wenn du sie eh generieren lässt, warum dann nicht einfach direkt die generiert nutzen?