Föreläsning 3: Komplexitetsanalys, sökning, rekursion

Mål Läs i kursboken

Komplexitetsanalys

Sökning

Rekursion

3. Analysis Links to an external site.

6.2. Searching Links to an external site.

6.3. The Sequential Search Links to an external site.

6.4. The Binary Search Links to an external site.

5. Recursion Links to an external site. (utom 5.12)

Idag tittar vi på:

  • Komplexitetsanalys
  • Linjärsökning
  • Binärsökning
  • Testning
  • Rekursion
  • Frågestund Labb 2

Algoritmer

En beskrivning, i ett ändligt antal steg, av hur man löser ett givet problem.

Exempel:
Skriv en algoritm för att läsa in gps-data för platser från en fil (t ex Ladda ner island.txt

eller kina.txt) och lagra dom i en lista.
Platserna är i filen ordnade med sydligast latitud först, men i listan vill vi att dom ska ligga i ordning från nordligaste till sydligaste, alltså i omvänd ordning.

Algoritm 1

  1. öppna filen
  2. läs in rubrikraden
  3. läs in första raden
  4. lägg raden sist i listan
  5. upprepa punkt 3 och 4 tills alla rader i filen lästs in
  6. vänd listan
Implementation med for-slinga och append
print("Algoritm 1 med append och reverse")
filnamn = "kina.txt"
rader = []
with open(filnamn, encoding = "utf-8") as landfil:
for rad in landfil:
rader.append(rad.strip())
rader.reverse()

#Kontrollera resultatet
print("Antal rader", len(rader))
for i in range(5):
print(rader[i])
Samma algoritm - implementation med while-slinga
print("Algoritm 1 med append och reverse + while")
filnamn = "kina.txt"
rader = []
with open(filnamn, encoding = "utf-8") as landfil:
rad = landfil.readline()
while rad:
rader.append(rad.strip())
rad = landfil.readline()
rader.reverse()

#Kontrollera resultatet
print("Antal rader", len(rader))
for i in range(5):
print(rader[i])

 
Algoritm 2

Här är en annan algoritm för samma problem:

  1. öppna filen
  2. läs in rubrikraden
  3. läs in första raden
  4. lägg raden först i listan
  5. upprepa punkt 3 och 4 tills alla rader i filen lästs in
Implementation med insert
print("Algoritm 2 med insert")
filnamn = "kina.txt"
rader = []
with open(filnamn, encoding = "utf-8") as landfil:
for rad in landfil:
rader.insert(0,rad.strip())
print("Antal rader", len(rader))

for i in range(5):
print(rader[i])

 

Algoritm 1 lägger in platserna sist i listan med append.

Algoritm 2 lägger in platserna först i listan med insert.

Bägge algoritmerna går snabbt för Island (ca 17 000 platser) men algoritm 2 går mycket långsammare för Kina (ca 850 000 platser). Varför?


Komplexitetsanalys

Det är intressant att se tidsåtgången för en algoritm. Denna anges ofta som funktion av indatas storlek, som av tradition kallas n. Exempel: För sortering är LaTeX: nn antalet tal som ska sorteras.
Hur växer tidsåtgången LaTeX: T\left(n\right)T(n) för växande LaTeX: nn?

https://www.desmos.com/calculator Links to an external site.

n log(n) n*log(n) n2 2n
10 s 1 s 10 s 100 s 17 min
100 s 2 s 3 min 2 tim 1022 år
10000 s (ca 3 tim) 4 s 11 tim 3 år

Vi analyserar oftast värsta fallet (det är i regel enklare att räkna på) men man kan också räkna på medelfallet.

Istället för att ange den exakta tidsfunktionen LaTeX: T\left(n\right)T(n) nöjer vi oss med att ange ordoklassen LaTeX: O\left(n\right)O(n).

Definition

   LaTeX: T\left(n\right)T(n) är LaTeX: O\left(F\left(n\right)\right)O(F(n)) 

om det finns positiva konstanter LaTeX: cc och LaTeX: n_0n0 sådana att

LaTeX: 0\le T\left(n\right)\le c\cdot F\left(n\right)0T(n)cF(n)  för LaTeX: n\ge n_0nn0

Vad innebär detta?

  • LaTeX: c\cdot F\left(n\right)cF(n) anger en övre gräns för LaTeX: T\left(n\right)T(n) då LaTeX: nn är stort.
  • Vi behöver bara ta bara med den term som växer snabbast.
  • Vi kan bortse från multiplikation med konstant.
  • Det spelar ingen roll vilken logaritm vi använder.

