Content |
Erste Tests mit eindimensionalen Arrays
Aufgabe
-
Eine Funktion init_vector soll einen Vektor initialisieren. Der Vektor wird dabei spezifiziert über die Anfangsadresse, die Anzahl der Elemente und dem Abstand zwischen den Elementen. Dabei ist das erste Element mit einer 1 zu initialisieren, das zweite Element mit einer 2 usw.
-
Analog dazu soll die Funktion print_vector einen Vektor ausgeben, der auf die gleiche Weise spezifiziert wird.
Ein Test sollte dann
-
ein globales Array mit 8 Elementen deklarieren,
-
zunächst das gesamte Array als einen Vektor initialiseren und ausgeben,
-
dann das globale Array für zwei Vektoren der Länge 4 verwenden, die im Speicher hintereinander liegen und jeweils zu initialisieren und auszugeben sind, und
-
schließlich das globale Array für zwei Vektoren der Länge 4 zu verwenden, wobei die Elemente des globalen Arrays jeweils alternierend dem ersten und dem zweiten Vektor gehören, und diese wiederum zu initialisieren und auszugeben.
Lösungsvorschlag
#include <stdio.h> #include <stdlib.h> void init_vector(double* v, size_t len, size_t incr) { for (size_t i = 0; i < len; ++i) { v[i*incr] = i + 1; } } void print_vector(double* v, size_t len, size_t incr) { for (size_t i = 0; i < len; ++i) { printf(" %4.1lf", v[i*incr]); } printf("\n"); } #define MAX_LEN 8 double vector[MAX_LEN]; int main() { double* x = vector; printf("initialize x as one vector\n"); size_t len = MAX_LEN; init_vector(x, len, 1); printf("x = "); print_vector(x, MAX_LEN, 1); printf("using the space for two vectors\n"); len = MAX_LEN/2; double* y = vector + len; init_vector(x, len, 1); init_vector(y, len, 1); printf("x = "); print_vector(x, len, 1); printf("y = "); print_vector(y, len, 1); printf("vector = "); print_vector(vector, MAX_LEN, 1); printf("using the space for two interleaving vectors\n"); y = vector + 1; init_vector(x, len, 2); init_vector(y, len, 2); printf("x = "); print_vector(x, len, 2); printf("y = "); print_vector(y, len, 2); printf("vector = "); print_vector(vector, MAX_LEN, 1); }
Übersetzen und Ausführen
$shell> gcc -Wall -o example1_vector example1_vector.c $shell> ./example1_vector initialize x as one vector x = 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 using the space for two vectors x = 1.0 2.0 3.0 4.0 y = 1.0 2.0 3.0 4.0 vector = 1.0 2.0 3.0 4.0 1.0 2.0 3.0 4.0 using the space for two interleaving vectors x = 1.0 2.0 3.0 4.0 y = 1.0 2.0 3.0 4.0 vector = 1.0 1.0 2.0 2.0 3.0 3.0 4.0 4.0
Aufgabe
Um zu sehen, wie die Zugriffszeiten skalieren, sollten Sie diese messen für Vektorlängen für alle Zweierpotenzen beginnend von 8.192 bis 67.108.864. Damit die Messungen sich möglichst wenig gegenseitig beeinflussen, sollten Sie für jede Vektorlänge - zwei doppelt so große Vektoren vector1 und vector2
dynamisch mit Hilfe von malloc belegen,
-
vector1 dann in zwei hintereinander liegende Vektoren aufteilen und diese mit Zeitmessung initialisieren,
-
vector2 in zwei ineinander verwobene Vektoren aufteilen und diese ebenfalls mit Zeitmessung initialisieren und
-
abschließend vector1 und vector2 wieder freigeben.
Lösungsvorschlag
#include <stdio.h> #include <sys/times.h> #include <unistd.h> #include <stdlib.h> /* return real time in seconds since start of the process */ double walltime() { #ifndef CLK_TCK /* CLK_TCK specifies the number of ticks per second */ static int CLK_TCK = 0; if (!CLK_TCK) { CLK_TCK = sysconf(_SC_CLK_TCK); } #endif struct tms timebuf; /* times returns the number of real time ticks passed since start */ return (double) times(&timebuf) / CLK_TCK; } void init_vector(double* v, size_t len, size_t incr) { for (size_t i = 0; i < len; ++i) { v[i*incr] = i + 1; } } void print_vector(double* v, size_t len, size_t incr) { for (size_t i = 0; i < len; ++i) { printf(" %4.1lf", v[i*incr]); } printf("\n"); } #define MAX_LEN 134217728 int main() { double* x; double* y; // two vectors living in the space of "vector" double t0, t1, t2; // time stamps printf(" len t1 (separate) t2 (interleaving) t2/t1\n"); for (size_t len = 8192; len <= MAX_LEN/2; len *= 2) { printf("%8zd", len); /* separate vectors */ double* vector1 = malloc(sizeof(double) * len * 2); x = vector1; y = vector1 + len; t0 = walltime(); init_vector(x, len, 1); init_vector(y, len, 1); t1 = walltime() - t0; printf(" %12.2lf", t1); /* interleaved vectors */ double* vector2 = malloc(sizeof(double) * len * 2); t0 = walltime(); x = vector2; y = vector2 + 1; init_vector(x, len, 2); init_vector(y, len, 2); t2 = walltime() - t0; printf(" %12.2lf %16.2lf", t2, t2/t1); printf("\n"); free(vector1); free(vector2); } }
Übersetzen und Ausführen
$shell> gcc -Wall -o example2_vector example2_vector.c $shell> ./example2_vector len t1 (separate) t2 (interleaving) t2/t1 8192 0.00 0.00 1.00 16384 0.00 0.00 1.00 32768 0.00 0.00 1.00 65536 0.00 0.01 16786438.07 131072 0.00 0.00 1.00 262144 0.01 0.01 1.00 524288 0.01 0.02 2.00 1048576 0.02 0.05 2.50 2097152 0.04 0.08 2.00 4194304 0.10 0.16 1.60 8388608 0.19 0.34 1.79 16777216 0.38 0.65 1.71 33554432 0.75 1.30 1.73 67108864 1.49 2.62 1.76