Methoden Mehrdimensionale Arrays übereinander legen

[Jake14]

Hallo, ich habe folgende Aufgabe:





Nun komme ich seit Tagen nicht darauf, wie ich die Arrays übereinander legen kann. Ich soll ja offensichtlich nicht bei workArray[0][0] beginnen, sondern bei [1][1]. Wie kann ich die Methode gestalten, sodass sie filterArray nur an jene Stellen über workArray legt, bei denen filterArray auch nicht "über den Rand" geht?

 

[kneitzel]

Wo genau ist Dein Problem und was waren bisher Deine Ansätze?

Und wenn ich das Bild anschaue, dann wird zuerst bei [0][0] angesetzt - also [0][0] vom workArray ist bei [0][0] vom filterArray.

Und wenn Du da die beiden Bilder anschaust: Wo ist denn beim zweiten Bild angesetzt? Da wirst Du doch bestimmt eine Gesetzmäßigkeit erkennen.

Und wie immer: teile und herrsche! Zerlege das Problem also in Teilprobleme, die dann von der Komplexität her beherrschbar werden für Dich.

 

[Jake14]

Wo genau ist Dein Problem und was waren bisher Deine Ansätze?

Und wenn ich das Bild anschaue, dann wird zuerst bei [0][0] angesetzt - also [0][0] vom workArray ist bei [0][0] vom filterArray.

Und wenn Du da die beiden Bilder anschaust: Wo ist denn beim zweiten Bild angesetzt? Da wirst Du doch bestimmt eine Gesetzmäßigkeit erkennen.

Und wie immer: teile und herrsche! Zerlege das Problem also in Teilprobleme, die dann von der Komplexität her beherrschbar werden für Dich.

Du hast recht, ich muss bei [0][0] starten. Ich hatte einen Denkfehler, bin jetzt aber auf dem richtigen Weg. Danke dafür!

Ich habe jetzt eine Methode, welche diese Aufgabe lösen kann, aber bei einem größeren workArray nicht mehr funktioniert:

    private static double[][] applyFilter(double[][] workArray, double[][] filterArray) {
        // TODO: Implementieren Sie hier Ihre Lösung für die Methode
        double[][] filteredArray = new double[workArray.length][workArray[0].length];

        int filterHeightMiddle = (filterArray.length) / 2;
        int filterWidthMiddle = (filterArray[0].length) / 2;

            for (int k = 0; k <= workArray[0].length-filterArray[0].length ; k++) {
                for (int i = 0; i < workArray.length; i++) {
                    for (int j = 0; j < filterArray.length; j++) {
                        filteredArray[filterHeightMiddle][filterWidthMiddle + k] += workArray[i][j + k] * filterArray[i][j];
                    }
                }
            }

        print(filteredArray);
        return filteredArray;
    }


    public static void main(String[] args) {

        double[][] workArray = new double[][] {{0, 1, 2, 3}, {4, 5, 6, 7}, {8, 9, 10, 11}/*, {0, 1, 2, 3}*/};
        double[][] filterArray = new double[][] {{1, 0, 0}, {1, 2, 0}, {0, 0, 3}};

        applyFilter(workArray, filterArray);

    }

Durch die for-Schleife in Zeile 9 würde "i" zu groß werden und ich erhalte eine out of bounds exception... Wie kann ich das korrigieren?

 

[kneitzel]

Was mich erst einmal stört sind die Variablennamen. Was ist k, i und j? Und Variablen mit einer gewissen Länge, die sich nur durch zwei Buchstaben unterscheiden, finde ich auch nicht wirklich gut. Aber auf den ersten Blick sieht der Code korrekt aus.

Der Fehler dürfte ein falscher Test sein, denn laut Aufgabe gilt immer:
Die length von workArray, filterArray und result (dein filteredArray) ist immer gleich. Also in dem Beispiel der Aufgabe ist die Höhe immer 3.
Wenn Du aber in workArray jetzt eine 4te Zeile einfügst, dann gilt dies nicht mehr.
==> Also die Teilarrays müssen länger werden ... 5, 6, 7 Elemente pro Array!


Kleiner Exkurs, weil ich es zuvor erwähnt hatte:
Generell ist es aber immer gut, die Komplexität gering zu halten: Teile und Herrsche!

Du baust da einen Algorithmus, der einfach zu komplex ist und so schwer zu überblicken ist. Ein Indiz dafür sind zu viele Verschachtelungen (Du hast da gleich drei Schleifen! In der Regel sollte es nur eine sein, maximal zwei!)

