Datastructuren

Deze pagina bevat uitvoerbare code.

Terug naar lijsten

In PGM1 week 7 zag je dat een lijst mutable is: L[i] = x past de lijst zelf aan, in plaats van dat er een nieuwe lijst ontstaat. Die kennis gebruik je vandaag verder. Identiteit, waarde en shallow/deep copy komen hier niet terug.

Data die zelf iets doet

Tot nu toe deed jij iets met data. De functie staat vooraan en de data gaat erin:

len(my_list)
sum(my_list)
my_list + [9]

Vanaf nu zie je het ook andersom:

my_list.append(9)

Hier staat de lijst vooraan en de handeling erachter. Je vraagt niet aan een functie om iets met de lijst te doen; je vraagt het aan de lijst zelf.

Zo’n handeling die bij de data zelf hoort heet een methode. Je schrijft hem met een punt: eerst het ding, dan de punt, dan wat het moet doen.

my_list = [11, 21]
my_list.append(42)
my_list

[11, 21, 42]

Let op wat er niet gebeurt: er komt geen nieuwe lijst uit. append geeft niets terug, hij verandert de lijst die er al was.

my_list = [11, 21]
resultaat = my_list.append(42)
print(resultaat)

None

None, dus. Dit is dezelfde mutatie als my_list[0] = 42, alleen anders opgeschreven.

Daarmee heb je twee manieren om er een element bij te zetten:

Wat er gebeurt

Schrijfwijze

Er komt een nieuwe lijst

my_list = my_list + [9]

De lijst zelf verandert

my_list.append(9)

Allebei goed. Wanneer het verschil uitmaakt zie je verderop in de cursus.

Neem dit voorlopig aan

Een methode is een handeling die bij een object hoort: data met handelingen eraan vast. Wat een object precies is en hoe je er zelf een maakt, zie je verderop in Programmeren 2, in week 5.

Voor nu is het een schrijfwijze die je moet herkennen en kunnen gebruiken. Je komt hem overal tegen, want vrijwel alles in Python werkt zo, en dat is ook de reden dat je hem nu al nodig hebt.

Dictionaries

Dictionaries zijn willekeurige containers

d = {47: 2, 42: 1}

Elementen (of waarden) worden opgehaald met een sleutel op een willekeurige positie:

d[47] == 2
d[42] == 1

Goed nieuws, sleutels kunnen ook andere typen dan int zijn!

Van Dale

Een bekende structuur

  • woord ⟶ verklaring

  • naam ⟶ telefoonnummer

  • afkorting ⟶ betekenis

  • dier ⟶ jaren Chinese dierenriem

Chinese dierenriem

Dictionaries zijn in

zodiac_years = {
    "rabbit": [1999, 1987, 1975],
    "ox": [1997, 1985, 1973],
    "dragon": [2000, 1998]
}

De sleutels zijn hier strings en de bijbehorende waarden zijn lists. Dit voorbeeld gaat over de jaren per dier in de Chinese dierenriem, zie het Wikipedia artikel voor de volledige lijst.

Is "dragon" een sleutel in zodiac_years?

"dragon" in zodiac_years

True

Is 1969 een waarde in zodiac_years["dragon"]?

1969 in zodiac_years["dragon"]

False

Woorden tellen

list_of_words = ["spam", "spam", "taart", "spam"]

word_count = {}

for word in list_of_words:
    if word not in word_count:
        word_count[word] = 1
    else:
        word_count[word] += 1

word_count

{'spam': 3, 'taart': 1}

Dictionary-methodes

Tellen zoals hierboven kan korter. .get(sleutel, standaardwaarde) zoekt op zonder een KeyError te riskeren: bestaat de sleutel niet, dan krijg je de standaardwaarde terug in plaats van een foutmelding.

word_count.get("spam", 0)

3

word_count.get("koekje", 0)

0

Daarmee kan het tellen in één regel per woord, zonder if ... else:

word_count[word] = word_count.get(word, 0) + 1

Twee andere methodes geven je de sleutels of de waarden apart:

list(word_count.keys())

['spam', 'taart']

list(word_count.values())

[3, 1]

En .items() geeft je beide tegelijk, als paren (sleutel, waarde). Zo’n paar is een tuple - hetzelfde soort tuple dat je in PGM1 week 7 al bent tegengekomen. Dat maakt het doorlopen van een dictionary korter: in plaats van word_count[word] telkens opnieuw op te zoeken, pak je de waarde meteen mee.

for word, count in word_count.items():
    print(word, "komt", count, "keer voor")

spam komt 3 keer voor
taart komt 1 keer voor

Model genereren

Gegeven de volgende tekst:

text = "Ik wil taarten en 42 en spam. Ik krijg toch spam en taarten voor de vakantie? Ik wil 42 taarten!"

