Problem mit ArrayList

M

member42

Aktives Mitglied
Hallo,
ich habe ein Array was ich zu einer ArrayList hinzufüge. Wenn ich danach einen Wert im Array ändere und dann die Liste ausgebe, wurde der Wert im Array geändert, obwohl ich das Array ja vorher zur Liste hinzugefügt habe(und sich die Werte eigentlich nicht mehr ändern dürften). Kann wer erklären woran das liegt?

Java: 
private static int[][] f =  { {1, 2, 3},
                            {4, 5, 6},
                            {7, 8, 9}};

public static void main(String[] args) {
          ArrayList<int[][]> a = new ArrayList<>();
          a.add(f);
          f[0][0] = 42;

         for(int[][] arr: a) {
             print(arr);
         }
}
Danke im Vorraus.
 
Dein Array ist ein Objekt, das im Speicher angelegt wird. Die Variable f speichert die Adresse des Objekts im Hauptspeicher (sie referenziert das Array). Ein Element Deiner Liste ist also nicht etwa ein Array sondern nur die Referenz dazu.

Das erste Element Deiner Liste enthält also die gleiche Adresse wie Dein f. Daher spielt es keine Rolle, ob Du nun über f oder über die Liste auf das Array zugreifst: es ist immer der selbe Speicherbereich.
 
Ok, danke. In meinem Programm tausche ich 2 Zahlen in einem Array und füge das Array dann zu einer Liste hinzu. Danach werden die Zahlen wieder zurückgetauscht und ich habe dasselbe Problem wie oben. Ich habe das Problem mit einer Arraykopie gelöst, gibt es noch eine bessere Möglichkeit?
 
Das hängt davon ab, was Du vor hast. Ganz allgemein kann man nur sagen, dass es natürlich richtig ist, eine Kopie anzulegen, wenn Du eine Kopie brauchst 🙂 Ob ein Problem anders (besser) lösbar ist, hängt vom Problem ab.
 
Da ich bisher noch keine bessere Lösung zu dem aus Post #3 gefunden habe, wollte ich nochmal fragen ob es eine bessere Alternative gibt. Ich tausche in dem Array zwei Zahlen und füge es zu einer ArrayList hinzu. Danach soll das Array in der Liste nicht mehr verändert werden, auch wenn an dem Array wieder was geändert wird.
Java: 
swapNumbers(board, x1, y1, x2, y2);

int copy[][] = new int[size][size];

for (int j = 0; j < size; j++) {
    copy[j] = board[j].clone();
}
list.add(copy);

swapNumbers(board, x1, y1, x2, y2);
 
Also meiner Meinung nach ist das so nicht gut und wird so nicht gemacht.

Was ist das denn für ein zweidimensionales Array? Das hat doch eine Bedeutung!
Was machst Du damit? Da gibt es doch irgendwelche Funktionen drauf!

Statt mit solchen Konstrukten zu arbeiten sollte man lieber eine Klasse erstellen. Die kann die Daten dann so speichern, klar. Aber das intern und geht für die außen nichts an. Und wenn es morgen kein zweidimensionales Array mehr sein soll sondern irgendwas anderes, dann ist das auch ok, denn Du musst nur die Klasse ändern. Alles außerhalb hatte ja keine Ahnung, wie es implementiert wurde. (=> Kapselung ist hier der wichtige Begriff)

Das ist halt etwas, das mir komplett fehlen würde.

Beispiel wäre z.B. eine Matrix. Da kann man dann mit rechnen und all sowas. Aber alles ist in einer Klasse Matrix und man hantiert nicht mit diesen zweidimensionalen Arrays rum.
 
kneitzel hat gesagt.:
Was ist das denn für ein zweidimensionales Array? Das hat doch eine Bedeutung!
Was machst Du damit? Da gibt es doch irgendwelche Funktionen drauf!
Zum Vergrößern anklicken....
Ja, das war auch nur ein Beispiel. Ich habe das Array auch in einer Klasse(das ist für ein Sliding-Puzzle, das Nummern vertauschen ist für die Verschiebungen), mir geht geht es nur darum das Array nicht jedesmal kopieren zu müssen, auch wenn es so funktioniert.
 
