Java Algorithmen und Datenstrukturen in Java

[HerrDrachen]

Hallo,

ich wollte fragen, wie das Thema "Sortieren von Algorithmen" in der Praxis aussieht.
Ich habe mir einen Video Kurs von udemy zu diesem Thema gekauft und lerne den auch grade.

Der Algorithmus wird mit Daten gefüttert, und je nachdem welcher Sortieralgorithmus, Bubble Sort, Selection Sort,
Insertion Sort, Shell Sort, Merge Sort, Quick Sort, Counting Sort das ist, ist der Algorithmus entweder schnell oder
weniger schnell.
https://en.wikipedia.org/wiki/Big_O_notation#/media/File:Comparison_computational_complexity.svg

So verhält sich der Algorithmus wenn er mit z.B. 1 Million Daten gefüttert wird, es werden dann so und soviele Schritte
durchlaufen. Der Algorithmus ist dann entweder schnell oder sehr langsam.

Meine Frage jetzt:
Habe ich das soweit richtig verstanden?
Und was sind das für Daten, die mit Hilfe von Sortieralgorithmen sortiert werden?
Im Video ist das immer jeweils ein Array mit der Länge 7, aber wie sieht das in der Praxis aus?
Es ist ja wohl kaum immer ein kurzes Array...
Sind das immer Arrays die da sortiert werden?
Dieses Thema ist ein sehr wichtiges und großes Thema, aber warum ist es so wichtig?

Es geht mir darum zu verstehen, wofür man diese Theorie in der Praxis halt braucht!

 

[Raijin]

Ja, in der Regel sind das Arrays, die sortiert werden. Das Thema ist deswegen so wichtig, weil der Aufwand bei 7 Elementen noch überschaubar ist, weil man das ja auch banal von Hand in wenigen Sekunden machen kann, aber bei großen Datenmengen kann der falsche Sortieralgorithmus massiv Performance kosten und den Aufwand buchstäblich potenzieren!

Nutzt man nun so einen aufwändigen Algorithmus und hat nur eingeschränkte Hardware zur Verfügung - zB embedded Systeme - macht es einen riesigen Unterschied.

 

[Frazer1]

Es kommt auch durchaus auf deinen Anwendungsfall an. Sortieren musst du nicht nur Arrays. Im übertragen Sinne kann es auch sein, dass du eine Lagerverwaltung hast und dort die Waren von Robotern sortiert auf die Regalbretter gelegt werden sollen. Hier dauert es sehr lange einzelne Elemente zu bewegen (Sekunden oder Minuten). Bubblesort, was immer nur Nachbarn tauscht wäre hier also gänzlich ungeeignet, da es viele unnötigen Tauschoperationen vornimmt.
Wenn man einen Anwendungsfall hat, in dem man nur sehr wenig Speicher zur Verfügung hat (embedded Systems) kann es sein, dass Quick Sort (je nach Implementierung, hier angenommen, es werden immer neue Arrays erstellt, die dann wieder sortiert werde) zu viel Speicher benötigen würde und deshalb nicht verwendet werden kann.

Sortiert werden kann und muss man eigentlich alles. Wenn du einen Preisvergleich hast, kannst du meistens nach Preis auf- und absteigend die Ergebnisse anzeigen lassen. Nach Namen oder anderen Werten ist es auch oft möglich. Viele Daten will man vielleicht auch chronologisch geordnet haben und möchte sie desshalb nach dem Datum sortieren. Oder du hast die Zeiten aller Sportler bei einem Wettkampf gemessen und willst jetzt die besten 3 haben. Auch hierfür müssen die Daten sortiert werden. Es gibt eigentlich keine Begrenzung für die Art der Daten die sortiert werden sollen.

 

[HerrDrachen]

Was sind das für große Datenmengen die sortiert werden? Paar Beispiele nennen?

Es gibt doch in Java Standard-Libraries, also wo das richtige sortieren schon drin ist?
Man muss diese Algorithmen also nicht von Hand selber schreiben?
Also einfach die Standard Library verwenden und nicht weiter nachdenken?

Wie gesagt, muss man diese Algorithmen denn selber schreiben oder kann man das was
Java mitliefert einfach benutzen? Denn diese Algorithmen selber zu schreiben ist echt schwer.

 

[Raybeez]

Man nimmt Arrays mit Zahlen, weil man dort die Wirksamkeit von Sortieralgorithmen gut darstellen kann. Wenn man andere Datenstrukturen hat spielt die Struktur selber eine große Rolle in der Aufwandsberechnung.

