Programexempel från Progmet-föreläsning 4, torsdag 13 september 2012 ==================================================================== Operationer på en (enkellänkad) länkad lista: insättning först (har vi redan sett), insättning sist, traversering (dvs att gå igenom listan), (insättning sorterad), sökning (som i programmet unique-1), (sökning i sorterad), borttagning, sökning+borttagning, upprensning (men nämn: automatisk skräpsamling!) Tidskomplexitet: linjär tidskomplexitet, "O(n)", O(2n) = O(n) = O(75n) konstant tid, "O(1)", O(2) = O(1) = O(75000) kvadratisk tidskomplexitet, "O(n^2)" Om vi hinner (fet chans...): Dubbellänkade listor Funktionsbibliotek med generella funktioner, generiska datatyper (t ex en generisk lista) C++ och klasser (Det här tar nog minst två dagar.) 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: automatisk 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! Metod: Läs tal precis som förut, men spara talet i listan bara om det inte redan finns där! Dvs, vi behöver ett sätt att kolla om ett tal finns i en länkad lista! En annan sorts traversering: Sökning (ur unique-1.cpp) ------------------------------------------------------ Finns i listan (sant/falskt: bool exists_in_list(struct talpost *firstp, double wanted) { struct talpost *thisp = firstp; while (thisp != NULL) { if (thisp->talet == wanted) return true; thisp = thisp->next; } return false; } Kan vara bra att returnera en pekare till rätt listpost: 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; } Läs-loopen i programmet unique-1 -------------------------------- 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. Varför??? 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 för framlanges-1 ------------------------- (långsamma laptopen: Lenovo ThinkPad X100e, processor AMD Turion Neo X2 L625 1,6 GHz) framlanges-1 med 10 000 tal: 0.74 s framlanges-1 med 20 000 tal: 2.83 s (dvs ca 4 gånger mer än 0.74 s) framlanges-1 med 100 000 tal: 1:28.46 = 88.4 s (dvs någorlunda nära 100 gånger mer än 0.74 s) framlanges-1 med 200 000 tal: 6:00.43 = 360.43 s (dvs ca 4 ggr mer änb 88.4 s) Slutsats: "Kvadratisk tidskomplexitet"! Övning: Varför? Körtider för framlanges-1 på en snabbare dator (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 Fortfarande kvadratisk tidskomplexitet! 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 för framlanges-2 ------------------------- (långsamma laptopen: Lenovo ThinkPad X100e, processor AMD Turion Neo X2 L625 1,6 GHz) framlanges-2 med 10 000 tal: 0.05 s framlanges-2 med 20 000 tal: 0.09 s framlanges-2 med 100 000 tal: 0.30 s framlanges-2 med 200 000 tal: 0.57 s Nu har vi linjär tidskomplexitet igen! Och mycket snabbare. Obs: Det är en annan sak än tidskomplexiteten! Körtider för framlanges-2 på en snabbare dator (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 Fortfarande linjär tidskomplexitet! 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