InsertionSort mit Generics

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);
        }
    }
 

httpdigest

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

kneitzel

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

httpdigest

Top Contributor
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!
 

kneitzel

Top Contributor
Zum coden benutze ich Eclipse :) Ich schreibe mir mal eben einen Testfall und melde mich dann :)
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!
 

kneitzel

Top Contributor
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!
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)!
 

Kirby.exe

Top Contributor
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)
 

Kirby.exe

Top Contributor
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
 
X

Xyz1

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

kneitzel

Top Contributor
Warum? Ich sehe kein Problem mit List... Was übersehe ich?
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 ...
 

httpdigest

Top Contributor
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. :)
 
X

Xyz1

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

Xyz1

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

Meniskusschaden

Top Contributor
Und damit:
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.
hast du diese Aussage:
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.
erfolgreich widerlegt, denn du hantierst ja offensichtlich mit List<T> list.
 

kneitzel

Top Contributor
Ja das ist meistens so, wenn der Lehrer keine Ahnung hat. :(
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.
 
X

Xyz1

Gast
Und damit:

hast du diese Aussage:

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

Und ich hoffe jetzt sehr, dass das JDK da keine grottige Sortieralgorithmen verwendet die im Mittel O(n^2) bieten
Das JDK bietet schnelle Sortieralgorithmen an und wandelt aber vorher in ArrayList um (und dann zurück), falls der konkrete Typ noch nicht ist.
 

kneitzel

Top Contributor
Und damit:

hast du diese Aussage:

erfolgreich widerlegt, denn du hantierst ja offensichtlich mit List<T> list.

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
 

Kirby.exe

Top Contributor
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.
Wir werden zu dem Algorithmus nächste Woche in der Uni eine Laufzeit Analyse durchführen :)
 
X

Xyz1

