InsertionSort mit Generics

Kirby.exe

Kirby.exe

Top Contributor
Also ich habe die Aufgabe eine generische InsertionSort Methode zu schreiben und stehe auf dem Schlauch xD In der Testumgebung wird keine Java Errormeldung geworfen, sondern es kommt lediglich die folgende Meldung:

Bildschirmfoto 2020-04-06 um 13.57.51.png

Dies kann zum Beispiel an einem Runtime Error liegen (Endlosschleife,....).

Hier ist mal mein Code:

Java: 
public static <T extends Comparable<? super T>> void sort(List<T> list) {
        T keyValue;
        int j;
        for(int i = 0; i < list.size(); i++){
            keyValue = list.get(i);
            j = i--;
            while(j >= 0 && list.get(j).compareTo(keyValue) == 1) {
                list.add(j+1, list.get(j));
                j--;
            }
            list.add(j+1, keyValue);
        }
    }
 
Hol' dir zuerst einmal eine Desktop-basierte IDE. Dein Programm verursacht vermutlich/vielleicht eine Endlosschleife, der Prozess beendet sich also nicht und somit gibt dir (vermutlich) die Web-basierte IDE diese Fehlermeldung.
 
Ja, gut erkannt. So ist denn die Endlosschleife?

Du hast eine Schleife, in der Du von i = 0 weiter gehst so lange i < list.size() und i wird immer um 1 erhöht.

Und dann fügst Du der List mindestens ein Element hinzu. Aber du nimmst nie ein Element raus.

Also i = 0. Du nimmst das Element mit Nummer 0. Dann ist j nicht größer als 0. Also fügst Du das Element hinzu - und zwar an Stelle 0. 0 -1 + 1 = 0 Wenn die Liste 4 Element hatte, dann hat sie nun 5.

Interessant wird es noch bei der While Schleife ... dann kannst Du noch richtig viele Elemente bekommen 🙂

Dadurch das Du immer mindestens 1 Element hinzu fügst und i nur um 1 erhöht wird, hast Du eine Endlosschleife.
 