list_of_words = text.split()
word_count = {}

for word in list_of_words:
    if word not in word_count:
        word_count[word] = 1
    else:
        word_count[word] += 1

print(f"There are {len(word_count)} DISTINCT words")  # expressions in f-strings!

word_count

There are 13 DISTINCT words

{'Ik': 3,
 'wil': 2,
 'taarten': 2,
 'en': 3,
 '42': 2,
 'spam.': 1,
 'krijg': 1,
 'toch': 1,
 'spam': 1,
 'voor': 1,
 'de': 1,
 'vakantie?': 1,
 'taarten!': 1}

Sets

len(word_count) hierboven is het aantal verschillende woorden. Een dictionary is daar eigenlijk net iets te zwaar voor: hij houdt ook een aantal per woord bij, en dat heb je hier niet nodig. Voor “welke waarden komen voor, zonder duplicaten” is er een lichter datatype: de set.

unique_words = set(list_of_words)
unique_words

{'42',
 'Ik',
 'de',
 'en',
 'krijg',
 'spam',
 'spam.',
 'taarten',
 'taarten!',
 'toch',
 'vakantie?',
 'voor',
 'wil'}

Een set heeft geen volgorde en geen duplicaten. len(unique_words) is daarom hetzelfde getal als len(word_count) hierboven, maar dan zonder dat je een dictionary nodig had om het te tellen.

len(unique_words)

13

Zoeken gaat met in, net als bij een lijst of dictionary. En je breidt een set uit met .add():

"wil" in unique_words

True

unique_words.add("koekje")
unique_words

{'42',
 'Ik',
 'de',
 'en',
 'koekje',
 'krijg',
 'spam',
 'spam.',
 'taarten',
 'taarten!',
 'toch',
 'vakantie?',
 'voor',
 'wil'}

Unie en doorsnede

.add() breidt één set uit. Twee sets combineer je met unie en doorsnede - allebei zowel als methode als als operator:

groep_a = {"appel", "peer", "banaan"}
groep_b = {"appel", "kiwi", "banaan"}

De unie: alles wat in minstens één van de twee zit.

groep_a.union(groep_b)

{'appel', 'banaan', 'kiwi', 'peer'}

groep_a | groep_b

{'appel', 'banaan', 'kiwi', 'peer'}

De doorsnede: alles wat in allebei zit.

groep_a.intersection(groep_b)

{'appel', 'banaan'}

groep_a & groep_b

{'appel', 'banaan'}

Unie en doorsnede leveren een nieuwe set op, uit twee bestaande. Dat is iets anders dan .add(), dat er één set aan het uitbreiden was.

Met een paar aanpassingen van het programma dat woorden telt, is het mogelijk om een eenvoudige taalgenerator te maken.

In plaats van het tellen van woorden wordt gekeken welk woord na een voorgaand woord wordt gebruikt.

%run assets/markov.py

words_follow = create_dictionary(text)

words_follow

{'$': ['Ik', 'Ik', 'Ik'],
 'Ik': ['wil', 'krijg', 'wil'],
 'wil': ['taarten', '42'],
 'taarten': ['en', 'voor'],
 'en': ['42', 'spam.', 'taarten'],
 '42': ['en', 'taarten!'],
 'krijg': ['toch'],
 'toch': ['spam'],
 'spam': ['en'],
 'voor': ['de'],
 'de': ['vakantie?']}

Het stappenplan voor het maken van een taalmodel is als volgt:

  1. begin met het vorige woord previous_word als “$”

  2. voor elk volgend woord in de lijst van woorden voeg het toe aan …

  3. maak previous_word gelijk aan new_word

    • behalve als new_word[-1] punctuatie is, maak previous_word dan gelijk aan …

Tekst genereren

Een $ staat voor het begin van een zin. Dit model heeft voor elk woord een lijst van woorden waar uit gekozen kan worden. Als we dit random doen, wordt er een random tekst gegenereerd.

generate_text(words_follow, 42)

'Ik wil taarten en taarten en 42 taarten! Ik wil 42 taarten! Ik wil taarten voor de vakantie? Ik wil 42 en 42 taarten! Ik wil 42 en 42 taarten! Ik krijg toch spam en taarten en taarten voor de vakantie? Ik '

Als we een veel grotere tekst gebruiken om onze database mee te vullen, kunnen we betere teksten genereren.

Het stappenplan voor het genereren van tekst is als volgt:

  1. begin met previous_word als de “$” string

  2. kies random een new_word dat volgt op previous_word en voeg het toe aan …

  3. maak previous_word gelijk aan new_word

    • behalve als new_word[-1] punctuatie is, maak dan previous_word gelijk aan …

In het werkcollege werk je dit uit tot een programma dat een heel essay genereert.