TDDE44 Programmering, grundkurs

Föreläsning 7

Johan Falkenjack, johan.falkenjack@liu.se

Föreläsningsöversikt

• Information om datorsalstentan
• Laboration 7
• Kort om algoritmer och komplexitet
• Skriva till fil
• Ännu mer om testning av kod
• Repetition

Datorsalstentan

logistik på plats, upplägg, inlämning

Datorsalstenta, 30 maj kl. 8.00-12.00

• Anmälan via Lisam eller LiU-appen.
  • Anmälningsperiod: 30 april-20 maj
• Info på kurshemsidan under "Datorsalstenta" (håller på att uppdateras)
• Nytt upplägg för i år: "hybridrättning"
• Kort allmän info
  • https://www.ida.liu.se/edu/ugrad/datortenta/

Sal, inloggning, kontroll av bok

• Information om vilken sal du ska gå till vid SU17/18
• Inloggning
  • Står "tentainloggning"
  • Logga in med LiU-ID och ditt vanliga lösenord
  • Liknande datormiljö som vid labbande, men utan internetåtkomst
• Kontroll av bok

Filer: tenta, datafiler, referens-PDF

• Din hemkatalog under tentan nås via ~/
• Tentan som PDF samt eventuella filer som hör ihop med tentan finns i katalogen ~/given_files
• ~/given_files är skrivskyddad

Skriva tentan - rekommendation

• kopiera ev. datafiler från given_files till skrivbordet
• spara dina filer till skrivbordet
• Skrivbordet via terminal: cd ~/Desktop

Frågor under tentan

• Praktiska frågor: jour-assistenter och tentavakter
• Frågor om tentauppgifter: använd studentklienten
• Studentklienten: program som startas automatiskt vid inloggning och används för kommunikation med examinator samt inlämning av uppgifter

Tentaupplägg

• Två delar, Del 1 och Del 2
• Del 1: grundläggande uppgifter, samma storlek som Pythonuppgifter 1-3
• Del 2: något mer omfattande uppgifter

• Inga avdrag för avvikelser från PEP8 eller PEP257

Del 1

• Krävs för att bli godkänd på tentan
• Rättas live under tentatillfället och uppgifterna kan kompletteras i mån av tid
  • Detta är nytt för i år och vi hoppas att ni har överseende med ev. barnsjukdomar.
• Del 1 innehåller 4-5 uppgifter: 1.1, 1.2, etc.
• Kom ihåg att lämna in en uppgift så fort ni är klara med den.
  • Om ni skickar in alla uppgifter 5 minuter innan tentans slut hinner ni inte få svar eller möjlighet att komplettera.
• För att gå godkänt på Del 1 måste alla uppgifter vara godkända.

• Målsättningen är att alla ska veta huruvida de blivit åtminstone godkända på tentan vid tentatidens slut.

Del 2

• Rättas bara om Del 1 är godkänd och rättas efter tentan.
• Består av några få större problemlösningsuppgifter.
• Inkompletta och delvis felaktiga lösningar KAN ge några poäng. (IDA != MAI)

• Man kommer inte veta om man uppnått kraven för 4 eller 5 vid tentatidens slut.

Betyg

• Betyg 3: Godkänd på del 1.
• Betyg 4: Godkänd på del 1 + ca 40 % på del 2.
• Betyg 5: Godkänd på del 1 + ca 70 % på del 2.

Inlämning av uppgifter

• En fil per uppgift
  • Eventuella deluppgifter (ex. 1.2.1, 1.2.2, etc.) lämnas in i samma fil.
• Döp filen så att uppgiftsnummret finns med, t.ex. uppg12.py för ovanstående deluppgifter (står i tentan)
• Filen skickas in via studentklienten:
  • 1. Tryck på knappen "Skicka in uppgift"
  • 2. Välj vilken uppgift och välj vilken fil som skickas in
  • 3. Bekräftelse på att filen är mottagen "Begäran mottagen"

Prova-på-tenta 14 maj 8.15-9.00 och 9.15-10.00

• 8.15: Person 1 i varje labbpar i webreg (och ev. Person 3)
• 9.15: Person 2 i varje labbpar i webreg
• Lokal enligt vanliga schemat i TimeEdit

