Java Array Copy

[Boeby]

Hi @ all,

Hab da kurz eine Frage:
In Java wird ja alles per Value übergeben und nicht per Reference. So auch ein Array.
Da der Wert eines Arrays aber die Referenz dazu ist, wird quasi doch per Reference übergeben.
Wie erstelle ich nun am besten ein Copy eines Arrays ?

Zur Verdeutlichung meines Problems:

	public static void main(String[] args) {
		int[] array = { 55, 07, 78, 12, 42, 43, 51, 1, -1, 6, 3, 18 };
//		 int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
//		 int[] array = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};

		for (int a : array) {
			System.out.println(a);
		};
		System.out.println("Die Anzahl durchläufe im Bubblesort sind " + bubbleSort(array));
 		System.out.println("Die Anzahl durchläufe im Quicksort sind " + quickSort(array, 0, array.length-1, 0));
		System.out.println("Die Anzahl durchläufe im Bucketsort sind " + bucketSort(array, 80));
		System.out.println("Die Anzahl durchläufe im Insertionsort sind " + insertionSort(array));
		System.out.println("Die Anzahl durchläufe im Mergesort sind " + mergesort(array, 0, array.length-1));
		for (int a : array) {
			System.out.println(a);
		};
		// InsertionSort(n*n), SelectionSort(n*n) RadixSort, BucketSort(n+m=n),QuickSort(n*n)(best: n*logn), HeapSort(n*log n), MergeSort(n*log n)

Erklärung:
Man sieht hier das Erstellen eines neues Arrays, und die übergabe an mehrere Sortiermethoden. Nach der ersten Sortiermethode ist das Array allerdings sortiert. Eigentlich okay, aber ich möchte mit dem Anfangszustand in die nächste Methode..
Die Methoden sollten also das Array für sich kopieren und sortieren. Und nicht verändern..

Versteht man mein Problem ?
Wie übergebe ich nun eine Kopie des Arrays ?

 

[cx01]

Ich glaub, mit clone müsste das gehen. Also z.B:

System.out.println("Die Anzahl durchläufe im Bubblesort sind " + bubbleSort((int[])array.clone()));

 

[HaGGi.13]

Du könntest auch ein neues Array erstellen und dieses mit den Werten das anderen per for-Schleife Stück für Stück füllen.
Dann hast du eine neue Referenz des neuen Arrays aber die Werte des alten dort drin.

 

[ice-breaker]

In Java wird ja alles per Value übergeben und nicht per Reference. So auch ein Array.
Da der Wert eines Arrays aber die Referenz dazu ist, wird quasi doch per Reference übergeben.

äääh...
In Java wird alles bis auf die primitiven Datentypen (int, long, byte, ...) per Referenz übergeben

Wie erstelle ich nun am besten ein Copy eines Arrays ?

das ist abhängig vom Array und was darinsteckt
Wenn das Array Objekte enthält, soll die Kopie auf die gleichen Objekte verweisen oder auf Kopien der Objekte?
für ersteres: System.arraycopy
für zweiteres: clone

Versteht man mein Problem ?
Wie übergebe ich nun eine Kopie des Arrays ?

indem man eine Kopie erstellt

Du könntest auch ein neues Array erstellen und dieses mit den Werten das anderen per for-Schleife Stück für Stück füllen.
Dann hast du eine neue Referenz des neuen Arrays aber die Werte des alten dort drin.

System.arraycopy wäre deutlich effizienter

 

[Boeby]

Ja ne for-each wäre natürlich schon eine Lösung, aber ich habe gedacht da gäbe es was eleganteres.. Auch in Sachen Performance ists doch zimlich aufwendig, nach jeder sortierfunktion das array zu durchlaufen und kopieren..

äääh...
In Java wird alles bis auf die primitiven Datentypen (int, long, byte, ...) per Referenz übergeben

ääähm, ja da hast du Recht. Mein Fehler

das ist abhängig vom Array und was darinsteckt
Wenn das Array Objekte enthält, soll die Kopie auf die gleichen Objekte verweisen oder auf Kopien der Objekte?
für ersteres: System.arraycopy
für zweiteres: clone

Im jetzigen Fall sind es int's, danke aber für den Hinweis bezüglich dem Zusammenhang mit dem Inhalt. - Muss mir da noch Gedanken machen..

System.arraycopy wäre deutlich effizienter

Danke - Ich glaube danach habe ich gesucht..

Ergänzung (20. Juni 2010)

Ich habs jetzt so gelöst:
(Danke für die Berichtigungen)

public static void main(String[] args) {
int[] array = { 55, 07, 78, 12, 42, 43, 51, 1, 6, 3, 18 };
// int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
// int[] array = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};

int[] usearray = new int[array.length+1];
System.arraycopy(array, 0, usearray, 0, array.length);
for (int a : usearray)
System.out.println(a);
System.out.println("Die Anzahl durchläufe im Bubblesort sind " + bubbleSort(usearray));
System.arraycopy(array, 0, usearray, 0, array.length);
System.out.println("Die Anzahl durchläufe im Quicksort sind " + quickSort(usearray, 0, usearray.length-1, 0));
System.arraycopy(array, 0, usearray, 0, array.length);
System.out.println("Die Anzahl durchläufe im Bucketsort sind " + bucketSort(usearray, 80));
System.arraycopy(array, 0, usearray, 0, array.length);
System.out.println("Die Anzahl durchläufe im Insertionsort sind " + insertionSort(usearray));
System.arraycopy(array, 0, usearray, 0, array.length);
System.out.println("Die Anzahl durchläufe im Mergesort sind " + mergesort(usearray, 0, usearray.length-1));
for (int a : usearray)
System.out.println(a);
// InsertionSort(n*n), SelectionSort(n*n) RadixSort, BucketSort(n+m=n),QuickSort(n*n)(best: n*logn), HeapSort(n*log n), MergeSort(n*log n)
}

 

[1668mib]

Nein, in Java wird alles by value übergeben.
Die Frage ist nur: Was wird übergeben?

Beispiel:

void doSomething(MyClass o)
{
  o.setSomething(1);
}

Wirkt sich auch für den Aufrufer aus... das übergebene Objekt o wurde eventuell verändert.

Anderes Beispiel

void doSomething(MyClass o)
{
  o = new MyClass();
}

Hat keine Auswirkungen auf den Aufrufer... er erhält nicht das neue Objekt, weil die Adresse des Objekts o nun mal by value übergeben wird.


Im .C# gibt es deshalb auch noch echte Referenz-Parameter...

 

[kuddlmuddl]

Ich glaub du (mib) verwendest den Begriff by value anders als andere hier?
Wie du selbst sagst:

"weil die Adresse des Objekts o nun mal by value übergeben wird. "

Gerade das hätte ich jetzt als "by reference" verstanden/gelernt. Und zwar weil eben die Adresse übergeben wird.
In C++ wird per default eben nicht die Adresse sondern eine Kopie des gesamten Objektes in der Methode zur Verfügung gestellt. Das ist dann das, was ich (und scheinbar auch andere hier?) als by value verstanden hätten.

C++:
void doSomething(MyClass o)
{
  o.setSomething(1);
}

Sowas hätte eine katastrophale Laufzeit in C++ wenn MyClass viel Speicher benötigt. Bei jedem Methodenaufruf wird eine Kopie aller Attribute/Felder/Member(-variablen) von o (Typ: MyClass) angelegt.

"Üblich" (dh. by reference) wäre daher in C++

void doSomething(MyClass [B]&[/B]o)
{
  o.setSomething(1);
}

Das "&" ist in Java "überflüssig" (nicht möglich) weil eh immer alles (natürlich von primitiven Datentypen abgesehen) per Referenz übergeben wird. Echte Kopien sollte man immer per .clone() anlegen, wenn man sie braucht. (auch deep-copy genannt)

Ergänzung (21. Juni 2010)

@Topic:
Und um nochmal was zum Thema des eigentlichen Threads beizutragen.. wieso haben deine Sortieralgorithmen so viele Parameter?
Ich vermute mal, du nutzt so sachen wie array.length und 0 innerhalb der Methoden, damit rekursive Aufrufe wissen wo sie arbeiten sollen?
Mein Tipp wäre zu jeder Methode einen "Wrapper" zu implementieren.

Also eine einfache Methode

void quickSort(int[] array) {
    // hier den Aufruf mit allen wichtigen Argumenten. Also bei dir:
    quickSort(array, 0, array.length-1, 0);
}

Das hätte dann den Vorteil, dass alle Algorithmen leicht zu verwenden sind weil sie eine naheliegende und einheitliche Signatur haben. (Alle bekommen nur ein array als Argument)
Der Wrapper kümmert sich also quasi um die korrekte Verwendung deiner tatsächlich implementierten quicksort() Methode und bekommt nur das unsortierte Array.
Da man in Java Methoden überladen darf (gleicher Name aber unterscheidbar, da unterschiedliche Signatur) wäre das auch wunderbar lesbar

 

[1668mib]

@kuddlmuddl:
Ok, das ist nun offtopic :-)

