Du verwendest einen veralteten Browser. Es ist möglich, dass diese oder andere Websites nicht korrekt angezeigt werden. Du solltest ein Upgrade durchführen oder ein alternativer Browser verwenden.
mal ganz allgemein und Sprachunabhängig. Wie würdet ihr Strings in einer Liste alphanumerisch sortieren (händisch)?
Ich hab mir sowas wie splitten und inseration sort vorgestellt. Eventuell brauch ich ne 2 Liste. . . (Performanz und Speicherkomplexität erstmal hinten angestellt)
Habt ihr eventuell bessere Vorschläge für das Konzept?
Grundsätzlich sollte jede Sprache eine Möglichkeit bieten auf einer Liste eine Sortierung mit einem benutzerdefinierten Comparator aufzurufen. Ich verstehe die Frage nicht? Wie sortiere ich eine Liste - in dem ich einen Sortier-Algorithmus (Mergesort, Quicksort, ...) drauf anwende und dabei eine Vergleichfunktion verwende.
Wenn ich auf einem Blatt Papier eine Liste von Namen wie z. B.
Code:
Michael
Christopher
Jessica
Matthew
Ashley
Jennifer
Joshua
Amanda
Daniel
David
habe, dann könnte ich damit beginnen, mit den "kleinsten" Namen zu suchen. Ich fange also mit Michael an, merke mir den als den bislang kleinsten Namen, gehe weiter zu Christopher, stelle fest, dass der kleiner als Michael ist, merke mir somit Christopher als bislang kleinsten Namen usw. Wenn ich alle Namen durch habe, weiß ich, dass Amanda der kleinste Name ist.
Ich streiche also Amanda aus der Liste und schreibe mir den Namen ans Ende meiner bislang leeren, sortierten Liste. Damit wäre der erste Durchgang beendet. Im zweiten Durchgang wäre der kleinste Name dann Ashley, da Amanda schon gestrichen ist. In meiner sortierten Liste stünde: Amanda, Ashley. Den Vorgang wiederhole ich, bis alle Namen gestrichen sind.
Alternativ: statt den Namen zu streichen und in eine neue Liste einzutragen, könnte ich die Namen auch nummerieren. Amanda wäre die 1, Ashley die 2 usw.
Händisch (auf dem Papier) würde ich wahrscheinlich einen Mix aus Bubble und Insertion Sort verwenden.
Wenn ich's selbst programmieren müsste, würde ich Shell-Sort implementieren, der ist intuitiv und einfach, wenn man erst mal das Prinzip verstanden hat.
In der Praxis würde ich aber lediglich den Comparator schreiben (bei String nicht notwendig, da gibt's das schon) und Collections.sort(...) verwenden, aktuell wird dort - glaub ich - eine Tim-Sort verwendet, der sich sehr gut bewährt hat. Wenn mal was Besseres kommt, bauen sie das dann ein.
Mal angenommen, es gäbe keinen Comparator, wie würde man das aufziehen, wenn man zum Beispiel nach 'B' sortieren möchte oder nach einem beliebigen Buchstaben oder nach der Länge statt nach Alphabet?
Als Tipp für die Implementierung habe ich -1, 0, 1 bekommen.
Was nach meinen Verständnis nur mit 0(n²) umzusetzen wäre, also ne Art Bubblesort.
Letztlich sollte die Klasse alphanumerisch und nach Länge sortieren können und bestenfalls nichts aus dem Standart verwenden, da ich es nicht in Java machen soll.
Wie gesagt mein jetziger Stand ist das es alphabetisch sortiert, ich könnte aber noch ne Art Comparator gebrauchen, um mit dem gleichen Quicksort auch noch nach Länge/beliebigen Buchstaben sortieren kann
Mal angenommen, es gäbe keinen Comparator, wie würde man das aufziehen, wenn man zum Beispiel nach 'B' sortieren möchte oder nach einem beliebigen Buchstaben oder nach der Länge statt nach Alphabet?
Als Tipp für die Implementierung habe ich -1, 0, 1 bekommen.
Sortieren impliziert ja, dass es eine Ordnung gibt. Wie diese zustandekommt, spielt keine Rolle. Am Ende fragst Du also immer: ist x "kleiner" bzw. "größer" (im Sinne der Ordnung) als y.
Wenn ich z. B. eine Ordnung Z < Y < X < ... < B < A festlege, dann ist "Zeppelin" kleiner als "Asphalt" und das Ergebnis ist dann eine alphabetisch absteigend sortierte Liste.
Im Code musst Du also nur die Stelle, an der verglichen wird, ersetzen. Zum Beispiel durch eine compare-Methode, die zwei zu vergleichende Elemente als Parameter erwartet und -1 liefert, falls das erste Element "kleiner" (im Sinner der Ordnung) als das zweie Element ist, +1, falls es sich andersrum verhält und 0, fall die beiden Elemente gleich sind.
um Beispiel durch eine compare-Methode, die zwei zu vergleichende Elemente als Parameter erwartet und -1 liefert, falls das erste Element "kleiner" (im Sinner der Ordnung) als das zweie Element ist, +1, falls es sich andersrum verhält und 0, fall die beiden Elemente gleich sind.
was mich nur noch interessieren würde, was soll den mit den Rückgaben ( -1 0 1) passieren?
also ich hab jetzt quasi jeweils 3 Teillisten die die Elemente dann aufnehmen.
ist das auch so gedacht?
was mich nur noch interessieren würde, was soll den mit den Rückgaben ( -1 0 1) passieren?
also ich hab jetzt quasi jeweils 3 Teillisten die die Elemente dann aufnehmen.
ist das auch so gedacht?
Nein, es Du vergleichst zwei Elemente, also z.B. a und b. Wenn beim Compare Aufruf etwas < 0 raus kommt, dann wird a vor b gestellt. Kommt etwas > 0 raus, dann kommt erst b und dann a.
==> So kannst Du also durch Vergleichen von Elementen diese sortieren ... und darum ging es doch.
Das müsste ich dann aber mit 2 Schleifen( verschachtelt) machen oder?
Ich hab vorangehend vergessen, dass ich die Teillisten dann wieder zusammen führe, und dann sind sie ja auch sortiert wovon ich mir ein Laufzeitvorteil verspreche im Vergleich zu den 2 Schleifen
for (int i = 0; i < array.length-1; i++) { // Invariante: alle Elemente 0 bis i-1 sind bereits sortiert
for (int j = i+1; j < array.length; j++) {
int reihenfolge = vergleiche(array[i], array[j]);
if (reihenfolge > 0) { // array[i] ist "größer" als array[j]
vertausche(array, i,j); // vertausche die beiden Elemente im Array
}
}
}
for (int i = 0; i < array.length-1; i++) { // Invariante: alle Elemente 0 bis i-1 sind bereits sortiert
for (int j = i+1; j < array.length; j++) {
int reihenfolge = vergleiche(array[i], array[j]);
if (reihenfolge > 0) { // array[i] ist "größer" als array[j]
vertausche(array, i,j); // vertausche die beiden Elemente im Array
}
}
}
Logisch. Wenn die Elemente schon in der richtigen Reihenfolge stehen, braucht man daran nichts zu ändern. Der Punkt ist aber die vergleiche-Methode, die -1, 0 oder 1 liefert, je nachdem, ob das erste Element kleiner als, gleich oder größer als das zweite Element ist.
Es wird also alphabetisch sortiert und bei Gleichheit wird die kleingeschriebene Variante nach hinten gestellt. (Ich weiß gerade nicht wie man diese Art der Sortierung nennt...)
Wie kommt man dazu, so eine komplexe compareTo Methode zu schreiben? Mit dem tauschen und so ist doch nun wirklich unnötig.
Man geht die Zeichen durch von 0 bis höchstem Index des kürzesten Strings und vergleicht die Zeichen. Sind diese nicht gleich, dann kann man die Differenz zurück geben.
Wenn die Schleife durchlaufen wurde ohne dass ungleiche Zeichen gefunden wurden, dann wird die Differenz der Längen zurück gegeben.
=> kurz, knapp und einfach verständlicher Code. Wenn man sich den Source von String anschaut, dann dürfte man auch genau sowas finden.
Es wird also alphabetisch sortiert und bei Gleichheit wird die kleingeschriebene Variante nach hinten gestellt. (Ich weiß gerade nicht wie man diese Art der Sortierung nennt...)
Die Implementierung der vergleiche-Methode? Nirgends, die spielt hier auch keine Rolle. Du wolltest wissen, wie mit den Rückgabewerten umzugehen ist und ich habe Dir ein Beispiel dazu gezeigt. Die Sortierfunktion sortiert anhand der Rückgabewerte der vergleiche-Methode. Die Reihenfolge im Ergebnis wird also durch die vergleiche-Methode bestimmt.
Übrigens: die vergleiche-Methode ist nichts anderes als die compare-Methode eines Comparators
Klar, ich hätte auch einfach die Methode von String nehmen können, aber das wäre uninteressant. Es ginge bestimmt auch ohne Vertauschen, ist dann aber nicht mehr so gut lesbar.
Hier nochmal ein Beispiel, anhand dessen alles deutlicher werden sollte:
Ich weiß leider wie gesagt nicht wie diese Sortierung genau heißt. Du anscheinend aber auch nicht, sonst hättest du nicht so einen Kommentar abgegeben.
Hier wurde explizit danach gefragt, wie man alles selber umsetzen kann. Manchmal macht das auch Sinn, wenn man zum Beispiel an eingebettete Systeme/Mikrocontroller denkt, bei denen kein Sortierverfahren zur Verfügung steht. Ganze Wörterbücher lassen sich damit natürlich nicht sortieren, denn dafür ist die "sort" Methode zu schlecht... das liegt auf der Hand.
wird also alphabetisch sortiert und bei Gleichheit wird die kleingeschriebene Variante nach hinten gestellt. (Ich weiß gerade nicht wie man diese Art der Sortierung nennt...)
Klar, ich hätte auch einfach die Methode von String nehmen können, aber das wäre uninteressant. Es ginge bestimmt auch ohne Vertauschen, ist dann aber nicht mehr so gut lesbar.
Aber daraus folgt doch höchstens, dass man zweimal vergleichen muss. Das ist doch erst recht ein Grund, es vernünftig lesbar zu gestalten - z.B. gemäß dem Vorschlag von @kneitzel. Er hat doch gar nichts geschrieben, dass nicht in Einklang mit deinen Sortieranforderungen zu bringen ist.
Ok, dann sind wie wieder beim üblichen Punkt, bei dem Du Deine komplexere Version für lesbarer hältst. Ist ok, der Meinung darfst Du sein und ich verzichte diesmal auch auf Argumente. Wer sich ein eigenes Bild machen will, der kann meinen Vorschlag implementieren und den Code vergleichen.
Ich hab's mal gemacht, allerdings mit einer kleinen Abweichung, weil mir bei der Sortierfolge von @Blut1Bart die Position von Mueller1 nicht gefällt. Bei ihm kommt folgendes heraus: Meier, Muelle, Mueller, Mueller1, mUELLER, mueller, Mustermann
und bei mir dieses Ergebnis: Meier, Muelle, Mueller, mUELLER, mueller, Mueller1, Mustermann
Java:
private static int compare(String a, String b) {
int result = compare(a, b, false);
return result!=0 ? result : compare(a, b, true);
}
private static int compare(String a, String b, boolean caseSensitive) {
for (int i = 0; i<a.length() && i<b.length(); i++) {
char charA = caseSensitive ? a.charAt(i) : upper(a.charAt(i));
char charB = caseSensitive ? b.charAt(i) : upper(b.charAt(i));
if (charA != charB) {
return charA - charB;
}
}
return a.length() - b.length();
}
private static char upper(char ch) {
return (ch >= 'a' && ch <= 'z') ? (char)(ch - 'a' + 'A') : ch;
}
Könntest du solche Kommentare lassen? Danke. Denn das bringt niemandem etwas. Wenn man es selber nicht kann, dann dürfte man aus meiner Sich gar nicht den Code von anderen bewerten. Leider hat kneitzel aufgrund seiner "Erfahrung" eine Art Narrenfreiheit, worüber man nur den Kopf schütteln kann.
Nochmal: Es bringt absolut nichts, die compareTo Methode von String hier 1:1 wiederzugeben. Deshalb kann er von mir etwas lernen, von euch nicht.
wie würde man das aufziehen, wenn man zum Beispiel nach 'B' sortieren möchte oder nach einem beliebigen Buchstaben oder nach der Länge statt nach Alphabet?
Als Tipp für die Implementierung habe ich -1, 0, 1 bekommen.
Was nach meinen Verständnis nur mit 0(n²) umzusetzen wäre, also ne Art Bubblesort.
Letztlich sollte die Klasse alphanumerisch und nach Länge sortieren können und bestenfalls nichts aus dem Standart verwenden, da ich es nicht in Java machen soll.
Wie gesagt mein jetziger Stand ist das es alphabetisch sortiert, ich könnte aber noch ne Art Comparator gebrauchen, um mit dem gleichen Quicksort auch noch nach Länge/beliebigen Buchstaben sortieren kann
Hier ein Beispiel für die Stringlänge. Mit berücksichtigt hab ich, ob einer der Werte oder beide null sind.
[CODE lang="java" title="Beispiel für Stringlänge"] public int compare(String o1, String o2) {
if (o1 == null) {
return o2 == null ? 0 : 1;
} else if (o2 == null) {
return -1;
} else {
return Integer.compare(o1.length(), o2.length());
}
}
[/CODE]
Wenn man z.B. Personen nach Vornamen und Namen sortieren will, könnte man das z.B. so machen:
[CODE lang="java" title="Beispiel für Stringlänge"] public int compare(Person o1, Person o2) {
if (o1 == null) {
return o2 == null ? 0 : 1;
} else if (o2 == null) {
return -1;
} else {
int result = o1.getFirstName().aa.compareToIgnoreCase(o2.getFirstName());
if (result != 0) {
return result;
} else {
return o1.getLastName().aa.compareToIgnoreCase(o2.getLastName());
}
}
}
[/CODE]
Wenn du mit Lambda arbeitest, kannst du allerdings auch getrennte Komparatoren für Vor- und Nachnamen schreiben und diese dann aneinanderhängen (thenCompare).
Eigentlich schon, man muss nur definieren, woraus dieser magische Wert, bzw. das Sortierkriterium besteht. Ohne zu wissen, was das Sortierkriterium ist, könnte man Strings genausogut nach deren Hash-Wert sortieren oder nach der Adresse im Speicher (letztere unterscheidet sich natürlich bei jeder Ausführung des Programms)
Das ist jetzt aber wirklich Unfug. Er weiß nicht, wie man compare implementiert. Damit ist es relativ egal, welche konkreten Code man als Beispiel hier aufführt.
Beim Code der compareTo() Methode von String, kann man sich immerhin darauf verlassen, dass er nicht, benennen wir es vorsichtig, "seltsam" ist.
Da die Java-Bibliotheken natürlich auch noch weitere Dinge beachten müssen, kann es schon sein, dass der Code dort etwas umfangreicher ist, aber der Kern von compareTo() ist z. B. dieses:
Java:
public static int compareTo(byte[] value, byte[] other, int len1, int len2) {
int lim = Math.min(len1, len2);
for(int k = 0; k < lim; ++k) {
if (value[k] != other[k]) {
return getChar(value, k) - getChar(other, k);
}
}
return len1 - len2;
}
EDIT: Entscheidender ist allerdings, zu verstehen (und in der Doku zu lesen), was die compare Methode von einem verlangt. Letztlich legt man durch die Implementierung selbst selbst fest, wie die Reihenfolge aussehen soll. Was im Übrigen der Sinn des ganzen ist, eine Möglichkeit zu schaffen, für Mengen von eigenen Typen eine spezifische Sortierung zu ermöglichen.
Das meinte ich mit "magischen Wert". Es gibt keinen Hash-Wert, den man für jeden String einzeln einmal berechnen könnte, anhand dessen man alle Strings vergleichen könnte.
Das meinte ich damit, dass meine Variante, nennen wir es, "unerwartete" Ergebnisse liefert. Prinzipiell kann er oder sie durch diese spezielle "compareTo()"-Methode auch etwas lernen, stimmt. Auch, wenn da "byte[]"-Parameter sind...
Minimale Methodenanzahl als Entwurfsziel? Hach, das ist so schön retro. Hatte ich das letzte Mal beim HP-41. Der hatte nur einen festen Call-Stack für maximal sechs Aufrufebenen von Unterprogrammen. Ja ja, so war das damals in den Achtzigern.
Könntest du solche Kommentare lassen? Danke. Denn das bringt niemandem etwas. Wenn man es selber nicht kann, dann dürfte man aus meiner Sich gar nicht den Code von anderen bewerten. Leider hat kneitzel aufgrund seiner "Erfahrung" eine Art Narrenfreiheit, worüber man nur den Kopf schütteln kann.
Also eigentlich wollte ich diese Diskussion wirklich nicht, aber da hier auch Anfänger über diesen Thread kommen, werde ich mal wieder Argumente bringen. (Etwas, das ich auch von Dir erwarten würde, aber da kommt ja leider nie etwas wirklich brauchbares - was dann eben genau zu solchen Kommentaren führt! Dann bring doch einfach Argumente für Deine Behauptungen statt nur auf Deiner Position zu beharren!)
Aber behandeln wir ein paar Punkte, die hier angesprochen wurden:
Warum Code aufteilen in mehrere Methoden?
- Zum einen ist dies eine einfache Form der Dokumentation. Das wird schnell deutlich, wenn ich einfach einen Code nehme und diesen kommentiere:
Java:
// c1 to upper char
if (c1 >= 'a' && c1 <= 'z') {
c1 -= 'a' - 'A';
}
Und das mache ich jetzt zu eine Methode - natürlich wären hier jetzt noch Refactorings sinnvoll, aber die lasse ich komplett weg. Wie so eine Methode aussehen könnte, wurde ja schon gezeigt.
==> Der Bezeichner der Methode dient somit direkt der Dokumentation. Die Methode besagt genau, was denn in der Methode gemacht wird.
- Übersichtlichkeit: Je kleiner die Methode, desto leichter lässt sich diese überblicken. Und desto leichter findet man Fehler. Speziell, wenn man dann zu dem Schritt kommen sollte, dass man Unit Tests schreibt, wird man es so deutlich leichter haben, Methoden vollständig zu testen.
- Doppelten Code vermeiden! Auch hier ist das Beispiel von @Blut1Bart top: Den Code mit dem Umwandeln hat er zwei mal hintereinander. Doppelter Code! Das ist blöd, wenn es um Anpassungen geht. Da muss man dann bei einer Anpassung an mehreren Stellen anpassen. Daher vermeidet man sowas. Bei so einfachen Codes mag man noch drüber hinweg sehen wollen, aber dies ist ein Prinzip, das sehr wichtig ist.
- KISS: Keep it simple, stupid: Eines der Prinzipien von Clean Code. Statt also einer komplexeren Methode hat man lieber mehrere, einfache, "dumme" Methoden.
Wieso ist es unproblematisch, mehr Methoden zu haben?
Es gibt immer wieder Leute, die meinen, etwas auf Resourcen optimieren zu wollen. Ein Methodenaufruf kommt mit einem Overhead daher was die CPU angeht und es wird Speicher auf dem Stack verbraucht. Da könnte man dann tatsächlich meinen, dass sowas Sinn machen könnte.
- Optimierungen macht man nicht! (Oder für die Experten: Noch nicht!). Zum einen wird etwas optimiert, bei dem unklar ist, ob dies überhaupt optimiert werden muss. Ich erkaufe mir also etwas mit schlechter lesbaren Code von dem unklar ist, ob ich es brauche. Daher macht man es nicht. Sollte sich heraus stellen, dass ich es doch brauche (Speicherprobleme, zu lange Laufzeiten, Stack Overflow, ...), dann bringt es nichts, blind zu optimieren. Statt dessen wird dann erst einmal analysiert, was denn das Problem ist. Ein Stack Overflow kommt in erster Linie bei Rekursiven Aufrufen vor. Da wäre es also zielführender, an so einer Stelle etwas zu drehen. Wenn etwas zu lange läuft, dann sind die Probleme meist nicht ein Methodenaufruf (Komplexität O(1)) sondern die Komplexität eines Algorithmus. Da sollte man also ggf. den Algorithmus anpassen. Also immer erst das Problem analysieren um es dann zu lösen.
An der Stelle einfach einmal überlegen, wie sehr ein Methodenaufruf in einer rekursiven Methode den Stack belastet. Also angenommen dieses toUpperCase würde in einer Methode aufgerufen, die sich selbst rekursiv aufruft. Die Belastung des Stacks ist 1 Aufruf. Denn toUpperCase wird aufgerufen (Stack wird belastet) um sich dann nach dem Umwandeln direkt zu beenden (Stack wird wieder entlastet).
- Optimierungen werden schon an anderer Stelle durchgeführt!
Viele Dinge können automatisch deutlich besser optimiert werden! So optimiert der Java Compiler und der JIT Compiler. Es kann also sein, dass die Methode, die wir geschrieben haben, eh schon als Code eingegliedert wurde.
Auf Bezeichner achten!
Aus meiner Sicht ist es wichtig, auf Bezeichner zu achten. Ich frage mich immer, wie Leute auf die Idee kommen, Variablen immer mit Ax zu bezeichnen mit A Element aus [a-z] und x Element aus [0-9]. Was bitte ist c1? c2? a? b? Die Variablen sagen nichts aus. Das mag in einem engen Kontext ok sein, aber dann muss der Kontext auch wirklich sehr eng gefasst sein. (Also wieder: kurze, kleine Methoden!) Aber besser ist es immer, wenn die Bezeichner aussagen, was enthalten ist.
Links
Natürlich geht das alles nicht auf mich zurück. Ich habe mir dies auch nur "geklaut".
Clean Code Developers
Eine Seite, in der Neulinge an Clean Code heran geführt werden sollen. Es wird hier mit Graden gearbeitet, so dass man einzelne Punkte nach und nach dazu nimmt. Finde ich sehr gut, da man so nicht gleich erschlagen wird.
Uncle Bob
Uncle Bob (Robert C. Martin) ist einer derjenigen, die sehr stark im Bereich Agiler Entwicklung und Clean Code mitgewirkt haben. Er hat mehrere Bücher zu dem Thema gehalten und hält auch viele Vorträge. Letztere sind auch auf YouTube und ich habe mir erlaubt, diese zu verlinken.
SOLID Principles
Eine der wichtigsten Grundlagen sind die SOLID Principles. Finden sich natürlich auch schon in den ersten Links, aber diese "Basis" muss dennoch auch separat erwähnt werden.
Das einfach einmal an dieser Stelle zur Erläuterung meiner Position. Ich hoffe, dass ich die Punkte deutlich machen konnte. Sollte noch etwas unklar geblieben sein oder ein wichtiger Punkt nicht behandelt worden sein, so bitte ich um eine kleine Information und ich würde dann noch weiter ergänzen (So das nicht eh schon von Anderen ergänzt wird!)
Minimale Methodenanzahl als Entwurfsziel? Hach, das ist so schön retro. Hatte ich das letzte Mal beim HP-41. Der hatte nur einen festen Call-Stack für maximal sechs Aufrufebenen von Unterprogrammen. Ja ja, so war das damals in den Achtzigern.