Aber die Laufzeit ist nicht die einzige wichtige Größe. Es spielt auch eine Rolle, ob ein Sortieralgorithmus stabil ist und wie viel zusätzlichen Speicher er braucht.

Es gibt doch in Java Standard-Libraries, also wo das richtige sortieren schon drin ist?
Man muss diese Algorithmen also nicht von Hand selber schreiben?
Also einfach die Standard Library verwenden und nicht weiter nachdenken?

Das betrifft fast jedes Programmierproblem: Man kann auf existierende Bibliotheken zurückgreifen oder etwas selber programmieren. Bei letzterem lernt man mehr und man hat mehr Möglichkeiten. Es dauert allerdings auch länger.

Das ist bei Spieleengines ähnlich. Man kann seine eigene Engine programmieren und hat dann die komplette Kontrolle, oder man greift zu einer fertigen Engine und ist dann in seinen Möglichkeiten auf die Fähigkeiten der Engine beschränkt.

 

[Frazer1]

Das reicht in den meisten Anwendungsfällen, und am Anfang auf jeden Fall aus. Erst wenn es spezieller wird, du besondere Einschränkungen hast, wie die beiden von mir am Anfang genannten Beispiele muss man sich damit mehr beschäftigen. Ich hab ja schon einige Beispiele genannt. Oder ist es noch nicht verständlich?

 

[HerrDrachen]

Andere Datenstrukturen das wären dann Listen, Stacks, Queues, Hashtables, Trees, Heaps?

Ich habe die Beispiele schon verstanden, danke auch dafür.
Ich will halt nur wissen, ob man es selber schreiben muss.....oder es es andere Wege gibt.
Das zu schreiben, sind nur paar Zeilen Code....aber von der Logik her, sehr sehr schwer zu verstehen und
umzusetzen.

Was ist zusätzlicher Speicher? Wo steht wieviel zusätzlicher Speicher gebraucht wird?

 

[Raijin]

Es geht nicht unbedingt darum, die Sortieralgorithmen von Hand zu programmieren, sondern um an einem konkreten Beispiel zu merken, dass es Unterschiede gibt - sei es die Zeit oder eben auch der Speicherbedarf. Man muss nicht für jede beliebige Sortieraufgabe gezielt einen Algorithmus auswählen, sondern es geht darum, dass man in begrenzten Umgebungen eben genauer hinsehen muss.

Für die heimische Videosammlung ist das wie vollkommen egal, gerade wenn es auf einem Desktop passiert. Bewegt man sich aber auf embedded Systemen oder es werden beim Sortiervorgang externe Ressourcen benötigt (siehe Beispiel Waren/Roboter von @Frazer1) ist das schon was anderes.

Auch kann man nicht einfach eine Standardbibliothek auf beliebige Daten werfen, sondern muss ggfs Comparer bauen, die überhaupt erst einen Vergleich bzw. darauf basierende Sortierung ermöglichen.


Am Ende geht es aber primär darum, sich der Unterschiede grundsätzlich bewusst zu sein, damit man im Rahmen des aktuellen Projekts weiß auf welcher Basis man einen Algorithmus wählen sollte. Ich habe auch nicht alle Algorithmen im Kopf und muss ggfs nochmal nachlesen welcher sich warum besser eignet - wenn man denn begriffen hat warum und wieso der falsche Algorithmus zu großen Problemen führen kann.

Das ist beim Programmierenlernen doch ganz normal. Man lernt erstmal wie es zu Fuß geht und dann darf man auch fertige Teile verwenden.

 

[HerrDrachen]

btw: Wie werden in der Praxis GUI erstellt?

Mit Programmen wie für Java, https://www.google.com/search?q=sce...rsHjAhUEKVAKHQmkC2IQ_AUIESgB&biw=1680&bih=865 Scene Builder....oder doch selber schreiben in Code?


@
Raijin

Ja, aber um zu merken, dass es Unterschiede gibt, muss man sich nicht 5 oder 10CP im Studium mit sowas
beschäftigen....!

 

[dbeuebeb]

Sortiert werden immer Arrays. Der Elementtyp ist dabei vollkommen egal. Zum Sortieren gibt du dann eine Funktion an, die von zwei Elementen aus dem Array entscheidet, ob a<b, a=b oder a>b (auf die Reihenfolge bezogen).

Zum GUI basteln kannst du entweder einen GUI-Builder verwenden, oder den Code selbst schreiben (letzteres ist die gängigere Variante, da GUI-Builder oft problematisch sind).

 

