Der Boyer-Moore-Horspool-Algorithmus zur Substring-Suche. Der wird bei Zig in der Standard-Library für ìndexOf verwendet.
Passend dazu hat jemand eine Implementierung eines anderen Alogrithmus auf SIMD-Basis geschrieben.
Der Boyer-Moore-Horspool-Algorithmus zur Substring-Suche. Der wird bei Zig in der Standard-Library für ìndexOf verwendet.
Passend dazu hat jemand eine Implementierung eines anderen Alogrithmus auf SIMD-Basis geschrieben.
Raytracing, die Rendergleichung und Bidirektionale Reflexionsverteilungsfunktion.
Hier gibt es noch tolle Kanäle dazu: g5min und cgvrlab903.
Und noch ein paar Videos: Introduction to Computer Graphics. Und noch ein Walk-Through und das obligatorishe Computerphile-Video.
Wie zstd funktioniert, eine Reihe: Zstandard Worked Example Part 1: Concepts
Bitwise Binary Search: Elegant and Fast. Was nicht im Titel steht: Durch das Bitwise wird sie branchless.
Floyds Algorithmus ist auch mehr Algorithmus als Datenstruktur. Er dient dazu, den Anfang eines Zykels in einer verketteten Liste zu finden. Der Zykel kann dabei an einem beliebigen Punkt starten.
Kennengelernt habe ich ihn über diesen Sketch. Dort wird der Algorithmus etwas anders vorgestellt: Zum Finden eines doppelten Eintrags in einem Array. Im Vergleich zu einem Hash-Set bzw. ähnlichen Varianten hat Floyds algorithmus lineare Zeit und konstanten Speicher, also schon echt gut.
In diesem Video wird der Algorithmus noch mal genauer erklärt. Um zu verstehen, was das macht, hab ich das auch mal in Python implementiert und gegen zwei naive Implementierungen getestet. Ergebnis: Das mit dem Speicherverbrauch merkt man sofort — die lineare Laufzeit kickt nicht so. Vielleicht waren die Daten zu wenig oder ich habe falsch gemessen.
Datenstrukturdienstag: In Anlehnung an letzte Woche: Die Levensthein-Distanz.
Ein Maß für die Ähnlichkeit zweiter Strings. Grob gesagt gibt es an, wie viele Tasten man auf der Tastatur drücken muss, um von einem String auf den anderen zu kommen (mit Backspace etc). Es gibt verschiedene Algorithmen, um dieses Maß zu berechnen. Auf Wikipedia ist eine rekursive und eine Matrix-Variante. Sie unterscheiden sich deutlich in der Platzkomplexität.
Verwenden kann man das z. B: fĂĽr eine Rechtschreibkorrektur. Oder generell, wenn man Nutzereingaben hat und man weiĂź, dass Nutzer sich genre vertippen.
Datenstrukturdienstag: Eher ein Algorithmus: MinHash.
Damit lassen sich zwei Mengen auf Ähnlichkeit prüfen. Das kann man z. B. verwenden, wenn man zwei Wortmengen hat und rausfinden möchte, ob es ungefähr das gleiche ist. Laut Wikipedia wurde das bei AltaVista verwendet, um Duplikate bei den indizierten Webseiten zu vermeiden.
Datenstrukturdienstag: Heute wieder keine Datenstruktur, sondern dieses Mal wirklich nur ein Algorithmus bzw. ein Konzept: Die Hilbert-Curve.
Anwendungsfall: Man ordnet einem Punkt (beliebige Dimension, z. B. einem Punkt in einem Bild) einen Punkt auf einer Kurve zu. Man denkt sich jetzt vielleicht “Toll, das kann ich auch. Einfach die einzelnen Zeilen hintereinander legen”. Die Hilbert-Kurve hat aber eine besondere Eigenschaft: Punkte, die nah beieinander auf der Kurve waren, sind es auch im Ursprungssystem. Man kann deshalb die Länge (und somit die “Auflösung) erhöhen und die Punkte auf der Hilbert-Kurve verlieren nicht ihren räumlichen Bezug.
Damit kann man z. B. den IPv4-Adressraum schön plotten.
Da gibt es ein sehr gutes Video von einem meiner lieblings-Youtuber zu, 3blue1brown.
Update: Korrektur der Punktposition, nach Hinweis eines Lesers.
Richtig coole Idee: Hashing zur Stringsuche. Der Autor verlinkt auch die Knuth-Morris-Pratt-String-Suche.
Wir hatten neulich ja die Bewertungssysteme von HN und Reddit. Hier schreibt Chatroulette, wie sie ihr Matchmaking machen[hinweis].
Ab und zu muss man aus einem größeren Zahlenraum auf einen kleineren mappen, z. B. auf den Index eines Arrays. Da sieht man häufig eine Konstruktion mit Modulo: arr[i % n] (wobei n die Länge des Arrays ist).
FĂĽr manche ist Modulo zu langsam. In dem Fall kann man diesen Hack anwenden. Aber Achtung, macht nicht das gleiche wie Modulo. Aber verteilt trotzdem auf die Range, die man haben will (ob das wir Modulo bei Zufallswerten auch einen Bias einfĂĽhrt, steht da glaub ich aber nicht).
Wo wir gerade bei Ratings waren: Hier eine Analyse, wie es möglicherweise bei Hacker News funktioniert. Hier ist noch eine andere Analyse.
Wie Reddit ihre Dinge (Kommentare, Posts) sortiert (oder es zumindest mal getan hat). Reddit war wohl vor ein paar Jahren auch noch open source. Hier gibt’s den originalen Quelltext davon. Dieses Ranking-System wird auch auf pr0gramm verwendet.