Anleitung
Zähle die Häufigkeit der Buchstaben in Texten mithilfe paralleler Berechnung.
Bei Parallelität geht es darum, Dinge parallel zu erledigen, die man auch nacheinander erledigen kann. Ein häufiges Beispiel ist das Zählen der Buchstabenhäufigkeit. Nutze die Parallelität, um die Gesamthäufigkeit jedes Buchstabens in einer Liste von Texten zu berechnen.
Asynchrone Tasks
Tasks sind die wichtigste Abstraktion, um in Lean asynchronen Code zu schreiben.
Sie sind leichtgewichtig und können parallel in einem anderen Thread oder nebenläufig im selben Thread ausgeführt werden.
Tasks können rein oder unrein sein.
Reine Tasks erstellst du mit Task.spawn, das eine reine Berechnung entgegennimmt.
Unreine Tasks entstehen aus IO-Berechnungen, zum Beispiel mit IO.asTask, das ein IO α innerhalb der IO-Monade zu einem Task α anhebt.
In dieser Übung ist die Funktion calculateFrequencies monadisch und gibt ein IO (Std.TreeMap Char Nat) zurück.
Dadurch kannst du unreine Tasks über IO.asTask verwenden, und es ist auch möglich, reine Tasks für Zwischenberechnungen zu starten, bevor du den endgültigen Wert zurückgibst.
Datenrennen vermeiden
Da Lean eine funktionale Sprache ist, sind die meisten Werte persistent, das heißt unveränderlich.
Operationen, die einen Wert zu verändern scheinen, erzeugen in Wirklichkeit einen neuen Wert mit den gewünschten Änderungen.
Das bedeutet, dass Speicher oft sicher zwischen Tasks geteilt werden kann, ohne dass Datenrennen entstehen.
Beachte jedoch, dass nicht alle Datenstrukturen gleich gut für die persistente Nutzung geeignet sind.
Wenn du zum Beispiel ein einzelnes Element eines Array aktualisierst, muss dafür meist das gesamte Array kopiert werden.
Dasselbe gilt für Std.HashSet und Std.HashMap.
Um solche Datenstrukturen effizient zu machen, setzt Lean auf Referenzzählung.
Solange es nur eine Referenz auf einen Wert gibt, können Aktualisierungen destruktiv ausgeführt werden, wodurch unnötiges Kopieren entfällt.
Andere Datenstrukturen wie List, Std.TreeSet und Std.TreeMap sind darauf ausgelegt, intern ihre Struktur zu teilen.
Bei Aktualisierungen verwenden sie unveränderte Knoten wieder, sodass mehrere Werte Referenzen auf dieselben Knoten teilen können.
Dadurch erfordert das Ändern eines Teils der Struktur meist kein Kopieren des gesamten Werts.
Deshalb eignen sie sich besonders gut dafür, zwischen Tasks geteilt zu werden.
Ausführungsgeschwindigkeit messen
Die Ausführungszeit jedes Tests wird mit IO.monoNanosNow in Nanosekunden gemessen und neben den Ergebnissen angezeigt.
Du kannst mit verschiedenen Ansätzen experimentieren und ihre Auswirkung auf die Laufzeitleistung überprüfen.