[HerrDrachen]

Ist es nicht einfacher nen GUI-Builder zu verwenden und dann im Builder festzulegen welcher Code
ausgeführt werden soll, wenn man einen bestimmten Button etc drückt?

Was ist besser JavaFX oder Swing...warum?
Wo liegen da die Unterschiede?

 

[dbeuebeb]

Ist es nicht einfacher nen GUI-Builder zu verwenden und dann im Builder festzulegen welcher Code
ausgeführt werden soll, wenn man einen bestimmten Button etc drückt?

Für sehr einfache GUIs schon. Wenn es dann allerdings komplexer wird, hilft dir der GUI-Builder auch nicht mehr weiter. Zumal du ja trotzdem den Code, der vom GUI-Builder erzeugt wird, verstehen musst.

In einem Informatikstudium lernst du auch nicht, wie man GUIs zusammenbastelt, sondern eben die Grundlagen von Mathematik und Informatik. Da sind tatsächlich ~80% des Studiums reine Mathematik. Für die gemeine Berufspraxis ist das allerdings nicht von Belang.

 

[mental.dIseASe]

Ja, aber um zu merken, dass es Unterschiede gibt, muss man sich nicht 5 oder 10CP im Studium mit sowas
beschäftigen....!

Tut auch keiner. In der Regel ist das in eine Vorlesung Algorithmik oder Grundlagen der theoretischen Informatik eingebettet. Wenn man damit den Bogen zu (Halb-)Ordnungen zieht, ergibt das schon alles einen Sinn.

 

[HerrDrachen]

Worum geht es in der theoretischen Informatik? (darüber weiss ich leider kaum was)
im Vergleich zu Algorithmen, oder was ist theoretische Informatik überhaupt?

 

[Raijin]

Ja, aber um zu merken, dass es Unterschiede gibt, muss man sich nicht 5 oder 10CP im Studium mit sowas
beschäftigen....!

Das kommt auf den Studiengang an. Ich hab zB Technische Informatik studiert und da ist das ganz normal. Auch "beliebt": "Automaten und formale Sprachen", seinerzeit mit einer Durchfallquote von ohne Witz fast 90%! Mein Prof hat das Lehrbuch geschrieben und hat das Thema gelebt und geliebt - und er hat immer alle Tafeln mehrfach vollgekritzelt, was natürlich in keinem Skript stand....

Sowas gehört aber nun mal mit zum Basiswissen eines Softwareentwicklers. Auch wenn jeder Hobbyprogrammierer meint, es würde reichen ein Buch zu lesen, um sich Programmierer nennen zu können, gehört eben noch viel mehr dazu.

Ein Elektriker lernt auch nicht nur mit dem Schraubenzieher umgehen zu können, sondern muss zig Schaltungen bauen, die am Ende keine Sau mehr von Hand baut.

 

[Killkrog]

Und was sind das für Daten, die mit Hilfe von Sortieralgorithmen sortiert werden?

Wahrhaftig alles, was du dir nur vorstellen kannst.

Sind das immer Arrays die da sortiert werden?

Oft.

Dieses Thema ist ein sehr wichtiges und großes Thema, aber warum ist es so wichtig?

Sortierte Datenmengen können extreme Vorteile haben.

Stellen wir uns einmal vor, wir haben eine große Datenbank mit Personen. Jede
Person hat unter anderem von uns eine interne ID bekommen. Nehmen wir weiterhin
an, die Personen sind in einer zufälligen Reihenfolge in der Datenbank.
Wie finden wir nun also eine Person mit einer gegebenen ID? Wir gehen von vorne
nach hinten durch und schauen, wo die richtige ist. Das kann recht lange dauern.
Bei einer Menge von n Personen kann es im schlimmsten Fall n Vergleiche dauern.

Stellen wir uns stattdessen vor, diese Datenbank wäre sortiert. Das
bedeutet, die Personen sind mit aufsteigender ID in der Liste. Wie können wir
nun suchen? Das macht man so:
1. Ich sehe mir das mittlere Element der Liste an.
2. Wenn die ID dieser Person kleiner ist als die, die ich suche, dann muss meine
gesuchte Person in der linken Hälfte der Liste sein. Andernfalls in der rechten.
Ich hab mit einer einzigen Überprüfung die Hälfte aller Daten ausschließen
können. Das nennt man eine boolsche Suche und ist sehr performant. Zum Beispiel
kann ich eine Liste mit 1'073'741'824 Einträgen mit nur 30 Überprüfungen durchsuchen (2^30).