mihe7 hat gesagt.:
Und warum speicherst Du dann nicht einfach die Züge?
Zum Vergrößern anklicken....
Habs etwas ungenau beschrieben. Ich löse das SlidingPuzzle mit dem A* Algorithmus, was auch soweit funktioniert. In jedem Knoten speichere ich u.a die Brettstellung. Aber wenn ich für jeden Knoten wie oben in #5 die Nachfolgeknoten berechne(also mit Kopie) und das bei Millionen von Knoten, wirkt sich das wahrcheinlich ziemlich auf die Laufzeit aus.
 
Du brauchst auch keine Kopien, wenn Du Dich auf die Züge konzentrierst 🙂

Du hast einen Ausgangsbelegung (Brettstellung), die dem Wurzelknoten entspricht. Korrigiere mich, wenn ich falsch liege: es gibt ein leeres Feld, das von max. vier belegten Feldern umgeben sein kann und jedes der belegten Felder kann auf das leere Feld geschoben werden. Macht bis zu vier Züge.

Ein Zug kann die Brettstellung direkt ändern, weil er bei Bedarf auch rückgängig gemacht werden kann.
 
mihe7 hat gesagt.:
Du brauchst auch keine Kopien, wenn Du Dich auf die Züge konzentrierst 🙂
Zum Vergrößern anklicken....

Wie meinst du das genau? So ähnlich wie du es beschrieben hast mache ich es eigentlich(also mit Zug rückgägig machen und so). Hier ist einmal die Methode um alle Child Knoten von einem Node zubestimmen:
Java: 
/*
Gibt alle Kindknoten in einer Liste zurück
*/
private int[][] moves = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
......

private ArrayList<Node> getChildren() {
    ArrayList<Node> children = new ArrayList<>();

    for (int i = 0; i < moves.length; i++) { // maximal 4 Züge, rechts links oben unten

        if (inBoard(blankX + moves[i][0], blankY + moves[i][1])) { // Zug überprüfen
            swapNumbers(puzzle, blankX, blankY, blankX + moves[i][0], blankY + moves[i][1]); // leeres Feld mit anliegendem Feld tauschen,Zug machen

            int copy[][] = new int[size][size]; // klappt nur mit copy

            for (int j = 0; j < size; j++) {
                copy[j] = puzzle[j].clone();
            }
 
            Node child = new Node(this, copy); // besteht aus Vorgänger und brett
            child.blankX = this.blankX + moves[i][0]; // neus leeres Feld speichern
            child.blankY = this.blankY + moves[i][1];
            children.add(child);

            swapNumbers(puzzle, blankX, blankY, blankX + moves[i][0], blankY + moves[i][1]); // Zug rückgängig machen
        }

    }

    return children;
}
 
Zuletzt bearbeitet:
member42 hat gesagt.:
Wie meinst du das genau?
Zum Vergrößern anklicken....
Nehmen wir mal folgendes Feld an:
Code: 
123
4 5
678
Jetzt kannst Du 2, 4, 5 oder 7 verschieben. Das wäre ein Zug. Sagen wir mal, wir verschieben 2:
Code: 
1 3
425
678
Diesen Zug kann ich rückgängig machen, indem ich wieder die 2 verschiebe:
Code: 
123
4 5
678
Man braucht also nur die aktuelle Belegung (man muss nicht jede Belegung einzeln speichern) und eine Zugfolge (oder eben auch einen Baum von Zügen), weil jeder Zug rückgängig gemacht und somit die "alte" Belegung wiederhergestellt werden kann.
 
Also müssen in einem Knoten nur die Koordinaten des leeren Feldes und der Vorgängerknoten gespeichert werden? Ich muss ja für jeden Knoten eine Heuristik berechenen(ich verwende Manhattan Distanz), dafür brauche ich dann aber wieder das komplette Feld um diese zuberechen. Wie soll das dann funktionieren wenn ich nur Zugfolgen gespeichert habe?
 