Ein Vorgehen ist die "Top Down Methode":
Schreibe den Algorithmus High-Level auf. Was ist das denn dann?
Sowas wie
- Erzeuge Ergebnis Matrix (Das 2d Array würde ich als Matrix bezeichnen.... Array ist ein Datentyp. Dein Name ist ja auch Dein Name und nicht String. Also sagst Du ja auch nicht: "Wie ist Dein String?"
- Für jede Verschiebeposition:
---> Berechne Filter-Summe
---> Speicher Filter Summe in ErgebnisMatrix

Und das kannst Du direkt in Code umsetzen:

double[][] ergebnis = erzeugeErgebnisMatrix(....);
for (int verschiebung: berechneAlleVerschiebePositionen(...)) {
  double summe = berechneSumme(...);
  speichereSummeInMatrix(.....);
}

Was Du in den jeweiligen Methoden brauchst, ist dabei noch nicht festgelegt... also entweder keine Argumente angeben oder ich habe es durch ... aufgezeigt ...

Damit hast Du den Algorithmus der Aufgabe ... Du musst nur noch die Methoden schreiben:
- erzeugeErgebnisMatrix ist einfach - bekommt die original Matrix übergeben und erzeugt eine Neue mit gleicher Größe.
- berechneAlleVerschiebePositionen - da habe ich schon etwas vorgegriffen: Da ist der Typ int. Aber wir geben da mehrere int zurück. Das könnte also z.B. eine List<Integer> sein aber auch ein int[] würde funktionieren. An der Stelel dann wichtig. einfache Dinge kann man in die Methode gerne wieder rein ziehen. Dann wäre das z.B. wieder eine for Schleife wie Du sie schon hast. ==> Aus diversen Gründen würde ich das nicht machen, aber falls Du Probleme mit der for each Schleife hast, dann mache daraus eine normale for Schleife....
- berechneSumme berechnet dann nur noch die Summe der Multiplikationen. Der Name gefällt mir nicht. Es ist ja eine Filter Operation an einer Stelle ... berechneFilter oder so wäre dann eher besser ....
- speichereSummeInMatrix erklärt sich dann von alleine ...

So hast Du dann viele kleine Methoden, die Du auch einzeln prüfen kannst.

(Das geht auch Bottom Up, d.h. Du überlegst einmal, was Du so an Operationen brauchst und implementierst dann von unten nach oben. Dann weisst Du auch immer, was Du für die Methoden an Parameter brauchst ... Das Vorgehen spielt aber keine Rolle. Ich wollte es nur einmal kurz gesagt haben!)

 

[kneitzel]

Der Fehler dürfte ein falscher Test sein, denn laut Aufgabe gilt immer:
Die length von workArray, filterArray und result (dein filteredArray) ist immer gleich. Also in dem Beispiel der Aufgabe ist die Höhe immer 3.
Wenn Du aber in workArray jetzt eine 4te Zeile einfügst, dann gilt dies nicht mehr.
==> Also die Teilarrays müssen länger werden ... 5, 6, 7 Elemente pro Array!

Ich glaube das habe ich doch falsch gelesen. Das ist doch keine Bedingung.

Du musst die Schleife, die die Berechnung durchführt, in den richtigen Grenzen laufen lassen.
Du hast Drei Schleifen:
- k ist die Schleife mit dem Versatz ... Aber erst in eine Richtung!
- i/j sollen die Berechnungen durchführen. Dabei werden aber natürlich die Grenzen des filterArrays verwendet und nicht des workArrays!

Also darf i nur die Grenzen des filterArray nutzen und du brauchst noch eine Schleife für den zweiten Versatz,


Also einfach einmal aufzeichnen, was Du machen musst.

Du fängst erst in der ersten spalte an (Versatz vertikal 0) um da dann die Zeile abzuarbeiten (Horizontalen Versatz von 0 an durchgehen ...)
Dann gehst Du in die nächste Spalte (Versatz vertikal ist dann 1) und machst es erneut.

 

[Jake14]

Ich habe den Code jetzt so verändert, dass er auch mit längeren workArrays umgehen kann. Leider habe ich jetzt 4 Schleifen, aber es scheint zu funktionieren.
Du hast mit den Variablennamen natürlich recht, ich werde in Zukunft darauf achten.

Mein Code:

    private static double[][] applyFilter(double[][] workArray, double[][] filterArray) {
        // TODO: Implementieren Sie hier Ihre Lösung für die Methode
        double[][] filteredArray = new double[workArray.length][workArray[0].length];

        int filterHeightMiddle = (filterArray.length) / 2;
        int filterWidthMiddle = (filterArray[0].length) / 2;

        for (int l = 0; l <= workArray.length-filterArray.length ; l++) {
            for (int k = 0; k <= workArray[0].length - filterArray[0].length; k++) {
                for (int i = 0; i < filterArray.length; i++) {
                    for (int j = 0; j < filterArray.length; j++) {
                        filteredArray[filterHeightMiddle + l][filterWidthMiddle + k] += workArray[i + l][j + k] * filterArray[i][j];
                    }
                }
            }
        }
        return filteredArray;
    }