Es gibt Datenbank, dir nur sehr selten geändert werden, die aber rasend schnell
durchsucht werden können müssen. In so einem Fall wird die gesamte Datenbank
beim Einfügen/Löschen eines Eintrags komplett sortiert.

Es gibt doch in Java Standard-Libraries, also wo das richtige sortieren schon drin ist?
Man muss diese Algorithmen also nicht von Hand selber schreiben?
Also einfach die Standard Library verwenden und nicht weiter nachdenken?

Natürlich gibt es eine Menge Bibliotheken mit allen möglichen
Sortieralgorithmen. Das Kunststück ist zu wissen, welcher davon der beste für
den jeweiligen Anwendungsfall ist. Je nachdem, wie die zu sortierende Datenmenge
aussieht, sind verschiedene Algorithmen unterschiedlich gut geeignet. Zum
Beispiel gibt es Algorithmen, die sich unglaublich schwer damit tun, eine
absteigend sortierte Liste aufsteigend zu sortieren. Anderen wiederum ist das
völlig egal.

Manche Algorithmen benötigen keinen zusätzlichen Speicher beim Sortieren
(sie arbeiten "in-place"), andere wiederum erstellen zum Beispiel temporäre Arrays,
mit denen sie arbeiten. Das kann je nach Anwendungsgebiet tolerierbar sein oder
eben nicht.

Dann können Algorithmen zum Beispiel stabil sein oder nicht. Was heisst das?
Sagen wir, wir haben eine Liste mit Elementen, die jeweils einen Schlüssel haben, mit
dem wir sie sortieren. Sagen wir weiterhin, diese Schlüssel müssen nicht
eindeutig sein. Wenn wir beispielsweise drei Elemente mit gleichem Schlüssel
haben, dann wird ein stabiler Algorithmus diese Elemente zwar an der richtigen
Stelle in der Liste einordnen, wird aber NICHT die Reihenfolge dieser drei
Elemente untereinander verändern. Das Element dieser drei Elemente, was in der
Ausgangsliste am weitesten vorne stand wird auch in der sortieren Liste am
weitesten vorne sein.

Du siehst also, man kann nicht allgemeingültig sagen, dass ein Algorithmus der
beste ist.

Ich empfehle dir, die verschienden Sortierverfahren samt ihrer Vor- und
Nachteile hier nachzulesen: https://de.wikipedia.org/wiki/Sortierverfahren

 

[BeBur]

Nein du hast das schon richtig erkannt. In sagen wir 80% der Fälle ist dir die Geschwindigkeit egal und in 99% der Zeit ist dir der verwendete Algorithmus egal, da googlest du einfach 'java lib sort array' und nimmst das was schnell ist. Häufig wirst du die Daten dann auch gar nicht mit Java sortieren, sondern direkt in der Datenbank, welche sowieso selbstständig den Algorithmus wählen wird.

Ein Grundverständnis davon was die Big-O Notation ausdrückt ist dabei im Zweifel natürlich hilfreich.
Weitere Einschränkung: Kommt natürlich auch drauf an, in welchem Bereich du proggst.

 

[HerrDrachen]

Danke für eure Antworten!
Ich habe es jetzt etwas besser verstanden.

Vielleicht noch kurz: Wofür ist theoretische Informatik gut?

Man findet nur wenig Lernmaterial dazu, sieht eher langweilig aus.(zumindest auf den ersten Blick)

 

[kuddlmuddl]

Bei uns war theoretische Info zB Compiler-Bau, Ein bisschen Verschlüsselungsalgos bzw. Mitm-Szenarien, verschiedene Logiken (2, 3 Wertige, Aussagen, Prädikatenlogik) etc.
Auch die O-Notation hatten wir da.

 

[BeBur]

Theoretische Informatik behandelt im wesentlichen grundlegende Fragen.

Zum Beispiel, ob alle Programmiersprachen gleichmächtig sind und was Mächtigkeit überhaupt bedeuten soll. Und was eine Sprache braucht um 'hinreichend mächtig' zu sein. Und warum ein rein funktionaler Ansatz bei der Programmierung gleichmächtig ist (siehe auch Turing-Vollständig oder Church-Turing-These).

Es geht also unter anderem darum, was mit einer Programmiersprache gemacht werden kann und was nicht. Siehe Halteproblem für etwas, das Programmiersprachen grundsätzlich nicht können.

Für eine weitere Beschränkung von Programmiersprachen siehe P=NP Problem, welches man auch der theoretischen Informatik zuordnen könnte aufgrund der Relevanz.