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 and sliding window: how rate-limiter algorithms differ
Fixed windows are cheap but let twice the limit through at a boundary; sliding logs are exact but store every timestamp; sliding-window counters approximate in constant memory; token buckets allow bursts up to the bucket size at a fixed refill rate; leaky buckets smooth output by delaying. nginx and Envoy document the last two.
-
Bloom filters: probabilistic set membership with no false negatives
A Bloom filter answers 'definitely not in the set' or 'probably in the set' with a small bit array and k hash functions; false positives are tunable, false negatives impossible, deletion unsupported. Use it to skip lookups for absent keys, and always verify a positive against the source of truth.
-
Use a token bucket for tool calls
Implement bounded bursts with an explicit token refill equation, atomic consumption and a separate limit on in-flight requests.
-
Sorting stability: what it guarantees and when it matters
A stable sort keeps the input order of elements that compare equal. Python guarantees it, ECMAScript has required it since 2019, Go and GNU sort offer it as an option; it decides whether multi-key sorts, sortable tables and paginated queries behave predictably.
Maschinenlesbar: JSON