6.5 KiB

Raw Permalink Blame History

Assignment: Vektor (heap-basiert)

📆 Fällig: ---- 📆 Musterlösung

Ihre Rakete hat das Raumschiff der Kryptonier getroffen und es ist mit einer lauten Explosion vom Himmel gefallen. Sie fühlen sich wie Will Smith in Independence Day.

Ziel: Ziel dieses Assignments ist es, die Vektoren der letzten Woche auf ein anderes Speichermodell umzubauen.

Vector: Struktur und Funktionen

Beschreibung des Programms

Die hier zu implementierende Aufgabe orientiert sich in der Funktionsweise an den stack-basierten Vektoren des letzten Assignments, allerdings mit dem Unterschied, dass die Speicherallokation jetzt von den Funktionen Ihrer Vektor-Bibliothek durchgeführt wird.

Implementieren Sie eine Struktur Vector und die dazugehörigen Funktionen in einer Datei vector_heap.c mit deren Hilfe man auf dreidimensionalen Vektoren die wichtigsten Operationen durchführen kann. Drei Dimensionen reichen, um die Flugbahn der Rakete zu berechnen!

Die Komponenten x, y und z sollen als double gespeichert werden.

Ihre Implementierung soll die folgenden Aktionen unterstützen:

vec_new - Erzeugen eines neuen Vektors mit Daten für die drei Komponenten
vec_new_null - Erzeugt einen Nullvektor (alle drei Komponenten [x,y,z] sind 0)
vec_add - Addieren zweier Vektoren
vec_sub - Subtrahieren zweier Vektoren
vec_mul_scalar - Multiplikation des Vektors mit einem Skalar
vec_mul_dot - Skalarmultiplikation zweier Vektoren
vec_mul_cross - Kreuzprodukt zweier Vektoren
vec_norm - Erzeugung des Einheitsvektors aus einem gegebenen Vektor (d.h. Vektor der Länge 1 mit derselben Richtung wie der ursprüngliche Vektor). Beachten Sie, dass vom Nullvektor kein Einheitsvektor erzeugt werden kann. In diesem Fall müssen Sie eine entsprechende Rückgabe machen, um den Fehler anzuzeigen.
vec_length - Berechnung des Betrages (der Länge) eines Vektors
vec_collinear - Test, ob zwei Vektoren kollinear (parallel oder antiparallel) sind
vec_equals - Test, ob zwei Vektoren gleich sind
vec_print - Ausgabe des Vektors auf der Console
vec_to_s - Umwandlung des Vektors in einen String

Keine der Funktionen verändert die übergebenen Vektoren, sondern erzeugt einen neuen Vektor und gibt diesen zurück. Siehe hierzu das Beispiel unten.

Bei einer C-Bibliothek muss man sich entscheiden, wer für die Allokation des Speichers zuständig ist. Hier entscheiden wir uns dafür, dass die Bibliothek den Speicher beschafft und der Verwender ihn wieder freigeben muss. Auch die vec_to_str-Funktion beschafft Speicher für den String per malloc, den der Verwender per free wieder freigeben muss. Das folgende Beispiel zeigt, wie Ihre Vektor-Bibliothek zu benutzen ist:

Vector *v1, *v2, *v3, *v4, *v5;
char *result;

/* Vektoren erzeugen */
v1 = vec_new( 10.0, 20.0, 30.0);
v2 = vec_new(-20.0, 99.0, 38.0);

/* Kreuzprodukt berechnen. v1 und v2 bleiben unverändert,
   Ergebnis wird als neuer Vektor (v3) zurück gegeben. */
v3 = vec_mul_cross(v1, v2);

/* Ergebnis ausgeben */
result = vec_to_str(v3);
printf("Das Ergebnis ist: %s\n", result);
free(result);

/* Speicher für die Vektoren wieder freigeben */
free(v3);
free(v2);
free(v1);

Schreiben Sie eine Header-Datei vector_heap.h, welche die exportierten Funktionen als Prototypen enthält. Diese werden wir für die Tests benötigen. Kommentieren Sie die Funktionen ausreichend.