Gast
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!
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
Anas Zufallszahlen & Laufzeitmessung (insertionSort) Allgemeine Java-Themen 5
X Insertionsort von Permutationen Allgemeine Java-Themen 5
P Generics und Arrays Allgemeine Java-Themen 6
M Generics / Typen Allgemeine Java-Themen 1
Kirby.exe Vererbung bei Generics Allgemeine Java-Themen 7
H Klarnamen etc... (von Wie Generics lernen?) Allgemeine Java-Themen 26
D Wie Generics lernen? Allgemeine Java-Themen 26
L Compiler-Fehler Generics beim Anhängen von Predicates Allgemeine Java-Themen 1
W Vererbung Generics - mal wieder die verhaßte Rückwärtskompatibilität Allgemeine Java-Themen 2
S Verstaendnisfrage Generics Allgemeine Java-Themen 19
W Generics + Vererbung Allgemeine Java-Themen 47
I Methoden Generics-Methode Allgemeine Java-Themen 3
D Mit Generics arbeiten - Übungsaufgabe Allgemeine Java-Themen 3
K Factory Pattern: Mit Generics umgehen Allgemeine Java-Themen 6
G Generics Allgemeine Java-Themen 31
perlenfischer1984 Liste mit generics zurück liefern Allgemeine Java-Themen 8
Hacer Generics & Collections Allgemeine Java-Themen 8
N Interface Generics für Enum-Filterung verwenden Allgemeine Java-Themen 5
H Collector Generics Problem (incl. Stream & Lambda) Allgemeine Java-Themen 4
C Gemeinsame Oberklasse zweier Generics Allgemeine Java-Themen 10
erdmann Datentypen Methodendeklaration mit Generics Allgemeine Java-Themen 2
Z Datentypen Verschachtelte Generics Allgemeine Java-Themen 1
N Datentypen Generics Allgemeine Java-Themen 5
S Mit Generics Klasse erstellen die selbst T erweitert..? Allgemeine Java-Themen 4
Tarrew Generics - Type erasure Allgemeine Java-Themen 5
N Problem mit Generics und Interface Allgemeine Java-Themen 4
H Generics als Parameter Allgemeine Java-Themen 1
kaoZ Generics und Vererbung Allgemeine Java-Themen 3
A Datentypen Generics: Wie am besten auf Typparameter zugreifen Allgemeine Java-Themen 2
C Generics Objekt in ArrayList Allgemeine Java-Themen 2
vandread Kleine Generics Aufgabe aus einer Prüfung... wie ist das gemeint? Allgemeine Java-Themen 6
G Generics sind zu streng - oder ich zu naiv? Allgemeine Java-Themen 3
G Verschachtelte Generics Allgemeine Java-Themen 2
O Generics Allgemeine Java-Themen 42
M Problem mit Generics Allgemeine Java-Themen 10
M Generics (bounded wildcards statt Interface Bezeichnern) -- Sinn oder Unsinn? Allgemeine Java-Themen 2
darekkay Generics: Wildcard und Object Allgemeine Java-Themen 5
H Collections Generics und Reflection Allgemeine Java-Themen 6
F Google Guice + Generics + Vererbung Allgemeine Java-Themen 5
H Problem mit Java Generics Allgemeine Java-Themen 6
J Generics: Typparameter als Klasse zurückliefern Allgemeine Java-Themen 4
H Generics Allgemeine Java-Themen 5
P Probleme mit Generics Allgemeine Java-Themen 5
B Generics und primitve arrays Allgemeine Java-Themen 6
M Generics Allgemeine Java-Themen 11
1 Collections Generics, internes Verhalten Allgemeine Java-Themen 16
T Warnungsfreie Verwendung von Generics Allgemeine Java-Themen 11
M Probleme mit Generics Allgemeine Java-Themen 5
D Java Generics Allgemeine Java-Themen 8
2 Generics: bounded wildcards Allgemeine Java-Themen 4
J Generics / vermeiden von downcasts Allgemeine Java-Themen 2
2 Generics oder nicht? Allgemeine Java-Themen 8
E Problem mit Generics und Comparable Allgemeine Java-Themen 16
W Erweitern einer Klasse mit Generics Allgemeine Java-Themen 8
H Generics für Methode Allgemeine Java-Themen 14
N Überladen mit Hilfe von Generics Allgemeine Java-Themen 3
S Generics: Fuer Set<T> ein T-Klassenobjekt erhalten? Allgemeine Java-Themen 3
Q Der innere Typ von Generics? Allgemeine Java-Themen 3
N Generics-NullpointerException Allgemeine Java-Themen 7
2 Generics - Typ Allgemeine Java-Themen 12
P Generics Problem Allgemeine Java-Themen 10
S Type safety Warnings beim casten von Generics Allgemeine Java-Themen 6
N Generics Allgemeine Java-Themen 3
V Frage zu Generics Allgemeine Java-Themen 2
S java generics klassen deklaration Allgemeine Java-Themen 7
B hashtable für unterschiedliche Typen - mit Generics Allgemeine Java-Themen 8
E Generics Allgemeine Java-Themen 3
MQue Generics Allgemeine Java-Themen 4
R Problem mit Reflection und Generics Allgemeine Java-Themen 3
C Klassen, die aufeinander verweisen (mit Generics) Allgemeine Java-Themen 16
G Generics - W.card unter Nutzung von Annotationsklasse? Allgemeine Java-Themen 6
G sortieren von generics Allgemeine Java-Themen 10
G Generics in Map. Type of value abhängig vom key Allgemeine Java-Themen 3
A Generics Verständnisfrage Allgemeine Java-Themen 7
Z Generics funzt nicht? Allgemeine Java-Themen 2
T Generics Allgemeine Java-Themen 18
G ComboBox: Nur eine Art Klasse zulassen (Generics) Allgemeine Java-Themen 3
J Generics Expertenwissen? Allgemeine Java-Themen 5
S Generics-Problem Allgemeine Java-Themen 3
T Generics und Wil-dcards Allgemeine Java-Themen 8
Q Typen von Generics & Casten Allgemeine Java-Themen 3
S Generics Allgemeine Java-Themen 2
R Problem mit Generics Allgemeine Java-Themen 2
G Trotz Generics Cast-Fehler! Allgemeine Java-Themen 5
T TreeMap durch Comparator mit Generics sortieren Allgemeine Java-Themen 9
T Generics und instanceof Allgemeine Java-Themen 10
T Generics und Exceptions Allgemeine Java-Themen 6
M Beliebig viele Typen bei Generics Allgemeine Java-Themen 3
G Reflection objekt mit generics erzeugen Allgemeine Java-Themen 5
S Singleton Pattern mit Generics Allgemeine Java-Themen 4
G Generics und Comparable Allgemeine Java-Themen 11
H Generics Problem Allgemeine Java-Themen 3
F Generics: spricht etwas dagegen raw types zu verwenden? Allgemeine Java-Themen 31
M Generics - besser programmieren, Warnung umgehen Allgemeine Java-Themen 4
E Java, UML, Generics Allgemeine Java-Themen 6
P Array von Vectoren + Generics Allgemeine Java-Themen 6
M ArrayList erweitern - generics Allgemeine Java-Themen 4
E Generics -> UML Allgemeine Java-Themen 4
G Generics: Instanzieren einer Klasse in einer Methode. Allgemeine Java-Themen 2
MQue getter- Methode, Generics Allgemeine Java-Themen 3

Ähnliche Java Themen


Oben