• Möjlighet för både er och assistenterna att förbereda er inför riktiga tentan.
• Se miljön, prova att ställa frågor i studentklienten, prova att skicka in uppgift och få feedback.

• Utnyttja den här möjligheten! Vi vet av erfarenhet att många blir stressade första gången de ser tentamiljön och detta är ett sätt för er att slippa den stressen vid det riktiga tentatillfället.

På kurshemsidan (håller på att uppdateras)

• Exempeltenta (tidigare format, ny exempeltenta på gång) och övningsuppgifter
• PDF som ni kommer ha tillgänglig som referens
• https://www.ida.liu.se/~TDDE44/tenta/

Laboration 7

Stavningskontroll

Laboration 7

• Uppgiften
  • Ordfrekvensdata
  • Redigeringsavstånd
  • Klasser
• Förberedelser: UML-diagram
• Problem som kan uppstå när man har mycket data

Laboration 7: Rättstavning

• "Fortsättning" på laboration 2
• Skript som använder ordfrekvensdata för att hitta okända ord i en text och föreslå alternativ till dessa ord med hjälp av redigeringsavstånd
  • T.ex. hoppssn → hoppsan
• Rapport om okända ord + förslag sparas till fil

Laboration 7: filer

• ordfrekvensfiler
  • innehåller antal förekomster av olika ord från diverse källor
  • mest förekommande först i filerna
• några textfiler
  • exempel på texter som ni kan "rättstava"
  • använd gärna egna texter

Kortaste redigeringsavståndet

• Algoritm som räknar ut antal redigeringsoperationer som behövs för $word_A$ → $word_B$
• Levenshtein-avstånd: minsta antalet operationer av typerna lägg till bokstav, ta bort bokstav och ersätt bokstav som förändrar ett ord till ett annat.
  • 'katt' → 'hatt'; en operation (ersätt 'k' med 'h')
  • 'katt' → 'kalas'; tre operationer (ersätt första 't' med 'l', ersätt andra 't' med 'a', lägg till 's')
  • 'hall' → 'hal'; en operation (ta bort ett 'l')
• Funktionen minimum_edit_distance(s1, s2) finns implementerad och redo att importera från filen med.py

Laboration 7: Klasser

• Rita UML-diagram och skriv ert program utifrån det. Visa för labbassistent innan ni börjar koda.
• Uppdatera UML-diagrammet under tiden ni programmerar. Visa slutgiltig version vid redovisning och bifoga i inlämningen.
• Minst följande tre klasser:
  • SpellingWarning: innehåller information om upptäckta ev. stavfel (som t.ex. plats, ordet och förslag)
  • Report: innehåller SpellingWarning-objekt
  • WordFrequencyData: innehåller ordfrekvensdata + metoder för att uppdatera/använda denna data
• För varje upptäckt fel skapar ni en instans av klassen SpellingWarning.
• Utöver dessa klasser är det upp till er.

Förberedelser innan ni börjar implementera

• Läs igenom instruktionerna på kurshemsidan
• Diskutera med er labpartner och rita upp UML-diagram.
• Visa upp ert UML-diagram och berätta hur ni tänkt för en assistent.
  • Förra året hoppade många över det här steget och fick flera jobbiga kompletteringar när deras approach var orimlig, undvik att göra samma misstag.

Tips

• En rapport har många upptäckta fel → jmf. flera hus i en stad
• Vid kontroll av flera filer → skapa flera rapporter (instanser)

• Behövs flera klasser? Vad vill ni representera? När ska man använda en inbyggd datatyp, t.ex. list eller dictionary och när ska man skapa en klass?
• Försök att se till så att en klass har ett ansvarsområde.
• Kom ihåg att metoder jobbar på data som klassen representerar.

Konsekvenser av öka mängden data att bearbeta

Laboration 7

• Körtid < 1 minut för minsta datafilen
• Går att köra <1 minut för största datafilen om man tillämpar vissa (rimliga) begränsningar.

Exempeluppgift