Der Punkt ist, dass Java die Adresse des Parameters auf jeden Fall kopiert beim Aufruf... diese wird als by value übergeben. Dieses Beispiel zeigt den Sachverhalt nochmals:

public class ParamTest {
	public static void doSomething(MyClass c)
	{
		c.s = "doSomething";
	}

	public static void doEvenmore(MyClass c)
	{
		c = new MyClass();
		c.s = "doEvenmore";
	}

	public static void main(String[] args) {
		MyClass c = new MyClass();
		doSomething(c);
		System.out.println(c.s);
		doEvenmore(c);
		System.out.println(c.s);
	}
}

class MyClass
{
	MyClass() { s = ""; }
	public String s;
}

Welche Ausgabe wäre zu erwarten?


Hier mal der Vergleich in C#... Da sieht man den Unterschied mit ref...

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ParamTest
{
    public class MyClass
    {
        public MyClass() { s = ""; }
        public String s;
    }

    public class ParamTest
    {
        public static void doSomething(MyClass c)
        {
            c.s = "doSomething";
        }

        public static void doEvenmore(MyClass c)
        {
            c = new MyClass();
            c.s = "doEvenmore";
        }

        public static void doEvenmore2(ref MyClass c)
        {
            c = new MyClass();
            c.s = "doEvenmore";
        }

        public static void Main(String[] args) {
		    MyClass c = new MyClass();
		    doSomething(c);
            System.Console.WriteLine(c.s);
		    doEvenmore(c);
            System.Console.WriteLine(c.s);
            doEvenmore2(ref c);
            System.Console.WriteLine(c.s);

            System.Console.Read();
	    }
    }

}

 

