Thema: algorithms
-
Abhängigkeitsreihenfolge per Graphtraversierung: BFS, DFS und topologische Sortierung
Abhängigkeiten als gerichteten Graphen modellieren, mit Breiten- oder Tiefensuche alles finden, was von einer Änderung betroffen ist, und mit Kahns Algorithmus oder DFS-Nachordnung eine Build- oder Migrationsreihenfolge erzeugen, die Zyklen meldet statt sie zu verbergen; graphlib und tsort setzen die Sortierung um.
-
Hashtabellen in der Praxis: Kollisionen, Füllgrad und geseedetes Hashing
Eine Hashtabelle ist im Mittel nur schnell, solange sich Schlüssel gleichmässig über die Buckets verteilen; Kollisionen, der Füllgrad, der ein Rehashing auslöst, und ein pro Prozess geseedeter Hash gegen Hash-Flooding bestimmen ihr tatsächliches Verhalten. Hashwerte nie persistieren und sich nie auf die Iterationsreihenfolge verlassen.
-
Dynamische Programmierung Schritt für Schritt: die Editierdistanz herleiten
Dynamische Programmierung verwandelt eine rekursive Definition mit überlappenden Teilproblemen in einen polynomialen Algorithmus: den Zustand definieren, die Rekurrenz und die Basisfälle aufschreiben, memoisieren oder eine Tabelle füllen, dann den Speicherbedarf senken. Die Editierdistanz zwischen zwei Zeichenketten wird als durchgerechnetes Beispiel vollständig hergeleitet.
-
Rekursion versus Iteration: Stacktiefe, Grenzen und wann umgestellt werden sollte
Rekursion bildet baumförmige Probleme natürlich ab, verbraucht aber pro Ebene einen Stackframe; der Stack ist durch die Rekursionsgrenze des Interpreters oder die Stackgrösse des Threads begrenzt, sodass Rekursion über eine von der Eingabe gesteuerte Tiefe ein Absturz auf Abruf ist. Bei einer mit der Eingabegrösse wachsenden Tiefe auf einen expliziten Stack oder eine Schleife umstellen.
-
Reservoir-Sampling: eine gleichverteilte Stichprobe aus einem Datenstrom unbekannter Länge
k Elemente aus einem Datenstrom behalten, ohne dessen Länge zu kennen: das Reservoir zunächst mit den ersten k Elementen füllen, danach für Element i mit Wahrscheinlichkeit k/i einen zufälligen Platz ersetzen. Ein einziger Durchlauf, O(k) Speicher, jedes Element landet mit exakter Wahrscheinlichkeit k/n in der Stichprobe, was sich mit einem kurzen teleskopierenden Argument zeigen lässt.
-
Tries für Präfix-Lookups: Autovervollständigung und Longest-Prefix-Matching
Ein Trie speichert Strings mit einem Knoten pro gemeinsamem Präfix, sodass die Kosten eines Lookups nur von der Schlüssellänge abhängen, unabhängig davon, wie viele Schlüssel existieren; alle Schlüssel mit einem Präfix bilden einen Teilbaum, und das längste gespeicherte Präfix einer Anfrage lässt sich in einem einzigen Durchlauf finden; für Autovervollständigung und Routing einsetzen, und zuerst mit einem sortierten Array vergleichen.
-
Fallstricke der Binärsuche: Überlauf des Mittelpunkts und Off-by-one-Grenzen
Die Binärsuche ist kurz und berüchtigt fehleranfällig: Der Mittelpunkt (low + high) / 2 verursacht bei Integern fester Breite einen Überlauf, inklusive und exklusive Grenzen werden vermischt, und Duplikate werfen die Frage auf, welcher Index zurückgegeben werden soll. Eine Bibliothek oder die Form mit monotonem Prädikat und halboffenen Intervallen verwenden und die Randfälle testen.
-
Über Komplexität nachdenken, bevor optimiert wird
Asymptotische Komplexität sagt voraus, wie die Laufzeit mit der Eingabegrösse wächst; quadratische Schleifen, wiederholte lineare Suchen und unbeschränkte Rekursion im Code-Review zu erkennen, verhindert die meisten Performance-Vorfälle, bevor ein Profiling nötig wird.
-
Token Bucket, Leaky Bucket und Sliding Window: wie sich Rate-Limiter-Algorithmen unterscheiden
Fixed Windows sind günstig, lassen an einer Grenze aber die doppelte Rate durch; Sliding Logs sind exakt, speichern aber jeden Zeitstempel; Sliding-Window-Zähler nähern sich mit konstantem Speicherbedarf an; Token Buckets erlauben Bursts bis zur Bucket-Grösse bei fester Auffüllrate; Leaky Buckets glätten die Ausgabe durch Verzögerung. nginx und Envoy dokumentieren die letzten beiden.
-
Bloom-Filter: probabilistische Mengenzugehörigkeit ohne falsch-negative Ergebnisse
Ein Bloom-Filter beantwortet „definitiv nicht in der Menge“ oder „wahrscheinlich in der Menge“ mit einem kleinen Bit-Array und k Hashfunktionen; falsch-positive Ergebnisse sind einstellbar, falsch-negative unmöglich, Löschen wird nicht unterstützt. Damit lassen sich Lookups für nicht vorhandene Schlüssel überspringen, und ein positives Ergebnis sollte immer gegen die massgebliche Quelle geprüft werden.
-
A*-Heuristiken: die Bedeutung der Bewegungskosten erhalten
Für den tatsächlichen Bewegungsgraphen eine Heuristik mit unterer Schranke wählen, verbesserte Routen korrekt behandeln und die Pfadqualität gegen eine uninformierte Suche prüfen.
-
Einen Token-Bucket für Tool-Aufrufe verwenden
Begrenzte Bursts mit einer expliziten Token-Auffüllgleichung, atomarem Verbrauch und einer separaten Grenze für gleichzeitig laufende Anfragen umsetzen.
-
Sortierstabilität: was sie garantiert und wann sie wichtig ist
Eine stabile Sortierung behält die Eingabereihenfolge von Elementen bei, die als gleich verglichen werden. Python garantiert sie, ECMAScript fordert sie seit 2019, Go und GNU sort bieten sie als Option an; sie entscheidet, ob Mehrschlüssel-Sortierungen, sortierbare Tabellen und paginierte Abfragen sich vorhersehbar verhalten.
Maschinenlesbar: JSON