Föreläsningsöversikt¶
- Info om duggan
- Ny klass:
dict - Mer om dataabstraktion
- Nästlade datastrukturer
- Bearbetning av nästlade datastrukturer
- Fördefinierade
- Godtyckliga
Dugga 27/10, kl. 14.00-16.00¶
- Anmälan via LiU-appen eller Liunet.
- Utan anmälan, ingen dugga, utanför vår kontroll. Sista anmälningsdatum 10 dagar innan duggan.
- Tillåtet stödmaterial:
- Kurslitteratur (bok/utskrift) utan anteckningar
- Pythondokumentationen som PDF och websida (se kurshemsidan)
- 1 A4-sida egna anteckningar (enkelsidigt)
- Skrivmaterial och kladdpapper
- Kod/Föreläsningsbilder/övriga anteckningar ej tillåtet
Dugga 27/10, kl. 14.00-16.00¶
- Kom i tid. Duggan börjar 14.00, prick!
- Innan måste ni ha legitimerat er, hängt av er, loggat in, fått ev. böcker kontrollerade.
Dugga 27/10, kl. 14.00-16.00¶
- I SU-sal, ni använder Visual Studio Code + terminal
- Personliga inställningar och hemkatalog kommer inte vara tillgängliga
- Se till att ni vet hur ni testkör era program (gör inte misstaget att lämna in kod ni inte testat)
- Uppgifter liknar Pythonuppgifterna, se exempeldugga på kurshemsidan
- Kommunikation (chat) med Johan samt inlämning sker via tenta-klient
- Assistent för hjälp med tekniska problem kommer finnas på plats
Dugga 27/10, kl. 14.00-16.00¶
- Live-rättning, dvs duggan rättas direkt och ni får resultatet i tentaklienten.
- 2-30 minuters väntetid beroende på hur många som lämnar in samtidigt.
- Möjlighet att komplettera i mån av tid.
- Räkna inte med tid att komplettera, satsa på att göra rätt direkt.
Prova-på dugga 10/10, kl. 10.15-11.00 och 11.15-12.00¶
- Till för att prova tentasystemet, inte för att visa representativa uppgifter.
- En person i varje labbpar kommer kl 10, den andra kommer kl 11, kom överens sinsemellan vem som ska komma vilken tid eftersom datorplatserna bara räcker till hälften av er åt gången.
Repetition: for- loop eller while-loop?¶
- Mindre logistik om vi itererar över en sekvens med
for:
In [1]:
values = list(range(100))
i = 0
while i < len(values):
value = values[i]
if value == 42:
print("I found the answer!")
i += 1
for value in values:
if value == 42:
print("I found the answer!")
I found the answer! I found the answer!
Repetition: Varför finns ens while-loopen?¶
while-loopar är nödvändiga om man vill upprepa givet ett villkor snarare än för varje element i en viss sekvens.
In [2]:
import random
secret_word = random.choice(["apelsin", "banan", "citron"])
guess = None
tries = 0
while guess != secret_word:
if guess != None:
print("Fel!")
guess = input("Gissa vilket ord jag tänker på: ")
tries += 1
print("Rätt! Det tog " + str(tries) + " försök.")
Gissa vilket ord jag tänker på: apelsin Fel! Gissa vilket ord jag tänker på: banan Rätt! Det tog 2 försök.
Dictionary¶
- Dictionary eller
dicti Python.- Mer generellt: associationslista (eng. associative array, symbol table, map)
- Kärt barn har många namn.
- Nyckel-värde-par
- Värden hämtas med hjälp av nyckel istället för index som i fallet med listor och tupler.
- Alla datatyper som är oföränderliga (immutable) kan användas som nycklar, t.ex. flyttal, heltal, strängar, tupler
- Alla datatyper kan vara värden
Syntax¶
In [3]:
dict_example = {"key1": "value 1", 345: "value 2", 3: 54}
print(dict_example["key1"])
value 1
In [4]:
print(dict_example["key2"])
--------------------------------------------------------------------------- KeyError Traceback (most recent call last) Cell In[4], line 1 ----> 1 print(dict_example["key2"]) KeyError: 'key2'
In [5]:
print(dict_example.get("key2"))
None
In [6]:
print(dict_example.get("key2", "defaultvärde om inte nyckeln finns"))
defaultvärde om inte nyckeln finns
Iterera över en dict¶
- Punktnotation för att komma åt alla
- nycklar:
dict.keys() - värden:
dict.values() - nyckel-värdepar:
dict.items() - ("
dict" refererar här till ett godtyckligt värde av typen dictionary, denna notation används även i pythondokumentationen)
- nycklar:
- Metoderna
dict.keys(),dict.values()ochdict.items()returnerar olika "vyer".- Vyer kan liknas vid temporära listor.
- Ordningen i vyer är inte pålitlig eftersom
dictär fundamentalt oordnad.
Iterera över nycklar¶
In [7]:
dict_example = {"key1": "value 1", 345: "value 2", 3: 54 }
for key in dict_example.keys():
print(key)
key1 345 3
Iterera över värden¶
In [8]:
dict_example = {"key1": "value 1", 345: "value 2", 3: 54 }
for value in dict_example.values():
print(value)
value 1 value 2 54
Om vi vill ha både nycklar och värden då?¶
- Dåligt sätt:
In [9]:
dict_example = {"key1": "value 1", 345: "value 2", 3: 54 }
for key in dict_example.keys():
print(key, ":", dict_example[key])
key1 : value 1 345 : value 2 3 : 54
Om vi vill ha både nycklar och värden då?¶
- Bättre sätt:
In [10]:
dict_example = {"key1": "value 1", 345: "value 2", 3: 54 }
for key, value in dict_example.items():
print(key, ":", value)
key1 : value 1 345 : value 2 3 : 54
Dataabstraktion¶
Abstraktion¶
- programabstraktion: dela upp problem i delproblem, dela upp en funktion i flera funktioner
- dataabstraktion: koppla ihop och strukturera information
Dataabstraktion¶
In [11]:
# en variabel per värde
pokemon_name = "pidgey"
ability1 = "big-pecks"
ability2 = "tangled-feet"
ability3 = "keen-eye"
- Hur gör vi om vi vill ha information om fler eller färre "abilities" på ett smidigt sätt?
Dataabstraktion¶
In [12]:
pokemon_name = "pidgey"
# listor kan användas för att lagra 0 eller fler värden
abilities = ["big-pecks", "tangled-feet", "keen-eye"]
- Listor kan användas för information som kan innehålla fler än ett värde.
- Hur gör vi om vi vill ha information om flera pokemons? Ska vi ha
pokemon_name1,pokemon_name2,abilities1,abilities2?
Dataabstraktion¶
In [13]:
pokemon1 = ["pidgey", ["big-pecks", "tangled-feet", "keen-eye"]]
pokemon2 = ["ditto", ["imposter", "limber"]]
In [14]:
print(pokemon1[1][1])
tangled-feet
- Vi kan samla ihop informationen om varje pokemon till en lista samt bestämma den ordning som informationen ska komma i.
Dataabstraktion¶
In [15]:
pokemon = [ ["pidgey", ["big-pecks", "tangled-feet", "keen-eye"]],
["ditto", ["imposter", "limber"]] ]
In [16]:
print(pokemon[0][1][1])
tangled-feet
- Vi kan också samla ihop alla pokemon-listor i en lista.
Dataabstraktion¶
In [17]:
pokemon = [ { "name": "pidgey",
"abilities": ["big-pecks", "tangled-feet", "keen-eye"] },
{ "name": "ditto",
"abilities": ["imposter", "limber"] } ]
In [18]:
print(pokemon[0]["abilities"][1])
tangled-feet
- Vi hade även kunnat använda ett dictionary för att representera en Pokémon.
Dataabstraktion¶
In [19]:
pokemon = {"pidgey": { "name": "pidgey",
"abilities": ["big-pecks", "tangled-feet", "keen-eye"] },
"ditto": { "name": "ditto",
"abilities": ["imposter", "limber"] }}
In [20]:
print(pokemon["pidgey"]["abilities"][1])
tangled-feet
- Här har vi istället för en lista använt ett dictionary som har namnen på pokemons som nyckel och dictionaryt med all pokemon-information som värde.
Dataabstraktion¶
In [21]:
pokemon = {"johsj47": { "name": "johan falkenjack",
"abilities": ["adhd", "autism", "computer science"] } }
- Här har vi istället för en lista använt ett dictionary som har namnen på pokemons som nyckel och dictionaryt med all pokemon-information som värde.
Abstrakta datatyper (ADT)¶
- "Programming with abstract data types" (1974). Barbara Liskov & Stephen Zilles.
- Abstrakt datatyp
- datastruktur baserad på någon mer primitiv datatyp, t.ex. en lista
- funktioner som används på dessa datastrukturer
- poängen är att abstrahera bort onödig komplexitet
- Föregångare till en objektorienterad approach.
- Vi har redan pratat om en ADT: Stack.
Exempel på abstrakt datatyp¶
- Kö (eng. queue)
- lista med element är kön, index
0är nästa på tur - funktionen
create_empty_queue()som returnerar en tom kö - funktionen
enqueue(value, queue)som lägger till värdetvaluetill slutet på könqueue - funktionen
dequeue(queue)som returnerar värdet som är först i kön och plockar även bort det från kön
- lista med element är kön, index
En kö i Python¶
In [22]:
def create_empty_queue():
return ('queue', [])
def enqueue(value, queue):
if queue[0] == 'queue':
queue[1].append(value)
else:
raise TypeError("Not a queue")
def dequeue(queue):
if queue[0] == 'queue':
if queue[1]:
return queue[1].pop(0)
else:
return None
else:
raise TypeError("Not a queue")
En kö i Python¶
In [23]:
q = create_empty_queue()
print(1, q)
enqueue('a', q)
print(2, q)
enqueue('b', q)
print(3, q)
print(4, f"{dequeue(q)=}")
print(5, q)
enqueue('c', q)
print(6, q)
1 ('queue', [])
2 ('queue', ['a'])
3 ('queue', ['a', 'b'])
4 dequeue(q)='a'
5 ('queue', ['b'])
6 ('queue', ['b', 'c'])
In [24]:
print(7, f"{dequeue(q)=}")
print(8, f"{dequeue(q)=}")
print(9, f"{dequeue(q)=}")
7 dequeue(q)='b' 8 dequeue(q)='c' 9 dequeue(q)=None
Stop! Tupler var ju inte muterbara!¶
Hur ser vår datastruktur ut?¶
In [25]:
q = create_empty_queue()
print(1, q)
1 ('queue', [])
Hur ser vår datastruktur ut?¶
In [26]:
q = create_empty_queue()
print(1, q)
1 ('queue', [])
Hur ser vår datastruktur ut?¶
In [27]:
enqueue('a', q)
print(2, q)
2 ('queue', ['a'])
Hur ser vår datastruktur ut?¶
In [28]:
enqueue('b', q)
print(3, q)
3 ('queue', ['a', 'b'])
Hur ser vår datastruktur ut?¶
In [29]:
print(4, f"{dequeue(q)=}")
print(5, q)
4 dequeue(q)='a'
5 ('queue', ['b'])
Hur ser vår datastruktur ut?¶
In [30]:
enqueue('c', q)
print(6, q)
6 ('queue', ['b', 'c'])
...men om ett elementet i sig är muterbart, så kan vi ändra i det.¶
Bearbetning av nästlade datastrukturer¶
Nästlade datastrukturer¶
- $A$ är en nästlad datastruktur om
- $A$ innehåller flera värden
- Ett av värdena i $A$ i sin tur innehåller flera värden
In [31]:
list_of_lists = [["Ada Lovelace", 1815], ["Joan Clarke", 1917]]
list_of_dicts = [ { "name": "Ada Lovelace", "birthyear": 1815 }, { "name": "Joan Clarke", "birthyear": 1815 } ]
dict_with_some_list_value = { "name": "ditto", "abilities": ["imposter", "limber"] }
Hur kommer vi åt nästlade värden?¶
In [32]:
lista1 = [["a", "b", "c"], ["d", "e", "f"]]
# första elementet i lista1
print(f"{lista1[0]=}")
# första elementet i första elementet i lista1
print(f"{lista1[0][0]=}")
# andra elementet i första elementet i lista1
print(f"{lista1[1][1]=}")
lista1[0]=['a', 'b', 'c'] lista1[0][0]='a' lista1[1][1]='e'
Hur kommer vi åt nästlade värden?¶
In [33]:
dict1 = { "frukter": ["a", "b", "c"],
"bilar": ["d", "e", "f"] }
# värdet associerat med nyckeln "frukter"
print(f"{dict1['frukter']=}")
# första elementet i listan associerad med nyckeln "frukter"
print(f"{dict1['frukter'][0]=}")
# andra elementet i listan associerad med nyckeln "frukter"
print(f"{dict1['frukter'][1]=}")
dict1['frukter']=['a', 'b', 'c'] dict1['frukter'][0]='a' dict1['frukter'][1]='b'
En nästlad loop för att bearbeta en nästlad datastruktur¶
In [34]:
outer_list = [ ["a", "b", "c"], ["d", "e", "f", "g"] ]
# om vi för varje inre lista i outer_list vill skriva ut den inre listans element?
outer_index = 0
while outer_index < len(outer_list):
inner_list = outer_list[outer_index]
# kod som skriver ut varje element i inner_list
inner_index = 0
while inner_index < len(inner_list):
print(inner_list[inner_index])
inner_index += 1
outer_index += 1
a b c d e f g
Vi har faktiskt någon typ av sekvenser... for!¶
In [35]:
outer_list = [ ["a", "b", "c"], ["d", "e", "f", "g"] ]
# om vi för varje inre lista i outer_list vill skriva ut den inre listans element?
for inner_list in outer_list:
for inner_element in inner_list:
print(inner_element)
a b c d e f g