Programmeringsmetodik: Lösningar till tentamen 2009-08-20

Observera att detta är ett förslag på lösning. Det finns andra lösningar som också är korrekta.

Observera också att just den här lösningen inte skulle ge full poäng på tentan, eftersom jag inte modulariserat programmet med abstrakta datatyper och uppdelning på flera filer.

Om man skulle skriva det här programmet på riktigt, och inte som en tentauppgift där man just ska visa att man förstått modularisering, skulle man förmodligen inte bry sig om den typen av modularisering, eftersom programmet är så litet att det blir överblickbart ändå, och alltför mycket uppdelning kan tvärtom göra programmet svårare att skriva och förstå.

Här finns också ett program som slumpar fram filerna platser.txt och mosade.txt, så att man kan provköra sitt program: skapa-filer.c. (Programmet skapar 3 miljarder mosningar, och filen mosade.txt blir ungefär 30 gigabyte stor.)

Uppgiften (30 p)

Den här lösningen använder en hashtabell med fix storlek. På en modern dator med snabb processor (Intel Core i7 920) men förhållandevis långsam disk (Western Digital Caviar Green 1TB SATA/300), och med 2 miljoner platser och 3 miljarder mosningar, tar programmet ca 20 minuter att köra. Att bara läsa filen med de 3 miljarderna mosningar från disken, utan att behandla data på något sätt, tar på samma dator 5 minuter.

Programmet max-mosade.c:

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

#define TROLIGT_ANTAL_PLATSER (3*1000*1000)
#define HASH_SIZE (TROLIGT_ANTAL_PLATSER * 2)

struct plats {
    int nr;
    double latitud, longitud;
    int mosade; // Vi räknar med att maxantalet mosade får plats i en vanlig "int"
    struct plats* next_in_bucket;
};

struct plats* hash_table[HASH_SIZE];

int hashfunktion(int nyckel) {
    return nyckel % HASH_SIZE;
}

struct plats* find(int platsnummer) {
    struct plats* p = hash_table[hashfunktion(platsnummer)];
    while (p != NULL) {
        if (p->nr == platsnummer)
            return p;
        p = p->next_in_bucket;
    }
    return NULL;
}

int main(void) {
    FILE* platsfil = fopen("platser.txt", "r");
    if (platsfil == NULL) {
        fprintf(stderr, "Gick inte att öppna platsfilen!\n");
        exit(EXIT_FAILURE);
    }

    printf("Läser platser...\n");
    int antal_platser = 0;
    struct plats platsen;
    while (fscanf(platsfil, "%d %lf %lf", &platsen.nr, &platsen.latitud, &platsen.longitud) == 3) {

        platsen.mosade = 0;
        platsen.next_in_bucket = NULL;

        struct plats* p = malloc(sizeof(struct plats));
        if (p == NULL) {
            fprintf(stderr, "För många platser. Minnet är fullt!\n");
            exit(EXIT_FAILURE);
        }

        *p = platsen;

        // Stoppa in platsen i hashtabellen!
        int hashplats = hashfunktion(p->nr);
        p->next_in_bucket = hash_table[hashplats];
        hash_table[hashplats] = p;

        ++antal_platser;
    }

    fclose(platsfil);

    printf("Läst in platser: %d\n", antal_platser);

    FILE* mosfil = fopen("mosade.txt", "r");
    if (mosfil == NULL) {
        fprintf(stderr, "Gick inte att öppna mosfilen!\n");
        exit(EXIT_FAILURE);
    }

    printf("Läser mosade...\n");
    long int antal_mosningar = 0; // Det totala antalet mosningar får nog inte plats i en vanlig "int"
    int platsnummer, mosade;
    while (fscanf(mosfil, "%d %d", &platsnummer, &mosade) == 2) {

        struct plats* p = find(platsnummer);
        if (p == NULL) {
            fprintf(stderr, "Aj aj aj! Plats nummer %d finns inte!\n", platsnummer);
            exit(EXIT_FAILURE);
        }
        p->mosade += mosade;

        ++antal_mosningar;
    }

    fclose(mosfil);

    printf("Läst in mosningar: %ld\n", antal_mosningar);

    printf("Letar efter platsen med maxantalet...\n");

    // Vi förutsätter att det finns minst en plats med mer än noll mosade
    struct plats maxmosning;
    maxmosning.mosade = 0;
    for (int i = 0; i < HASH_SIZE; ++i) {
        struct plats* p = hash_table[i];
        while (p != NULL) {
            if (p->mosade > maxmosning.mosade)
                maxmosning = *p;
            p = p->next_in_bucket;
        }
    }

    printf("Platsen med maxantalet: nummer %d, latitud %f, longitud %f, %d mosade!\n",
           maxmosning.nr, maxmosning.latitud, maxmosning.longitud, maxmosning.mosade);

    return 0;
}


Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se), 20 augusti 2009