Introduktion till programmering i Python
Föreläsning 12:
Analys av algoritmer, komplexitet, rekursion, beräkningsbarhet
Chalmers (DAT455)
Version 20220804
Aarne Ranta
Agenda
Sökalgoritmer: linjär och binär sökning
Komplexitet
Sortering
Rekursiva funktioner
Rekursiva datatyper
Beräkningsbarhet och stopproblemet
Sökalgoritmer: linjär och binär sökning
Sökproblemet
Hitta ett element och returnera ett värde, t.ex.
Pythons dictionaries och index()-metoden kan användas för detta.
Men hur fungerar de internt? Hur skulle vi göra om vi inte hade dem?
Linjär sökning
def linsearch(x, ns):
counter = 0
for n in ns:
if n == x:
return counter
else:
counter += 1
raise ValueError
Räknare för element som man går igenom
När man hittar en träff returnerar man räknarens värde
Annars inkrementerar man ränkaren
counter = counter + 1
Om man gått igenom listan och inte hittat x rapporteras ValueError.
Binär sökning
def binsearch(x, ns):
low = 0
high = len(ns) - 1
while low <= high:
mid = (low + high)//2
item = ns[mid]
if x == item:
return mid
elif x < item:
high = mid - 1
else:
low = mid + 1
raise ValueError
Definiera lägsta och högsta gränsen för den del av listan som man söker i.
Gränserna kommer att närma sig varandra
Om elementet inte finns i listan, rapporteras ValueError
Vi testar sökalgoritmerna
>>> ws = fileWords('data/bible.txt')
>>> len(ws)
824192
>>> linsearch('Mary', ws)
633028
>>> binsearch('Mary', ws)
ValueError
>>> sws = sorted(ws)
>>> binsearch('Mary', sws)
101588
Läs orden från den engelska bibeln.
Så många ord (tokens).
Mary förekommer först ganska sent, i Nya Testamentet.
Binärsökning är meningslös om listan inte är sorterad.
Låt oss sortera den
Nu får vi en position i den alfabetiska ordningen - vi borde väl ha sparat den ursprungliga också… men det är inte huvudsaken nu.
En grafisk jämförelse av algoritmerna
Linjär sökning: rött
Binär sökning: blått
x-axeln: miljoner element i listan
y-axeln: processortid i sekunder
Vi ser att linjär sökning följer en rak linje:
Men hur beter sig den binära sökningen?
Logaritmisk komplexitet
Låt oss säga att vi söker x bland 1000 element.
Steg 1: om x == 500, är vi klara. Annars går vi till en av halvorna, låt oss säga den övre.
Steg 2: om x == 750, klart. Annars
Steg 3: om x == 875, klart. Annars
Steg 4: om x == 938, klart. Annars
….
Steg 10: om x == 999, klart.
I det värsta fallet behöver vi 10 ~ log21000 steg. Vi säger att binär sökning har logaritmisk komplexitet.
Enkel mätning av processortid
import time
start = time.process_time()
code
end = time.process_time()
print(end-start)
Använd time-biblioteket
Kolla processortiden före körningen av koden
Kör koden
Kolla processortiden efter
Beräkna skillnaden
Det finns mera sofistikerade metoder, men denna är den enklaste.
Komplexitet
Ordo-notationen för komplexitet ("Big O")
logaritmisk: O(log n)
linjär: O(n)
log-linjär: O(n log n)
kvadratisk: O(n2)
kubisk: O(n3)
exponentiell: O(2n)
fakultet: O(n!)
Exempel på algoritmer av olika komplexiteter
logaritmisk: O(log n) binär sökning
linjär: O(n) linjär sökning
log-linjär: O(n log n) sortering (med bästa standardfunktioner)
kvadratisk: O(n2) sortering (med vissa enklare funktioner)
kubisk: O(n3) matrismultiplikation (den naiva metoden)
exponentiell: O(en) gå genom alla delmängder av en mängd
fakultet: O(n!) permutationer; determinant (Laplace-expansion)
Några till begrepp
Tidskomplexitet: antal steg eller längden av tid i funktion av datans storlek
Minneskomplexitet: mängd datorminne i funktion av datans storlek
Asymptotisk komplexitet: storleksordningen, dvs O-klassen
Värstafallskomplexitet: den maximala komplexiteten
Genomsnittlig komplexitet: genomsnittet för alla möjliga input-data
I teoretisk datalogi tittar man ofta på värstafallskomplexiteten, medan i praktiken kan den genomsnittliga komplexiteten vara viktigare.
Sortering
Hur ska man resonera?
Detta är något vi ofta gör i praktiken - t.ex. ordnar böcker i en bokhylla.
En naiv metod: selection sort.
Komplexitet: n + (n-1) + (n-2) + … + 1 = (n+1)(n/2) = (n2 +n)/2, därmed kvadratisk.
Selection sort
Zelle, s. 478
QuickSort
def quickSort(xs):
if xs:
pivot = xs[0]
return (
quickSort([x for x in xs[1:] if x < pivot]) +
[pivot] +
quickSort([x for x in xs[1:] if x >= pivot])
)
else:
return xs
Magiskt enkelt med rekursion och listkomprehensioner.
Om listan inte är tom:
Värsta fall: O(n2)
Genomsnitt: O(n log n)
Ett exempel på söndra och härska ("divide and conquer")-algoritmer.
Pythons sorted()?
Timsort https://en.wikipedia.org/wiki/Timsort (av Tim Peters)
Relaterat till merge sort (boken 13.3.2, QA session)
Tidskomplexitet O(n log n) - både genomsnittlig och värsta falls
Jämförelse mellan quickSort och Pythons sorted()
Blått: quickSort()
Grönt: sorted()
x-axeln: antal element
y-axeln: processortid i sekunder
Inte så meningsfullt egentligen, eftersom vi har kört med bara en testmängd (ord i bibeln). "Uteliggaren" ("outlier") vid 2000 element behöver förklaring.
permutationSort() - den sämsta tänkbara...
def permutations(xs):
if len(xs) < 2:
return [xs]
else:
ps = []
for qs in permutations(xs[1:]):
for j in range(len(xs)):
p = (qs[:j] + [xs[0]] + qs[j:])
ps.append(p)
return ps
def permutationSort(xs):
def sorted(ys):
for i in range(len(ys)-1):
if ys[i] > ys[i+1]:
return False
return True
for p in permutations(xs):
if sorted(p):
return p
Bygg en lista av alla permutationer (dvs olika ordningar av element)
En hjälpfunktion som testar om en lista är sorterad
Vi går igenom permutationerna tills vi hittar en sorterad lista.
Rekursiva funktioner
Tre sätt att upprepa en beräkning
def factFor(n):
r = 1
for k in range(1, n+1):
r *= k
return r
def factWhile(n):
r = 1
k = 1
while k < n+1:
r *= k
k += 1
return r
def factRec(n):
if n <= 1:
return 1
else:
return n * factRec(n-1)
For-loop:
While-loop:
Rekursiv funktion:
Några synpunkter om rekursiva funktioner
>>> start = time.process_time()
>>> x = factFor(800)
>>> end = time.process_time()
>>> end-start
0.0036279999999990764
>>> x = factWhile(800)
0.002654000000003265
>>> x = factRec(800)
0.002801999999999083
>>> x = factRec(999)
Traceback (most recent call last):
RecursionError: maximum recursion depth exceeded in comparison
>>> x = factRec(998)
>>> x
402790050127220994538240674597601587306681545756471103647447357787726238637266286878923131618587992…
De kan göra mer än while-loopar.
De kan också vara ungefär lika tidseffektiva.
I Python är de begränsade till rekursionsdjup ca. 1000, dvs. antal rekursiva anrop
Rekursiva datatyper
Träd
root
tree1
tree2
tree3
treen
…
Ett träd har en nod som är dess rot, samt grenar ("subtrees"), som själva är träd med varsin rot.
Objektet fortsätter neråt tills man når en nod utan grenar.
Exempel
Exempel: den svenska kungafamiljen år 2016 (utan makar)
En klass för träd
class Tree:
def __init__(self, node, subtrees):
self.root = node
self.subtrees = subtrees
def getParts(self):
return self.root, self.subtrees
def depth(tree):
(n, ts) = tree.getParts()
if ts:
return 1 + max([depth(t) for t in ts])
else:
return 1
Klassvariablerna:
Accessormetoden för att få fram roten och grenarna
Exempel: beräkna trädets djup med en rekursiv funktion
royal = Tree('CarlGustaf',
[Tree('Victoria',[Tree('Estelle',[]),Tree('Oscar',[])]),
Tree('CarlPhilip',[Tree('Alexander',[])]),
Tree('Madeleine', [Tree('Leonore',[]), Tree('Nicolas',[])])])
Exempel: syntaxträd
def atom(a):
return Tree(a, [])
def plus(x,y):
return Tree("+", [x, y])
def times(x,y):
return Tree("*", [x, y])
2 + 3 * 4
plus(atom(2), times(atom(3), atom(4)))
+
2
*
3
4
(2 + 3) * 4
times(plus(atom(2), atom(3)), atom(4))
*
+
4
3
2
Syntaxträd i en kompilator
källkod
parsning
syntaxträd
maskinkod
kodgenerering
2 + 3 * 4
plus(atom(2),
times(atom(3),atom(4)))
bipush 2
bipush 3
bipush 4
imul
iadd
Detta är en mycket förenklad bild, men visar hur man kan översätta aritmetiska uttryck med små heltal till kod i JVM Assembler (Java Virtual Machine). Uttrycken kan vara godtyckligt komplexa. Assemblern kan enkelt konverteras till binärkod rad för rad.
En funktion för kodgenerering
def postfix(tree):
f,ts = tree.getParts()
xs = []
for t in ts:
for s in postfix(t):
xs.append(s)
xs.append(str(f))
return xs
def jvm(tree):
def instr(f):
if f == "*":
return "imul"
elif f == "+":
return "iadd"
else:
return "bipush " + str(f)
instrs = map(instr, postfix(tree))
return '\n'.join(instrs)
En rekursiv funktion, som
Postfix betyder att roten (operatorn) kommer efter sina argument. Således:
2 + 3 * 4 → 2 3 4 * +
(2 + 3) * 4 → 2 3 + 4 *
Funktionen jvm() konverterar postfix-bitarna till olika instruktioner i maskinkoden.
Den skulle lika gärna kunna returnera binärkod direkt, t.ex. 01101000 i ställer för imul.
Beräkningsbarhet och stopproblemet
Beräkningsbarhet ("computability")
Finns det en algoritm för alla (precist formulerade) problem?
Matematisk version: finns det en Turing-maskin som kan lösa alla problem?
Svaret - från Turing själv! - är nej: det finns problem som är oavgörbara ("undecidable").
Ett av dessa är stopproblemet ("the halting problem"):
Skulle vara väldigt användbart i praktiken!
Stopproblemet: ett enkelt bevis
Zelle's bok, ss. 491-492:
Terminerar turing.py med input turing.py?
Detta är en motsägelse, som visar att terminates() är omöjligt att konstruera.
Andra icke-beräkningsbara problem
Att hitta bevis eller motbevis i predikatkalkylen (ett enkelt system för logik, som kan användas för att implementera matematiska bevis i datorn).
AI-kompletta problem: AI-problem som skulle kräva "obegränsad intelligens" för att lösa (inte lika seriöst som beräkningsbarhet, men en viktig insikt).
Exempel: översättning av naturliga språk.
Översättning som ett AI-komplett problem
Exempel: finsk "hän" till svensk "han" eller "hon".
translate.google.com 18/8/2020 (precis samma problem 3/8/2022)
Det finns hur mycket som helst att göra i programmering
Och det kommer aldrig att bli färdigt!
Python-grammatiken för hela kursen
<stm> ::= <exp>,* = <exp>,*
| <exp> <assignop> <exp>
| for <name> in <exp>: <block>
| def <name> (<arg>,*): <block>
| <exp>
| return <exp>,*
| if <exp>: <block> <elses>?
| while <exp>: <block>
| pass
| break
| try: <block> <except>* except: <block>
| class <name> (<name>,*)?: <block>
| assert <exp> ,<exp>?
| import <name> <asname>?
| from <name> import <imports>
| raise <name>
<asname> ::= as <name>
imports ::= * | <name>,*
<elses> ::= <elif>* else: <block>
<elif> ::= elif exp: <block>
<except> ::= except <name>: <block>
<block> ::= <stm> <stm>*
<exp> ::= <exp> <op> <exp>
| <name>.?<name>(<arg>,*)
| <literal>
| <name>
| ( <exp> )
| [ <exp>,* ]
| <exp>[exp]
| <exp>[<slice>,*]
| lambda <name>*: <exp>
| { <keyvalue>,* }
| [ <exp> for <name> in <exp> <cond>? ]
| - <exp>
| not <exp>
<keyvalue> ::= <exp>: <exp>
<arg> ::= <name>
| <name> = <exp>
<cond> ::= if <exp>
<op> ::= + | - | * | ** | / | // | % | == | > | >= | < | <= | != | in | not in | and | or
<assignop> ::= += | -= | *=
<slice> ::= <exp>?:<exp>? |
Tilldelningssatser generaliseras på två sätt:
Slicing i arrays (fält) kan ha flera element
Tilldelning med aritmetiska operatorer
Slicing-uttryck för arrays
Lästips och övningsklassen
Ur boken
Övningsklassen:
Förberedelse för tentan
Gör labbarna först: utan dem får man inget betyg på Ladok.
Gamla tentor finns i https://chalmers.instructure.com/courses/19152/files/folder/gamla-tentor
Live-föreläsningen den 22/8 går igenom ytterligare en gammal tenta, https://docs.google.com/presentation/d/1ATCJtMdHpcV1rHu9o7vZ_GmrlonB5M6JPh0HLLZ_-a4/edit?usp=sharing
Tentan 24/8 kl 14-18
Omtentan 7/10 kl 14-18
Båda på Canvas som Assignment, ingen anmälan behövs.
Senare omtentor under terminen kommer att annonseras på Chalmers tentamensschema.