Beim Programmieren ist alles ein Algorithmus. Irgendwie zumindest. Doch wie misst man die Zeitkomplexität?
Das ganze nennt sich Big-O-Notation, oder zu deutsch "Bachmann-Landau-Notation". Eigentlich ein recht trockenes Thema, doch auch irgendwie relevant in der heutigen Zeit von verteilten Systemen und großen Datenmengen. Doch was ist die Big-O-Notation? Was sagt sie aus? Wo kommt diese in der Praxis vor? Und inwieweit hat das ganze noch eine Relevanz in Zeiten von Cloud Computing und fast unbegrenzten Hardware-Ressourcen? Darum geht es in dieser Episode.
Bonus: Wie Andy und Wolfgang in deutscher Grammatik belehrt werden, ob es OK ist in 1on1s zu fluchen und das Hash-Kollisionen mit der ganzen Sache zu tun haben.
Feedback an stehtisch@engineeringkiosk.dev oder via Twitter an https://twitter.com/EngKiosk
Links
- Pocket Casts: https://pocketcasts.com/
- Learn Redis the hard way (in production): https://tech.trivago.com/post/learn-redis-the-hard-way/
- Redis KEYS Befehl: https://redis.io/commands/keys/
- Redis HSET Befehl: https://redis.io/commands/hset/
- kSQL: https://www.confluent.io/de-de/blog/ksql-streaming-sql-for-apache-kafka/
- Engineering Kiosk auf LinkedIn: https://www.linkedin.com/company/engineering-kiosk/
Sprungmarken
Hosts
- Wolfgang Gassler (https://twitter.com/schafele)
- Andy Grunwald (https://twitter.com/andygrunwald)
Engineering Kiosk Podcast: Anfragen an stehtisch@engineeringkiosk.dev oder via Twitter an https://twitter.com/EngKiosk
Transkript
Andy Grunwald(00:00:04 - 00:00:43)
Was lösen die folgenden Stichwörter für Gefühle bei dir aus? Optimierung von Algorithmen, Zeitkomplexität, Big O Notation, ASMR und Gänsehaut? oder Schlafstörungen und Panikattacken. Wenn es die Angst ist, dann versuchen wir dich mit dieser Episode zu therapieren. Denn darum geht es heute. Wir behandeln dieses Thema von der praktischen Seite. Was ist die Big-O-Notation? Wo findet man diese in der Praxis? Und hat das Ganze bei Cloud-Computing, schnellen CPUs und schier unendlichem RAM eigentlich noch eine Relevanz? Das und noch viel mehr in der nächsten Stunde. Doch zuerst starten wir mit Hörer-Feedback zur englischen Sprache und deutscher Grammatik. Und los geht's!
Wolfi Gassler(00:00:49 - 00:01:41)
So Andi, es ist mitten in der Nacht, sieben oder so in der Früh und trotzdem bin ich super glücklich, weil ich kann dir heute endlich tolle Kommentare vorlesen, weil ich habe das ganze ja schon kommen sehen, nachdem du ja in den letzten Folgen schön immer ganze Gruppen oder Länder beleidigt hast und jetzt sind endlich die Kommentare dazu da und das freut mich wirklich sehr. Also eines zielt genau auf das ab, dass du dich in der Folge 26 Hast du ja gleich ganz Deutschland beleidigt, indem du gemeint hast, die Deutschen sind die, die am schlechtesten Englisch können. Jonathan hat uns da ein schönes Kommentar geschrieben. Er hat zwar gesagt, er findet den Podcast super und alles, aber er findet, dass die Deutschen da sonst schon sehr schlecht wegkommen und wenn man mal mit Franzosen zusammengearbeitet hat, dann fühlt man sich eigentlich wie ein Native Speaker. Andi, willst du dich jetzt entschuldigen bei deinem Volk?
Andy Grunwald(00:01:41 - 00:01:52)
Entschuldigen möchte ich mich nicht, ich gebe zu, vielleicht war es ein bisschen drastisch ausgedrückt, aber ich sehe das so, in Deutschland hat man ja so eine Philosophie, wenn man nicht meckert, ist das ja schon Lob.
Wolfi Gassler(00:01:53 - 00:01:55)
Ich habe gedacht das ist die Bot-Philosophie.
Andy Grunwald(00:01:55 - 00:02:58)
Ich glaube das ist generell so die deutsche Mentalität, wir haben ja immer was zu meckern. Von daher, wenn man nicht meckert, ist das ja schon Lob. Und dann die zweite Thematik ist, ich meine, Deutschland hat ja eine Historie von hochqualitativer Arbeit, Ingenieurskunst und allem drum und dran. Das führt natürlich auch dazu, dass wir sehr hohe Ansprüche an uns selbst haben. Zumindestens ist das bei mir so. Ich habe sehr hohe Ansprüche an mich und auch an meine Teammitglieder und allem drum und dran. Und deswegen kann das natürlich sein, dass das ein oder andere Kommentar etwas negativ rüberkommt. Ist aber nicht so gemeint, sondern eher so eine Art Ansporn, dass man besser, dass man noch besser werden kann und noch ein bisschen was lernen kann. Und ob man sich immer mit anderen vergleichen sollte, weiß ich jetzt auch nicht, ob das alles immer ein guter Benchmark ist, aber generell, Jonathan, hast du natürlich recht, es gibt auch Leute und Länder, die können gegebenenfalls schlechter Englisch sprechen, manche wollen es vielleicht auch gar nicht.
Wolfi Gassler(00:02:58 - 00:03:30)
Also ich würde sowieso grundsätzlich sagen, es gibt keine, Sicherheit, dass jemand aus irgendeinem Land gut oder schlecht Englisch kann. Es kommt immer auf die Person drauf an und wie viel man lernt. Natürlich gibt es statistisch vielleicht mehr Leute, die in Frankreich schlechter Englisch können, wobei auch da muss ich sagen, das ist ein Akzent und vielleicht haben wir einfach mehr Probleme mit dem französischen Akzent oder mit einem indischen Akzent. Das heißt noch lange nicht, dass das Englisch schlecht ist. Also ganz allgemein würde das sowieso nicht runterbrechen wollen auf auf länder.
Andy Grunwald(00:03:31 - 00:03:41)
Man muss ja auch sagen wir generalisieren das ist relativ hart was natürlich auch völlig unfair ist es gibt in jedem land leute die könnten im oxford englisch glaube ich konkurrenz machen von daher.
Wolfi Gassler(00:03:42 - 00:05:08)
Und nachgereicht vielleicht auch noch, es gibt auch in Holland Holländer, sogar Junge, die extrem schlecht Englisch können. Es ist zwar die Ausnahme, aber es gibt auch diese Richtung. Also man kann es wirklich nicht generalisieren, vollkommen richtig. Aber ganz interessant, der Jonathan hat uns auch noch eine zweite Sache geschrieben und Perfekt, du hast nämlich jetzt schon in deiner Ausredensuche zu der ganzen Englischthematik das Wort Kommentar verwendet. Und zwar hast du wieder gesagt, das Kommentar. Und das hat uns der Jona dann auch angekreidet, weil wir das in der letzten Episode scheinbar 20 Mal erwähnt haben, mindestens. und immer das Kommentar gesagt haben. Und er hat uns natürlich richtigerweise darauf hingewiesen, dass es der Kommentar heißt. Und ich hab mir dann gedacht, als Österreicher, ist das wirklich der Kommentar? Ich glaube, wir sagen wirklich immer das Kommentar. Und hab dann ein bisschen gegoogelt und scheinbar ist es etwas gebräuchlicher in Österreich und in der Schweiz. Man findet es auch in Zeitungen. Also es wird verwendet, das Kommentar. Nichtsdestotrotz, es ist offiziell grammatisch falsch und nach Duden der Kommentar. Also Andi, ich habe schon gelernt, dass es der Podcast heißt, nicht das Podcast. Da hat mir ein Österreicher darauf hingewiesen. Jetzt wissen wir, dass es der Kommentar heißt, nicht das Kommentar. Ich glaube, jetzt sind wir ready, um das Podcast sinnvoll weiterzumachen. Und der Jonathan hat ja auch geschrieben, dass es ihm inhaltlich sehr gut gefällt und sich bedankt für das Podcast. Also Jonathan, danke für dein Feedback. Freut uns immer, egal in welche Richtung es geht. Und so haben wir jetzt gleich eine Einleitung in dieses Podcast gehabt.
Andy Grunwald(00:05:09 - 00:05:18)
Ich finde es aber schon beachtlich, dass du dir die Mühe machst und ein Gegenargument suchst, nur damit du Recht behältst. Ich bin eigentlich eher so ehrlich und nehme die Kritik einfach an und sage...
Wolfi Gassler(00:05:18 - 00:05:26)
Ja, ich war ja schockiert als Österreicher. Mein ganzes Leben habe ich mir gedacht, das ist ein Stars-Kommentar. Wahrscheinlich habe ich es in der Schule auch so geschrieben und gar nie als falsch angestrichen bekommen.
Andy Grunwald(00:05:26 - 00:05:56)
Ich nehme die Kritik einfach an und sage, ja, das habe ich einfach falsch gemacht. Danke, Jonathan, da habe ich wieder was gelernt. Auf der anderen Seite muss ich natürlich sagen, ich bin aus dem Pott. Ich bin froh, wenn wir Artikel verwenden und nicht immer nur dat. Von daher, das ist halt so. Ab und zu fühle ich mich halt schon benachteiligt, weil ich aus dem Pott komme und somit gar nicht in der Lage bin, ordentlich Hochdeutsch zu sprechen und die ordentliche Grammatik zu nutzen. Aber nee, Jonathan, du hast natürlich recht, nehme ich sehr gerne Anni Kritik, vielen Dank dafür und danke, dass du Hörer bist.
Wolfi Gassler(00:05:56 - 00:06:39)
Wenn wir übrigens gerade bei dem Thema sind, ist ja sehr interessant, wer uns alle hört, ihr habt nämlich jetzt von einer Deutschlehrerin das Feedback bekommen, weil ich mal in irgendeiner Folge gefragt habe, ob es überhaupt eine Managerin gibt, ob das nicht ein englisches Wort ist und man das überhaupt eindeutschen kann. Und sie hat gesagt, natürlich, es heißt Managerin, ist mittlerweile ein deutsches offizielles Wort und da gibt es natürlich die weibliche Form, gar keine Frage. Also man lernt nie aus, aber sehr interessant, wer uns alle hört. Danke an alle, die uns da grammatikalisch auch weiterhelfen, uns zu verbessern. Wir wollten uns ja sprachlich auch immer weiterbilden und das war ja eine Idee des Podcasts oder ein Grund, warum wir das gemacht haben. Hat sich auf jeden Fall schon rentiert. So viel grammatisches Feedback habe ich noch nie in meinem Leben bekommen seit der Schule.
Andy Grunwald(00:06:39 - 00:06:49)
Ich weiß nicht, ob wir besser sind in einer Artikulation, auf jeden Fall bekommen wir die Chance besser zu werden und werden mal schauen in den nächsten Episoden, ob wir das auch wirklich erfolgreich anwenden können.
Wolfi Gassler(00:06:49 - 00:06:53)
Wir sagen Chance übrigens, nicht Chance. Da ist kein G.
Andy Grunwald(00:06:53 - 00:06:57)
Ja, China, China, Chemie, Chemie. Ich glaube, das ist eine eigene Folge.
Wolfi Gassler(00:06:58 - 00:08:41)
Übrigens, weil wir gerade bei random Sachen sind, die gar nichts mit dem Podcast zu tun haben, ich habe auch in den letzten Tagen mit ein paar Leuten eine Diskussion geführt über Podcast-Player und zwar hauptsächlich mit Informatikern oder IT-Leuten und es haben sich sehr viele beschwert, dass sie mit Spotify nicht happy sind und dass es irgendwie schwierig zu nutzen sei und sie haben da keine sinnvolle Plattform. Und ihr habt dann immer Pocket Casts empfohlen, drum würde ich das jetzt auch mal empfehlen, jeder der es noch nicht probiert hat, ist eine kostenlose App, gehört meines Wissens noch immer den WordPress Leuten, also den ursprünglichen Gründern von WordPress, die haben das mal gekauft, oder die Company dahinter, und die bieten alle offenen Podcasts an, also die normal verteilt werden, natürlich jetzt keine Spotify Podcasts, Exclusive Podcasts, aber alle anderen sind drin. Und ist meiner Meinung nach wirklich eine super Podcast App, die dann die Folgen runterlädt, wenn man Wi-Fi hat und man kann es wirklich genau steuern. Hat auch wesentlich besseren Player als die Spotify App. Man kann genau einstellen, wie schnell der Speed sein soll und so weiter. Also kann ich nur empfehlen und wir bekommen nichts dafür gezahlt, dass wir das jetzt gerade erwähnt haben. das noch irgendwo hört und unzufrieden ist, jetzt gerade diese Episode probiert mal Pocket Casts aus. Verlinken wir natürlich gerne in den Shownotes. So, aber bevor wir in das Thema heute einsteigen, Andi hat noch eine Frage. Kennst du diese Situation, dass man ein Problem hat oder eine Situation und man erinnert sich dann zurück, dass man ja da eigentlich schon eine gute Lösung hat oder Informationen oder ein Wissen, das man anwenden kann. Man hat es aber schon fast wieder vergessen, ist dann aber recht glücklich, dass man dieses Toolset zur Verfügung hat, um das Problem oder diese Situation besser lösen zu können.
Andy Grunwald(00:08:41 - 00:10:14)
100 prozent gerade auch wieder letzte woche und zwar etwas aus meinem arbeitsalltag ich bin inzwischen wieder wieder team lead team manager engineering manager wie man es auch immer nennen möchte und da hatte ein teammitglied im in einem unserer ones mal wieder luft gelassen mal schön wieder ein bisschen dampf abgelassen weil manche dinge nicht so laufen wie sie laufen sollten Und da fiel mir auf der einen Seite wieder ein, genau dafür ist ein One-on-One da. Und das habe ich dann auch nochmal wieder betont, dass One-on-One mit deinem Vorgesetzten oder mit deinen Teammitgliedern ist genau dafür da, dass die Leute auch mal negative Luft ablassen können. Das ist dann besser im One-on-One als irgendwie im Stand-up, in der Retrospektive oder ähnliches, wo das dann im gegebenen Fall das ganze Team runterzieht. Die zweite Geschichte ist, Ein Teammitglied war relativ unglücklich über den Fortschritt, den wir bei manchen Projekten machen und da habe ich dann, da kam mir wieder die Idee, lass mich doch mal wieder ein paar Small Wins mit dem Team sharen. Dann habe ich so eine kleine Liste gemacht über Dinge, die wir in den letzten zwei Wochen erfolgreich auf die Straße gebracht haben, erfolgreich als Team durchgeführt haben. Und als ich die Liste dann wieder geshared hab, kam wieder auch das Feedback, hach, du hast ja recht, sorry, die hab ich so gar nicht gesehen. Und es ist dann auch mal wichtig, die kleinen Dinge wirklich zu zelebrieren. Und das sind so zwei kleine Storys, die ich zwar schon sehr, sehr lange in meiner sogenannten Toolbox habe, die ich aber dann hier und da mal wieder explizit anwenden muss, weil ich sie jetzt nicht zum röchentlichen Ritual gemacht habe.
Wolfi Gassler(00:10:15 - 00:10:23)
Wer noch mehr aus Andis Toolbox hören will übrigens zu 101, dem kann ich die Episode 10 empfehlen, wo wir die 101 im Detail besprechen.
Andy Grunwald(00:10:23 - 00:10:45)
Und heute sprechen wir dann genau über ein solches Thema. Und zwar die meisten Leute, die bereits eine Universität von innen gesehen haben, werden mit diesem Thema konfrontiert worden sein. Ich bin mir gar nicht sicher, ob auch Leute, die irgendwie Informatik LK oder ähnliches mit Abitur hatten, mit sowas in Berührung gekommen sein.
Wolfi Gassler(00:10:45 - 00:10:47)
Was ist denn LK?
Andy Grunwald(00:10:47 - 00:10:52)
Leistungskurs. Wie heißt das bei euch? Im Matura?
Wolfi Gassler(00:10:52 - 00:11:03)
Die Matura übrigens. Keine Ahnung, das hat sich schon zehnmal geändert, seitdem ich dort war. Vertiefung vielleicht gibt es am ehesten. Keine Ahnung, ob das Leistungskurs ist, aber sowas in der Richtung.
Andy Grunwald(00:11:03 - 00:11:12)
Schule hin oder her. Wir sprechen heute über die sogenannte Big-O-Notation oder über die Bachmann-Landau-Notation. Langweilig.
Wolfi Gassler(00:11:13 - 00:11:32)
Genau, jetzt hast du wahrscheinlich 80% unserer Hörerschaft verloren mit dem. Und ich möchte dazu sagen, dieses Thema kam nicht von mir, von der universitären Seite, sondern Andi hat dieses Thema mal vorgeschlagen. Also jetzt komm mal raus, warum willst du bitte dieses extrem langweilige, theoretische Informatikthema besprechen?
Andy Grunwald(00:11:32 - 00:11:45)
Weil ich genau das, was du gerade gesagt hast, ich möchte dieses Thema raus aus dieser extrem langweiligen, theoretischen Ecke holen und rein in die Praxis. Wir sprechen heute ein bisschen über Komplexität von Algorithmen.
Wolfi Gassler(00:11:45 - 00:11:49)
Jetzt sind die letzten 20 Prozent auch noch weggestorben und haben abgeschaltet.
Andy Grunwald(00:11:50 - 00:12:54)
Wir werden nicht wie damals in der Informatik 101-Vorlesung alle tollen Sortieralgorithmen durchgehen. Wir werden die Big-O-Notation, die Landau-Notation, die Zeitkomplexität eines Algorithmus mal ein bisschen praktisch begutachten, mal den einen oder anderen Use-Case geben wo das in der Praxis denn vorkommt und wie das denn relevant sein kann, aber auch was das denn eigentlich ist und warum das ganze relevant ist. Und das ganze Thema ist meines Erachtens nach nicht nur für Backendler oder nicht nur für Data Scientists oder für Data Engineers, sondern auch für Frontendler und so weiter und so fort. Eigentlich für jeden und es spielt auch nicht nur eine Relevanz für Leute, die sich bei Google bewerben wollen, um im Whiteboard Interview zu glänzen, sondern auch in der einen oder anderen offiziellen Dokumentation von einer Datenbank findet man die Big-O-Notation wieder. Deswegen, falls ihr dann mal offizielle Dokumentation sucht, wisst ihr nach dem Hören dieser Episode, was damit anzufangen ist.
Wolfi Gassler(00:12:54 - 00:13:42)
Ich bin ja gespannt, was wir dann in den Statistiken sehen. Bei Spotify zum Beispiel sehen wir genau, wer an welcher Minute, also nicht wer, aber wie viele Leute bei welcher Minute rausdroppen und aufhören zu hören. Bin mal gespannt, wo das diesmal wirklich passiert. Es gibt ja so eine Grundregel für Präsentationen. Mit jeder Formel auf den Slides verlierst du 50 Prozent der Hörerschaft oder der Leute, die noch zuhören bei einem Vortrag. Bin mal gespannt, ob wir das auf Podcasts auch ummünzen können. Aber dann bleiben wir mal bei der praktischen Seite. Was ist denn dein Zugang zu dieser Big-O-Notation? Was hast du doch im Kopf von deinem Studium oder wie wendest du das an? Wo findest du das? Wie kommst du überhaupt auf dieses Thema? Also, dass es wichtig ist, okay, aber wo ist das bei dir im praktischen Leben denn so präsent irgendwo?
Andy Grunwald(00:13:42 - 00:15:04)
Naja, ich würde erstmal gerne die Frage erklären, warum ist das Thema überhaupt relevant, warum ist es überhaupt wichtig. Meines Erachtens nach ist Data the new Oil und ich meine, dieser Satz wird schon seit 10 Jahren durch die Presse getrieben, weil irgendwie jede Firma irgendwie einen Big Data Stack hat, einen Data Warehouse und wir reden jetzt nicht nur über jede Firma. Wer zum Beispiel zu Hause mit Home Assistant ein bisschen Heimatomatisierung macht, der wird mit hoher Wahrscheinlichkeit über kurz oder lang ebenfalls eine zeitbasierte Datenbank, eine Time-Series-Datenbank aufbauen, um die Temperatur seines Büros oder Wohnzimmers kontinuierlich zu messen. Und Achtung, wenn man diesen Datenpunkt irgendwie alle fünf Minuten misst und dass die ganze Sache mal ein paar Monate laufen, deshalb kommen natürlich auch schon eine ganze Menge Daten zusammen. Und deswegen Daten sind halt überall Daten zu speichern ist die eine Baustelle, Daten zu processen ist natürlich die andere Baustelle, und da die Antworten auf neue Fragen herauszuziehen. Und genau in dem zweiten Punkt, diese Daten zu verarbeiten, spielt diese Big-O-Notation und die Lambda-Notation natürlich eine Rolle. Denn umso komplexer ein Algorithmus, umso länger die Processing Time, umso größer die Daten natürlich sind. Und bei einer großen Anzahl an Daten kann man natürlich die Berechnungszeit, beziehungsweise die Zeit, die benötigt wird, um deine Frage auf Basis dieser Daten zu beantworten, deutlich reduzieren, wenn man einen effizienteren Algorithmus hat, beziehungsweise wenn man sich unter anderem mit der Komplexität, der Zeitkomplexität eines Algorithmus mal auseinandersetzt.
Wolfi Gassler(00:15:04 - 00:15:26)
Data is the new oil, ist sowieso veraltet, jetzt ist es bitte Solar is the new oil in der aktuellen Situation, aber kommen wir mal weg von dem politischen Zeug. Wo war denn das letzte Mal, wo du die O-Notation in der Praxis gesehen hast? Weil du bist immer noch irgendwie so auf der theoretischen oberflächlichen Schiene, wo Wo hast du konkret jetzt wirklich das letzte Mal eine O-Notation gesehen?
Andy Grunwald(00:15:26 - 00:15:30)
Immer wenn ich mit meiner Lieblingsdatenbank Redis unterwegs bin. Und zwar ist nämlich bei... Sagst du.
Wolfi Gassler(00:15:30 - 00:15:33)
Schon wieder Datenbank zu Redis, aber okay, lass das nochmal durchgehen.
Andy Grunwald(00:15:34 - 00:15:48)
Wenn man in die offizielle Dokumentation von Redis schaut und dort einen spezifischen Befehl sucht, steht zu jedem Befehl die Zeitkomplexität des Befehls da mit der Beschreibung, was und warum dieser Befehl so komplex ist.
Wolfi Gassler(00:15:49 - 00:15:51)
Und da steht dann die O-Notation?
Andy Grunwald(00:15:51 - 00:15:52)
Da steht dann die O-Notation, genau.
Wolfi Gassler(00:15:52 - 00:16:16)
Dann erklär mal für alle, die vielleicht es noch nie gehört haben oder sich auch nicht mal erinnern können, was die O-Notation ist. Jetzt bin ich gespannt. Ich habe ja, ich habe mich natürlich vorbereitet, weil ich war keine Ahnung mehr. Es ist schon wieder zehn Jahre her, obwohl ich damals theoretische Informatik sogar als Schwerpunkt eine Zeit hatte und einen Master drin machen wollte. Ich bin dann doch irgendwann draufgekommen, ist doch nichts für mich und habe dann Datenbanken als Schwerpunkt genommen.
Andy Grunwald(00:16:16 - 00:18:34)
So finde ich ja super, dass wir die Podcast-Folge machen, wenn das ganze Thema nichts für dich ist. Ja, super. In der Informatik wird die Big-O-Notation oder auch zu Deutsch Bachmann-Landau-Notation zur Analyse von Algorithmen verwendet und sie gibt in der Regel das Maß für die Anzahl der Elementarschritte eines Algorithmus an. Langweilig. Eigentlich ist es eine eine Art Formel beziehungsweise Einheit, um die Zeitkomplexität eines Algorithmuses anzugeben. Nehmen wir mal ein ganz einfaches Beispiel. Wir haben eine Liste, eine einfach verkettete Liste. Kommt im Linux Kernel ungefähr zehn Trillionen mal vor. Wir haben eine Liste mit 50 Elementen. Wenn man jetzt einen gewissen Wert in dieser Liste suchen möchte, dann ist das eine O-Notation von sogenannt O von N. wo n die Anzahl der Elemente in einer Liste ist. In diesem Fall ist o von n, wo n gleich 50 ist. Warum ist das so? Wenn ich jetzt den Wert in einer Liste suchen möchte, kann ich Glück haben und im ersten Listenelement diesen Wert gefunden zu haben. Ich kann aber auch Pech haben und dieser Wert, den finde ich ganz am Ende unserer Liste. Das würde bedeuten, o von n bedeutet, dass ich zum Suchen eines Wertes in einer Liste, die komplette Liste durchgehen muss. Und wir reden jetzt hier nicht von der binären Suche oder ähnliches. Wir reden hier nicht von von irgendwelchen Assumptions, wie dass das eine sortierte Liste oder ähnliches. Wir reden von einer einfach verketteten, unsortierten Liste, wo wir einen Wert suchen und da müssen wir im schlechtesten Fall einmal durch die ganze Liste gehen, jedes Element mit unserem gesuchten Wert vergleichen. Sind diese Werte gleich? Wenn nein, springen sie zum nächsten Listenelement. Und umso länger die Liste wird, umso länger wird die Processing Time eures Suchalgorithmuses, wo Wolfgang mit hoher Wahrscheinlichkeit sagen wird, dass das kein Algorithmus ist, aber umso länger dauert auf jeden Fall die Suche in der Liste, umso länger die Liste wird. Und da ist n, die Variable, die Anzahl der Items in der Liste. Das ist jetzt mal ein ganz einfaches, praktisches Beispiel, wofür man die Landau-Notation nutzen kann.
Wolfi Gassler(00:18:34 - 00:18:47)
Okay, das ist das, was man jetzt praktisch irgendwo liest. Jetzt wäre meine Frage, warum schreibe ich denn das O überhaupt hin? Warum schreibe ich nicht einfach die Komplexität oder best case is n oder worst case is n? Warum brauche ich dieses O?
Andy Grunwald(00:18:47 - 00:19:12)
Also damals im Studium, im Wirtschaftsinformatikstudium, war ich froh, dass ich Statistik 1 und Statistik 2 bestanden habe. Ich glaube, Statistik 1 habe ich mit 3,7 und Statistik 2 dann glaube ich mit 1,7 oder 2,0 bestanden. Und somit habe ich auf diese Frage einfach keine Antwort, aber da habe ich ja jemanden hier im Podcast, der einen akademischen, sehr hohen akademischen Titel hat und sogar theoretische Informatik gewählt hat, wie ich gerade gehört habe.
Wolfi Gassler(00:19:12 - 00:19:16)
Und deswegen hat das mit... Ja, aber auch abgewählt habe.
Andy Grunwald(00:19:16 - 00:19:20)
Wahrscheinlich hat das mit irgendwelchen griechischen Zeichen zu tun, wie in der Mathematik so üblich.
Wolfi Gassler(00:19:21 - 00:20:38)
Das weiß ich gar nicht, ob das O ein griechisches Zeichen ist. Bin ich mir jetzt gar nicht sicher. Könnte ich auch gar nicht sagen, muss ich zugeben. Aber grundsätzlich, was dahinter steckt, ist ja, dass das O eine Vereinfachung ist. Weil wenn du einen Algorithmus genau ausdrückst und genau berechnest, dann hat er eine spezielle Komplexität. Das ist dann vielleicht n² plus 5.000 Zeiteinheiten zum Beispiel oder es sind selten Zeiteinheiten, sondern irgendwelche Vergleichsschritte zum Beispiel. Dann hast du n² Vergleichsschritte plus 5.000, weil du am Anfang noch irgendwas machst. Und mit der O-Notation kannst du das Ganze dann vereinfachen und die 5.000 zum Beispiel fallen weg, weil das eine Konstante ist und in der O-Notation kann man eben Konstanten zum Beispiel in den meisten Fällen zumindest streichen. Das heißt, es vereinfacht alles. Das heißt, wenn du zum Beispiel O von n² hast oder quadratische Komplexität, heißt es nicht, dass es wirklich der Algorithmus genau n² ist, aber er hat quadratisches Wachstum. Das heißt, man vereinfacht das Ganze ein bisschen und bricht es auf eine einfachere Form runter, damit es einfach schneller verstehbar ist und damit man schneller einschätzen kann, was denn dieser Algorithmus macht oder wie schnell dieser Algorithmus ist.
Andy Grunwald(00:20:38 - 00:20:47)
Sorry, ich bin gerade eingeschlafen. Was hast du gesagt? Hier werden wir natürlich in den Spotify-Statistiken wieder ganz viele Leute sehen, die weggedroppt sind. Danke, Wolfgang.
Wolfi Gassler(00:20:47 - 00:20:49)
Immer gerne.
Andy Grunwald(00:20:49 - 00:22:11)
Was ich immer so als Streitpunkt in dieser Lander-Notation sehe, ist, dass ich in der Praxis sehr oft sehe, dass es eigentlich unklar ist, von welchem Case wir reden, wenn wir diese Notation bei Algorithmen nutzen. Reden wir hier vom Best Case, vom Worst Case oder vom Average, vom durchschnittlichen Fall? Und jetzt fragt ihr euch, Andi, warum spielt das eine Relevanz? Ja, relativ einfach. Nehmen wir mal wieder unsere einfach verkettete Liste, eine einfache, unsortierte, verkettete Liste. Wir suchen dort einen Wert in der Liste. Im besten Fall ist das erste List-Item unser gesuchter Wert. Oder die Liste hat nur ein Item. Dann ist zwar n auch gleich 1 und die Suche ist immer noch o von n. Man könnte aber auch sagen, im allerbesten Case, und jetzt alle Mathematiker, bitte haut mich nicht, ich bin praktisch veranlagt. Für mich ist das hier so. Challenge mich gerne mathematisch, lasst aber die Formel weg, die verstehe ich eh nicht. Summzeichen kriege ich gerade noch hin, aber der Rest ist anscheinend wieder weg. Im besten Fall ist das dann o von 1, weil das erste Item in der Liste kann natürlich unser gesuchter Wert sein. Im average case, im durchschnittlichen Fall, ist der gesuchte Wert genau in der Mitte unserer Liste, somit wäre das o von n durch 2 und im worst case wäre es dann o von n, wo dann unser gesuchtes Item das letzte Item in der Liste ist.
Wolfi Gassler(00:22:12 - 00:23:40)
Es ist ja eigentlich interessant, weil grundsätzlich hat sich da die Praxis und die akademische Welt schon irgendwo in der Mitte getroffen, würde ich mal sagen, weil bei Definition ist die O-Notation immer worst case. Es gibt keinen best case eigentlich bei der Groß-O-Notation. Dafür ist die Omega-Notation zum Beispiel zu verwenden. Also es ist einfach so ein Omega-Zeichen, dieses Hufeisenartige Ding. Und das wäre dann die untere Schranke. Also was ist der Best Case? In der Mathematik wäre das also genau definiert. Dann ist aber die Praxis gekommen und man liest jetzt überall, auch auf Wikipedia, die Best Case Komplexität ist O von 1 und die Worst Case Komplexität ist O von n zum Beispiel. Also mittlerweile wird das Groß O für Average, Best und Worst Case verwendet, obwohl rein mathematisch gesehen das eigentlich immer der Worst Case ist, weil es immer die obere Schranke definiert. Da gibt es auch eine interessante Frage, Andi, zum Beispiel jetzt bei deinem Algorithmus, den du erwähnt hast, bei der Suche. Wenn ich jetzt sagen würde, die Suche in einer Linked List hat Zeitkomplexität O von n², also quadratische Komplexität. Stimmt das? Oder vielleicht macht man es noch anschaulicher. Wir wissen ja mittlerweile alle, was exponentielles Wachstum ist, dank Corona. Das hat ja mittlerweile wirklich jeder verstanden. Also kann ich sagen, die Komplexität von einer Suche in einer sortierten Linked-List ist exponentiell.
Andy Grunwald(00:23:40 - 00:23:40)
Ich würde sagen nie.
Wolfi Gassler(00:23:41 - 00:24:07)
Wird wahrscheinlich jeder sagen, mathematisch ist es korrekt, weil mathematisch sagt die O-Notation nur, dass du beschreibst, dein Algorithmus ist auf jeden Fall darunter und schneller. Das heißt, auch wenn du sagst, das ist exponentiell, wäre das korrekt, weil dein Algorithmus schneller als exponentiell ist. Und was wir eigentlich in der Praxis immer wollen, ist ja wirklich, die obere Grenze die obere Schranke die möglichst nah am Algorithmus dran sitzt.
Andy Grunwald(00:24:08 - 00:24:15)
Also willst du mir jetzt eigentlich sagen ich kann eigentlich immer daher kommen immer Algorithmen ausdenken und sagen okay das ist hier o Quadrat.
Wolfi Gassler(00:24:15 - 00:24:17)
Es muss dann aber besser besser als Quadrat sein.
Andy Grunwald(00:24:18 - 00:24:33)
Ja, Moment, Moment, also du willst mir erstmal sagen, ich pack da jetzt einfach immer O von N² dran und das ist erstmal mathematisch immer korrekt und alles weitere, umso näher ich wirklich an die Realität komme, umso näher ich wirklich an die Zeitkomplexität immer des Algorithmus komme, umso korrekter ist das und das kann ich dann als Mikrooptimierung abschmeißen und einfach nicht machen, oder?
Wolfi Gassler(00:24:34 - 00:24:48)
Ja, im Großen und Ganzen schon. Es kann natürlich auch ein Algorithmus sein, der n hoch 3 ist, dann stimmt n² natürlich nicht. Aber grundsätzlich, wenn du immer irgendwas Höheres nimmst, exponentiell ist es glaube ich ganz gut, weil hoffentlich die meisten Algorithmen besser als exponentiell sind.
Andy Grunwald(00:24:48 - 00:24:53)
Vielen Dank, dass ihr da wart. Das war mein TED-Talk. Ich erleichtere euer Leben. Bis zum nächsten Mal.
Wolfi Gassler(00:24:54 - 00:24:59)
Genau, also wenn man die Onnotation mathematisch richtig versteht, hat man ein leichtes Leben.
Andy Grunwald(00:24:59 - 00:25:02)
Was eine Schummelei, die Mathematik, was eine Schummelei.
Wolfi Gassler(00:25:02 - 00:26:50)
Ein anderer wichtiger Punkt bei der Onnotation, gerade wenn man im Informatikbereich unterwegs ist, sind diese Konstanten, die ich schon erwähnt habe, die ja da einfach weggestrichen werden. Aber wenn du jetzt zum Beispiel, keine Ahnung, jetzt eine Datenbank hast und du hast da irgendeine Komplexität von einem Algorithmen, von irgendeinem Algorithmus ein Quadrat und du hast da irgendwelche Konstanten dran, zum Beispiel plus 5000, weil du davor eben was studieren musst oder irgendeine Startzeit brauchst, also irgendwas am Anfang machst, vielleicht irgendwelche Vorsudierungen oder irgendwas machst du konstant im Vorhinein mit dieser Liste. dann würde das in der O-Notation wegfallen. In der Realität ist das aber natürlich extrem wichtig. Wenn du da bei jeder Berechnung von diesem Algorithmus am Anfang extrem viel Zeit brauchst, um da irgendwas aufzubauen oder irgendwas zu machen, dann ist das in der Praxis natürlich sehr wohl relevant. In der O-Notation fällt das einfach alles weg. Das heißt, auch da muss man wieder genau reinschauen, was sagt die O-Notation und was sagt die Praxis und wie schnell ist das wirklich in der Praxis. Aber es hilft natürlich einfach mal grob abzuschätzen, wo wir umgehen. Und darum sieht man in der Informatik eigentlich auch primär nur immer 1, n², n, alles was Bäume sind, sind log n. Und dann kann man so grob abschätzen, wie schnell etwas ist, dass man einfach so ein Gefühl dafür bekommt. Und darum ist es halt einfach wichtig, dass man mal die O-Notation gesehen hat und sich da nicht abschrecken lässt, weil das wirklich gute Information ist, wichtige Information, die einem wirklich extrem schnell anzeigt, wie komplex ist denn irgendwas. Und dafür ist sie, glaube ich, gut. Alles andere, was da wirklich mathematisch dahinter steckt und so, ist zwar interessant, aber braucht man, ehrlich gesagt, in der Realität weniger. Ich bin auch so überrascht, dass du mit der Onotation da irgendwie bei Redis Erfahrung gemacht hast, weil, ehrlich gesagt, ich sehe sie sehr, sehr selten, muss ich sagen, im praktischen Leben.
Andy Grunwald(00:26:50 - 00:27:41)
Die Story dahinter ist relativ einfach und zwar habe ich, ich glaube 2014 oder 2015, hatte Trivago relativ Probleme mit der Skalierung der Datenbank Backends und wir hatten Redis da auch ziemlich viel im Einsatz. Und wir hatten eine relativ große Redis-Datenbank, die sehr viele, sehr viele Keys hatten und war ein paar Gigabyte groß. Die Datenbank haben wir unter anderem als Cache genutzt, aber unter anderem auch als Persistent Storage, wo die Datenpersistenz jetzt nicht so unglaublich wichtig war. Da haben wir ab und zu mal einen Cron-Job gehabt, der gesagt hat, ich connecte mich zur Redis-Datenbank, hole mir alle Keys in dieser Datenbank und schiebe diese Keys asynchron in MySQL, in anderen Data Storage.
Wolfi Gassler(00:27:41 - 00:27:44)
In sinnvollen Data Storage, ja? Wie war das?
Andy Grunwald(00:27:44 - 00:27:47)
MySQL ist ein Adressbuch mit SQL-Interface, oder wie war das, ne?
Wolfi Gassler(00:27:47 - 00:27:50)
Ah, diese Sachen merkst du dir wieder, ey, klar.
Andy Grunwald(00:27:50 - 00:30:29)
Auf jeden Fall lief der Cron-Job alle 30 Minuten, alle 45 Minuten, irgendwie relativ regelmäßig. Und irgendwann haben wir halt in unseren Monitoring-Statistiken, damals war das halt noch kein Graf Harner, ich glaub, da war das irgendwie noch, weiß ich gar nicht mehr, was da gegrafft wurde, ist ja auch egal, sehen wir da halt so einen Megaspike an Connection-Failures. Da denk ich so, hä? Was ist denn jetzt los? Und so habe ich dann noch investigiert, investigiert und investigiert und im Endeffekt war es halt wie folgt. Redis zu der Zeit war halt noch Single-Threaded, inzwischen sind die modernen Versionen Multi-Threaded. Nicht jeder Command läuft Multi-Threaded, aber viele. Und das bedeutet, Als wir den Befehl Keys ausgeführt haben, der gesagt hat, gib mir mal alle Keys in dieser Redis-Datenbank. Dieser Command ist O von N, weil Redis im internen Speicher nachguckt, durch die ganze Liste geht und mir die Keys zurückgibt, kam dort eine sehr große Liste an Strings zurück. Und diese große Liste hat halt enorm viel Zeit benötigt, was dann diesen Single-Threaded-Redis-Server geblockt hat und in der Zeit konnten keine neuen Connections angenommen werden. Da Trivago zu der Zeit aber auf PAP lief und PAP nach dem Request-Response-Behavior arbeitet, das bedeutet, ein Request kommt rein, eine Datenbank-Connection wird aufgemacht, es werden irgendwelche Operationen gemacht, die Datenbank-Connection wird wieder zugemacht, der Response wird gesendet und der Speicher von dieser Anfrage ist wieder weg, war es natürlich so, dass Trivago relativ viel Traffic hatte, Während die Keys-Operation auf der Redis-Datenbank ausgeführt wurde, wollten natürlich ziemlich viele Clients zu dem Redis-Server connecten, konnten nicht, sind in Timeout gerannt, haben Connection-Errors geschmissen. Und bis ich das mal wirklich verstanden habe, ich sag mal so, sind ein paar Tage vergangen, schäm ich mich inzwischen für, aber hey, solche Learnings macht halt jeder. Ich werd's nie vergessen. Und seitdem achte ich halt immer in Redis, okay, was ist das für eine Zeitkomplexität, weil manche Befehle immer noch single-threaded ausgeführt werden, und du somit immer im Hinterkopf hast, oh, fuck, das kann den ganzen Server blocken. Und das war meine Berührung, und deswegen hab ich dieses Thema mal aufgebracht. Und zu diesem ganzen Thema hab ich auch einen sehr langen Blogpost geschrieben, ist irgendwo noch unter tech.trivago.com zu finden. Da habe ich diese ganze Story mal niedergeschrieben, auch wie wir Segmentation-Faults in Redis getriggert haben, auf Previously und so weiter und so fort. Spannende Story auf jeden Fall, aber deswegen finde ich unter anderem Redis so schön und deswegen finde ich auch die Redis-Dokumentation so schön, weil sie auf so kleine Details wirklich Acht geben. Das ist eine der wenigen Dokumentationen, die ich gesehen habe, wo diese Zeitkomplexität gut und in einfachen Worten beschrieben ist.
Wolfi Gassler(00:30:29 - 00:31:12)
Ich sage ein gutes Beispiel, genau das, was ich zuerst auch erwähnt habe, mit der Praxis, weil O von N ist ja eigentlich so ganz allgemein, wenn es um Sodieralgorithmen geht oder andere Algorithmen, ist man ja super happy, wenn man O von N hat, dass man nur einmal durch die Daten durchgehen muss. Und man würde sagen, O von N ist super schnell, kann aber in manchen Umständen auch eben langsam sein, wenn man eben durch alle Daten durchgehen muss, vor allem, wenn man viele Daten hat, wie du richtig sagst. Das kann in der Praxis dann durchaus Probleme geben, wo man am Papier sagt, es schaut eigentlich eh ganz gut aus, offen ein, gar keine Frage. Du hast es auch schon richtig gesagt, Zeitkomplexität. Du hast immer Zeitkomplexität gesagt, weil es gibt ja auch Space Complexity, also, wie versetzt man das ins Deutsche, Space Complexity?
Andy Grunwald(00:31:12 - 00:31:23)
Das hat jetzt aber nichts mit dem neuen Teleskop zu tun, was jetzt endlich mal die Bilder von der NASA dann irgendwie zu uns geschickt hat, die sehr gut aussehen, oder? Also es hat nichts mit dem Weltraum oder ähnliches zu tun, oder? Raumkomplexität?
Wolfi Gassler(00:31:23 - 00:32:40)
Wenn es hilft für die Übersetzung, hat es vielleicht was damit zu tun. Raumkomplexität klingt eigentlich ganz logisch. Ja, ist wahrscheinlich Raumkomplexität. Es klingt auch sehr komisch. Auf jeden Fall, Space Complexity wird genauso auch mit der O-Notation verwendet, aber gibt eben an, wie sich das Ganze bezüglich Memory Speicher verhält. Du kannst zum Beispiel Sodieralgorithmen optimieren in Bezug auf Zeit, wenn du dafür extrem viel abspeicherst. Und dann wird die Space Complexity erhöht, du speicherst ganz viel ab zwischen Schritte und solche Dinge und dadurch kannst du dann aber schneller zum Beispiel eine Liste sodieren. Also diese zwei Sachen muss man immer abwägen. Ist Space ein Problem oder ist Time ein Problem? Soll es schneller werden und verbrauche ich dadurch mehr Speicherplatz oder eben umgekehrt? Die Sachen kann man meistens abwägen. Ist ja dasselbe mit einem Index in der Datenbank. Wenn ich Sachen optimieren will, kann ich mir die in einem Index abspeichern, brauche dann aber natürlich mehr Speicherplatz, dafür bin ich im Zugriff dann schneller. Also diese Herangehensweise gibt es ja in vielen Bereichen in der Informatik und darum sieht man auch bei Studieralgorithmen, zum Beispiel wenn man jetzt auf die Studieralgorithmen auf die Wikipedia-Seite geht, ist es genau angegeben, Best Case, Average, Worst Case und wie sieht das Ganze für Space zum Beispiel aus.
Andy Grunwald(00:32:40 - 00:32:53)
Jetzt haben wir natürlich sehr viel von O von N gesprochen und von worst case und O von N², O von N³ und so weiter und so fort. Eine Frage von Praktikern in Akademika, kann man niedriger als O von 1 gehen?
Wolfi Gassler(00:32:53 - 00:32:57)
Es heißt übrigens Blattkomplexität. Klingt ja voll komisch.
Andy Grunwald(00:32:57 - 00:33:00)
Erinnert mich irgendwie an Raupen in meinem Garten.
Wolfi Gassler(00:33:00 - 00:33:36)
Blattkomplexität. Kleiner als O von 1. Also ich würde jetzt sagen, nein, alle theoretischen Informatiker, verbessert mich bitte. Aber eigentlich gibt man ja über das N an, wie das Ganze anwächst, wenn du mehr Daten hast. Weil umso größer n, umso mehr Datenpunkte du hast, umso größer dann deine Komplexität. Und 1 heißt eigentlich gleichbleibende Komplexität. Also das heißt auch nicht, dass man das Element immer sofort findet. Zum Beispiel, wenn du immer fünf Schritte brauchst, um dein Element zu finden, ist es auch O von 1, weil es eben konstant ist. O von 1 heißt konstante Komplexität.
Andy Grunwald(00:33:36 - 00:33:38)
Warum heißt das dann nicht O von 5?
Wolfi Gassler(00:33:38 - 00:34:05)
Es heißt eigentlich, also du kannst auch O von 5 schreiben, da sind wir wieder bei dieser oberen Grenze, aber die O-Notation erlaubt dir, diese Aussage O von 5 zu vereinfachen, weil das ist eine konstante Komplexität. Weil es ist kein Unterschied, ob du jetzt 10.000 Einträge hast oder eine Million Einträge. Du brauchst immer 5 Schritte. Das heißt Komplexität konstant und O von 1 heißt konstante Komplexität.
Andy Grunwald(00:34:06 - 00:35:15)
Mal ein kleines Beispiel von einem tollen Befehl bei Redis, der eine konstante Komplexität ausgeschrieben hat von O von 1. Und zwar ist das HSet, HashMapSet. Der setzt einen neuen Key mit einer neuen Value in einer HashMap. für Leute, die in Programmiersprachen unterwegs sind, die keine Hashmaps haben. In JavaScript wäre das zum Beispiel ein JavaScript-Objekt, also ein JSON. In PHP wäre das ein Array mit einem, ich wollte gerade sagen, nichtnumerischen Index, aber das ist ja auch falsch, weil in PHP kann ja gefühlt alles eine Hashmap sein, weil da irgendwie alles ein Array ist. Auf jeden Fall ist das ein konstanter Zugriff, weil man direkt einen Wert abfragen kann, wenn man den Key kennt. Und das ist eine konstante Komplexität, egal wie groß die HashMap ist oder egal wie groß die Datenbank ist. Man muss natürlich dann ein paar Grundinformationen haben, wie zum Beispiel, wie die HashMap selbst heißt oder wie das Feld heißt. Aber solange man diese Basisinformationen hat, ist die Abfrage eines Wertes in einer HashMap in der Regel O von 1.
Wolfi Gassler(00:35:15 - 00:36:33)
Wie du schon richtig sagst, in der Regel, weil ganz oft sind Hashmaps eigentlich O von N. Man sagt zwar, das ist O von 1, weil man direkt den Key trifft, aber was ist denn, wenn du mehrere Elemente speichern willst mit dem selben Key? Weil die Implementierung von den meisten Hashmaps sind ja aufgebaut, dass man irgendwelche Hashing-Funktionen hat und die Hashing-Funktionen entscheiden ja dann, wo dieses Element sitzt, im Speicher zum Beispiel. Und du kannst jetzt natürlich, wenn du zum Beispiel eine Hash-Funktion hast, die einfach Modulo 5 ist, also du hast 5 Speicherplätze und speicherst da jetzt viele Zahlen rein, dann kann es natürlich passieren, dass du die Zahl 5 auf den Eintrag 0 legen willst und die Zahl 10 auf den Eintrag 0 legen willst, weil beide Modulo 5 jeweils auf den Eintrag 0 verweisen. Und dann hast du aber ein Problem, weil dann liegen zwei Elemente auf Platz 0. Und wenn du jetzt 5, 10, 15, 20, 25 und so weiter in die Liste speicherst, wird es immer auf dem Platz 0 gespeichert und du hast plötzlich eine ganz lange Liste an Position 0. Das heißt, du hast im schlimmsten Fall eine Linked-List an Position 0, weil deine Hash-Funktion so schlecht gewählt war und damit hast du eigentlich wieder die Komplexität O von N. Also in der Realität ist es manchmal nicht korrekt, aber im Average Case ist es O von 1.
Andy Grunwald(00:36:33 - 00:36:59)
Genau, das geht aber dann ganz tief runter auf die Implementierung dieser HashMap, weil man kann ja auch sagen, okay, wenn du einem Key einen zweiten Wert zuweist in der HashMap, dass der originale Wert, der erste Wert, einfach bland überschrieben wird. Das, was du ja gerade sagst, ist, okay, die Values, wenn du mehrere Values unter demselben Key speichern möchtest, werden dann zu einer Link-List transformiert. Das geht ja dann wirklich ganz runter auf die jeweilige Implementierung der HashMap.
Wolfi Gassler(00:37:00 - 00:37:08)
Es geht nicht darum mit dem selben Key, sondern dass die Hash-Funktion das auf den selben Key mappt, also auf den internen Key.
Andy Grunwald(00:37:08 - 00:37:09)
Aber ist das dann nicht eine Hash-Collision?
Wolfi Gassler(00:37:10 - 00:37:29)
Ja, genau. Und die musst du aber irgendwie auflösen. Du kannst ja trotzdem, wenn du jetzt zwei Zahlen speichern willst, 5 und 10, das sind zwei unterschiedliche Zahlen, zwei unterschiedliche Keys, aber die landen vielleicht intern trotzdem, weil es eine dumme Hash-Funktion ist, beide auf Platz 0. Und da musst du irgendwie trotzdem zwei Elemente speichern. Du kannst nicht Elemente verlieren.
Andy Grunwald(00:37:29 - 00:37:29)
Ja.
Wolfi Gassler(00:37:29 - 00:37:31)
Mit unterschiedlichen Keys 5 und 10.
Andy Grunwald(00:37:31 - 00:37:36)
Moment, wer sagt, dass das Element dann bei einer Hash-Kollision nicht überschrieben wird? Das sagt die Implementierung.
Wolfi Gassler(00:37:36 - 00:37:39)
Ja, aber dann verlierst du Elemente.
Andy Grunwald(00:37:39 - 00:37:40)
Ja und? Vielleicht ist das der Trade-Off.
Wolfi Gassler(00:37:41 - 00:38:01)
Okay, ich kenne jetzt keine HashMap-Implementierung, die Elemente verliert, wenn man sie reinspeichert, aber es gibt natürlich auch da Optimierungen, aber wie gesagt, auch da, wenn man ins Detail geht und in die Implementierung, kann es sein, dass O von 1 nicht korrekt ist. Aber für den Average Case kann man mal sowieso annehmen, dass es stimmt, weil sonst wäre es eine schlechte Hash-Funktion.
Andy Grunwald(00:38:01 - 00:38:07)
Bleiben wir mal bei der Praxis und nicht bei deiner komischen Theorie mit Hash Collisions und allem drum und dran.
Wolfi Gassler(00:38:07 - 00:39:38)
Da sind wir eben schon in dem Bereich da. Ist das natürlich dann wirklich ein praktisches Problem, das beim Programmieren wirklich passieren kann? Wenn ich nicht genau weiß, wie Sachen implementiert werden, dann können das ganz eigenartige Fehler dann sein, die dann auftreten oder dass irgendwas plötzlich komplett langsam wird, weil die zum Beispiel eben ganz spezielle Daten darin speichern. möchte. Es gibt zum Beispiel auch Sudieralgorithmen, die extrem schlecht sind, wenn die Liste schon halb sudiert ist oder verkehrt sudiert ist. Und wenn ich dann den falschen Sudieralgorithmus verwende, dann ist er extrem langsam, weil meine Liste zum Beispiel verkehrt sudiert ist. Manche anderen sind super schnell in dem Fall. Also da ist die Implementierung schon wichtig und darum ist es glaube ich auch wichtig, dass man sich damit beschäftigt und eben solche O-Notationen versteht und vielleicht auch mal, vor allem wenn man ein Problem hat, dann reinschauen kann, okay, was ist denn die Implementierung da dahinter? Macht das vielleicht ein Problem mit meinen Werten? Weil die, auch in einer Datenbank zum Beispiel, wenn ich irgendwie eine verteilte Datenbank habe, da ist ja dann eine Hot Partition bekommen, weil meine Daten eben über die Hash Funktion so aufgeteilt werden, dass alles auf einem Server landet, obwohl ich ja drei Server zur Verfügung hätte. Also auch dort ist das ein Problem. Aber das kann im kleinen Fall in meinem simplen Studieralgorithmus auch schon der Fall sein, dass ich da ein Problem habe. Oder in meiner Hash-Implementierung. Oder was für eine Implementierung auch immer. Also da ist es wichtig, dass man dann ins Detail geht und auch keine Scheu hat, mal irgendwie nachzuschauen, okay, was ist denn das für eine Implementierung auch wirklich dahinter.
Andy Grunwald(00:39:38 - 00:40:05)
Was mich jetzt gerade interessiert, inwieweit kann man die Bachmann-Landau-Funktion denn auf Datenbanken mappen? Klar, kriegt man da irgendeine Verbindung hin zu Sachen wie, meine Query macht ein Full-Table-Scan oder ähnliches, oder gibt's irgendwas, wo man die Landau-Notation zum Beispiel bei den Algorithmen, wie ein Index aufgebaut wird, verwenden kann oder ähnliches?
Wolfi Gassler(00:40:06 - 00:41:05)
Jaja, natürlich. Also du kannst die Onotation im Prinzip überall verwenden und auch bei einem Algorithmus in der Datenbank ist ja kein Unterschied, ob du jetzt eine interne Indexstruktur in deinem Hauptspeicher hast oder jetzt in einer Datenbank. Da ist ja überhaupt kein Unterschied. Und wie ich schon gesagt habe, zum Beispiel Bäume, sei es jetzt ein Binärbaum, sei es ein B-Baum in der Datenbank oder irgendeine Hauptspeicherdatenbank, irgendein spezieller Index, Da hast du natürlich überall die O-Notation und da wird auch alles definiert in dieser Komplexität, dass du eben bei Bäumen zum Beispiel immer Log n hast und wenn du einen B-Baum hast, der zum Beispiel einen Auffächerungsgrad von 200 hat, also der bei jedem Knoten 200 Subknoten hat, dann hast du eben einen 200er-Log von N und darum sind Binärbäume auch ziemlich cool und skalieren auch ziemlich gut mit extrem großen Datenmengen und drum ist B-Baum immer noch der Standardindex in den meisten Datenbanksystemen, wenn man nichts anderes definiert.
Andy Grunwald(00:41:05 - 00:41:12)
Was mal ganz cool wäre, wenn jetzt ein Query-Optimizer die Landau-Notation irgendwie im EXPLAIN-Statement mit eingeben würde. Das wäre nicht ganz cool.
Wolfi Gassler(00:41:14 - 00:41:39)
Ja, für eine Query ist es natürlich wesentlich schwieriger und die Query hängt natürlich dann auch stark davon ab, was du in der Query geschrieben hast und wenn du irgendwie ein where-Statement hast, dann kannst du nicht mehr so allgemeine Aussagen treffen. Also die O-Notation ist vor allem für allgemeine Aussagen zu einem Algorithmus, dass das halt immer dieselbe Komplexität ist. Darum habe ich auch dieses N immer dabei, damit es allgemeingültig für alle möglichen Datenmengen ist.
Andy Grunwald(00:41:40 - 00:41:54)
Aber wenn wir, wenn wir jetzt genau darüber sprechen, frage ich mich natürlich auch, wie relevant ist die ganze Sache heutzutage noch in Zeiten von Cloud, in Zeiten von teurer Arbeitskraft, in Zeiten von, ich kann da einfach eine dickere Box hinschmeißen.
Wolfi Gassler(00:41:54 - 00:41:58)
Jetzt wirst du aber abwarten, wenn du Arbeitskräfte als dicke Boxen bezeichnest.
Andy Grunwald(00:41:59 - 00:42:30)
Okay, nur damit ich mir keine Feinde mache. Wir haben teure Fachkräfte, die schreiben noch teureren Code. Vielleicht haben wir sogar 10x Engineers irgendwo. Und mit Boxen meine ich natürlich, gibt's nicht noch ne dickeren Server und ist ja nicht günstiger, als wenn ich da jetzt ein Software-Engineer oder ein Team für ne Woche dran sitze. So, ich hoffe, das haben wir geklärt. Zurück zur Frage. Können wir nicht einfach mehr RAM in der Amazon Cloud kaufen und dann läuft das alles schneller? Wie relevant ist das, die Optimierung der Landungnotation, die Komplexität, die Zeitkomplexität von Algorithmen heutzutage noch?
Wolfi Gassler(00:42:30 - 00:42:35)
Das ist eine ziemlich schwere Frage, aber wenn du die Frage schon stellst, hast du wahrscheinlich eine gute Antwort drauf, oder?
Andy Grunwald(00:42:35 - 00:42:37)
Erklär mir doch mal ganz kurz, warum das eine schwere Frage ist.
Wolfi Gassler(00:42:37 - 00:43:19)
Ich glaube, es ist extrem schwierig zu entscheiden, wann es sinnvoll ist, darüber nachzudenken, weil es gibt ja diese klassische Micro-Optimization und Leute, die extrem gern sofort in die Optimierung reinspringen, bevor überhaupt irgendwas funktioniert. Und das sind natürlich alles Extreme, ist klar. Aber da den richtigen Mittelweg zu finden, ist vermutlich nicht so einfach. Ich glaube, es ist sicher gut, ein Grundverständnis zu haben von den Algorithmen, dass man schon vielleicht den einen oder anderen richtigen Algorithmus wählt, wenn man anfängt. Da spart man sich einfach viel Zeit. Aber jetzt einen Punkt zu definieren, ab dem es richtig oder falsch ist, das ist, glaube ich, extrem schwierig. Oder hast du da eine allgemeingültige Herangehensweise?
Andy Grunwald(00:43:19 - 00:45:31)
Nichts Allgemeines. Ich denke, hier passt natürlich die typische Informatiker-Antwort. It depends. Und zwar ist es so. Bei einem kleinen Datensatz, denke ich, ist die Relevanz der Optimierung der London-Notation deines Algorithmus eher irrelevant, allein weil CPUs sind so schnell geworden, RAM gibt es noch und nöcher. Viele Libraries sind wirklich optimiert bis unters Dach anhand von Datentypen und Co. Es kommt natürlich ganz drauf an, an welche Ressource ist dein Algorithmus gebunden? Ist dein Algorithmus netzwerktechnisch? Ist dein Algorithmus RAM-technisch? Ist dein Algorithmus CPU-technisch? Generell würde ich sagen, okay, auch bei den heutigen Netzwerkinterfaces und ähnliches und auch Netzwerken, besonders wenn man in der Cloud ist, ich meine die ganzen Cloud, wobei da haben wir natürlich relativ dicke Leitungen zwischen den Switches, zwischen den Racks, zwischen den Availability Zones, zwischen den Regions. Bei kleinen Datensätzen ist es, glaube ich, nicht so die Relevanz gegeben, dass man da wirklich viel Arbeit reinsteckt. Da würde ich eher sagen, okay, make it work statt make it fast. Bei dem Buzzword Big Data ist das natürlich eine andere Baustelle und hier würde ich gerne auch nochmal unterscheiden und zwar auf der einen Seite kann man natürlich sagen Big Data und Batch Processing, da denke ich jetzt an Importe, die einmal in der Nacht laufen. Da wo es halt nicht so wirklich relevant ist, ob die jetzt 15 oder 30 Minuten laufen, sondern da ist es nur relevant, dass die morgens um 8 Uhr zum Arbeitsbeginn verfügbar sind. Oder nächtliche Reports, Kalkulationen von irgendwelchen Businessmetriken, die dann ans Management gehen oder ähnliches. Da ist natürlich, da muss man natürlich schon ein Auge drauf haben, dass, wenn die Datenmenge wächst, dass diese Reports dann natürlich auch in einer gewissen Zeit fertig werden und nicht dann bei steigender Datenmenge dann irgendwie, wann um 8 Uhr kommen, um 8.30 Uhr, um 9 Uhr und irgendwann kommen sie gegen 13 Uhr. Das, da sollte man dann gegebenenfalls schon mal entweder in die Algorithmen gucken, wie man die Daten generiert, oder natürlich, was man natürlich auch sehr oft übersieht ist, kann man nicht irgendwas im Datenschema selbst optimieren, in den Queries, durch Indizes und ähnliches. wo ich aber wobei das ist dieselbe.
Wolfi Gassler(00:45:31 - 00:45:48)
Frage wie batch versus streaming und die ganzen patch anhänger sagen ja das kann man ja das kann ja ruhig länger dauern wenn man immer auf der schiene gewesen wäre wenn man nie in die streaming ecke gegangen oder hätte in irgendeiner form echtzeit reports überhaupt möglich die heutzutage ja fast standard sind genau das ist.
Andy Grunwald(00:45:48 - 00:45:57)
Ja genau der zweite punkt wo ich darauf hinaus möchte im streaming bereich im bereich realtime data und co Ist das eine andere Baustelle? Weil da geht's ja wirklich darum, um.
Wolfi Gassler(00:45:57 - 00:46:05)
Exekuten ... Ja, aber der ganze Bereich hat sich ja erst entwickelt, weil Leute angefangen haben, das zu optimieren, und weil Batch zu langsam war.
Andy Grunwald(00:46:05 - 00:46:22)
Da weiß ich gar nicht, ob das sich nur entwickelt hat, weil Leute angefangen haben, Algorithmen zu optimieren, oder ob das nicht einfach ein genereller Need ist, um irgendeinen Competitor-Advantage langsam mal zu haben und schneller zu reagieren können, weil die ganze Welt sich schneller dreht, ja?
Wolfi Gassler(00:46:23 - 00:46:44)
Also da würde ich ziemlich viel drauf hätten, dass das eine technische Innovation war, weil die Business-Leute waren ihre Reports gewöhnt und irgendwann ist mal jemand gekommen, hey wir könnten das auch Realtime machen und dann haben die Business-People natürlich gesagt, oh wow, cool, das nehmen wir. Also ich bin mir ziemlich sicher, dass niemand hergekommen ist und gesagt, ich will das Realtime haben und dann ist eine technische Lösung gefunden worden. Ist glaube ich zumindest meine Vermutung.
Andy Grunwald(00:46:45 - 00:46:49)
Ja, da ist jetzt aber müßig, auch darüber zu diskutieren, weil ich habe eine Meinung und du hast eine Meinung und.
Wolfi Gassler(00:46:49 - 00:46:51)
Jetzt könnten wir... Ja, aber meine ist richtiger.
Andy Grunwald(00:46:51 - 00:48:22)
Natürlich ist deine richtiger. Ist es wie immer, der Klügere gibt nach, deswegen beenden wir diese Diskussion jetzt auch. Wie dem auch sei, im Streaming-Bereich ist natürlich die Optimierung von Algorithmen eine ganz andere Baustelle und da holt man schon noch die ein oder andere Optimierung und das Quäntchen, Quäntchenzeit raus. Da kommt es aber natürlich auch darauf an, okay, In welchem Streaming-Bereich bist du unterwegs? Wie machst du dein Streaming? Was berechnest du da? Also sind wir in der Lage, die Berechnung auf jedem einzelnen Datensatz zu machen oder müssen wir konstant über irgendeine Art von Sliding-Window juckeln und ein Subset der Daten irgendwo vorhalten? Müssen wir Nehmen wir mal sowas wie Kafka SQL und KSQL und wie sie alle heißen, müssen wir mehrere Realtime Streams miteinander joinen. Das spielt ja alles eine Relevanz in wie tief oder wie komplex die Optimierung deiner Berechnungen da alle ist. Und da kann es natürlich schon relevant sein, aber man muss natürlich auch beachten, in welcher Industrie ist man jetzt. Also ist man jetzt im Web-Bereich, wo es auf vielleicht die eine oder andere Sekunde jetzt nicht so stark ankommt, sondern ah ok, bei Facebook Messenger hat jetzt jemand geschrieben, ob das jetzt eine Sekunde früher oder später ankommt, würde ich mich mal aus dem Fenster lehnen, ist jetzt nicht so relevant, wohingegen beim High Frequency Trading an der Frankfurter Börse, im Keller, im Data Center schon eine andere Relevanz spielt, ob das jetzt eine Millisekunde oder Nano-, Mikrosekunde oder keine Ahnung welchem Zeitsegment man da unterwegs ist, da ist es natürlich eine andere Baustelle.
Wolfi Gassler(00:48:23 - 00:50:07)
Aber auch, wenn man jetzt zum Beispiel clientseitig unterwegs ist mit JavaScript, dann kann es durchaus auch relevant sein, weil du halt unter Umständen nicht weißt, wer deine App verwendet. Und gerade wenn du User hast, die vielleicht schwächere Handys haben, dann kann es halt auch wichtig sein, dass du da ein bisschen in die Details gehst und das auch testest, weil auf deinem super duper Handy, was super viel RAM hat, da läuft das Ganze vielleicht super smooth. und dann auf 90 Prozent der User, die vielleicht schwächere Handys haben, hast du wieder große Probleme. Also auch in dem Bereich, glaube ich, macht es Sinn, da schon mal in die Details zu gehen und das so grob abzuklopfen, ob es da irgendwo Probleme gibt. Aber ich bin auch deiner Meinung, dass man eigentlich auf die Datengröße achten muss und darum gibt es ja auch dieses N in der O-Notation, weil wenn mein N immer nur 5 ist, ist das ganz egal, dann kann es auch N hoch 3 sein, weil dann ist es immer noch extrem schnell. Also erst wenn mein N wirklich groß wird und ich viele Daten habe, wird es zum Problem und ich glaube, solange ich nicht weiß, dass mein N extrem groß wird und zwar innerhalb kürzester Zeit. Wenn ich irgendwie ein kleines Projekt starte und ich weiß, ja in drei Jahren wird es mal ganz groß werden, würde ich mir jetzt keinen Kopf darüber zerbrechen, weil bis dahin hat sich schon alles wieder geändert. Also dieses N ist glaube ich extrem wichtig, aber es ist auch unbedingt nötig, dass Entwickler oder auch Data Scientists sich mit der Optimierung beschäftigen und das im Hinterkopf haben, dass es die Optimierung gibt und dass man da vielleicht auch viel rausholen kann. Und wenn jetzt Google für jede Suchanfrage irgendwo 0,02% Speed rausholt, dann haben die insgesamt wahrscheinlich extrem viel Zeit eingespart, extrem viel Hardware eingespart und extrem viel CO2 eingespart.
Andy Grunwald(00:50:08 - 00:50:23)
Du hast einen validen Punkt angesprochen, das kommt natürlich auch auf den Scale an. Wenn ich jetzt in meiner persönlichen Webseite das CSS optimiere und zwei Kilobyte kleiner mache, freue ich mich natürlich auch. Ob das jetzt so einen großen Effekt auf die Green IT hat, wage ich zu bezweifeln.
Wolfi Gassler(00:50:24 - 00:50:36)
Sagt Andi, der mir seit Wochen vorwirft, dass unser Matomo Analytics Script auf der Webseite nicht G7 ist, was irgendwie, keine Ahnung, vier Kilobyte hat oder so.
Andy Grunwald(00:50:36 - 00:51:38)
Also wenn jemand in der Lage ist, einen Nginx-Server zu konfigurieren und ein JavaScript komprimiert auszuliefern, würde ich gerne bitten, dass ihr mal Kontakt mit dem Wolfram annehmt, weil er kriegt es einfach nicht hin auf seinem Nginx-Server. Zurück zum Scale. Wenn natürlich jetzt aber ein Software-Ingenieur beim Google Chrome die Render Engine optimiert, dass sie nicht mehr so viel CPU frisst, die Render Engine von den Webseiten, dann hat das natürlich ein Scale und keine Ahnung, wie viele Millionen Rechner davon betroffen sind und von dieser Optimierung dann Vorteile ziehen. Das ist natürlich dann schon eine andere Baustelle. Ich glaube, bezüglich Mikrooptimierungen und sinnvollen Optimierungen, da muss man immer ein bisschen den Kontext kennen. Wo bin ich hier unterwegs? Macht das Sinn? Oder ist das wirklich die wichtigste Arbeit und die impactvollste Arbeit, die ich wirklich hier gerade machen kann? Oder treibt euch da der innere Monk nach vorne und ihr wollt einfach den perfekten Code schreiben? Da würde ich dann mal zwei Schritte zurückgehen und fragen, okay, gibt's den perfekten Code? Weil wenn ihr morgen auf den Code wieder schaut, dann wollt ihr den bestimmt auch wieder refactoren.
Wolfi Gassler(00:51:38 - 00:52:39)
Da habe ich übrigens eine coole Geschichte, dass Optimierung auch im ersten Moment zumindest schlechter sein kann. Wir hatten mal bei Trivago den JavaScript-Code für den Client optimiert, und die Metriken sind dann extrem runtergegangen, dass wir mehr User hatten, die dann gedroppt sind und die Seite nicht mehr verwendet haben. Obwohl wir den JavaScript-Code verbessert hatten und die Geschwindigkeit und am Ende hat sich dann herausgestellt, dass das Problem war, dass durch den schnelleren JavaScript-Code die Webseite besser funktioniert hat auf sehr schwachen Handys, damals in Indien vor allem und bevor die Optimierung durchgeführt wurde, hat die Webseite gar nicht funktioniert auf diesen Handys. Das heißt, diese Handys haben gar keine Analytics gesendet, weil die einfach abgestürzt sind und plötzlich hat das JavaScript mehr oder weniger funktioniert, immer noch schlecht, darum haben es die Leute dann auch nicht verwendet, aber die Analytics-Daten sind wenigstens gesendet worden und am Ende sind die Metricking nach unten gegangen, weil einfach mehr Metricking eingetroffen sind. Also es kann auch so einen Effekt haben.
Andy Grunwald(00:52:40 - 00:53:11)
Genug von uns für die heutige Episode. Wenn ihr bis hierhin durchgehalten habt, freue ich mich. Wenn ihr noch wach seid, freue ich mich umso mehr und nicht bei Professor Wolfgang eingeschlafen seid. Dennoch hoffen wir, dass wir euch einen kleinen Einblick in die Zeitkomplexität von Algorithmen geben konnten. warum die Big-O-Notation oder die Bachmann-Landau-Notation auch in der Praxis noch seine Relevanz hat, wie die ganze Sache bei Redis aussehen kann und ob ihr euren Code optimieren solltet oder nicht.
Wolfi Gassler(00:53:11 - 00:54:10)
Und jetzt müssen wir uns dann noch einen guten Titel für diese Episode überlegen, weil wenn wir sie O-Notation nennen, dann fangen die Leute ja nicht mal an, sie zu hören. Also Andi, da musst du diesmal sehr, sehr, sehr kreativ sein. Wir machen dann übrigens auch einen Screenshot, wenn wir die ersten Daten haben und tweeten den natürlich auch auf ENG Kiosk, wann die Hörer rausgedroppt sind im Vergleich zu einer guten Folge. Dann sieht man das vielleicht auch ganz schön. Oder vielleicht alle dabei geblieben sind. Das wäre natürlich noch besser, wenn alle Hörerinnen dabei bleiben. Aber alle, die jetzt noch mithören, danke, danke fürs Durchhalten. Und wenn ihr uns Feedback senden wollt, wie immer auch gerne bei E-Mail stetig at engineeringcuse.dev oder auf Twitter, wo wir dann eben auch den Screenshot veröffentlichen werden. Wir haben jetzt auch eine LinkedIn-Page. Der Andi war da sehr umtriebig und hat eine LinkedIn-Page gemacht. Also wenn ihr uns lieber auf LinkedIn folgt, dem Business-Hipster-Netzwerk schlechthin, dann gerne auch da verlinken wir natürlich in den Shownotes unsere LinkedIn-Page.
Andy Grunwald(00:54:10 - 00:54:11)
Und zum Schluss dieser Episode, ich hab.
Wolfi Gassler(00:54:11 - 00:54:19)
Leider nach einem Flachwitz gesucht, der eine O-Notation mit eingebaut hat, kein Wunder.
Andy Grunwald(00:54:19 - 00:54:32)
Entweder sowas oder der irgendwas mit Algorithmen zu tun hat. Leider nicht gefunden, deswegen heute noch ein unglaublich schlechtes Ding. Wolfgang, egal wie gut es dir geht, Bill Gates besser.
Wolfi Gassler(00:54:33 - 00:54:59)
Der hat auch definitiv mehr Geld als ich, also vollkommen recht. Ich geh jetzt in die Ecke weinen. Aber ich hätte noch einen Mathematikerwitz, den ganz klassischen. Trifft ein Kosinus auf eine Gruppe von Sinus? Sinuse? Ist das Sinuse? Kosinuse? Kosinüse? Trifft ein Kosinus auf eine Gruppe von Sinusen? Fragt der Kosinus, was muss ich tun, damit ich bei euch mitreden darf? Was sagen die Sinuse? Du musst dich integrieren.
Andy Grunwald(00:55:02 - 00:55:25)
Okay, so viel dazu. Vielen Dank fürs Hören. Wir freuen uns natürlich immer wieder über Feedback. Falls wir auch irgendwas Falsches gesagt haben, bitte, bitte, bitte schreibt uns. Wir nutzen diesen Podcast natürlich auch, um uns weiterzubilden. Wir wollen auch lernen. Wir sind bisbegierig. Und wir schrecken nicht vor kritischem Feedback zurück. Vielen Dank fürs Hören. Habt einen schönen Tag. Bis zur nächsten Episode.
Wolfi Gassler(00:55:26 - 00:55:27)
Tschüss. Ciao.