Algorithms

Ob Sie einen Schlüssel in einem Python-dict mit zehn Einträgen suchen oder in einem mit zehn Millionen: Es dauert gleich lange. Das liegt nicht an einer besonders schnellen Sprache. Pythons dict, Javas HashMap und JavaScripts Map sind allesamt Hash-Tabellen, und das gesamte Design existiert, damit Suche, Einfügen und Löschen im Durchschnitt mit O(1) laufen. Die Big-O-Notation nennt diese Suche “konstante Zeit”. Hier ist der Mechanismus, der das verdient. Wie eine Hash-Tabelle einen Schlüssel in einen Array-Index umwandelt Eine Hash-Tabelle ist ein Array plus eine Funktion, die einen Schlüssel in eine Position in diesem Array umwandelt. ...

<.+> gegen <b>bold</b> and <i>italic</i> findet nicht <b>. Es findet die gesamte Zeichenkette, vom ersten < bis zum allerletzten >. Nichts ist defekt. Genau das soll ein greedy Quantifizierer tun, und es ist auch der häufigste “Regex matcht zu viel”-Bug überhaupt. Sobald klar ist, was die Engine beim Lesen des Musters tut, hören dieser Bug und die meisten seiner Verwandten auf, Rätsel zu sein. Wie eine Regex-Engine Ihr Muster Liest Eine Regex-Engine vergleicht Ihr Muster nicht mit der Zeichenkette wie man zwei Zeichenketten auf Gleichheit vergleicht. Die Engines, die Sie täglich nutzen (re in Python, RegExp in JavaScript, PCRE, .NET, Java), sind regex-directed: Sie lesen das Muster von links nach rechts, Token für Token, und versuchen für jedes Token, Zeichen aus der Zeichenkette an der aktuellen Position zu konsumieren. Wenn ein Token passt, rückt die Engine sowohl den Muster-Zeiger als auch den Zeichenketten-Zeiger vor. Wenn ein Token fehlschlägt, macht die Engine Backtracking: Sie geht zum letzten Punkt zurück, an dem sie eine Wahl hatte, etwa ein Quantifizierer, der weniger Zeichen hätte matchen können, oder ein noch nicht probierter Alternationszweig, und probiert die andere Option. ...

Eine Funktion, die sich selbst aufruft, hat eine maximale Tiefe, und die ist kleiner, als die meisten erwarten: 1.000 Aufrufe in CPython standardmäßig, etwa 10.000 bis 15.000 in Node und in Browser-Engines, je nachdem, wie viel jeder Frame belegt. Wird dieses Limit überschritten, wird das Programm nicht einfach langsamer. Es stürzt ab. Python löst RecursionError: maximum recursion depth exceeded aus; JavaScript löst RangeError: Maximum call stack size exceeded aus. Beide Fehler haben die gleiche Ursache, und wenn Sie sie einmal verstanden haben, wissen Sie, wann Rekursion das richtige Werkzeug ist und wann sie zum Risiko wird. ...

Führen Sie 0.1 + 0.2 in einer Python-Shell aus, kommt nicht 0.3 heraus, sondern 0.30000000000000004. Probieren Sie es in JavaScript, Java, Go, C oder Rust, und Sie bekommen denselben sechzehnstelligen Schwanz. Jede dieser Sprachen tut genau das, was der Hardware-Standard vorschreibt. Eine Zahl, die unendlich viele Binärstellen bräuchte, wird in 64 Bit gepresst, und irgendetwas muss nachgeben. Warum sich 0.1 nicht exakt binär speichern lässt Computer speichern Gleitkommazahlen zur Basis 2. In Basis 2 hat der Bruch 1/10 eine periodische Entwicklung, genau wie sich 1/3 in Basis 10 endlos wiederholt (0.3333...). Ausgeschrieben beginnt 0.1 binär so: ...

Ein Zugriff auf ein Python-Dictionary dauert etwa 100 Nanosekunden, egal ob das Dictionary 1.000 oder 1.000.000 Schlüssel enthält. Eine verschachtelte Schleife, die eine Liste auf Duplikate prüft, braucht eine halbe Millisekunde bei 200 Elementen und 136 Millisekunden bei 3.200. Sechzehnmal die Eingabe, fast 280-mal die Wartezeit. Gleiche Maschine, gleiches Python. Die Big-O-Notation ist der Name für diesen Unterschied. Was die Big-O-Notation misst Big O beschreibt, wie die Laufzeit (oder der Speicherverbrauch) eines Codestücks wächst, wenn die Eingabe größer wird. Es ist keine Stoppuhr-Messung, und es ist egal, ob Ihr Laptop schnell oder langsam ist. Entscheidend ist die Form der Wachstumskurve: Verdoppelt sich die Zeit, wenn Sie die Eingabe verdoppeln, vervierfacht sie sich, oder bewegt sie sich kaum? ...