Exempel:

LaTeX: T\left(n\right)=10n^2\:+\:100n\:+\:\log_{10}n\:+1000T(n)=10n2+100n+log10n+1000    säger vi är    LaTeX: O\left(n^2\right)O(n2)

  • För små indata är analys onödig - använd den enklaste algoritmen!
  • Inläsning från fil tar längre tid än åtkomst av redan inlästa värden.
  • Minnesåtgång kan också vara relevant.

Uppgift: Matrismultiplikation

Vad är tidskomplexiteten för matrismultiplikation? Ange O(...)

Testa med ChatGPT

tidskomplexitet för en funktion med två slingor (fungerar fint)

För kodexempel ger ChatGPT ofta en rimlig analys.

ChatGPT: Ordoklass för en funktion (blir fel)

Men att hitta Ordoklassen för en given funktion blir oftast fel.


Sökning

Förutsättningar:

  • Vi söker efter något element i en lista med n element.
  • Det element vi söker efter karakteriseras av en söknyckel (eng key) men kan också ha andra data.

Frågor:

  • Vad ska hända om det sökta elementet inte finns med?
  • Kan det finnas flera element med samma nyckel? Vill man i så fall hitta alla?

Linjärsökning (Sequential search)

Den enklaste sökningen: bryter så fort den hittar det sökta elementet.

Algoritm:

  1. Gå igenom varje element i listan:
    • Jämför elementet med nyckeln, och
    • ...returnera True om dom är lika
  2. Returnera False om hela listan gåtts igenom utan att elementet hittats.

Linjärsökning är LaTeX: O\left(n\right)O(n) (i värsta fallet måste vi titta på alla LaTeX: nn elementen).

Här följer en funktion för linjärsökning i en lista.

def exists(the_list, key):
    for x in the_list:
        if x == key:
            return True
    return False

Uppgift: Förbättra funktionen

Den här funktionen talar bara om huruvida elementet finns med i listan.  Hur ska den modifieras för att returnera den plats i listan (index) där elementet finns? 

 


Binärsökning

Om listan är sorterad är den snabbaste sökningsalgoritmen binärsökning. Algoritm:

  1. Beräkna intervallets mittpunkt.
  2. Är det nyckeln? Avbryt, det sökta elementet är funnet.
  3. Annars: Avgör om det nyckeln finns i första eller andra halvan och fortsätt söka där (upprepa från punkt 1)
  4. Om halvan du söker i krympt till ingenting: Avbryt. Det sökta elementet fanns inte med.
11 13 13 20 22 25 28 30 31 32 32 48 62
11 13 13 20 22 25
20 22 25
25


Binärsökning är LaTeX: O\left(\log_2n\right)O(log2n) i värsta fallet. Varför det?

Vi söker bland n element och undrar hur många varv sökningen kan ta?

Antal element att söka bland halveras i varje varv, så första varvet får vi LaTeX: \frac{n}{2}n2, andra varvet LaTeX: \frac{n}{4}n4, tredje varvet LaTeX: \frac{n}{8}n8. Vi är klara när det bara finns ett element kvar att titta på och då är LaTeX: \frac{n}{2^x}=1n2x=1 där LaTeX: xx är antal varv. Vi två-logaritmerar bägge led och får att LaTeX: x=\log_2nx=log2n.
Här följer en funktion för binärsökning:

def binary_search(data, key):
low = 0
high = len(data)-1

while low <= high:
middle = (low + high)//2
if data[middle] == key:
return True
else:
if key < data[middle]:
high = middle - 1
else:
low = middle + 1
return False

Binärsökning är en knepig algoritm att implementera korrekt.

Uppgift: Testning

Hur testar vi att koden ovan fungerar? Föreslå data att testa med!

Här är några förslag! Testa:

  1. normalfallet, t ex att söka efter 14 i listan [9, 14, 23, 54, 92, 104]
  2. att söka efter ett tal som inte finns med, t ex 15
  3. att söka i en tom lista []
  4. att söka efter vänstraste elementet 9 ...
  5. ... och högraste elementet 104.
  6. att söka efter ett element bortom vänstra gränsen, t ex 8 ...
  7. ... och bortom högra gränsen, t ex 105.

Exempel på testprogram med unittest:  Ladda ner test_binsearch.py


Rekursion

