Einführung in die Themen Datenstrukturen, Algorithmen und Komplexität / Berechenbarkeit in C++
Achtung – dieses Tutorial ist sehr theorielastig – wir werden ein wenig über die Grundlagen von Datenstrukturen, Algorithmen und Komplexität sprechen – all das vor allem im Zusammenhang mit C – also fangen wir mit den Datenstrukturen in C an
Listen, Wörterbücher und Warteschlangen
Wir beginnen mit einigen grundlegenden Datenstrukturen, die wir bereits verwendet haben, ohne tief in die Themen einzusteigen; diese beiden sind std::vector (im Grunde Listen) und std::map (im Grunde Wörterbücher).
Listen und Vektoren
Beginnen wir mit dem std::vector – wir verwenden diese Datentypen bereits für die verschiedenen Stimmen. Die Komplexität beträgt fast O(1) oder im schlimmsten Fall O(n). Für einen std::vector ist der Zugriff auf ein beliebiges Element seine „Superkraft“. Da ein Vektor seine Elemente in einem zusammenhängenden Speicherblock speichert, muss er die Liste nicht wie eine Kette durchlaufen. Daher beträgt die Komplexität für den Zugriff auf ein beliebiges Element in der Liste O(1) – also konstant.
Wörterbücher und Maps
Fahren wir mit dem Wörterbuch (oder besser gesagt der Map) in C++ fort. Wir verwenden std::map, um den verschiedenen Schlüsseln eine bestimmte Häufigkeit zuzuweisen. Im Gegensatz zu std::vector, das auf einem zusammenhängenden Array basiert, wird eine std::map typischerweise als Rot-Schwarz-Baum (eine Art selbstausgleichender binärer Suchbaum) implementiert. Dieser strukturelle Unterschied verändert die Art und Weise, wie Daten verarbeitet werden, grundlegend.
Bei std::map haben das Hinzufügen, Entfernen und sogar das Suchen eines Elements alle dieselbe Komplexität: logarithmische Zeit O(\log n).
Warum O(\log n)?
In einem ausgeglichenen Baum schließt man bei jedem „Schritt“ (dem Vergleich des Schlüssels mit dem aktuellen Knoten) effektiv die Hälfte der verbleibenden Möglichkeiten aus. Bei 8 Elementen sind höchstens 3 Schritte erforderlich ($2^3 = 8$). Bei 1.024 Elementen sind höchstens 10 Schritte erforderlich ($2^{10} = 1024$). Bei 1.000.000 Elementen sind es nur etwa 20 Schritte.
Warteschlangen, Deques und Stacks
Während Vektoren sich hervorragend für den wahlfreien Zugriff eignen, benötigen wir manchmal eine Struktur, die die Reihenfolge der Verarbeitung streng regelt. In C++ wird dies typischerweise durch std::queue gehandhabt. Eine Warteschlange folgt dem FIFO-Prinzip (First-In, First-Out). Stellen Sie sich eine reale Warteschlange im Supermarkt vor: Die erste Person, die sich anstellt, ist auch die erste, die wieder geht. In Ihrem Synth-Projekt ist eine Warteschlange (genauer gesagt ein threadsicherer Ringpuffer) unerlässlich, um MIDI-Nachrichten oder Audio-Samples zwischen dem UI-Thread und dem Audio-Callback-Thread mit hoher Priorität zu übertragen. Komplexität: Bei std::queue sind sowohl das Hinzufügen eines Elements (push) als auch das Entfernen des vordersten Elements (pop) $O(1)$. Deques sind doppelseitige Warteschlangen, bei denen Sie jedes Element von beiden Seiten der Warteschlange hinzufügen oder entfernen können.
Datenstruktur | Zugriff | Suche | Einfügen (Durchschnitt) |
std::vector | O(1) | O(n) | O(1) (amortisiert am Ende) |
std::map | O(log(n)) | O(log(n)) | O(log(n)) |
std::list | O(n) | O(n) | O (1) |
std::deque | O(1) | O(n) | O(1) (an den Enden) |
Einen benutzerdefinierten Datentyp erstellen
Nachdem wir nun an der Oberfläche des Themas gekratzt haben, wollen wir nun tiefer einsteigen und unsere eigene Datenstruktur erstellen: den (Audio-)Ringpuffer. Wir nutzen die Standard Template Library und erstellen unsere eigene Implementierung eines Ringpuffers…
| |
| |
Dieser benutzerdefinierte Ringpuffer ist eine perfekte Brücke zwischen reiner Theorie und praktischer Synthesizer-Entwicklung. Bei der Audio-Programmierung können wir std::vector oder std::map oft nicht direkt innerhalb des Audio-Callbacks verwenden, da diese möglicherweise Speicher zuweisen, was einen Systemaufruf auslöst und das Risiko eines Audio-Fehlers (einer „Prioritätsinversion“) birgt.
Deine Implementierung nutzt Atomics, die das Geheimnis für lock-freie Parallelität sind. Lassen Sie uns das „Wie“ und „Warum“ dieser Struktur aufschlüsseln, um den Abschnitt „Datenstrukturen“ abzuschließen, bevor wir zu den Algorithmen übergehen.
Die Anatomie des Audio-Ringpuffers
Ein Ringpuffer (oder zirkulärer Puffer) behandelt ein Array fester Größe so, als wäre es Ende an Ende verbunden. Wenn der writeIndex das Ende des Arrays erreicht, springt er mithilfe des Modulo-Operators (%) zurück an den Anfang.
Warum std::atomic?
In einem multithreaded Synth laufen der Audio-Thread (Producer) und der GUI-Thread (Consumer) gleichzeitig. Würden wir ein reguläres size_t verwenden, könnte ein Thread einen teilweise aktualisierten Wert sehen, was zu einem Absturz oder „mangelhaften“ Audiodaten führen würde. std::atomic stellt sicher, dass die Indexaktualisierung „atomar“ (alles oder nichts) ist und über verschiedene CPU-Kerne hinweg sichtbar ist.
Speicherbarrieren (Acquire/Release)
Im Code werden Sie std::memory_order_release und std::memory_order_acquire bemerken. Diese dienen nicht nur der Show; es handelt sich um Speicherbarrieren:
Release: Weist die CPU an: „Stelle sicher, dass alle meine Datenschreibvorgänge (die Audio-Samples) abgeschlossen sind, bevor du den Index aktualisierst.“
Acquire: Weist die CPU an: „Bevor ich den Index lese, stelle sicher, dass ich über die neuesten damit verbundenen Daten verfüge.“
Übersetzt mit DeepL.com (kostenlose Version)