• text.txt innehåller en text på 1000 ord
• ordfrekvenser.tsv innehåller ordfrekvenser för 500k ord;
  • varje rad består av
  • ett ord
  • ett tab-tecken ('\t')
  • frekvensen som ordet förekommer i en viss text-korpus (samling av texter)
• Vi ska skriva en algoritm som tar fram vilka ord i text.txt som finns med i ordfrekvenser.tsv

Loopar: Se upp för att göra om saker i onödan. Alt 1

• 1. Kontrollera ett ord. För varje word_to_check i texten som ska kontrolleras (1 000 ord)
  • 1.1 Läs in data. läs in alla ordfrekevenser och spara dem som tupler av ord och frekvens i listan freq_data (500 000 ord)
  • 1.2 Finns ord med i data? Gå igenom alla inlästa ord och kontrollera om det är word_to_check (500 000 ord)

• $\sim 1\ 000 \times (500\ 000 + 500\ 000) = 1 \times 10^9$ operationer
• Om en operation tar 1 nanosekund ($1 \times 10^{-9}$) tar vår algoritm 1 sekund

Loopar: Se upp för att göra om saker i onödan. Alt 2

• 1. Läs in data. Läs in alla ordfrekevenser och spara dem som tupler av ord och frekvens i seprata listor för olika längd på orden, dvs en lista per ordlängd. (500 000 ord)
• 2. Kontrollera ett ord. För varje ord word_to_check i texten som ska kontrolleras (1000 ord)
  • 2.1 Finns ord med i data? Gå igenom alla inlästa ord av rätt längd och kontrollera om det är word_to_check, avbryt så fort ordet hittats (25 000 ord, givet antagandet att vi har i snitt 50 000 ord per ordlängd och vi i snitt behöver söka igenom hälften av dessa för att hitta ordet vi söker)

• $\sim 500\ 000 + (1000 \times 25\ 000) = 2,55 \times 10^7$ operationer
• Om en operation tar 1 nanosekund ($1 \times 10^{-9}$) tar detta alternativ 0,0255 sekunder

Loopar: Se upp för att göra saker i onödan

• Alt 1:
  • Läser in all ordfrekvensdata för varje ord som ska kontrolleras
  • Kontrollerar word_to_check mot alla ord, även de som inte har samma ordlängd.
• Alt 2:
  • Läser in all ordfrekvensdata en gång.
  • Kontrollerar word_to_check mot de ord som har samma längd
  • Avbryter sökning när ordet har hittats

Komplexitet

Hur krävande är det att lösa en specifik uppgift med en specifik algoritm?

Vad är en algorithm?

• Informellt: En väldefinierad beräkningsbar (computational) procedur som givet ett värde, eller en mängd värden, som input producerar ett värde, eller en mängd värden som output. (Cormen et. al. 2009. Introduction to algorithms.)
• En algoritm sägs vara korrekt om det för varje korrekt indata, avslutar med korrekt utdata.

• Vad innebär beräkningsbarhet? Att en algoritm som givet ett ändligt antal operationer ger ett korrekt svar kan konstrueras. De flesta vardagsproblem är beräkningsbara.
• https://en.wikipedia.org/wiki/List_of_undecidable_problems

Kort om komplexitet

• Tids- och minneskomplexitet.
• Hur mycket tid/minne behövs per enhet av in-data.

• Dvs. om vi skalar upp data, hur skalar resursanvändningen upp?

• Idag är minne billigt och vi bryr vi oss främst om tidskomplexitet och offrar gärna minnesresurser för snabbare program.

Komplexitet

• Hur mycket behöver datorn göra? Hur komplicerat är det att lösa ett givet problem med en viss algoritm?
• Exempel, for-loop, leta efter största elementet
  • Hur många operationer behöver algoritmen?

def get_max_value(values):
    max_value = values[0]
    for value in values:
        if value > max_value:
            max_value = value
    return max_value

Komplexitet

• Ju större len(values) är, desto mindre betydelse har antalet operationer utanför for-loopen.
• Antal operationer är asymptotiskt proportionerligt mot len(values)
• Ordo-notation (eng. Big O notation)
• För nedanstående funktion: $O(n)$, där $n$ är storleken på input
  • Utläses "Ordo n" på svenska och "Order of n" på engelska.

