data1k.txt: En testfil med 1000 mätvärden, med sensorsidan 1000000, som ska ge resultatet x=17, y=42, value=1.200000. Körtiden med programmen nedan är knappt märkbar.
data2M.txt (obs: 43 megabyte): En testfil med 2000000 mätvärden, med sensorsidan 1000000, som ska ge resultatet x=17, y=42, value=2.000000. Körtiden med hashtabell-programmet nedan (uppgift 2) är några sekunder. Med list-programmet (uppgift 1) tar det 1-2 timmar, beroende på hur snabb dator man har.
/* list-brightest.c */ #include <stdlib.h> #include <stdio.h> #include <string.h> #include <errno.h> struct Pixel { int x; int y; double brightness; struct Pixel *next; }; struct Pixel *first = NULL; struct Pixel *find_pixel(int x, int y) { struct Pixel *p = first; while (p != NULL) { if (p->x == x && p->y == y) return p; p = p->next; } return NULL; } struct Pixel *new_pixel(int x, int y) { struct Pixel *p = (struct Pixel *)malloc(sizeof(struct Pixel)); if (p == NULL) { fprintf(stderr, "Memory full. Couldn't allocate space for another pixel.\n"); exit(EXIT_FAILURE); } p->x = x; p->y = y; p->brightness = 0; p->next = first; first = p; return p; } void add_measurement(int x, int y, double value) { struct Pixel *p = find_pixel(x, y); if (p == NULL) p = new_pixel(x, y); p->brightness += value; } struct Pixel *find_brightest_point(void) { struct Pixel *p = first; struct Pixel *brightest_pixel_so_far = NULL; double brightest_value_so_far = 0.0; while (p != NULL) { if (p->brightness > brightest_value_so_far) { brightest_value_so_far = p->brightness; brightest_pixel_so_far = p; } p = p->next; } return brightest_pixel_so_far; } int main(void) { char file_name[1000]; FILE *tsin; int x, y; double brightness; long int number; struct Pixel *brightest_pixel; printf("Data file name: "); fgets(file_name, sizeof file_name, stdin); /* Get rid of the trailing newline character from fgets */ if (file_name[strlen(file_name) - 1] == '\n') file_name[strlen(file_name) - 1] = '\0'; tsin = fopen(file_name, "r"); if (tsin == NULL) { fprintf(stderr, "Couldn't read the data file '%s'.\n", file_name); fprintf(stderr, "Possible cause: %s (error code %d).\n", strerror(errno), errno); exit(EXIT_FAILURE); } number = 0; printf("Reading data from from '%s'...\n", file_name); while (fscanf(tsin, "%d %d %lf", &x, &y, &brightness) == 3) { add_measurement(x, y, brightness); ++number; } fclose(tsin); printf("Finished reading %ld measurements from '%s'.\n", number, file_name); printf("Finding brightest point...\n"); brightest_pixel = find_brightest_point(); printf("Brightest point: x=%d, y=%d, value=%f\n", brightest_pixel->x, brightest_pixel->y, brightest_pixel->brightness); return EXIT_SUCCESS; }
/* hash-brightest.c */ #include <stdlib.h> #include <stdio.h> #include <string.h> #include <errno.h> #define HASH_TABLE_SIZE (3*1000*1000 + 1) struct Pixel { int x; int y; double brightness; struct Pixel *next; }; /* Automatically set to all NULL, so we don't need to initialize */ struct Pixel *hash_table[HASH_TABLE_SIZE]; unsigned int hash_pixel(int x, int y) { return (x + y) % HASH_TABLE_SIZE; } struct Pixel *find_pixel(int x, int y) { unsigned int bucket = hash_pixel(x, y); struct Pixel *p = hash_table[bucket]; while (p != NULL) { if (p->x == x && p->y == y) return p; p = p->next; } return NULL; } struct Pixel *new_pixel(int x, int y) { unsigned int bucket = hash_pixel(x, y); struct Pixel *p = (struct Pixel *)malloc(sizeof(struct Pixel)); if (p == NULL) { fprintf(stderr, "Memory full. Couldn't allocate space for another pixel.\n"); exit(EXIT_FAILURE); } p->x = x; p->y = y; p->brightness = 0; p->next = hash_table[bucket]; hash_table[bucket] = p; return p; } void add_measurement(int x, int y, double value) { struct Pixel *p = find_pixel(x, y); if (p == NULL) p = new_pixel(x, y); p->brightness += value; } struct Pixel *find_brightest_point(void) { int bucket; struct Pixel *brightest_pixel_so_far = NULL; double brightest_value_so_far = 0.0; for (bucket = 0; bucket < HASH_TABLE_SIZE; ++bucket) { struct Pixel *p = hash_table[bucket]; while (p != NULL) { if (p->brightness > brightest_value_so_far) { brightest_value_so_far = p->brightness; brightest_pixel_so_far = p; } p = p->next; } } return brightest_pixel_so_far; } int main(void) { char file_name[1000]; FILE *tsin; int x, y; double brightness; long int number; struct Pixel *brightest_pixel; printf("Data file name: "); fgets(file_name, sizeof file_name, stdin); /* Get rid of the trailing newline character from fgets */ if (file_name[strlen(file_name) - 1] == '\n') file_name[strlen(file_name) - 1] = '\0'; tsin = fopen(file_name, "r"); if (tsin == NULL) { fprintf(stderr, "Couldn't read the data file '%s'.\n", file_name); fprintf(stderr, "Possible cause: %s (error code %d).\n", strerror(errno), errno); exit(EXIT_FAILURE); } number = 0; printf("Reading data from from '%s'...\n", file_name); while (fscanf(tsin, "%d %d %lf", &x, &y, &brightness) == 3) { add_measurement(x, y, brightness); ++number; } fclose(tsin); printf("Finished reading %ld measurements from '%s'.\n", number, file_name); printf("Finding brightest point...\n"); brightest_pixel = find_brightest_point(); printf("Brightest point: x=%d, y=%d, value=%f\n", brightest_pixel->x, brightest_pixel->y, brightest_pixel->brightness); return EXIT_SUCCESS; }