i wird sogar wieder um 1 reduziert, bleibt also effektiv immer bei 0:
Java: 
        for(int i = 0; i < list.size(); i++){ // <- inkrement
            keyValue = list.get(i);
            j = i--; // <- dekrement!
 
Kirby_Sike hat gesagt.:
Zum coden benutze ich Eclipse 🙂 Ich schreibe mir mal eben einen Testfall und melde mich dann 🙂
Zum Vergrößern anklicken....
Warum kannst Du das dann nicht testen? Code schreiben ohne jeden Test ist einfach nur Müll. Gleich von Anfang an abgewöhnen. Und es ist doch nun wirklich trivial, da eine kleine Applikation zu schreiben, die eine kleine Liste sortiert um dann das einmal auszuprobieren. Und dann hast Du auch einen Debugger zur Hand um mal Schritt für Schritt zu schauen, was Du da lustiges anstellst!
 
httpdigest hat gesagt.:
i wird sogar wieder um 1 reduziert, bleibt also effektiv immer bei 0:
Java: 
        for(int i = 0; i < list.size(); i++){ // <- inkrement
            keyValue = list.get(i);
            j = i--; // <- dekrement!
Zum Vergrößern anklicken....
Ohm das habe ich ganz übersehen ... Hatte ich irgendwie als j = i - 1; gelesen. Dann kann man Kirby gleich noch abwatschen, was er so einen Code schreibt. Goldene Regel - speziell für Anfänger aber auch generell für Clean Code: Incrementor (egal ob pre oder post) immer nur als eigenständiges Statement und wirklich NIEMALS innerhalb einer Zeile.

Es ist ja gut und richtig, das ihr lernt und versteht, wie das funktioniert. Aber nutzt es einfach nicht in eurem Code (es sei denn, es ist explizit verlangt)!
 
Immerhin habe ich jetzt eine Errormeldung xD
Code: 
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at java.base/java.util.Arrays.copyOf(Arrays.java:3720)
    at java.base/java.util.Arrays.copyOf(Arrays.java:3689)
    at java.base/java.util.ArrayList.grow(ArrayList.java:237)
    at java.base/java.util.ArrayList.grow(ArrayList.java:242)
    at java.base/java.util.ArrayList.add(ArrayList.java:517)
    at InsertionSort.sort(InsertionSort.java:20)
    at InsertionTest.main(InsertionTest.java:15)
 
Habe es gelöst....Hat jemand ein Brett für mich, welches ich mir vor den Kopf hauen kann? xD Man sollte natürlich die richtige Methode benutzen xD set und nicht add....Ich fühle mich einfach nur dumm xD
 
Lol, und als nächstes werde ich meine WBK verlieren, weil ich nun als Gewalttäter abgestempelt werde, der andere wegen Lapalien körperlich angreift 🙂
 
Es empfiehlt sich auch, den konkreten Typ sicherzustellen und nicht mit List<T> list zu hantieren. Falls sich dahinter keine ArrayList verbirgt sollte man in diese umwandeln.
 
thecain hat gesagt.:
Warum? Ich sehe kein Problem mit List... Was übersehe ich?
Zum Vergrößern anklicken....
Das frage ich mich gerade. Denn die Implementation gegen ein Interface würde ich sogar als das explizit bessere Design bewerten. Evtl. hat Tobias die Laufzeit des Algorithmus im Blick. Je nach List Implementation könnte es günstiger sein erst eine ArrayList zu bilden damit Zugriffe über die Id schneller sind.

Aber das sind dann Optimierungen... da würde ich ggf den Algorithmus generell überdenken ...
 
Da die Callsite sowieso nur monomorphic ist, wird der JIT da direkt die ArrayList-Implementierungen/Methoden aufrufen und kein Dynamic Dispatch durch das Interface machen. Der dabei injizierte Laufzeittyp-Test kann absolut vernachlässigt werden. Es sei denn natürlich, dass die ganze Methode mit etwas anderem als einer RandomAccess List aufgerufen wird. 🙂
 
Java: 
	public static <T extends Comparable<? super T>> void sort(List<T> list) {
		for (int i = 0; i < list.size() - 1; i++) {
			int min = i;
			for (int j = i + 1; j < list.size(); j++) {
				if (list.get(min).compareTo(list.get(j)) > 0) {
					min = j;
				}
			}
			list.add(i, list.remove(min));
		}
	}

	public static void main(String[] args) {
		ArrayList<Integer> list1 = new ArrayList<Integer>();
		LinkedList<Integer> list2 = new LinkedList<Integer>();
		for (int i = 0; i < 1000; i++) {
			int r = Random.randInt(0, 1000);
			list1.add(r);
			list2.add(r);
		}
		long t0 = System.currentTimeMillis();
		sort(list1);
		long t1 = System.currentTimeMillis();
		sort(list2);
		long t2 = System.currentTimeMillis();
		System.out.println(list1.size());
		System.out.println(list2.size());
		System.out.println(t1 - t0);
		System.out.println(t2 - t1);
	}

Code: 
1000
1000
26
874

ArrayList ist etwa 34mal so schnell wie LinkedList - und das bei nur 1000 Elementen (und bei meiner nicht besonders effizienten Implementierung), bei noch mehr Elementen ist der Unterschied noch wesentlich dramatischer.
 
Und bevor mir jetzt wieder jemand vorwirft, schlechter Test, keine Aufwärmphase usw. ... dem kann ich nur erwidern, dass im Code die ArrayList Variante zuerst aufgerufen wurde...
 
Und damit:
Tobias-nrw hat gesagt.:
ArrayList ist etwa 34mal so schnell wie LinkedList - und das bei nur 1000 Elementen (und bei meiner nicht besonders effizienten Implementierung), bei noch mehr Elementen ist der Unterschied noch wesentlich dramatischer.
Zum Vergrößern anklicken....
hast du diese Aussage:
Tobias-nrw hat gesagt.:
Es empfiehlt sich auch, den konkreten Typ sicherzustellen und nicht mit List<T> list zu hantieren. Falls sich dahinter keine ArrayList verbirgt sollte man in diese umwandeln.
Zum Vergrößern anklicken....
erfolgreich widerlegt, denn du hantierst ja offensichtlich mit List<T> list.
 
Tobias-nrw hat gesagt.:
Ja das ist meistens so, wenn der Lehrer keine Ahnung hat. 🙁
Zum Vergrößern anklicken....
Ja, so Aussagen kommen immer, wenn Leute keine Ahnung haben 🙁

Also wenn man jemandem etwas beibringen will, dann wird man - zumindest in der Schule - langsam heran geführt. Da wird so ein Algorithmus erst einmal implementiert. Mögliche Probleme werden dann angesprochen, wenn die Schüler den Algorithmus verstanden haben.

Ansonsten ist das auch aus meiner Sicht relativer Murks. Nehmen wir einfach den Fall: Wir haben die Aufgabe bekommen, eine solche Funktion zu schreiben. Dann hätten wir den Code wie vorgestellt geschrieben. Unit Test Erfolgreich. Es Funktioniert ja. Selbst auf LinkedList funktioniert es - wenn auch schlecht.

Jetzt stellen wir fest: Es ist zu langsam. Was machen wir?
Nein, wir frickeln nicht einfach eine Lösung dran. Wir analysieren es. Die erste Frage ist halt direkt: Braucht es eine Linked List an der Stelle? Das Kernproblem ist nicht der Algorithmus, sondern das wir Daten in einer LinkedList halten, die wir sortieren wollen.
Aber heya - wir haben gegen Interfaces implementiert. Also eine Sache von wenigen Minuten das zu beheben.

Und wenn die LinkedList aus gutem Grund verwendet wurde (Mir fällt nichts ein ... Speicherplatz? Wenn Speicherplatz eng ist, dann ist ein umkopieren auch nicht machbar ....) dann würde ich dieses Performance-Thema als solches betrachten. Und dann ist der Algorithmus als solcher schon zu ersetzen. Und ohne da jetzt im Detail dem nachzugehen: Wenn ich es eh umkopiere in eine andere Struktur, dann kann diese Struktur doch gleich beim Insert sortiert einfügen und ich dürfte etwas performanter sein. Aber das ist etwas, das man kaum noch macht, da diese Art von Algorithmen in der Regel bereits fertig nutzbar vorhanden sind. (Und ich hoffe jetzt sehr, dass das JDK da keine grottige Sortieralgorithmen verwendet die im Mittel O(n^2) bieten.
 
Meniskusschaden hat gesagt.:
Und damit:

hast du diese Aussage:

erfolgreich widerlegt, denn du hantierst ja offensichtlich mit List<T> list.
Zum Vergrößern anklicken....
Was laberst du? Ich habe lediglich gezeigt wie man es nicht machen sollte.

JustNobody hat gesagt.:
Und ich hoffe jetzt sehr, dass das JDK da keine grottige Sortieralgorithmen verwendet die im Mittel O(n^2) bieten
Zum Vergrößern anklicken....
Das JDK bietet schnelle Sortieralgorithmen an und wandelt aber vorher in ArrayList um (und dann zurück), falls der konkrete Typ noch nicht ist.
 
Meniskusschaden hat gesagt.:
Und damit:

hast du diese Aussage:

erfolgreich widerlegt, denn du hantierst ja offensichtlich mit List<T> list.
Zum Vergrößern anklicken....

Nein, nicht wirklich. Er hat sich nur etwas ungünstig ausgedrückt. Er hat aufgezeigt, dass das Sortieren einer LinkedList über so einen Algorithmus grausig ist. Auf Grund der sehr schlechten Zugriffszeiten beim Zugriff über den Index ist seine Aussage ja lediglich, dass man vor dem sortieren erst eine Umwandlung in eine ArrayList machen sollte um diese dann zu sortieren.

Wäre eine Optimierung. So Optimierungen machen aber halt Lehrer, die keine Ahnung haben. Andere analysieren das Problem und lösen das Problem selbst. Und wenn das JDK das machen sollte: Ja, die haben halt andere Anforderungen: Die haben keinen Zugriff auf den Code, der die Daten bereit stellt und die Anforderung ist halt: LinkedList muss auch möglichst schnell sortiert werden. Da ist die Umwandlung durchaus interessant. Aber ich würde da dann ggf. zu einem balanced binary tree sort greifen. Den zusätzlichen Speicherbedarf haben wir ja bei der Anforderung eh. Aber das Thema Sortieralgorithmen war zu lange kein Thema bei mir - das ist halt etwas, das man heute eigentlich nicht mehr selbst schreibt. Aber das übrige ich 08/15 Software-Entwicklung. Performance Optimierungen macht man nicht. Wenn, dann kommt erst eine Analyse und dann mit klar definierten Anforderungen eine Umsetzung. Aber so aus der Hüfte schießen und andere als Ahnungslos darstellen ist unüblich ...

Siehe dazu: https://clean-code-developer.de/die-grade/roter-grad/#Vorsicht_vor_Optimierungen
 
JustNobody hat gesagt.:
Ja, so Aussagen kommen immer, wenn Leute keine Ahnung haben 🙁

Also wenn man jemandem etwas beibringen will, dann wird man - zumindest in der Schule - langsam heran geführt. Da wird so ein Algorithmus erst einmal implementiert. Mögliche Probleme werden dann angesprochen, wenn die Schüler den Algorithmus verstanden haben.

Ansonsten ist das auch aus meiner Sicht relativer Murks. Nehmen wir einfach den Fall: Wir haben die Aufgabe bekommen, eine solche Funktion zu schreiben. Dann hätten wir den Code wie vorgestellt geschrieben. Unit Test Erfolgreich. Es Funktioniert ja. Selbst auf LinkedList funktioniert es - wenn auch schlecht.

Jetzt stellen wir fest: Es ist zu langsam. Was machen wir?
Nein, wir frickeln nicht einfach eine Lösung dran. Wir analysieren es. Die erste Frage ist halt direkt: Braucht es eine Linked List an der Stelle? Das Kernproblem ist nicht der Algorithmus, sondern das wir Daten in einer LinkedList halten, die wir sortieren wollen.
Aber heya - wir haben gegen Interfaces implementiert. Also eine Sache von wenigen Minuten das zu beheben.

Und wenn die LinkedList aus gutem Grund verwendet wurde (Mir fällt nichts ein ... Speicherplatz? Wenn Speicherplatz eng ist, dann ist ein umkopieren auch nicht machbar ....) dann würde ich dieses Performance-Thema als solches betrachten. Und dann ist der Algorithmus als solcher schon zu ersetzen. Und ohne da jetzt im Detail dem nachzugehen: Wenn ich es eh umkopiere in eine andere Struktur, dann kann diese Struktur doch gleich beim Insert sortiert einfügen und ich dürfte etwas performanter sein. Aber das ist etwas, das man kaum noch macht, da diese Art von Algorithmen in der Regel bereits fertig nutzbar vorhanden sind. (Und ich hoffe jetzt sehr, dass das JDK da keine grottige Sortieralgorithmen verwendet die im Mittel O(n^2) bieten.
Zum Vergrößern anklicken....
Wir werden zu dem Algorithmus nächste Woche in der Uni eine Laufzeit Analyse durchführen 🙂
 
Das hat mit der theoretischen Laufzeitkomplexitätsanalyse wenig zu tun, wohl aber mit der praktischen. 😉

Also nochmal, ja man kann die Funktionssignatur so lassen, und muss auch nicht immer nach ArrayList konvertieren, wenn es um theoretische Betrachtungen geht. Btw. gutes Gelingen!
 

Aktuelle Jobs

Neue Themen

Ähnliche Themen

InsertionSort sortiert erste Zahl im Array nicht mit?
Antworten: 6
InsertionSort Problem
Antworten: 2
Best&Worst Case bei Insertionsort
Antworten: 10
Ist das noch Insertionsort?
Antworten: 3
Zufallszahlen & Laufzeitmessung (insertionSort)?
Antworten: 2

Zurück
Oben