[ice-breaker]

Ich glaub du (mib) verwendest den Begriff by value anders als andere hier?

er hat nicht unrecht, man kann Call-By-Reference verschieden auslegen.


Ein C(++)-Programmierer versteht unter Call-By-Reference (transformiert auf Java) z.B. folgendes:

Integer i = new Integer(4);
callSomeMethod(i);
assert(i.toInt() == 7) // true

public void callSomeMethod(Integer i) {
  i = new Integer(7);
}

also das er direkt auf der Referenz (Speicheradresse) arbeitet, wo das Objekt liegt.



Wobei es da dann auch die 2. Auffassung (bisher vertreten) gibt:

Integer i = new Integer(4);
callSomeMethod(i);
assert(i.toInt() == 4) // true

public void callSomeMethod(Integer i) {
  i = new Integer(7);
}

weil eigentlich nur eine Reference auf ein Objekt kopiert (Copy-By-Value) wird. Also i ist in der Methode ein Duplikat der Referenz auf das Objekt, sobald diese Referenz aber verändert wird, zeigt sie auf ein neues Objekt.
Der spezielle Fachbegriff dafür "Passing a reference by value."

In beiden Ansätzen arbeitet man mit einer Referenz des Objektes, aber sie unterscheiden sich eben doch noch inwieweit man mit der Referenz arbeiten kann.

