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.
 
mihe7

mihe7

Top Contributor
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.
 
M

member42

Aktives Mitglied
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?
 
mihe7

mihe7

Top Contributor
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.
 
M

member42

Aktives Mitglied
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);
 
K

kneitzel

Gast
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.
 
M

member42

Aktives Mitglied
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!
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.
 
M

member42

Aktives Mitglied
Weil sonst, wie schon geschrieben die Werte in der Liste nachträglich verändert werden was nicht passieren soll.
 
M

member42

Aktives Mitglied
Und warum speicherst Du dann nicht einfach die Züge?
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.
 
mihe7

mihe7

Top Contributor
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.
 
M

member42

Aktives Mitglied
Du brauchst auch keine Kopien, wenn Du Dich auf die Züge konzentrierst :)

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:
mihe7

mihe7

Top Contributor
Wie meinst du das genau?
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.
 
M

member42

Aktives Mitglied
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:
mihe7

mihe7

Top Contributor
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.
 
M

member42

Aktives Mitglied
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.
 
X

Xyz1

Gast
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).... :D
 
mihe7

mihe7

Top Contributor
Ich würde es für den Anfang mit Knuth halten: premature optimization is the root of all evil.
 
X

Xyz1

Gast
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....
 
M

member42

Aktives Mitglied
bevor ich da mit irgendwelchen Optimierungen rangehe, würde ich erstmal schauen, dass das Zeug läuft.
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.
 
X

Xyz1

Gast
Was soll dein Programm eigentlich bewirken
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

mihe7

Top Contributor
Ist das was ich geschrieben hatte den von der Logik her richtig?
Wenn ich mal davon ausgehe, dass die Manhatten-Distanz des Puzzles der Summe der Manhatten-Distanzen aller Felder (außer dem leeren) ist, dann muss sich durch Verschiebung eines Felds die Distanz des Puzzles genau um 1 ändern.
 
M

member42

Aktives Mitglied
dann muss sich durch Verschiebung eines Felds die Distanz des Puzzles genau um 1 ändern.
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?
 
M

member42

Aktives Mitglied
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?
 
mihe7

mihe7

Top Contributor
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.
 
M

member42

