Wie erkennt man einen Zykel in einer Linked List mit niedriger Zeit- und Speicherkomplexität?
Im Engineering Kiosk Adventskalender 2024 sprechen befreundete Podcaster⋅innen und wir selbst, Andy und Wolfi, jeden Tag kurz & knackig innerhalb von wenigen Minuten über ein interessantes Tech-Thema.
Unsere aktuellen Werbepartner findest du auf https://engineeringkiosk.dev/partners
Das schnelle Feedback zur Episode:
Links
- Engineering Kiosk Episode #28 O(1), O(log n), O(n^2) - Ist die Komplexität von Algorithmen im Entwickler-Alltag relevant?: https://engineeringkiosk.dev/podcast/episode/28-o1-olog-n-on2-ist-die-komplexit%C3%A4t-von-algorithmen-im-entwickler-alltag-relevant/
- Zyklus Erkennung: https://en.wikipedia.org/wiki/Cycle_detection
- Floyd's Linked List Cycle Finding Algorithm: https://cp-algorithms.com/others/tortoise_and_hare.html
- Advent of Code: https://adventofcode.com/
Sprungmarken
Hosts
- Wolfgang Gassler (https://mastodon.social/@woolf)
- Andy Grunwald (https://andygrunwald.com/)
Feedback
- EngKiosk Community: https://engineeringkiosk.dev/join-discord
- Buy us a coffee: https://engineeringkiosk.dev/kaffee
- Email: stehtisch@engineeringkiosk.dev
- LinkedIn: https://www.linkedin.com/company/engineering-kiosk/
- Mastodon: https://podcasts.social/@engkiosk
- Bluesky: https://bsky.app/profile/engineeringkiosk.bsky.social
- Twitter: https://twitter.com/EngKiosk
Transkript
Andy Grunwald (00:00:05 - 00:00:53) 
Willkommen zu einem weiteren Türchen vom Engineering Kiosk Adventskalender. Der Dezember wird oft als langsamer Monat bezeichnet. Viele planen ihre Weihnachts Auszeit. Somit ist auch in vielen Firmen etwas ruhiger, weil die Kunden ebenfalls mit sich selbst beschäftigt sind. OK, dies gilt gegebenenfalls nicht für die Bereiche, die zum Jahresende noch alle Budgets verbraten müssen, aber ihr wisst schon, was ich meine. Somit ist der Dezember auch die Zeit, wo man die man müsste mal Projekte und Fragen angehen kann. Und eine Frage geht mir seit Tagen nicht mehr aus dem Kopf. Weitere Fragen, die auf meiner man müsste mal Liste stehen, sind z.B. datenstruktur und Algorithmenfragen aus Lead Code Aufgaben. Und um sowas geht es heute. Ich übergebe an Wolfgang. Los geht's.
Wolfi Gassler (00:00:53 - 00:05:33)
Der Advent ist ja auch eine Zeit, wo man schwierige Coding Puzzles lösen muss. Also es gibt ja Advent of Code, wo man jeden Tag so eine Aufgabe gestellt bekommt. Hat ja schon wirklich Tradition. Wir haben übrigens bei uns am Discord Server auch einen eigenen Channel dafür und eine Rangliste. Wenn ihr da mitmachen wollt, kann ich euch nur empfehlen. Und darum dürfen natürlich bei unserer Mini episoden Serie auch die Coding Challenges nicht fehlen. Und darum habe ich mir heute mal vorgenommen, die zu ÿousand Zyklerkennung anzugehen. Also z.B. in einer Link List, um den Zyklus zu erkennen in meiner Liste. Und es ist eigentlich relevanter, als man denkt, weil wie oft habt ihr denn schon eine while Schleife einfach programmiert, um durch eine Liste durchzulaufen? Jetzt, wenn man annimmt, man hätte in der Liste irgendwo einen Zyklen drin, dann hätte man eine Endlosschleife und das Programm würde ewig einfach weiter rennen und nicht weiter arbeiten. Also ist die Zyklerkennung natürlich durchaus wichtig. Aber bevor wir da in die Lösungswege einsteigen, kleiner Recap linked Lists. Also eine linked Liste ist eigentlich eine Anzahl an Knoten und jeder Knoten hat einen Wert und einen Zeiger. Und der Zeiger zeigt dann eben jeweils auf das nächste Element, auf den nächsten Knoten von dieser Liste. Und so kann man immer wieder Knoten dranhängen oder auch Knoten zwischendrin einfügen. Also es ist eine grundlegende Datenstruktur. Ist auch ein ganz klassisches Beispiel, wenn man mal programmieren lernt und Pointer lernt in C, C oder auch in anderen Sprachen, lernt man das gerne anhand einer linked List. Und wenn man da jetzt natürlich nicht zu dem nächsten Knoten zeigt bei einem Knoten, sondern zu einem Knoten, den es davor schon gab, dann läuft man natürlich in so eine Endlosschleife hinein und hat einen Zykl. Und das ist natürlich gerade bei großen Listen ein Problem, wenn man das erkennen möchte. Und im Prinzip gibt es da zwei Ansätze, die man wählen kann. Und der erste Ansatz ist so der dumme, naive Ansatz, man bildet einfach eine Hashmap, wenn man durch die Liste durchläuft und speichert alle Elemente nochmal in dieser Hashmap ab. Und wenn ein Knoten schon in meiner Hashmap vorhanden ist, dann habe ich einen Zykl erkannt. Und wenn man das Ende der Liste erreicht, ohne dass man Zykl erkannt hat, dann gibt es eben keinen Zyklen in dieser Liste. Das Problem an dieser Methode, die ist zwar sehr einfach, aber man hat natürlich einen extremen Speicherplatzbedarf, und zwar O. O Notation, Komplexität haben wir übrigens auch schon in einer anderen Episode im Detail besprochen, wenn ihr das jetzt nicht sagt, Episode 28 haben wir verlinkt in den Shownotes zu Komplexität und O Notation. Also hat O von n bezüglich Speicherplatz und auch O von n bezüglich der Zeitkomplexität wird, dadurch man durch die gesamte Liste natürlich einmal durchlaufen muss, also nicht sehr effizient. Und üblicherweise gibt es natürlich wesentlich bessere Algorithmen. Und da gibt es in dem Fall zur Zyklerkennung den Floyd Cycle Detection Algorithm, oder wie er auch oft genannt wird, Schildkröte und Hase oder Tortoise and Hair im Englischen. Und da ist eigentlich sehr einfach dieser Ansatz, aber doch smart und speichereffizient, weil er eben keinen zusätzlichen Speicher benötigt. Und das läuft einfach so, dass man sich zwei Zeiger vorbereitet, die durch die Liste durchlaufen, und zwar einen langsamen Zeiger, die Schildkröte, und einen schnellen Zeiger, den Hasen. Beide Zeiger starten am Anfang, am Kopf der Liste, und der langsame Zeiger, die Schildkröte, die wandert einfach Schritt für Schritt, Knoten für Knoten durch die Liste. Und der zweite Zeiger, der Hase, springt im Prinzip durch die Liste und macht immer zwei Schritte. Und die Theorie ist, wenn es einen Zyklus gibt, Ÿousand, dann springt er, der Hase, irgendwann wieder zurück und muss die Schildkröte einholen von hinten. Das heißt, irgendwann treffen sich die zwei und wenn es keinen Zyklen gibt, treffen sich die zwei nicht und erreichen das Ende der Liste. Dann gibt es keinen Zyklen. Also supertrivial, braucht im Gegensatz zum Hashing überhaupt keinen zusätzlichen Platz, weil man eben nur zwei Zeiger hat. Und die Komplexität, die Zeitkomplexität ist auch O, dadurch man einfach durch die Liste durchläuft, vielleicht einen kleinen Teil mal doppelt durchläuft, aber im Prinzip in der O Notation ist es einfach O von N. By the way, kleines Fun Fact, der Algorithmus wurde nur Robert Floyd zugeschrieben und zwar von Donald Knuth, weil man hat den direkt nie in Floyds Aufzeichnungen gefunden. Also es könnte auch einfach sein, dass es ein allgemeiner Algorithmus ist. Man nennt es dann Folgtheorem, weil man nicht klar bestimmen kann, wer das eigentlich erfunden hat oder das erste mal definiert hat. Wie gesagt, Knuth hat es 1969 Floyd zugeschrieben, aber kann natürlich sein, dass es gar nicht direkt von ihm kommt. Also wenn ihr das nächste mal eine Linked Liste macht, denkt mal dran, ob ihr einen Zyklus drinnen habt oder ob ihr noch so eine Zyklerkennung machen wollt. Und die dumme Variante, die schnelle, gerade wenn die Liste kurz ist, kann man natürlich schnell dieses Hashing implementieren. Aber ehrlich gesagt, die wesentlich schlauere Schildkröten und Hasen Methode ist ja auch super einfach zu implementieren. Zwei Zeiger und läuft durch. Und damit wünsche ich euch noch gutes Coding.
Andy Grunwald (00:05:34 - 00:06:03)
Vielen dank Wolfgang. Damit ist mir der Erfolg auch bei etwas fortgeschritteneren Leadcode Aufgaben sichergestellt. Wenn dir das kurze, aber doch theoretische Wissen gefallen hat, schau doch mal in unsere anderen Episoden rein, da gibts auf jeden Fall noch mehr davon. Und wenn du jetzt noch andere Arten kennst, wie man einen Zyklus in einer Linked List erkennt, lass es uns doch wissen. Links zu unseren Social Media Kanälen sowie zu unserer Discord community findest du in den Shownotes. Das war es von uns für heute. Wir hören uns in der nächsten Episode wieder.
Wolfi Gassler (00:06:03 - 00:06:08)
Bis bald. Ÿousand.