def get_max_value(values):
    max_value = values[0]
    for value in values:
        if value > max_value:
            max_value = value
    return max_value

• Har ni kommit till Maclaurin-utvecklingar i Analysen? Där används Ordo för att beskriva storleken på resttermen.

Komplexitet, nästlade loopar

• Antalet par-kombinationer man kan bilda givet $n$ värden
• $\{ 1, 2, 3, ..., n \}$

def get_pairs(values)
    pairs = []
    for v1 in values:
        for v2 in values:
            pairs.append(str(v1) + ":" + str(v2))
    return pairs

• $O(n^2)$

Komplexitet i stigande ordning

• $O(1)$: konstant
• $O(\log n)$: logaritmisk
• $O(n)$: linjär
• $O(n \log n)$: kvasilinjär eller log-linjär
• $O(n^2)$: kvadratisk
• $O(n^3)$: kubisk
• $O(n^c)$: polynomiell av grad $c$ ($c$ är konstant)
• $O(2^n)$: exponentiell
• $O(n!)$: faktoriell

Skriva till fil

Öppna fil för att läsa/skriva

• open(filepath, mode) returnerar den öppnade filen som ett file-objekt.
• mode är en sträng vars defaultvärde är 'r' som i read
• Andra giltiga värden på mode är 'w' som i write och 'a' som i append
  • mode='r' read: vi kan endast läsa från filen
  • mode='w' write: vi kan endast skriva till filen, existerande innehåll skrivs över
  • mode='a' append: vi kan endast skriva till filen, existerande innehåll bevaras, nytt innehåll läggs till slutet på filen
• Metoden file.write(s) skriver strängen s till filen file.
  • Om inte filen redan finns så skapas den när vi skriver till den.

Öppna fil med explicit teckenkodning

• open(filepath, mode, encoding='utf-8')
  • Vi kan tvinga python att öppna filen med en viss teckenkodning genom att använda nyckelordsargumentet encoding. Kan behövas t.ex. om man kör Windows och ska läsa/skriva textfiler kodade i utf-8.

Exempel, skriva till fil

# öppna fil för att lägga till text till
datafile = open("filnamn.txt", "a")
datafile.write("Glöm inte bort")
datafile.write("radbryt!\n")

# stäng filen som vi öppnat
datafile.close()

Testning av kod

Testning och felsöking

• Felsökning:
  • Jag vet att något är fel med den här koden. Jag måste nu ta reda på var och varför det blir fel.

• Testning:
  • Jag vet inte om programmet fungerar eller inte. Jag behöver ta reda på om alla delar fungerar som de ska.

Felsökning

• När vi vet att koden vi skrivit inte fungerar som den ska behöver vi t.ex. ta reda på:
  • Under vilka omständigheter fungerar inte koden?
  • Var i koden uppstår felet? / Vad orsakar felet?
• Verktyg vi kan använda oss av vid felsökning
  • Felmeddelanden när programmet kraschar
  • Spårutskrifter
  • Olika debugverktyg

Testning

• Syftet med testning är att ta reda på om det vi testar fungerar eller inte. T.ex. om programmet uppför sig som vi förväntar oss.
• Stor bredd i det man kan referera till med "testning"
• Testning hjälpa oss påvisa förekomsten av fel.
• Rent praktiskt omöjligt att med hjälp av testning garantera frånvaron av fel, men vi kan använda testning för att minimera antalet fel!

Testning i denna kurs och utanför denna kurs

Testning i denna kurs

• Testning är en del av lärandemålen för kursen
• Ni har alla testat er kod på ett eller annat sätt

Testning inom mjukvaruutveckling

• Test på olika abstraktionsnivåer:
  • enhetstestning - enskilda enheter, "units", av mjukvaran för sig själv, t.ex. enskilda funktioner, klasser
  • integrationstest - test av specifika enheters interaktion med varandra
  • systemtest - test av systemet som helhet
• Test enligt olika kriterier:
  • funktionstest - test av specifik funktionalitet hos ett program, t.ex. "lägga till en uppgift"
  • prestandatest - test av prestanda hos programmet, t.ex. hur lång tid tar det att öppna en fil, hur mycket minne använder programmet, etc.
  • acceptanstest - test av alla krav ställda på programmet
  • användbarhetstestning - test av hur användbart programmet är för en viss användarkategori