Aber es ist trotzdem ganz klar kein Passing-By-Value weil sonst die Identitäten beider Objekte (i ausserhalb der Methode, und i innerhalb der Methode als Parameter) verschieden sein müssten, und das ist nicht der Fall.

 

[kuddlmuddl]

Ich wollt keine Detail-Diskussion lostreten - nur auf ein Missverständnis hinweisen^^

 

[DjNDB]

Ich würde die Methode Arrays.copyOf() verwenden, die es für verschiedene primitive Datentypen sowie generisch gibt. Die Klasse Arrays ist extrem praktisch, insbesondere wenn man mal schnell ein ganzes Array mit Werten ansprechend ausgegeben haben möchte.

 

[ice-breaker]

die Idee ist sehr gut!
nutzt intern System.arraycopy (effizient) und ist sehr leicht zu bedienen.

 

[Boeby]

@kuddlmuddl
Das ist schon okay. - Aus solchen Diskussionen kann ich viel lernen.. - Danke also für die Diskussion

Zur ersten Frage zurück:

System.out.println("Die Anzahl durchläufe im Bubblesort sind " + bubbleSort(array));
System.out.println("Die Anzahl durchläufe im Quicksort sind " + quickSort(array, 0, array.length-1, 0));
System.out.println("Die Anzahl durchläufe im Bucketsort sind " + bucketSort(array, 80));
System.out.println("Die Anzahl durchläufe im Insertionsort sind " + insertionSort(array));
System.out.println("Die Anzahl durchläufe im Mergesort sind " + mergesort(array, 0, array.length-1));

Also wird hier nicht das Array kopiert, sondern die Referenz - korrekt ? (Mein Hauptproblem war ja, dass sich das Array verändert )
Aus Speichersicht also kein grosser Unterschied ?

Und um nochmal was zum Thema des eigentlichen Threads beizutragen.. wieso haben deine Sortieralgorithmen so viele Parameter?
Ich vermute mal, du nutzt so sachen wie array.length und 0 innerhalb der Methoden, damit rekursive Aufrufe wissen wo sie arbeiten sollen?

Ja genau, es geht um die Rekursion. Dein Tipp mit dem Überladen ist natürlich gut. Ja es sind teilweise der Startpunkt im Array und auch das Ende.
Ich wollte hier die Laufzeit der einzelnen Algorithmen analysieren. (Bei der Rekursion kam ich jedoch an meine Grenzen - aber das ist ein anderes Thema..)


@1668mib

Funktioniert das in der Praxis ?

class MyClass
{
	MyClass() { s = ""; }
	public String s;
}

Das verstehe ich nicht.. Erst im Default-Konstruktor s als String benutzt und dann später definiert ??

 

[DjNDB]

Ich wollte hier die Laufzeit der einzelnen Algorithmen analysieren.

Deine Ausgabe spricht von einer "Anzahl Durchläufe" was so klingt als würdest du ausprobieren wie oft du einen Algorithmus in einer bestimmten Zeit laufen lassen kannst.

Es wäre wahrscheinlich aussagekräftiger wenn du ein größeres Array mit Zufallszahlen verwenden und die Zeit für das Sortieren je Algorithmus messen würdest. Dabei würde ich die Arraygröße so wählen, dass es beim schnellsten Algorithmus mindestens einige Sekunden dauert um den Messfehler gering zu halten.