Rekursiv kommer från latinet och betyder återlöpande. Om man i definitionen av ett begrepp använder begreppet självt så är definitionen rekursiv. Rekursiva tankar kan också användas för problemlösning.

  • Rekursiv tanke:   reducerar problemet till ett enklare problem med samma struktur
  • Basfall:  ett fall som inte leder till rekursivt anrop

Rekursiv bild

Sifferexempel

Triangeltalet S(N) är summan av de N första heltalen. S(4)=1+2+3+4
Fråga: Vad är värdet på S(N)?
Rekursivt svar: S(N) = S(N-1) + N ... men S(1)=1.
Här följer en rekursiv funktion för beräkning av triangeltalet:

    def S(n):
        if n == 1: 
            return 1
        else:
            return S(n-1) + n

 Fråga: Hur lång är den länkade listan?

Rekursivt svar: 1 (första elementet) + längden av resten av listan..., men en tom lista har längden 0.

def listlen(p):
      if p == None:  
         return 0
else: return 1 + listlen(p.next)

 Fråga: Vilken siffersumma har heltalet n?

Rekursivt svar: Sista siffran plus siffersumman om man stryker sista siffran i n, ...men noll har siffersumman noll.

def siffersumma(n):
      if n == 0:  
         return 
else: return n%10 + siffersumma(n//10)

Fråga: Hur många siffror har heltalet n?
Rekursivt svar: En siffra mer än om man stryker sista siffran i n, ...men tal mindre än tio är ensiffriga.

def antalsiffror(n)
      if n...

Hur fungerar det?

När man skriver egna rekursiva funktioner bör man lita på att det rekursiva anropet fungerar - man behöver inte analysera anropsgången för varje fall. Men för att förstå varför rekursion kan vara extra minneskrävande är det vara bra att känna till hur programspråken hanterar rekursiva anrop.

  • För varje anrop skapas en aktiveringspost som innehåller data för anropet, t ex parametrar, lokala variabler och anropspunkt.
  • Aktiveringsposten pushas på en stack.
  • När det rekursiva anropet är klart poppas aktiveringsposten från stacken, varefter föregående anrop ligger överst på stacken.
s(1)
s(2)
s(3)
s(4)
huvudprogram

Rekursiv binärsökning

Binärsökning är lätt att göra rekursivt! Basfallet är att listan är tom, dvs har noll element.

 

Rekursiv binärsökningsfunktion:

 

def binsok(listan, nyckel):
    if len(listan) == 0:
        return False
    else:
        mitten = len(listan)//2
        if listan[mitten] == nyckel:
            return True
        else:
            if nyckel < listan[mitten]:
                return binsok(listan[:mitten], nyckel)
            else:
                return binsok(listan[mitten+1:], nyckel)

Denna version är enkel att förstå men betydligt långsammare att köra! Varje funktionsanrop tar extra tid, och dessutom kopieras delar av listan vid varje anrop.

  • En rekursiv funktion kan alltid omformuleras utan rekursion, men om det finns flera rekursiva anrop i funktionen kan det vara besvärligt.
  • För vissa problem är en rekursiv funktion mycket enklare att formulera och ger kortare kod än utan rekursion. Ofta måste man gå via den rekursiva lösningen i tanken även om man gör en icke-rekursiv lösning.
  • En rekursiv lösning kan ge långsammare kod. Varje funktionsanrop tar ju lite extra tid.

 

Frågestund Labb 2

  • Vad är ett privat attribut?

Ett privat attribut inleds med understreck (t ex self._strumpor) och går bara att komma åt inuti klassen. Läs mer om privata attribut här: slides 

  • Hur fixar man inläsningen med Kattis?

Om det inte fungerar att använda "input" så kan du läsa in från "sys.stdin", så här

    indata = sys.stdin.readline()

Titta också på exemplet "A different problem" i Kattis hjälptexter

  • Kattis säger "Wrong answer" men mitt svar ser rätt ut - vad ska jag göra?
    1. Ta bort ledtexten (skriv bara input() istället för input("Ge korten: ) ")
    2. Se till att det är mellanslag mellan värdena i utskriften (1 2 3 istället för 123)
    3. Döp om ditt huvudprogram till main.py
    4. Om varken 1 , 2 eller 3 löser problemet så är det bäst att fråga!
  • Blir x en array om jag skriver så här?
          x = []

Nej, x blir en lista. Du kan kolla vilken typ/klass x har har genom att skriva print(type(x))

  •  Har kö index?

Nej.