Programexempel från Progmet-föreläsning 2, onsdag 1 september 2010 ================================================================== *** Obs: Jag har flyttat om dessa exempel lite sen föreläsningen *** Planering för idag: Att hantera flera värden (double, heltal, poster...): fil Parametrar till main Att hantera flera värden (double, heltal, poster...): array (repetion) Pekare (repetition) malloc och free av en enda "variabel" (double, heltal, post) malloc och free av array Länkad lista: "invasiv enkellänkad lista" (double, heltal, post) Om vi hinner (fet chans...): Operationer på en (enkellänkad) länkad lista: insättning först, insättning sist, (insättning sorterad,) traversering, sökning, (sökning i sorterad), borttagning, sökning+borttagning, upprensning (och skräpsamling!) Tidskomplexitet: O(1), O(2) = O(1), O(N), O(N/2) = O(N) Riktiga tider på riktiga datorer Hantera flera värden - hur? --------------------------- Från C-kursen: fil, array Fler sätt: dynamiskt allokerad array, länkad lista, ... Parametrar till main -------------------- enkel-skapa-tal.c ----------------- // enkel-skapa-tal.c -- genererar slumpmässiga reella tal #include #include #include int main(int argc, char* argv[]) { if (argc != 2) { fprintf(stderr, "Ledsen error. Skriv: enkel-skapa-tal ANTAL\n"); exit(EXIT_FAILURE); } int antal; if (sscanf(argv[1], "%d", &antal) != 1) { fprintf(stderr, "Ledsen error. '%s' är inget helttal.\n", argv[1]); exit(EXIT_FAILURE); } srand(time(NULL)); for (int i = 0; i < antal; ++i) printf("%.2f\n", rand() % 10000 / 110.0 - 10.0); return 0; } Körexempel ---------- > ./enkel-skapa-tal 7 62.15 -7.26 71.94 5.47 -1.57 69.94 61.18 > skapa-tal.c ----------- // skapa-tal.c -- skapar en textfil med slumpmässiga reella tal #include #include #include #include #include void usage(void) { fprintf(stderr, "Skriv: skapa-tal ANTAL MIN MAX FILNAMN\n"); exit(EXIT_FAILURE); } int main(int argc, char *argv[]) { if (argc != 5) usage(); unsigned long antal; // En vanlig int är ofta bara 32 bitar, även på 64-bitarssystem if (sscanf(argv[1], "%lu", &antal) != 1) usage(); double min; if (sscanf(argv[2], "%lf", &min) != 1) usage(); double max; if (sscanf(argv[3], "%lf", &max) != 1) usage(); FILE *filen = fopen(argv[4], "w"); if (filen == NULL) { fprintf(stderr, "Det gick inte att skriva filen '%s'.\n", argv[4]); fprintf(stderr, "Möjlig felorsak: %s (felkod %d).\n", strerror(errno), errno); exit(EXIT_FAILURE); } srand((unsigned int)time(NULL)); for (unsigned long i = 0; i < antal; ++i) fprintf(filen, "%f\n", min + (max - min) * rand() / RAND_MAX); fclose(filen); return 0; } Körexempel ---------- > ./skapa-tal Skriv: skapa-tal ANTAL MIN MAX FILNAMN > ./skapa-tal 7 -2 2 Skriv: skapa-tal ANTAL MIN MAX FILNAMN > ./skapa-tal 7 -2 2 tal.txt > cat tal.txt 0.809558 1.351454 0.921997 -1.268917 0.971315 -0.399999 1.366292 > ./skapa-tal 7 -2 2 /här-får-jag-inte-skriva.txt Det gick inte att skriva filen '/här-får-jag-inte-skriva.txt'. Möjlig felorsak: Permission denied (felkod 13). > ./skapa-tal 7 -2 2 /katalogen/finns/inte.txt Det gick inte att skriva filen '/katalogen/finns/inte.txt'. Möjlig felorsak: No such file or directory (felkod 2). > Att hantera flera värden (double, heltal, poster...): array (repetion) ---------------------------------------------------------------------- baklanges-1.c -- talen lagras i minnet i en array med fast storlek ------------- /* baklanges-1.c -- läser tal och skriver dem i omvänd ordning */ #include #include int main(void) { FILE *tsin; FILE *tsut; /* Eller: FILE *tsin, *tsut; */ double talen[17]; int antal = 0; int i; tsin = fopen("reella-tal.txt", "r"); /* Hm... */ /* Nu hoppas vi att det inte är fler än 17 tal... */ while (fscanf(tsin, "%lf", &talen[antal]) != EOF) antal++; fclose(tsin); tsut = fopen("ny-fil.txt", "w"); for (i = antal - 1; i >= 0; --i) fprintf(tsut, "%f", talen[i]); /* Hm... */ fclose(tsut); return 0; } baklanges-2.c ------------- /* baklanges-2.c -- som baklanges-1.c, men rättare */ Pekare (repetition) ------------------- double d; char c; d = 3.14; c = 'G'; double *p1; p1 = &d; p1 = &c; // Nej, nej, nej! char *p2; p2 = &c; *p1 = 3.14; *p1 = *p1 + 6.023 p1 = NULL; *p1 = 2.3; // Nej, nej, nej! void* p3; p3 = &d; p3 = &c; malloc och free av en enda "variabel" (double, heltal, post) ------------------------------------------------------------ double *p4; p4 = malloc(sizeof double); p4 = (double*)malloc(sizeof double); *p4 = 3.17; char *p5; p5 = malloc(sizeof char); *p5 = 'x'; free(p4); free(p5); free(p3); // Nej, nej, nej! malloc och free av array ------------------------ double a[7]; a[3] = -0.14; double *p6; p6 = malloc(7 * sizeof double); p6[3] = -0.14; p6 = realloc(p6, 9 * sizeof double); free(p6); free(p5); // Nej, nej, nej! baklanges-3.c -- allokera så mycket plats som behövs, med malloc ------------- /* baklanges-3.c -- nu med en malloc-allokerad array */ #include #include int main(void) { FILE *tsin; FILE *tsut; double *talen; int antal = 0; int i; tsin = fopen("reella-tal.txt", "r"); /* Först räknar vi talen. Det känns ju lite jobbigt... */ while (fscanf(tsin, "%*f") != EOF) antal++; rewind(tsin); talen = malloc(antal * sizeof(double)); /* Hm... */ i = 0; while (fscanf(tsin, "%lf", &talen[i]) != EOF) ++i; fclose(tsin); tsut = fopen("ny-fil.txt", "w"); for (i = antal - 1; i >= 0; --i) fprintf(tsut, "%f\n", talen[i]); fclose(tsut); free(talen); return 0; } baklanges-4.c -- allokerar mer plats allteftersom den läser ------------- // baklanges-4.c -- nu med realloc // Med modernare C, t ex med variabeldefinitioner mitt i funktionen. // I Visual Studio 2008 måste man kompilera som C++. #include #include int main(void) { FILE *tsin = fopen("reella-tal.txt", "r"); int antal = 0; double* talen = NULL; // Ja, det funkar sen med realloc. double talet; while (fscanf(tsin, "%lf", &talet) != EOF) { ++antal; talen = realloc(talen, antal * sizeof(double)); // I C++ krävs explicita typkonverteringar här: // talen = (double*)realloc((void*)talen, antal * sizeof(double)); talen[antal - 1] = talet; } fclose(tsin); FILE *tsut = fopen("ny-fil.txt", "w"); for (int i = antal - 1; i >= 0; --i) fprintf(tsut, "%f\n", talen[i]); fclose(tsut); free(talen); return 0; } Körtider (Lenovo ThinkPad X100e, processor AMD Turion Neo X2 L625 1,6 GHz) -------- 100 000 tal: 0.19 s 1 miljon 000 tal: 1.43 s 10 miljoner tal: 14.04 s 100 miljoner tal: 2:19.66 = 139.66 s Slutsats: "Linjär tidskomplexitet"! Blir det dubbelt så många tal, så tar det dubbelt så lång tid att köra. Blir det tio gånger fler tal, så tar det tio gånger längre tid att köra. Länkade listor: "intrusiv enkellänkad lista" -------------------------------------------- ... baklanges-5.c -- länkad lista! ------------- // baklanges-5.c -- nu med länkad lista // Funkar INTE att komplera som C++. Övning: Varför? #include #include struct talpost { double talet; struct talpost *next; }; int main(void) { FILE *tsin; FILE *tsut; struct talpost *first = NULL; struct talpost *this; double talet; tsin = fopen("reella-tal.txt", "r"); while (fscanf(tsin, "%lf", &talet) != EOF) { struct talpost *new; new = malloc(sizeof(struct talpost)); new->talet = talet; new->next = first; first = new; } fclose(tsin); tsut = fopen("ny-fil.txt", "w"); this = first; while (this != NULL) { fprintf(tsut, "%f\n", this->talet); this = this->next; } fclose(tsut); /* Hm... */ this = first; while (this != NULL) { free(this); this = this->next; } return 0; } baklanges-6.c ------------- // baklanges-6.c -- som baklanges-5.c, men rättare baklanges-7.cpp --------------- // baklanges-7.cpp -- som baklanges-6.c, men funkar i C++ #include #include struct talpost { double talet; struct talpost* next; }; int main(void) { struct talpost* firstp = NULL; FILE *tsin = fopen("reella-tal.txt", "r"); double talet; while (fscanf(tsin, "%lf", &talet) != EOF) { struct talpost* newp; newp = (struct talpost*)malloc(sizeof(struct talpost)); newp->talet = talet; newp->next = firstp; firstp = newp; } fclose(tsin); FILE *tsut = fopen("ny-fil.txt", "w"); struct talpost* thisp = firstp; while (thisp != NULL) { fprintf(tsut, "%f\n", thisp->talet); thisp = thisp->next; } fclose(tsut); thisp = firstp; while (thisp != NULL) { struct talpost* to_be_freed = thisp; thisp = thisp->next; free(to_be_freed); } return 0; } Körtider -------- (fortfarande en Lenovo ThinkPad X100e, processor AMD Turion Neo X2 L625 1,6 GHz) baklanges-6.c (i C) och baklanges-7.cpp (i C++) gav nästan exakt samma tider! 100 000 tal: 0.28 s 1 miljon tal: 2.12 s 2 miljoner tal: 4.31 s 10 miljoner tal: 21.56 s Slutsats: Lite långsammare än realloc-versionen, men "linjär tidskomplexitet" även här Jämför: körtider på en snabbare dator (Intel Core I7 920 2.66GHZ 8MB S-1366) ---------------------------------------------------------------------------- 100 000 tal: 0.10 s 1 miljon tal: 0.96 s 2 miljoner tal: 1.93 s 10 miljoner tal: 9.60 s Snabbare, men fortfarande linjär tidskomplexitet! Blir det dubbelt så många tal, så tar det dubbelt så lång tid att köra. Hur lång tid tar det att bara gå igenom en länkad lista? -------------------------------------------------------- Summering av alla talen i listan (ur baklanges-8.cpp): double sum_list(struct talpost *firstp) { double sum = 0; struct talpost *thisp = firstp; while (thisp != NULL) { sum += thisp->talet; thisp = thisp->next; } return sum; } .... printf("Summan av talen är: %f\n", sum_list(firstp)); Det märks ingen skillnad, med en miljon element i listan! Gör det 1000 gånger: for (int i = 0; i < 1000; ++i) { sum_list(firstp); } 1000 gånger 1 miljon steg = en miljard: Tar 20 sekunder min långsamma laptop, 5 sekunder på min snabba dator 20 sekunder / 1000 = 0.02 sekunder 5 sekunder / 1000 = 0.005 sekunder Dvs, en lista med 1 miljon element tar nånstans kring en hundradels sekund att gå igenom. Övning: Varför tar då baklanges-7-programmet 0.96 sekunder, med en miljon tal? Mer om vi hinner ---------------- Operationer på en (enkellänkad) länkad lista: insättning först, insättning sist, (insättning sorterad,) traversering, sökning, (sökning i sorterad), borttagning, sökning+borttagning, upprensning (och skräpsamling!) Tidskomplexitet: O(1), O(2) = O(1), O(N), O(N/2) = O(N) Riktiga tider på riktiga datorer Lästips om fasta arrayer, dynamiska arrayer och länkade listor -------------------------------------------------------------- Vi lär oss det där med data: Grunder om lagringsstrukturer (http://www.databasteknik.se/webbkursen/lagring/index.html) Gunnar Jokis kompendium (på kursens hemsida): kapitel 2 och 3 Men, varning, om kapitel 3: Stackar och köer är INTE en sorts länkade listor! Stackar och köer är abstrakta datatyper, och de kan IMPLEMENTERAS med hjälp av länkade listor, men även t ex med arrayer. Bilting-boken ("Vägen till C, 2:a uppl"): sid 195-202 Weiss-boken sid 72-74, 83-94 Janlert-boken kapitel 3 och 4