Tests

Überprüfen Sie die Funktionalität Ihrer Implementierung mit entsprechenden Unit-Tests (Datei vector_heap_test.c) und weisen Sie mit diesen Tests nach, dass die implementierten Operationen richtig funktionieren.

Für die Unit-Tests steht Ihnen eine ganz einfache Testbibliothek über das Header-File minitest.h zur Verfügung. Die Datei vector_heap_test.c enthält ein Beispiel für die Benutzung. Verwenden Sie das dort benutzte Schema und fügen Sie Ihre Tests hinzu.

Verwenden Sie bitte mindestens die folgenden Testdaten/Testfälle.

Multiplikation mit einem Skalar

[1, -5, 3] * 6 = [ 6, -30, 18 ]
[ 1, -5, 3 ] * -3 = [ -3, 15, -9 ]

Skalarprodukt zweier Vektoren

[ 1, 2, 3 ] * [ -7, 8, 9 ] = 36
[ -5, 9, 7 ] * [ 10, 3, 8 ] = 33

Addition und Subtraktion

[ 4, 0, 8 ] + [ -1, 4, 7 ] = [ 3, 4, 15 ]
[ 4, 0, 8 ] - [ -1, 4, 7 ] = [ 5, -4, 1 ]
[ 4, 0, 8 ] + [ -1, 4, 7 ] = [ -1, 4, 7 ] + [ 4, 0, 8 ]

Kreuzprodukt

[ 1, 2, 3 ] x [ -7, 8, 9 ] = [ -6, -30, 22 ]
[ 1, 2, 8 ] x [ 4, 3, 5 ] = [ -14, 27, -5 ]

Betrag

|[ 1, 1, 1 ]| = sqrt(3)
|[ 5, 4, 3 ]| = sqrt(50)

Kollinearität

[ 4, 5, 7 ] und [ 16, 20, 28 ] sind kollinear
[ 4, 5, 7 ] und [ 16, 20, 21 ] sind nicht kollinear

Komplexere Rechnung

([ -1, 5, -2 ] x [ 2, 1, 2 ]) * [ 2, 0, 5 ] = -31

Makefile

Automatisieren Sie das Compilieren und Testen Ihrer Programme mit einem Makefile. Dieses sollte mindestens die folgenden Targets haben:

all - baut alle Dateien
clean - setzt das Projekt zurück und löscht alle Kompilationsergebnisse
test - führt die oben beschriebenen Tests aus

Sie benötigen natürlich weitere Targets für die Objektdateien und fertigen Executables.

Benchmark

Sie haben jetzt zwei verschiedene Implementierungen einer Vektor-Bibliothek. Einmal wird der Speicher von der Bibliothek beschafft, einmal vom Verwender. Die spannende Frage ist, welche Version schneller ist.

Schreiben Sie für beide Bibliotheken einen kleinen Benchmark, der folgende Schritte wiederholt durchführt und die Zeit für die Ausführung misst.

Zwei Vektoren v1 und v2 anlegen.
Das Kreuzprodukt der Vektoren bestimmen (v3).
Das Produkt von v2 und v3 bestimmen.
Den Vektor v3 mit einem Skalar multiplizieren.
Den Vektor v4 mit einem anderen Skalar multiplizieren.

Sie können die Funktion clock() aus <time.h> verwenden, um eine genaue Zeitmessung durchzuführen.

Die Benchmarks sollten vector_heap_benchmark.c und vector_stack_benchmark.c heißen und in den jeweiligen Verzeichnissen der Bibliotheken liegen. Nehmen Sie die Ausführung der Benchmarks auch in die Makefiles auf, sodass sie beim test-Target ausgeführt werden.

Was fällt Ihnen auf?

Quellen

Skript zur Vorlesung
C-Tutorial
C von A bis Z
Vektorrechnung: Wikipedia: Vektor -- Rechenoperationentypedef

6.5 KiB Raw Permalink Blame History