• Speciella ramverk och program finns för att underlätta testning, men användning av dessa ligger utanför kursen.

Automatiserad testning

• Tester som kan skrivas i kod och köras automatiskt, t.ex. varje gång man lagt till ny funktionalitet eller refaktorerat (ändrat i existerande kod)
• Ofta felaktigt använt synonymt med enhetstestning men även t.ex. integrationstest, och i viss utsträckning systemtest, brukar automatiseras.
  • Även prestandatest kan ofta automatiseras när programmen ställer höga krav på prestanda, t.ex. i realtidssystem, simuleringsmjukvaror eller spel.

• Svårare att automattesta:
  • grafiska gränssnitt
  • funktionalitet som är beroende av komplex data som är resultatet av interaktion mellan många komponenter i ett system
  • funktionalitet som är beroende av yttre faktorer

• De två sistnämnda angrips ofta mha sk "mocking" men det är överkurs.

Vilka typer av test ingår i kursen?

• Test av funktioner, fungerar de som de ska?
  • funktion(indata) → returvärde
• Enklare test av instanser av klasser, t.ex.
  • instans.metod() → returvärde
  • instans.metod(indata) → returvärde
  • värdet hos instansvariabler efter att olika metoder körts

Vad ska man tänka på vid testning?

• Båda nedanstående funktioner ska addera talen v1, och v2 och sedan returnera resultatet.
• I nedanstående testkörning verkar båda vara korrekt implementerade?

def add_values1(v1, v2):
    return v1 + v2

def add_values2(v1, v2):
    return v1 * v2

# båda anropen returnerar 4, är båda implementationerna korrekta?
print(add_values1(2, 2))
print(add_values2(2, 2))

Vad behöver man veta för att testa sin kod?

Vad måste vi veta för att testa en enhet?

• Hur ser specifikationen ut? Dvs.

• Vilka starttillstånd och testförhållanden är giltiga?
  • Indata?
  • Värden på instansvariabler innan en metod körs?
• Vad ska enheten vi vill testa göra?
  • Hur ser utdata ut? Vilken utdata är giltig?
  • Vilken utdata ska vi förväntas oss givet en viss indata?

Testdata

• I de flesta fall är det omöjligt att göra en uttömmande testning, dvs testa alla möjliga fall (t.ex. alla möjliga indata).
• Vi behöver titta på giltiga indata och försöka hitta vilka kategorier av indata som finns.
• Vilka indata ger är samma returvärde?
• Vilka indata testar samma aspekt av implementationen?
• Att hitta dessa kräver ofta att man förstår hur implementationen av en funktion eller klass kan göras.
• Ett mål: med så få test som möjligt kunna täcka så många fall som möjligt.

Typfall och gränsfall

• Typfall (eng. typical case) är de testvärden som motsvarar den vanligaste typen av input där enheten förväntas bete sig normalt.
• Gränsfall (eng. edge case) är de testvärden som ligger nära, på eller utanför gränsen för normal användning.
  • Gränsfallen kan kräva fler test för olika typer av gränser och för att testa felhantering vid olika gränsöverträdelser.
  • Testning handlar till stor del om att hitta och definiera gränsfallen samt konstruera lämpliga tester för de fallen.
• Vad är några typfall och gränsfall för funktionen nedan:

from math import floor

def split_winnings(cash_prize_amount, number_of_winners):
    return floor(cash_prize_amount / number_of_winners)

split_winnings(, )

• Typfall: cash_prize_amount = 10 000 number_of_winners = 2, 3, 10, etc.
• Gränsfall: Negativa värden, 0 vinnare, värden som inte är tal över huvud taget, fel antal argument, etc

Vad behöver man göra för att testa sin kod?

Göra sitt program lättare att testa

• Genom att dela upp ett program i fler funktioner/klasser/ metoder ökar man även i de flesta fall upplösningen på det som går att testa
• Funktioner som returnerar värden är lättare att testa än funktioner som inte returnerar värden.
• Genom att dokumentera sin kod finns det en specifikation som man kan använda som vägledning för att skapa rätt test.

