Ich finde einige Datenstrukturen echt interessant. Immer wieder schön zu sehen, welche Hacks sich überlegt wurden. Vielleicht braucht es ja einen Datenstruktur-Dienstag?
Den Anfang macht…
Posts mit Tag "datenstrukturen"
Datenstrukturdienstag: Eine meiner lieblings-Strukturen, der Bloom-Filter.
Eine wichtige Eigenschaft eines Bloom-Filters ist die False-Positive-Rate. Das ist die Wahrscheinlichkeit für False-Positives. Zu dieser Wahrscheinlichkeit gab es 30 Jahre später noch eine neue Formel, da die ursprüngliche wohl fehlerhaft war. Hier ist ein Writeup dazu. Hier ist noch ein Paper dazu.
Was man in der Praxis für Probleme mit einem Bloom-Filter haben kann, hat Cloudflare mal aufgeschrieben.
Datenstrukturdienstag: Letzte Woche gab’s den Bloom-Filter, diese Woche muss man dann wohl den Cuckoo-Filter erwähnen.
Großer Unterschied (IMHO): Man kann auch Einträge wieder löschen.
Datenstrukturdienstag: Heute keine konkrete Datenstruktur, nur ein Link auf diese tolle Seite, die Algorithmen und Datenstrukturen mit IKEA-Bauanleitungs-artigen Grafiken erklärt.
Datenstrukturdienstag: Diese Woche keine probabilistische Datenstruktur. Stattdessen etwas eher klassischeres: Merkle-Tree.
Grundidee: Man hat Daten(-Blöcke), welche man hasht. Diese Hashes hasht man dann in Zweierpaaren zu einem neuen Hash. Das macht man so lange, bis man nur noch einen Hash übrig hat, der implizit einen Hash über alle Datenblöcke repräsentiert. Ein Knoten in dem Baum ist dabei ein Hash, die Kind-Zweige jeweils die Vorgänger-Hashes. Wer alle Datenblöcke vor sich liegen hat, kann den Merkle-Tree berechnen. Ist ein Datenblock fehlerhaft, stimmt am Ende der Root-Hash nicht.
Das Konzept kommt ursprünglich aus 1979 von Ralph Merkle. Eine der bekanntesten Anwendungen heutzutage ist die Bitcoin-Blockchain. Dort wird ein Merkle-Tree verwendet, um einen Hash über die Transaktionen innerhalb eines Blocks zu berechnen. Die Wurzel dieses Merkle-Trees ist bei Bitcoin dann Teil von dem, was als Grundlage für den SHA-1-Hash verwendet wird, der “gemined” wird. Ursprünglich erfunden wurde der Merkle-Tree, um P2P-Dateiaustausch zu vereinfachen. Hier ist ein Artikel dazu.
Datenstrukturdienstag: Der Prefix-Tree bzw. “Trie”.
Grundidee: Ein Baum, bei dem jeder Knoten ein Buchstabe ist. Will man einen String ablegen, “geht” bzw. erstellt man den entsprechenden Pfad, der zu dem String gehört. Man muss den Key deshalb nicht separat abspeichern. Der Pfad zum Wert ist der Key. Die Menge der Keys ist dadurch die Menge der Pfade, die in einem Blatt enden.
Neulich habe ich hiermit ein bisschen geliebäugelt, um es ggf. als optimierte Variante anstelle einer Hashmap zu verwenden. Die Keys, die ich in die Map gesteckt habe, waren alle sehr ähnliche Strings. Vor allem waren es Strings, die semantisch mehr miteinander zu tun hatten, je gleicher der Prefix ist. Das hätte vor allem die Lookup-Zeiten aufgrund von CPU-Caches reduzieren können.
Bevor ich ausprobiert hab, ob es sich lohnt, hab ich natürlich gegooglet. Wichtige Erkenntnisse dabei haben dieser und dieser post geliefert. tl;dr: Eine Standard-Hashmap (z. B. aus Java) ist ziemlich optimiert und ein Prefix-Tree lohnt sich meistens eher nicht. Manche sehen das auch als Contest an, die schnellste Hashtable zu schreiben.
Datenstrukturdienstag: Dieses Mal gibt es wieder eine probabilistische Datenstruktur: Count–min-Sketch. Damit kann man (probabilistisch) schätzen, wie oft ein Element vorgekommen ist, z. B. wenn man einen Datenstrom hat und vorbeigehende Dinge zählt.
Datenstrukturdienstag: Letzte Woche: Zählen, wie oft bestimmte Elemente vorkamen. Diese Woche: Zählen, wie viele Elemente in einer Menge enthalten sind.
Verwenden kann man dafür HyperLogLog (ja, wieder probabilistisch).
Anwendungsfall: Ihr habt eine Menge, zu der ständig neue Elemente hinzukommen. Ihr braucht euch nicht jedes Element merken. Aber es kann sein, dass ein Element, das eigentlich schon drin ist, noch mal hinzugefügt werden soll. Ihr wollt dieses Element nicht doppelt zählen (Fachbegriff Count-Distinct-Problem).
Konkret wollt ihr vielleicht die Anzahl der Aufrufe eines Videos zählen und nimmt dabei die ID des Users, der es angesehen hat, als Kriterium. Schaut sich die Person es noch mal an, wollt ihr sie nicht noch mal zählen. HLL hat dabei einen sehr langsam wachsenden Speicherbedarf (ursprünglich log(log(n)), daher der Name) und kann in O(1) Elemente hinzufügen.
In der Praxis muss man das natürlich nicht selber bauen. Redis hat das built-in. Und für jede Sprache gibt’s das sicherlich auch als Library.
HLL wird natürlich bei den “ganz großen” verwendet (Reddit hat hier berichtet, wie sie ihre Views zählten; habe gehört, dass sie es mittlerweile nicht mehr so machen). Diese Datenstruktur ist auch der Grund, warum Video-Views oder Upvote-Counts meistens nicht die genaue Zahl wiederspiegeln. HLL hat eine Fehlerrate von ~2%.
Es gibt von HLL noch weitere Abwandlungen, z. B. HLL++.
Datenstrukturdienstag: Log-Structured-Merge-Tree (LSM-Tree).
Das ist ein Suchbaum. Die Idee: Man hat mehrere Bäume (Bei Wikipedia C_0 und C_1). Der erste Baum liegt im RAM, der zweite auf der Festplatte. Neue Einträge kommen in den RAM. Wenn C_0 einen Threshold übersteigt, werden Daten von C_0 nach C_1 migriert, also auf die Festplatte.
Der Vorteil: Neu eingesetzte Daten liegen direkt im RAM und können schnell abgerufen werden. Aus diesem Grund wird diese Struktur auch gern bei In-Memory-Datenbanken verwendet.
Es kommt auch vor, dass man mehrere Level an Bäumen hat, z. B. ein C_2, das irgendwo auf einem anderen Server im Cluster liegt.
Datenstrukturdienstag:
B-Bäume und B+-Bäume (nein, das B steht nicht für “Binary”). Beides selbst-balancierende Suchbäume.
Was ist “Balancierend”? Wenn man einen Baum hat, in dem man Daten sucht, ist die Zeit, die man braucht, um ein Element zu finden, häufig an die Höhe des Baums gebunden. Es ist also von Vorteil, wenn der Baum möglichst niedrig ist. Je nach Baum kann es aber vorkommen, dass es einen langen Pfad gibt, der deutlich länger als die anderen im Baum ist. Sowas ist immer ungünstig, wenn man dann genau eines der Elemente sucht, das sich in diesem langen Pfad befindet. Hierfür hat balanciert man Bäume - d.h. man ordnet die Knoten so um, dass die Blätter des Baums immer in etwa auf der gleichen Höhe hängen. “Selbst-balancierend” heißt hier, dass das nicht ein Prozess ist, der ab und zu mal angestoßen wird, sondern dass die Operationen auf dem Baum (einfügen, Löschen etc.) so definiert sind, dass er sich beim Verändern entsprechend balanciert.
Beide Strukturen werden häufig in Datenbanken und vor allem in Dateisystemen verwendet, z. B. bei NTFS und ext4.
Datenstrukturdienstag: Mir ist aufgefallen, das ich sehr viele Bäume poste. Heute mal kein Baum, sondern eine verkettete Liste mit einem Trick: Die XOR-Linked-List.
Das ist eine Doppelt-Verkettete-Linked-List. Bei dieser Variante wird an jedem Knoten aber nur ein Pointer für die Prev- bzw. Next-Nodes benötigt. Dieser Pointer ist kein Pointer in dem Sinne, sondern das XOR des Prev- und Next-Pointers.
Das geht, weil man beim Traversieren der Liste ja weiß, von welchem Element man kommt. Man kann deshalb immer die Adresse des nächsten (bzw vorherigen) kNotens ausrechnen, indem man den Pointer, von dem man kommt, mit XOR drauf rechnet.
Warum man diese Struktur in der Praxis nicht wirklich sieht? Das kann man gut an der Sektion “Drawbacks” auf Wikipedia lesen. Naja, und eigentlich ist’s jetzt nicht so krass, einen Pointer pro Node einzusparen.
Datenstrukturdienstag: Der Splay-Tree. Ist von den Zugriffszeiten im Prinzip wie viele andere selbst-balancierte Bäume, aber mit einem Unterschied: Er schreibt auch bei Lesezugriff. So sortiert er häufig zugegriffene Nodes so um, dass sie schneller gefunden werden.
Bei zufälligem Zugriff performt er wie andere Bäume. Aber wenn im Zugriff ein Muster ist, kann seine Optimierung richtig zutrage kommen und wird ggf. schneller als O(log(n)).
Ich wollte diesen Baum mal in Rust implementieren, als Übungsaufgabe. Dann ist mir aufgefallen, dass der echt nicht so geil für alles ist, was mehr als einen Thread hat, da auch Leseoperationen schreibend zugreifen (naja, das war ja auch sein Vorteil). Vielleicht gibt’s da eine bessere Variante von, die dieses Problem nicht hat? Vielleicht eine, bei der jeder Thread seine Thread-Local-Kopie hat und nur die “richtigen” schreibenden Operationen synchronisiert werden? Wenn jemand eine Idee hat, her damit!
Wie viele Datenstrukturen ist er schon etwas älter und kommt aus 1985.
Datenstrukturdienstag: Heute keine “Datenstruktur”, eher ein Algorithmus. Aber das ist ja quasi beides das gleiche bzw nicht voneinander zu trennen.
FP-Growth (Frequent-Pattern) kommt zusammen mit dem FP-Tree. Der Algorithmus ist etwas komplizierter. Hier ist noch ein Artikel und ein Video dazu.
Was macht der? Das ist der Algorithmus hinter “Kunden, die X und Y kauften, kauften auch…”, also er findet oft zusammen auftretende Einträge. Das macht er sehr effizient, sodass man das auch auf großen Datenmengen (TM) laufen lassen kann.
Datenstrukturdienstag: Rot-Schwarz-Baum (oder RB-Tree).
Ist ein selbst-balancierender Suchbaum, der in den meisten Implementierungen einer Map bzw. eines Dictionaries verwendet wird.
Beispielsweise ist std::map in den meisten Implementierungen intern ein RB-Tree. Aber auch B-Bäume und AVL-Bäume werden gern verwendet.
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.
Datenstrukturdienstag: Die Circular-Linked-List mit Tail-Verweis (statt Head-Referenz). Ist auch die lieblings-Datenstruktur von Anders Hejlsberg, dem C#-Erfinder, die er hier genauer erläutert. Das ganze Interview ist auch ganz interessant.
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: 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.
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.
Eine halbe Datenstruktur: Linked timestamping
VSCode Text Buffer Reimplementation (2018). Geht im eine optimierte Variante von Piece Tables.
Postgres kann Indizes mit Bloom-Filter.
Use-Case:
In the case of an index access method, it allows fast exclusion of non-matching tuples via signatures whose size is determined at index creation. […] This type of index is most useful when a table has many attributes and queries test arbitrary combinations of them. A traditional btree index is faster than a bloom index, but it can require many btree indexes to support all possible queries where one needs only a single bloom index. Note however that bloom indexes only support equality queries, whereas btree indexes can also perform inequality and range searches.
Overflow in consistent hashing (2018).
Wie zstd funktioniert, eine Reihe: Zstandard Worked Example Part 1: Concepts
Zed ist gerade für Linux erschienen. Das ist ein Editor, an dem ehemalige Atom-Entwickler sitzen. Der ist vorallem interessant, weil sie von Grund auf auf Collaboration gesetzt haben. Die Kern-Datenstrukturen für ihre Textbearbeitung sind CRDTs.
Gerade sah ich einen schönen Artikel darüber, wie sie Positionen innerhalb des Texteditors intern darstellen: Zed Decoded: Text Coordinate Systems. Gibt es auch als Video.
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.
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.
Unter einem Artikel über Fixed-Integer-Width-Vektoren (hier) stand ein netter Hinweis, den ich hier mal zitiere:
Instead of doing stuff like
(word >> bit_offset) & self.mask, in C or C++ I usually write_bextr_u64, or when using modern C#Bmi1.X64.BitFieldExtract. Note however these intrinsics compile into 2 instructions not one, because the CPU instruction takes start/length arguments from lower/higher bytes of a single 16-bit number.
Geht seit Haswell (~2013), cool!