Ein Blog

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.

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.