Programexempel från Progmet-föreläsning 3, tisdag 6 september 2011 ================================================================== Kvar från igår: Körtider för baklanges-4, "linjär tidskomplexitet" Länkade listor: "intrusiv enkellänkad lista" Programmet baklanges-5 Körtider för baklanges-5 Hur lång tid tar det att bara gå igenom en länkad lista? Planering för idag: 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 Om vi hinner (fet chans...): Dubbellänkade listor Operationer på en dubbellänkad lista: ... Generella länkade listor: void-pekare i C, makron i C, templates i C++ C++: abstrakt datatyp (Person, komplexa tal, double) som klass Traversering = "gå igenom listan" (ur baklanges-7.cpp) ------------ struct talpost* thisp = firstp; while (thisp != NULL) { fprintf(tsut, "%f\n", thisp->talet); thisp = thisp->next; } En speciell sorts traversering: upprensning (men: skräpsamling!) ------------------------------------------- thisp = firstp; while (thisp != NULL) { struct talpost *to_be_freed = thisp; thisp = thisp->next; free(to_be_freed); } Programmet unique-1 ------------------- Indata: reella-tal.txt Utdata: ny-fil.txt -- utan dubbletter! En annan sorts traversering: Sökning (ur unique-1.cpp) ------------------------------------ struct talpost *find_in_list(struct talpost *firstp, double wanted) { struct talpost *thisp = firstp; while (thisp != NULL) { if (thisp->talet == wanted) return thisp; thisp = thisp->next; } return NULL; } .... while (fscanf(tsin, "%lf", &talet) != EOF) { if (find_in_list(firstp, talet) != NULL) { printf("Dubblett ignorerad: %f\n", talet); } else { struct talpost *newp; newp = (struct talpost*)malloc(sizeof(struct talpost)); newp->talet = talet; newp->next = firstp; firstp = newp; } } Körtider för unique-1 --------------------- (långsamma laptopen: Lenovo ThinkPad X100e, processor AMD Turion Neo X2 L625 1,6 GHz) Vad kan man vänta sig? (Från förra gången: "En lista med 1 miljon element tar nånstans kring en hundradels sekund att gå igenom") baklanges-7 med 100 000 tal: 0.28 s baklanges-7 med 1 miljon tal: 2.12 s baklanges-7 med 2 miljoner tal: 4.31 s baklanges-7 med 10 miljoner tal: 21.56 s Det var ju linjär tidskomplexitet: x gånger fler tal, x gånger längre tid unique-1 med 10 000 tal: 0.72 s unique-1 med 20 000 tal: 3.01 s (dvs ca 4 gånger mer än 0.72 s) unique-1 med 100 000 tal: 1:32.66 = 92.66 s (dvs någorlunda nära 100 gånger mer än 0.72 s) unique-1 med 1 miljon tal: Gissning: 10000 * 0.72 s = 7200 sekunder = 2 timmar Långsammare... Slutsats: "Kvadratisk tidskomplexitet"! Blir det dubbelt så många tal, så tar det FYRA så lång tid att köra. Blir det tio gånger fler tal, så tar det HUNDRA gånger längre tid att köra. Blir det x gånger fler tal, så tar det x*x gånger längre tid att köra. Övning: Varför? Sökningen i listan har linjär tidskomplexitet, men hela programmet har kvadratisk tidskomplexitet Körtider för unique-1 på en snabbare dator (Intel Core I7 920 2.66GHZ 8MB S-1366) --------------------------------------------------------------------------------- unique-1 med 10 000 tal: 0.22 s unique-1 med 100 000 tal: 21.25 s unique-1 med 200 000 tal: 1:25.57 = 85.57 s unique-1 med 1 miljon tal: Gissning: 2125 sekunder = 35 minuter Fortfarande kvadratisk tidskomplexitet! Insättning först ---------------- struct talpost* first = NULL; .... while (fscanf(tsin, "%lf", &talet) != EOF) { struct talpost* newp; newp = (struct talpost*)malloc(sizeof(struct talpost)); newp->talet = talet; newp->next = firstp; firstp = newp; } Insättning sist (ur framlanges-1.cpp) --------------- struct talpost* firstp = NULL; .... while (fscanf(tsin, "%lf", &talet) != EOF) { struct talpost* newp; newp = (struct talpost*)malloc(sizeof(struct talpost)); newp->talet = talet; newp->next = NULL; if (firstp == NULL) { // Listan var tom. Den nya posten blir första post. firstp = newp; } else { // Listan var inte tom. Den nya posten ska bli ny sista post. struct talpost* thisp = firstp; while (thisp->next != NULL) thisp = thisp->next; // Nu pekar thisp på den sista posten i listan. thisp->next = newp; } } Körtider (Intel Core I7 920 2.66GHZ 8MB S-1366) ----------------------------------------------- framlanges-1 med 10 000 tal: 0.19 s framlanges-1 med 100 000 tal: 18.96 s framlanges-1 med 200 000 tal: 1:15.84 = 75.84 s Slutsats: "Kvadratisk tidskomplexitet"! Övning: Varför? Insättning sist -- mycket snabbare (ur framlanges-2.cpp) ---------------------------------- struct talpost *firstp = NULL; struct talpost *lastp = NULL; .... while (fscanf(tsin, "%lf", &talet) != EOF) { struct talpost *newp; newp = (struct talpost*)malloc(sizeof(struct talpost)); newp->talet = talet; newp->next = NULL; if (firstp == NULL) { // Listan var tom. Den nya posten blir första post. firstp = lastp = newp; } else { // Listan var inte tom. Den nya posten ska bli ny sista post. lastp->next = newp; lastp = newp; } } Körtider (Intel Core I7 920 2.66GHZ 8MB S-1366) ----------------------------------------------- framlanges-2 med 10 000 tal: 0.01 s framlanges-2 med 100 000 tal: 0.06 s framlanges-2 med 200 000 tal: 0.13 s Nu har vi linjär tidskomplexitet igen! Borttagning ----------- ... Sökning+borttagning (ur borttagning-1.cpp) ------------------- // Nu tar vi bort talet "talet" ur listan if (firstp == NULL) { // Listan är tom -- gör inget } else if (firstp->talet == talet) { // Det är den första posten i listan som ska tas bort struct talpost *doomed = firstp; firstp = firstp->next; free(doomed); } else { // Listan var inte tom, och det är inte den första posten som ska bort struct talpost *thisp = firstp; while (thisp->next != NULL) { if (thisp->next->talet == talet) { // Det är nästa post som ska tas bort struct talpost *doomed = thisp->next; thisp->next = thisp->next->next; free(doomed); break; } thisp = thisp->next; } } Sökning+borttagning som funktion (ur borttagning-2.cpp) ------------------- void remove_from_list(struct talpost **firstpp, double wanted) { struct talpost *thisp = *firstpp; struct talpost *doomed = NULL; if (thisp == NULL) { // Listan är tom -- gör inget } else if (thisp->talet == wanted) { // Det är den första posten i listan som ska tas bort doomed = thisp; *firstpp = thisp->next; } else { // Listan var inte tom, och det är inte den första posten som ska bort while (thisp->next != NULL) { if (thisp->next->talet == wanted) { // Det är nästa post som ska tas bort doomed = thisp->next; thisp->next = thisp->next->next; break; } thisp = thisp->next; } } free(doomed); } .... if (find_in_list(firstp, talet) != NULL) { printf("Dubblett ignorerad, och borttagen: %f\n", talet); remove_from_list(&firstp, talet); } Sökning i sorterad ------------------ Inte så intressant. Det finns bättre datastrukturer för sorterade data. Insättning sorterad ------------------- Inte så intressant. Det finns bättre datastrukturer för sorterade data. Lästips om länkade listor (samma som för föreläsning 2) ------------------------------------------------------- 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