Zuletzt bearbeitet:
Du hast immer komplette Feld, der Unterschied ist lediglich, dass Du nicht in jedem Knoten eine Kopie davon abspeicherst.

Nehmen wir mal die Ausgangsbelegung von oben an, und sagen wir mal wir haben die Zugfolge 2, 3, 5, 8. Dann kannst Du doch für jeden Zug die Belegung angeben. Darüber hinaus verändert sich die Belegung ja immer nur um einen Zug, den Du Rückgängig machen kannst.

Ein Knoten besteht aus einem Verweis auf einen Vaterknoten (bei der Wurzel z. B. null), einer Liste von Verweisen auf die Kindknoten und Werten. Als Werte hättest Du den Zug (z. B. von Feld, nach Feld) und das Ergebnis der Berechnung(en). Ggf. bietet es sich an, einen Verweis auf die aktuelle Belegung (das ist nur eine) zu haben.

Wenn Du den Baum aufbaust, entspricht die aktuelle Belegung der Anfangsbelegung. Dann führst Du einen der möglichen Züge aus und erhältst damit die geänderte Belegung. Jetzt kannst Du das Ergebnis berechnen. Falls Du zurückkehren musst, machst Du den Zug rückgängig, ansonsten machst Du weiter.
 
Danke, ich versuche das so umzusetzen.
Bisher berechne ich für jeden Knoten die Manhattandistanz. Wäre es sinnvoll nur für die Brettausgangstellung die Manhattandistanz zuberechen und die dann immer weiter an die Nachbarknoten zugeben? Da sich beim Vertauschen von leerem und anliegenden Feld die M. Distanz um 1 oder -1 ändert.
 
Soo, schwer ist das nicht...
(Wo ist das Problem mit der ArrayList?)
Müsste richtig sein:
Java: 
import java.awt.Point;
import java.util.ArrayList;

public class MD {
    int md(int x1, int y1, int x2, int y2) {
        return Math.abs(x1 - x2) + Math.abs(y1 - y2);
    }
    void md(int x, int y, int x1, int y1, int x2, int y2, ArrayList list) {
        if (x == x2 && y == y2) {
            list.add(new Point(x, y));
            System.out.println(list);
            list.remove(list.size() - 1);
            return;
        }
        if (md(x, y, x1, y1) == md(x1, y1, x2, y2)) {
            return;
        }
        list.add(new Point(x, y));
        if (x1 < x2) {
            if (y1 < y2) {
                md(x + 1, y, x1, y1, x2, y2, list);
                md(x, y + 1, x1, y1, x2, y2, list);
            } else {
                md(x + 1, y, x1, y1, x2, y2, list);
                md(x, y - 1, x1, y1, x2, y2, list);
            }
        } else {
            if (y1 < y2) {
                md(x - 1, y, x1, y1, x2, y2, list);
                md(x, y + 1, x1, y1, x2, y2, list);
            } else {
                md(x - 1, y, x1, y1, x2, y2, list);
                md(x, y - 1, x1, y1, x2, y2, list);
            }
        }
        list.remove(list.size() - 1);
    }
    public static void main(String[] args) {
        MD m = new MD();
        m.md(0, 0, 0, 0, 2, 2, new ArrayList());
    }
}


Das lustige ist ja daran (zum Leidwesen mancher Fahrgäste), dass Taxifahrer in Manhattan random fahren können - und immer ankommen (insofern sie nicht zurückfahren).... 😀
 
Verstehe ich nich... Aber auch da lässt sich noch etwas optimieren, @mihe7 (Zum Bleistift, die Fallunterscheidung kann bei 4 Methoden entfallen)🙁

WICHTIG ist beim Testen, dass ihr (x,y) muss gleich dem Startpunkt (x1,y1) sein....
 
mihe7 hat gesagt.:
bevor ich da mit irgendwelchen Optimierungen rangehe, würde ich erstmal schauen, dass das Zeug läuft.
Zum Vergrößern anklicken....
Es funktioniert ja, nur teilweise sehr langsam. z.B für ein random 8er Puzzle teilweise über 2min. Deswegenwollte ich noch was optimieren, weil ich auch ein 15er lösen möchte, was bisher aber nicht möglich ist. Ist das was ich geschrieben hatte den von der Logik her richtig? Das müsste dann einiges an Zeit einsparen.