Aktives Mitglied
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.
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.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
R ArrayList Problem Java Basics - Anfänger-Themen 6
X Problem mit Arraylist in Arraylist Java Basics - Anfänger-Themen 2
J Threads Problem mit eigener ArrayList Java Basics - Anfänger-Themen 2
A Collections Problem mit ArrayList Java Basics - Anfänger-Themen 10
P Input/Output Problem bei Ausgabe von Arraylist Java Basics - Anfänger-Themen 6
O Klasse in ArrayList speichern Problem -gleiche Speicheradresse Java Basics - Anfänger-Themen 2
K ArrayList<Integer> problem Java Basics - Anfänger-Themen 3
B ArrayList Problem Java Basics - Anfänger-Themen 3
J Threads ArrayList Problem bei Threads Java Basics - Anfänger-Themen 3
B ArrayListe in Arraylist Problem Java Basics - Anfänger-Themen 3
G Arraylist Problem Java Basics - Anfänger-Themen 4
S problem mit ArrayList.clear Java Basics - Anfänger-Themen 2
B ArrayList-Problem Java Basics - Anfänger-Themen 2
R ArrayList Problem Java Basics - Anfänger-Themen 12
T Collections Problem mit ArrayList Java Basics - Anfänger-Themen 2
K Problem mit ArrayList Java Basics - Anfänger-Themen 4
B Problem bei ArrayList Java Basics - Anfänger-Themen 5
J Problem beim Löschen von elementen aus einer ArrayList Java Basics - Anfänger-Themen 5
J Problem Arraylist durchlaufen Java Basics - Anfänger-Themen 7
M ArrayList<int[]> - Problem mit JList! Java Basics - Anfänger-Themen 27
A ArrayList<T>: Problem mit contains() bei parametrisiertem T Java Basics - Anfänger-Themen 6
J ArrayList Problem Java Basics - Anfänger-Themen 5
G ArrayList Problem Java Basics - Anfänger-Themen 2
B ArrayList Code-Problem Java Basics - Anfänger-Themen 36
S ArrayList-Problem? Java Basics - Anfänger-Themen 3
A arraylist speichern/laden problem Java Basics - Anfänger-Themen 3
zilti Problem mit static ArrayList Java Basics - Anfänger-Themen 3
T Problem mit ArrayList Java Basics - Anfänger-Themen 6
G ArrayList Problem Java Basics - Anfänger-Themen 2
B ArrayList Problem ? Java Basics - Anfänger-Themen 6
M ArrayList problem Java Basics - Anfänger-Themen 3
T von ArrayList erben - Problem mit Generics Java Basics - Anfänger-Themen 2
W Problem beim lesen aus Arraylist Java Basics - Anfänger-Themen 2
0 Kleines Problem mit ArrayList Java Basics - Anfänger-Themen 25
J konkretes problem mit arraylist Java Basics - Anfänger-Themen 15
A Problem mit ArrayList Java Basics - Anfänger-Themen 6
S ArrayList - WrapperKlassen - PROBLEM Java Basics - Anfänger-Themen 25
J Allgemeines Problem mit Klassen Java Basics - Anfänger-Themen 2
U Problem mit dem initialisieren meines Strings in einer Schleife Java Basics - Anfänger-Themen 4
amgadalghabra algorithmisches Problem Java Basics - Anfänger-Themen 19
J Traveling Salesman Problem [Arrays] Java Basics - Anfänger-Themen 9
InfinityDE Problem mit Datenübergabe an Konstruktor Java Basics - Anfänger-Themen 7
C RegEx Problem Java Basics - Anfänger-Themen 4
J Anfänger TicTacToe, Problem bei Gewinnoption, sowohl Unentschieden Java Basics - Anfänger-Themen 8
E Taschenrechner GUI Problem mit Fehlerhandling Java Basics - Anfänger-Themen 6
M Input/Output Fallunterscheidung Problem Java Basics - Anfänger-Themen 17
P Problem beim Überschreiben einer vererbten Methode Java Basics - Anfänger-Themen 4
M Problem bei Ausgabe Java Basics - Anfänger-Themen 7
S Java Array Problem... Java Basics - Anfänger-Themen 2
G Problem bei der Ausgabe einer Main Claase Java Basics - Anfänger-Themen 7
F Problem mit KeyListener in kombination mit dem ActionListener Java Basics - Anfänger-Themen 4
L Subset sum problem mit Backtracking Java Basics - Anfänger-Themen 18
N Problem mit Scanner Java Basics - Anfänger-Themen 2
J Klassen Problem Java Basics - Anfänger-Themen 8
A Out.format problem. Java Basics - Anfänger-Themen 3
J Problem bei der Programmierung eines Tannenbaums Java Basics - Anfänger-Themen 9
A Array problem Java Basics - Anfänger-Themen 16
2 Taschenrechner mit GUI Problem bei der Berechnung Java Basics - Anfänger-Themen 8
W Remote Method Invocation RMI - Problem Java Basics - Anfänger-Themen 0
I Ich habe ein Problem Java Basics - Anfänger-Themen 3
A Problem bei returnen eines Wertes Java Basics - Anfänger-Themen 6
M Regex Erstellung Problem Java Basics - Anfänger-Themen 2
D Input/Output Problem bei der Benutzereingabe eines Befehls Java Basics - Anfänger-Themen 14
M (Sehr großes Problem) Listen als static in anderen Klassen verwendet Java Basics - Anfänger-Themen 12
F Habe ein problem mit dem ActionListener Java Basics - Anfänger-Themen 3
C Regex-Problem Java Basics - Anfänger-Themen 4
J Problem beim vergleich von zwei Integer Java Basics - Anfänger-Themen 3
M Problem in der Modellierung Java Basics - Anfänger-Themen 20
W Wo ist das URL-Problem ? Java Basics - Anfänger-Themen 1
S Generics-Problem: Class, Class<?>, Class<Object> Java Basics - Anfänger-Themen 4
D FileWriter / FileReader Problem Java Basics - Anfänger-Themen 10
G Problem beim Speichern von Objekten in einer Datei Java Basics - Anfänger-Themen 7
S Compiler-Fehler Exception in thread "main" java.lang.Error: Unresolved compilation problem: Java Basics - Anfänger-Themen 6
J Problem mit Array: 2 Klassen Java Basics - Anfänger-Themen 2
S Collections funktionale Listen (ListNode<E>) review und problem beim clone Java Basics - Anfänger-Themen 0
W OOP Vererbung und Problem bei Zählschleife in einer Methode Java Basics - Anfänger-Themen 10
C Problem mit If Else If und Überprüfung eines Counters Java Basics - Anfänger-Themen 3
F Problem mit Listen Java Basics - Anfänger-Themen 5
I wieder mit einer Umwandelung habe ich Problem (diesmal von char Array zu char) Java Basics - Anfänger-Themen 1
J Problem bei Umrechnung von Hex in Bin Java Basics - Anfänger-Themen 4
W Problem bei Programmierung von Monte-Carlo-Integration Java Basics - Anfänger-Themen 12
C Java Methoden "Parameter" Problem Java Basics - Anfänger-Themen 16
T Bruchrechner Problem Java Basics - Anfänger-Themen 16
M Problem mit meinem Programm Java Basics - Anfänger-Themen 6
pkm Problem mit der JSP-Syntax Java Basics - Anfänger-Themen 2
J Rückgabe-Problem Java Basics - Anfänger-Themen 10
D Problem mit der Serialisierung Java Basics - Anfänger-Themen 31
W Problem mit dem Wert von boolean-Variable Java Basics - Anfänger-Themen 3
W Problem mit Konsolenausgabe bei StringTokenizer Java Basics - Anfänger-Themen 2
O Verständniss Problem bei abstract class Java Basics - Anfänger-Themen 7
K Java Problem mit Übergabe von argumenten Java Basics - Anfänger-Themen 3
J "travelling salesman problem" mit Java Editor Java Basics - Anfänger-Themen 17
B Array Problem Java Basics - Anfänger-Themen 3
O Problem mit SOAP / javax.xml importieren Java Basics - Anfänger-Themen 7
V Variablen Problem mit Matheaufgabe / int first = mScanner.nextInt(); Java Basics - Anfänger-Themen 5
cpt.Tomato Scanner problem mit Passwort Login Java Basics - Anfänger-Themen 3
F Switch Case Problem mit Regex lösen? Java Basics - Anfänger-Themen 6
CT9288 Mini Anfänger-Problem mit loops, statements und ; Java Basics - Anfänger-Themen 4
C Two-Center Problem in Java Java Basics - Anfänger-Themen 0
H regex-Problem Java Basics - Anfänger-Themen 2

Ähnliche Java Themen

Anzeige

Neue Themen


Oben