Hur kan man testa?

• Att testa sitt program interaktivt kan ta tid (för att det sker manuellt), men ger stora möjligheter till att utforska resultaten.
• Att automatisera ett test, dvs skriva kod som testar funktionaliteten är snabbare och är upprepningsbart.
  • Viktigt att veta vad vi ska testa!

Exempel på automatisering av test

• Automatisera genomförandet av testoperationen, t.ex.
  • anrop av funktioner + okulär besiktning av resultaten för att validera korrekthet
• Exempel nedan där returvärden skrivs ut

def keep_even_values(values):
    output = []
    for value in values:
        if value % 2 == 0:
            output.append(value)
    return output

print(keep_even_values([]))
print(keep_even_values([1]))
print(keep_even_values([2]))
print(keep_even_values([1, 2, 3, 4]))

[]
[]
[2]
[2, 4]

Exempel på automatisering av test

• Automatiserad validering
  • automatisk jämförelse av faktiskt resultat av testoperationen med förväntat resultat
• Exempel med villkorssatser på nästa bild

Exempel på automatisering av test

def keep_even_values(values):
    output = []
    for value in values:
        if value % 2 == 0:
            output.append(value)
    return output


def test_keep_even_values():
    if keep_even_values([]) != []:
        return False
    if keep_even_values([1]) != []:
        return False
    if keep_even_values([2]) != [2]:
        return False
    if keep_even_values([1, 2, 3, 4]) != [2, 4]:
        return False
    return True


if test_keep_even_values():
    print("keep_even_values() fungerar.")
else:
    print("keep_even_values() fungerar INTE.")

keep_even_values() fungerar.

Nyckelordet assert

• Nyckelordet assert används när man vill kontrollera om ett uttryck är sant i syfte att fånga upp fall när det inte är det.
• Om uttrycket är sant går Python vidare i koden.
• Om uttrycket är falskt, inträffar ett AssertionError som sedan kan fångas.
• Man kan använda villkorssatser i samma syfte, men koden kan bli kortare och tydligare med assert
• Syntax:

assert uttryck

Exempel på automatisering av test (med assert)

def keep_even_values(values):
    output = []
    for value in values:
        if value % 2 == 0:
        output.append(value)
    return output


def test_keep_even_values():
    try:
        assert keep_even_values([]) == []
        assert keep_even_values([1]) == []
        assert keep_even_values([2]) == [2]
        assert keep_even_values([1, 2, 3, 4]) == [2, 4]
        return True
    except AssertionError:
        return False


if test_keep_even_values():
    print("keep_even_values() fungerar.")
else:
    print("keep_even_values() fungerar INTE.")

Repetition

Exempel på aggregering av data

• City kan tillhandahålla befolkningssiffra genom att fråga alla hushåll efter hur många som ingår i hushållet.

Association och scope

• Associationspil implementeras som en variabel i "från"-klassen.
• Om fler än 1 referens ska finnas, använd t.ex. lista eller dictionary
• Samma variabelnamn och metodnamn kan användas i flera klasser.

Vad händer när vi skapar en instans av en klass?

• Skapa instans av klass: Klassnamn(arg1, arg2, ..., argn)
• Python skapar ett objekt och kör klassens __init__()-metod
• Objektet som skapats skickas som det första argumentet till __init__().
• Argument som skickats med vid anrop av klassnamnet skickas vidare till __init__() efter self.

Hur kan nedanstående tolkas - syntax är viktigt

1. a
2. a()
3. a(b)
4. a[b]
5. a.b
6. a.b()
7. a.b = c
8. a = b.c
9. a = b.c()

Beståndsdelar i ett program

• värden (values): t.ex. siffror eller text (kallas för strängar)
• operatorer (operators): token/symbol som står för en instruktion
• variabler (variables): namngivna referenser till värden
• uttryck (expressions): ett uttryck kan beräknas till ett värde (ibland säger man även utvärderas istället för beräknas)
• nyckelord (keywords): speciella ord som refererar till instruktioner som ska utföras
• skiljetecken (punctuators)
• satser (statements): fullständig instruktion