@Tobias-nrw Was soll dein Programm eigentlich bewirken? Ganz oben berechnest du ja die M. Distanz,aber den Rest verstehe ich nicht.
 
member42 hat gesagt.:
Was soll dein Programm eigentlich bewirken
Zum Vergrößern anklicken....
Es berechnet alle Manhattan-Distanzen zwischen zwei geg. Punkten a mit (x1,y1) und b (x2,y2). Unverständlich sollte daran nüx sein.

Außerdem kann mit int md(a,b,c,d) die Summe der Beträge (== Manhattan-Distanz auch) erfragt werden.

Bevor Du sagst, etwas sei unverständlich, versuche Deinen eigenen Code nachzuvollziehen... Den Algo von der Schwierigkeit her muss man nämlich im zweiten Semester nachvollziehen können.
 
mihe7 hat gesagt.:
dann muss sich durch Verschiebung eines Felds die Distanz des Puzzles genau um 1 ändern.
Zum Vergrößern anklicken....
Ich glaube das ist nicht ganz richtig(korriegiere mich wenn mein Beispiel falsch ist).
Code: 
4 1 5    0 1 5
0 6 3 -> 4 6 3 Manhattan -1
2 7 8    2 7 8

4 1 5    4 1 5
0 6 3 -> 6 0 3 Manhattan +1
2 7 8    2 7 8

Dann müsste sich die Distanz doch um 1 oder -1 ändern können?
 
Dann müsste ich doch einmal die Distanz vorm swapen berechen(z.B bei 0 und 6 , die Distanz zur richtigen Position der 6) und nach dem swapen nochmal. Und jenachdem wie dann der Unterschied dieser beiden Distanzen ist, ist die Distanz der neuen Boardposition +1 oder -1 von der vorherigen.
Wäre das so richtig?
 
Du brauchst nicht einmal zu vertauschen. In Deinem Beispiel (mit 0 und 6) wäre die Koordinate des Ziels (2,1). Der Zug würde von (1,1) nach (0,1) gehen.

deltaX = abs(x_ziel - x_alt) - abs(x_ziel - x_neu)
deltaY = abs(y_ziel - y_alt) - abs(y_ziel - y_neu)

Da Du weißt, ob Du Dich horizontal oder vertikal bewegst, brauchst Du nur eine der beiden auszurechnen, um die Distanz-Änderung zu erhalten.

Würde der Zug durchgeführt, hättest Du also eine Erhöhung der tatsächlichen Distanz um 1 (weil Du ja eine Bewegung durchführst) und eine Erhöhung der Manhatten-Distanz um 1.
 
mihe7 hat gesagt.:
Du brauchst nicht einmal zu vertauschen. In Deinem Beispiel (mit 0 und 6) wäre die Koordinate des Ziels (2,1). Der Zug würde von (1,1) nach (0,1) gehen.
Zum Vergrößern anklicken....
Habe nochmal ne Frage zu den Zügen. Wenn ich in jedem Knoten bis(bis auf Startknoten) den Zug speichere der vom vorherigen zu diesem Knoten führt, wie soll ich dann über prüfen ob der Lösungszustand schon erreicht wurde?
So wie ich es bisher habe, kann ich ja einfach das Lösungsfeld mit dem Feld im aktuellen Knoten vergleichen.
 

Aktuelle Jobs

Neue Themen

Ähnliche Themen

ArrayList<ArrayList<ArrayList<String>>>
Antworten: 10
Problem mit Arraylist in Arraylist
Antworten: 2
ArrayList mit ArrayList als Inhalt - komische Sortierung?
Antworten: 12
Arraylist mit anderer ArrayList überschreiben
Antworten: 17
LinkedList<LinkedList<String>> nach ArrayList<ArrayList<String>> ?
Antworten: 9

Zurück
Oben