2d Array in Java schnell kopieren

cart · 29.05.2007

Wir sitzen hier grade an unserem Spiel und versuchen einige Sachen zu optimieren. Dabei liegt unser Augenmerk grade auf einem 2 dimensionalen Array (int). Dies wird mehrere tausend mal dupliziert, um für die KI die zukünftigen Züge zu berechnen und, falls wir das optimieren können, können wir da sicherlich ein paar ms sparen. Bisher läuft der Spaß so:

Code:

public int[][] copyGrundriss() {
	int[][] copy = new int[zeilen][spalten];
	for(int i=0; i< zeilen; i++) {
		for(int j=0; j < spalten; j++) {
			copy[i][j] = grundriss[i][j];
		}
	}
	return copy;
}

grundriss.clone(); funktioniert leider nicht, da er da nur die Referenzen kopiert und das ist absolut inaktzeptabel, da wir das Array natürlich bearbeiten und somit auch das Ausgangsarray.
Hat jemand eine Idee?

MegaVolt · 29.05.2007

System.arraycopy

Bist du wirklich ganz sicher dass array.clone() nur eine Object ID vergibt? Hab das anders in Erinnerung ...

cart · 29.05.2007

Dann hast du es scheinbar falsch in Erinnerung. Wir konnten es auch nicht glauben, aber der Debugger zeigte eindeutig die selben IDs. Kann dir gerne einen Screenshot hier posten.
Arraycopy funktioniert zwar für 1 dimensionale Arrays gut, aber bei mehr dimensionalen muss man das auch verschachteln, so dass es letztendlich auf das selbe rauskommt wie 2 for-loops.

Sholvar · 29.05.2007

also k.A. wo ich jetzt das genaue API für die Arrays finde, aber bei Objekten und allen dazugehörigen Klassen steht jeweils sowas drin:

clone() - Method in class java.lang.Object
Creates and returns a copy of this object.

klingt für mich, als wenn er nen komplett neues Objekt anlegt. Alles andere wäre ja auch irgendwie sinnlos. Für ne reine Referenzübergabe brauchts doch keine clone()-Methode.

Oder meinst du, dass eure Feld-Elemente Objekte sind und diese Referenzen nur kopiert werden?

Dann könnte man doch sowas machen wie

Code:

for(int Zeile blablubb)
    for(int Spalte (blablubb)
        neuesFeld[Zeile][Spalte] = altesFeld[Zeile][Spalte].clone();

cart · 29.05.2007

Wir wissen auch was in der API steht und wir sehen was der Debugger hinterher ausspuckt.

Dein Vorschlag ist genau das, was wir bisher tun und das ist nicht sehr performant.

Shihatsu · 29.05.2007

Also, clone dacht ich auch sofort, dann copy, dann hab ich beides gecheckt und hab den hier gezogen:

:eek3:

also mal wen angehaun, der 10 jahre mehr java aufm buckel hat, das war seine antwort:

Das einzige was mir da noch einfällt ist Multithreading.
Damit es schneller geht, könnte man die 2., innere Schleife als Thread losschicken.
Dafür brauchts freilich ne ganze Menge Hirnschmalz.

Bei der Aufgabe (füllen eines 2d Arrays) gibt’s auf jeden Fall Potenzial zum *echten* parallelen Rechen.
Und wenn auch nur je Zeile (i) ein Thread.
copy[][] darf dann aber auf KEINEN FALL synchronized sein, vielmehr müsst Ihr selbst schauen, dass die Threads Bereiche nicht mehrmals beschreiben….

…eine schöne Aufgabe!!

nunja... hilft dir das? :8[:

cart · 29.05.2007

Die Idee ist toll, aber das Array ist maximal 10*10 Felder groß. Dafür einen extra Thread bzw. mehrere anzuwerfen... Weiß nicht, ob es das bringt. Denke das ist eher mit einer dicken Kanone auf einen verdammt kleinen Shizu

Sholvar · 29.05.2007

Code:

public class Arraykopieren{
    public static void main(String[] args){
         ArrayElement[] Feld = new ArrayElement[10];
         
         for(int i=0; i< Feld.length; i++){
             Feld[i] = new ArrayElement();
         }
         
         ArrayElement[] Feld2 = Feld.clone();
         
         System.out.print(Feld + "---" + Feld2);

    }
}

erzeugt mir nen neues Element. Führt das einfach mal aus. 2 verschiedene Feld-Adressen.
Was aber identisch bleibt ist die Referenz auf die einzelnen Elemente, denn clone soll ja 1 zu 1 in das neue Feld-"Objekt" kopieren, was in den einzelnen Elementen steht.
Es bleibt dir also garnix anderes übrig, als neue Elemente zu erzeugen. Das macht deine Zählschleife oben aber auch nicht, denn die kopiert nur die Referenzen (was clone() ja auch macht).
Deshalb wollte ich halt wissen, ob du einfach das Feld kopieren willst oder ob du nen neues Feld mit neuen Elementen brauchst die einfach nur an der selben Stelle liegen, wie beim alten Feld.

Felder beschreiben hat nunmal immer nen Aufwand von Anzahl_Elemente*Anzahl_Feld_Dimensionen. Sogar wenn die clone() euch das abnehmen würde, würde es genauso lange dauern.
Du kannst aber durch if()s die Zahl etwas reduzieren in dem du nur dort überhaupt was machst, wo es sich nach dem alten Feld lohnt.

und nur mal als klugscheisserischer Ansatz nebenbei (das habt ihr ja sicher schon berücksichtigt

):
Wenn du wirkliche performance willst, macht es sich soweit ich weiss übrigens besser, das Feld als Koordinaten-Variablen in den einzelnen Spielsteinen zu lagern und diese einfach in nem Container zu sammeln. Koordinaten sind nämlich einfache int's und kein neues Objekt. Dann braucht man auch nur die überhaupt relevanten Elemente abgrasen, wenn man was sucht, sortiert oder kopiert und nicht die ganzen leeren Plätze auf dem Feld.

cart · 29.05.2007

Das Array ist ein reines int-Array (sieht man ja oben im Code) und bei primitiven Datentypen wird nicht die Referenz, sondern der Wert kopiert. Deshalb wird in der Lösung mit den 2 For-Schleifen nicht die Referenz des ints kopiert, sondern sein Wert. Es ist also schon was anderes als clone(). clone() kopiert _nur_ die Referenz. Egal was für ein Datentyp. Du kannst es ja mal mit einem Debugger ausprobieren, so wie Shizu es getan hat.

Zum letzten Absatz: Ja das haben wir berücksichtigt

Busta_inaktiv · 29.05.2007

Original geschrieben von cart
Arraycopy funktioniert zwar für 1 dimensionale Arrays gut, aber bei mehr dimensionalen muss man das auch verschachteln, so dass es letztendlich auf das selbe rauskommt wie 2 for-loops.

omg. arraycopy IST SCHNELLER als eine Kopie by element. Dein mehrdimensionales Array besteht aus vielen eindimensionalen, daher ist arraycopy natürlich schneller als verschachtelte Loops: Verschachtelung - 1.

Eine zweite, allerdings zweifelhafte, Performancesteigerung liegt in der Natur Javas: die OutOfBounds-Überprüfung. Fängt man um die for-Schleifen eine ArrayIndexOutblabla kann man dafür die for-Bedingung vollständig einsparen:
try{
for (int i = array.length; ; --i);
} catch (ArrayIndex... e) {}

Der Einsparung steht das häufige aufwändige Werfen einer Exception gegenüber, also von der Anzahl der Durchläufe/Elemente abhängig; außerdem maschinen-/softwareabhängig.
Nachteil: Verschandelung des Codes, Javaprinzipien werden gebrochen

Da es sich bei dir um recht kleine Arrays handelt lohnt sich die Exception-Methode wohl nicht (bei größeren wäre es der Fall); arraycopy ist aber auf jeden Fall weitaus schneller.

P.S. Es ist klar zu erkennen: du studierst an einer FH.

IPSWiZarD · 29.05.2007

darf ich fragen worum es geht?
weik, wulff oder projekt beim bauer?

zum thema kann ich als etechniker leider nix beitragen sorry :heul:

Sholvar · 29.05.2007

okok.

nochmal mit 2 int feldern probiert.

Code:

public class Arraykopieren{
    public static void main(String[] args){
         int[] Feld = new int[10];
         
         //feld anlegen
         for(int i=0; i< Feld.length; i++){
             Feld[i] = (int)(Math.random()*100);
         }
         
         //feld kopieren
         int[] Feld2 = Feld.clone();
         
         //kontrollausgabe ob er auch wirklich alles kopiert hat
         for(int i=0; i< Feld.length; i++){
            System.out.println(Feld[i] + "---" + Feld2[i]);
         }
         
         //nochmal das erste feld verändert
         for(int i=0; i< Feld.length; i++){
             Feld[i] = (int)(Math.random()*100);
         }
         
         System.out.println("##################################");
         
         //und wieder ausgabe mit neuen werten, aber nur fürs erste feld
         for(int i=0; i< Feld.length; i++){
            System.out.println(Feld[i] + "---" + Feld2[i]);
         }

    }
}

macht er bei mir auch super.

*edit*
ah ich versteh wo das prob liegt, bei mehr dimensionen liegt im ersten array die zweite dimension drin... hm... 8[ ok, wird nich funzen ^^

Busta_inaktiv · 29.05.2007

Ist diese Tabelle stets quadratisch? Falls nicht, die Schleife über den kleineren Index laufen lassen und arraycopy auf die arrays des größeren loslassen.

Kurzer Test:

Code:

//Erstellung der Vorlagen
		for (int i = 0; i < 10; i++) {
			for (int j = 0; j < 10; j++) {
				vorlage[i][j] = i;
			}
		}

//Die Gewinnermethode:
		for (int i = 0; i < zeilen; i++) {
			System.arraycopy(vorlage[i], 0, copy[i], 0, spalten);
		}

bei 5000000 Wiederholungen auf meinem Rechner, in ms:
Laufzeit 10265 carts Methode aus dem ersten Post
Laufzeit 25532 exceptions fangen wie oben beschrieben
Laufzeit 8812 arraycopy = Gewinnermethode

Vergrößert man die Arrays auf 100x100 ist Exceptions-Fangen 13% schneller als reines arraycp (und doppelt so schnell wie cart), bei 1000x1000 25% usw.

The_Company · 29.05.2007

Mach das Array eindimensional.

EnimaN · 29.05.2007

ich habe keine ahnung von java, aber bei anderen sprachen kommt es ziemlich stark darauf an, wie ein array intern gespeichert wird (ersten zeilen oder erst spalten) - wenn man das erstmal weiß kann man wohl direkt ganze zeilen / spalten kopieren und ist um einiges schneller, als wenn man es transponiert bewerkstelligt.

Whcttyh · 29.05.2007

wie ist denn arraycopy implementiert?

4GT_DosX · 29.05.2007

Man mag es kaum glauben aber beim Kopieren von Arrays kommt es auch auf die Reihenfolge der for-Schleifen an. Testet mal mit nem Timer eine andere Schleifenreihenfolge und versucht so viel wie geht an den Bedingungen der Schleifen zu optimieren.

Eindimensionales Array mit komplizierter berechneter Laufvariable könnte auch was bringen.

Und zu der Idee ein rechenintensives Spiel in Java zu schreiben, kann ich euch einen (extrem hilfreichen) Tipp nicht ersparen:
INLINE ASSEMBLER!

Bronzegraf · 29.05.2007

Mal kurz eine Frage: Warum habt ihr euch denn gerade auf diese Stelle eingeschossen? Profiler benutzt und gesehen, dass dort einen Menge Rechenzeit verbraucht wird?

Wenn ihr jetzt da wirklich optimieren wollt, dann macht eine Kombination aus The_Companys und Bustas Vorschlag^^

Original geschrieben von [UEP]Xyz
wie ist denn arraycopy implementiert?

nativ

Sholvar · 29.05.2007

ich hab den thread zwar nicht erstellt, aber ich hab hier heute massenweise gelernt. das macht locker 2 monate 8:00 vorlesungen ausschlafen. thx dafür! :top2:

@Busta:
was mich jetzt noch interessieren würde. könntest du deine Lösungen auch für n-dimensionale Reihungen hinbekommen? vielleicht ist das total einfach, aber ich hab mir heute erstmal durchgelesen was exceptions sind xD ich bin müde. Der Thread hier ist morgen aber als erstes bei mir aufm plan. Also: geht das auch für n-dimensionen? und wenn ja wie.

Danke nochmal! ^^

PS: FHFTW! :elefant:

Picard · 29.05.2007

Original geschrieben von 4GT_DosX

Und zu der Idee ein rechenintensives Spiel in Java zu schreiben, kann ich euch einen (extrem hilfreichen) Tipp nicht ersparen:
INLINE ASSEMBLER!

java kann inline assembler? :eek3:

hätte ich das damals gewusst, als wir in alpro nen algo schreiben mussten für 14millionen lottoziehungen incl auswertung... 14sekunden bei mir - bestzeit

Busta_inaktiv · 29.05.2007

bronzegraf hat natürlich vollkommen recht, bevor wir uns auf schnelles kopieren einschießen.

Original geschrieben von Sholvar
@Busta:
was mich jetzt noch interessieren würde. könntest du deine Lösungen auch für n-dimensionale Reihungen hinbekommen? vielleicht ist das total einfach, aber ich hab mir heute erstmal durchgelesen was exceptions sind xD ich bin müde. Der Thread hier ist morgen aber als erstes bei mir aufm plan. Also: geht das auch für n-dimensionen? und wenn ja wie.

Meine Tipps sind implementationsabhängig, die "Reihungen" müsstest du konkretisieren. Aber was meinst du mit "Lösungen"?

Original geschrieben von 4GT_DosX
Man mag es kaum glauben aber beim Kopieren von Arrays kommt es auch auf die Reihenfolge der for-Schleifen an. Testet mal mit nem Timer eine andere Schleifenreihenfolge und versucht so viel wie geht an den Bedingungen der Schleifen zu optimieren.

krass, interessiert mich. hast du ein paar quellen zur hand?

cart · 29.05.2007

@IPS.WiZarD:
Bauer

@Company:
Unmöglich. Die Arrays um die es sich handelt sind immer unterschiedlich groß und der Aufwand stünde in keinem Verhältnis zum Nutzen.

@Bronzegraf:
Weil die Stelle offensichtlich eine relativ hohe Laufzeit hat bei ein paar tausend Aufrufen. Der Rest wird natürlich auch optimiert, aber hier wissen wir halt grad nicht so wirklich weiter.

@Busta:
Der letzte Tipp ist fein. Müsste man nur vorher checken welcher Index größer ist. Werde das morgen mal implementieren und austesten.

Whcttyh · 30.05.2007

krass, interessiert mich. hast du ein paar quellen zur hand?

je weniger durchläufe, desto eher sollte die schleife vorkommen denke ich.

mich würde trotzdem interessieren, wie arraycopy implementiert ist. wieso ist das schneller? klar ist, dass ein geschwindigkeitsvorteil dadurch entsteht, dass der index nicht berechnet werden muss. was sonst noch?

kann nen java compiler sowas eigentlich nicht optimieren?

Clawg · 30.05.2007

Original geschrieben von cart
@Company:
Unmöglich. Die Arrays um die es sich handelt sind immer unterschiedlich groß und der Aufwand stünde in keinem Verhältnis zum Nutzen.

Intern ist ein zweidimensionales Array auch nur ein eindimensionales Array mit array[y][x] == array[x + y * dimension]

krass, interessiert mich. hast du ein paar quellen zur hand?

Zum Vergrößern anklicken....

Es ist schneller ein array[y][x] mittels for(y) for(x) durchzulaufen als mit for(x) for(y).
Eben genau deshalb weil intern das Array eindimensional ist und java es auf array[x + y * dimension] uebersetzt. Laeuft man in der inneren Schleife ueber x ist jeder Zugriff ein Cache-Hit weil die CPU beim ersten Zugriff gleich mal eine ganze Reihe von Bytes in der Umgebung cached.

cart · 30.05.2007

Original geschrieben von Clawg
Intern ist ein zweidimensionales Array auch nur ein eindimensionales Array mit array[y][x] == array[x + y * dimension]

Das ist schön. Trotzdem wird in dem Programm überall mit einem 2d-Array gearbeitet und es der Nutzen stünde in keinem sinnvollen Verhältnis zu dem Aufwand das alles umzuschreiben.

Clawg · 30.05.2007

achso, ich dachte du meinst den Rechenaufwand

Busta_inaktiv · 30.05.2007

thx claw.

Original geschrieben von cart
@Bronzegraf:
Weil die Stelle offensichtlich eine relativ hohe Laufzeit hat bei ein paar tausend Aufrufen. Der Rest wird natürlich auch optimiert, aber hier wissen wir halt grad nicht so wirklich weiter.

Mit solchen Aussagen muss man vorsichtig sein, was wirklich lange dauert ist a priori kaum zu sehen. Versucht's mal, kostenlose Profiler gibt's genug.

RRA^StArFiRe · 30.05.2007

Original geschrieben von cart

@Company:
Unmöglich. Die Arrays um die es sich handelt sind immer unterschiedlich groß und der Aufwand stünde in keinem Verhältnis zum Nutzen.

die arrays sind immer unterschiedlich groß?
aber du musst die bei initialisierung doch festsetzen. arbeitest ja schließlich nicht mit vektoren.

machs mit einem vektor, ist zwar nicht mehr so schön matrizen-übersichtlich, aber viel effizienter. kommt letzendlich nur n zeile und spaltenzugriffsberechnung ála [x][y]:= arr[y*spalten + x] raus. oder andersrum, je nachdem wie ihr euch das denkt.
oder denkt euch nen anderen algorithmus aus.
oder machts in C

The_Company · 30.05.2007

Original geschrieben von Clawg
Intern ist ein zweidimensionales Array auch nur ein eindimensionales Array mit array[y][x] == array[x + y * dimension]

Wenn man keine Ahnung hat...

Intern is ein 2D-Array implementiert als ein Array von Arrays.
Du kannst also array[1] = int[10]; array[2] = int[20]; tun. Was auch der Grund ist warum arraycopy nicht funktioniert.

Original geschrieben von Clawg
Es ist schneller ein array[y][x] mittels for(y) for(x) durchzulaufen als mit for(x) for(y).
Eben genau deshalb weil intern das Array eindimensional ist und java es auf array[x + y * dimension] uebersetzt. Laeuft man in der inneren Schleife ueber x ist jeder Zugriff ein Cache-Hit weil die CPU beim ersten Zugriff gleich mal eine ganze Reihe von Bytes in der Umgebung cached.

Bullshit, solange Du nen guten Compiler hast und nicht den L1 Cache ausreizt, und das tust Du mit nem 10x10 int Array (400 Bytes) definitiv nicht.
Du hast allerdings recht, dass es bei groesseren Arrays nen Problem wird, oder wenn die Arrays aus unterschiedlichen Memory Regionen kommen (was Du aber nicht wusstest, s.o.

)

The_Company · 30.05.2007

Original geschrieben von cart
@Company:
Unmöglich. Die Arrays um die es sich handelt sind immer unterschiedlich groß und der Aufwand stünde in keinem Verhältnis zum Nutzen.

Du koennntest doch einfach ne Wrapper-Klasse drumrum machen mit nem Accessor, sowas wie:

Code:

class MeinArray {
  int zeilen, spalten;
  int[] array;
  MeinArray (zeilen, spalten) {
    array = new int[zeilen*spalten];
  }
  int get (int x, int y) { return array[x + y * spalten] };
}

Damit haste dann dein eindimensionales Array und mit dem refactoring von Eclipse muesste das auch ziemlich schnell gehen.
Die Frage ist nur, ob sich das lohnt in Sachen Performance.

Busta_inaktiv · 30.05.2007

Original geschrieben von The_Company
Bullshit, solange Du nen guten Compiler hast und nicht den L1 Cache ausreizt, und das tust Du mit nem 10x10 int Array (400 Bytes) definitiv nicht.
Du hast allerdings recht, dass es bei groesseren Arrays nen Problem wird, oder wenn die Arrays aus unterschiedlichen Memory Regionen kommen (was Du aber nicht wusstest, s.o. )

Am Fakt, dass ein Zugriff auf array[y][x] mittels for(y) for(x) schneller ist als umgekehrt ändert das allerdings nichts:
50000000 Wiederholungen auf 10x10, Body der inneren "if (vorlage[k][j] == 0);" :
34891ms vs. 27344

Sholvar · 30.05.2007

ist ja auch irgendwie logisch, wenn man bedenkt, dass [y] das eigentliche Array enthält in dem die anderen Arrays verschachtelt sind, oder nich?

@Busta: Mit Lösung meine ich diese "Gewinnermethode". Geht die auch für n-dimensionale Reihungen? Dann muss man ja eigentlich doch wieder n-1 Zählschleifen rumbauen und kann nur die innerste Dimension kopieren, oder?

MegaVolt · 30.05.2007

schließe mich der mach-es-eindimensional-und-nutze-arraycopy an
oder, wenn ihr wert auf performance legt, nutzt c++

The_Company · 30.05.2007

Original geschrieben von Busta

Am Fakt, dass ein Zugriff auf array[y][x] mittels for(y) for(x) schneller ist als umgekehrt ändert das allerdings nichts:
50000000 Wiederholungen auf 10x10, Body der inneren "if (vorlage[k][j] == 0);" :
34891ms vs. 27344

Dann hat Java keinen guten Compiler :ugly:

Clawg · 30.05.2007

Wobei man Java zugute halten muss, dass es mitlerweile recht schnell geworden ist. Bei meinem letzten Programm war Java (der normale Compiler von Sun) gerade mal um einen Faktor 2 langsamer/speicherintensiver als ein aequivalentes C/C++ Programm.
Was Optimierung betrifft wuerde ich mich nicht als Java-Experte bezeichnen wuerde, weshalb wohl noch etwas mehr drin gewesen waere

4GT_DosX · 01.06.2007

Da hab ich ja was losgetreten:
Assembler und Java passen aus verschiedenen Gründen als Programmiersprachen eigentlich nicht zusammen.
Java setzt auf eine Virtual Machine auf, die die Programme quasi noch eine Ebene weiter von der Hardware wegbewegt. In diese Sprache Assembler einzubauen, kann (meiner Meinung nach) keine großen Erfolge bringen. Java ist auch der Versuch durch eben diese Virtual Machine eine Unabhängigkeit vom Betriebssystem zu erreichen, wogegen Assembler immer genau auf die jeweiligen Mikroprozessorarchitekturen zugeschnitten ist - genau das Gegenteil eben.

Genug geredet, es geht anscheinend trotzdem in eingeschränkter Form:
http://asm.objectweb.org/
http://java-source.net/open-source/bytecode-libraries

Das ganze war von mir eher scherzhaft als Seitenhieb auf C/CPP gedacht, ob sich das ganze lohnt, ist schwer zu sagen.

4GT_DosX · 01.06.2007

Noch was allgemeines zu Optimierungen:

Techniken:
-Schleifen aufrollen/loop unrolling
-Schleifen verschmelzen
-Verzweigungen eliminieren
-Schleifen vertauschen

Hans2000 · 01.06.2007

Code:

public static final int[][] copyArray (int[][] data)
{
        int[][] copy = (int[][])data.clone();
        for (int i = data.length - 1; i >= 0 ; i--)
        {
            if (data[i] != null)
                copy[i] = (int[])data[i].clone();
        }
        return copy;
}

Wie wärs damit?

cart · 01.06.2007

Ich hoffe du hast dich nicht extra wegen dem Post registriert...

Hans2000 · 01.06.2007

evtl...

2d Array in Java schnell kopieren

Technik/Software Forum

Technik/Software Forum

Technik/Software Forum

Administrator

Technik/Software Forum

Technik/Software Forum

Busta_inaktiv

Guest

Busta_inaktiv

Guest

The_Company

Guest

4GT_DosX

Guest

Bronzegraf

Guest

Busta_inaktiv

Guest

Technik/Software Forum

Clawg

Guest

Technik/Software Forum

Clawg

Guest

Busta_inaktiv

Guest

RRA^StArFiRe

Guest

The_Company

Guest

The_Company

Guest

Busta_inaktiv

Guest

The_Company

Guest

Clawg

Guest

4GT_DosX

Guest

4GT_DosX

Guest

Technik/Software Forum