Interessant wäre dann auch ein Vergleich deiner (eigenen?) Implementation mit dem optimierten Quicksort in Arrays.sort().

Ergänzung (21. Juni 2010)

Funktioniert das in der Praxis ?

class MyClass
{
	MyClass() { s = ""; }
	public String s;
}

Das verstehe ich nicht.. Erst im Default-Konstruktor s als String benutzt und dann später definiert ??

Was du da siehst ist deklarativ. Es gibt an der Stelle keinen Programmfluss, daher spielt auch die Reihenfolge keine Rolle. Es ist allerdings Konvention Instanzvariablen vor den Konstruktoren zu deklarieren.

 

[Boeby]

@DjNDB

Es geht mir hier nicht um die Zeit sondern mich interessieren die Anzahl der Vergleichsoperationen.
Landau-Notation, bzw nur das Big-O..
http://de.wikipedia.org/wiki/Landau-Symbole

Ich habe eigentlich ein Best-Case, Worst-Case und "durchschnittliches/zufälliges"-Verhalten analysieren wollen. Es sind sowenige Einträge damit ich das besser nachvollziehen kann..

Ich habe den Code mal hier hochgeladen:
Analyse.txt
(bin froh um comments, mir ist aber natürlich klar dass es vieles zum Verbessern gibt.. Es sollte lediglich funktionieren..)

 

[1668mib]

Mit dem Stil des Codes wollte ich auch sicher keine Preise gewinnen... ;-)

Aber wäre nicht eine Zeitmessung an sich nicht etwas aussagekräftiger als die Zahl der Vergleichsoperationen?

 

[nekro1]

In Rahmen meines Studiums habe ich die komplexitäten für die Sortierfunktionen (bubble, merge, quick... in Java berechnet. Glaube es war bis Arraygröße = 10000 Das ist schon lange her. Wenn du codes brauchst , kannst du sie haben.

 

[DjNDB]

Aber wäre nicht eine Zeitmessung an sich nicht etwas aussagekräftiger als die Zahl der Vergleichsoperationen?

Ich denke auch. Um die Laufzeitordnung per Simulation zu bestimmen wäre es
sinnvoller wie oben erwähnt große Arrays zu verwenden, und dann deren Größe deutlich zu variieren um zu sehen wie sich das auf die gemessene Dauer des Sortierens auswirkt.

Das kann man dann mit den theoretisch erwarteten Werten abgleichen oder zur grafischen Analyse schön plotten.

 

[ice-breaker]

Es geht mir hier nicht um die Zeit sondern mich interessieren die Anzahl der Vergleichsoperationen.
Landau-Notation, bzw nur das Big-O..
http://de.wikipedia.org/wiki/Landau-Symbole

und warum willst du die durch Testen herausfinden?
Immerhin kann man die alle wunderschön auf dem Papier beweisen, bekannt sind die Laufzeiten zudem auch noch.

Und eine sinnvollle Grenze für n ab der n*log(n)-Algorithmen besser sind als n^2 Algorithmen kann man durch testen ja auch nicht herausfinden (Stichwort: Microbenchmark)

 

[Boeby]

Naja, anstatt mit dem Debugger dass ganze manuell zu betrachten habe ich halt eine Variable eingeführt, die mir die Anzahl des vertauschen mitteilen soll.
Ich sollte ja irgendwie ein Gefühl für diese Algorithmen bekommen..
Das Ziel ist ja nicht dass ich jeweils den Worst-Case auswendig lerne, sondern dass ich verstehen kann weshalb ein Algorithmus n^2 ist, oder wieso auch nicht..
Klar beim BubbleSort ist das ja auch noch einfach zu sehen (2 Schleifen inneinander = n^2), aber es gibt ja auch schwierigere.. Ich muss dass ja auch für solche können die ich nicht gelernt habe..
PS: Internet habe ich an der Prüfung auch nicht..