Oppslagsverk


Basics

Et oppslagsverk (engelsk: dictionary) er en datastruktur hvor man kan slå opp på nøkkelverdier (“keys”) og hente ut en verdi som tidligere har blitt knyttet til denne nøkkelverdien. Tenk på nøkkelverdi som et slags «variabelnavn» og på et oppslagsverk som en samling med variabler.

# Opprett et tomt oppslagsverk
d = dict()             # kan også skrives som:   d = {}

# Legg til nøkler og verdier
d["my key"] = "my value"
d["name"] = "Arnoldus"
d["age"] = 42

# Hent ut verdiene
print(d["my key"])     # my value
print(d["name"])       # Arnoldus
print(d["age"])        # 42
print(d["age"] + 53)   # 95

# Hente ut verdiene, med default-verdi dersom nøkkel ikke eksisterer
print(d.get("age", 9)) # 42
print(d.get("foo", 9)) # 9   ("foo" er ikke en nøkkel i d)

# Endre på en verdi
d["age"] += 1          # kan også skrives som:   d["age"] = d["age"] + 1

# Verdien er endret
print(d["age"])        # 43
# Statisk opprettelse av oppslagsverk
d = { "key": "value", "foo": 42, 95: "McQueen", 99: 200 }

print(d["key"])                # value
print(d["foo"])                # 42
print(d[95])                   # McQueen
print(d[99])                   # 200
print(d["key_does_not_exist"]) # Krasjer
Enkle eksempler
# Oppretter oppslagsverket
country_map = {
    'Oslo': 'Østlandet',
    'Bergen': 'Vestlandet',
    'Drammen': 'Østlandet',
    'Stavanger': 'Vestlandet',
    'Kristiansand': 'Sørlandet',
}

# Ber bruker om navnet på en by og skriver ut hvor byen ligger
print("Skriv inn navnet på en by: ", end="")
city = input().title() # .title() gjør om til 'Title Case'
print()
if city in country_map:
    print(f"{city} er på {country_map[city]}")
else:
    print(f"Unnskyld, jeg aner ikke hvor {city} er")
# Oppretter et oppslagsverk
counts = dict()

# Ber brukeren om å skrive tall, og forteller så brukeren hvor mange ganger
# tallet er sett før.
while True:
    print("Skriv inn et tall (eller ingenting for å avslutte): ", end="")
    n = input()
    if (n == ""):
        break
    n = int(n)
    if n in counts:
        counts[n] += 1
    else:
        counts[n] = 1
    print("Jeg har nå sett tallet", n, "totalt", counts[n], "ganger.")
print("Ferdig, counts:", counts)
Opprette oppslagsverk
# Opprett et tomt oppslagsverk
d1 = dict()
print(d1)

d2 = {}
print(d2)

# Opprett oppslagsverk statisk
d3 = {"foo":"bar", 42:99}
print(d3)

d4 = dict(foo="bar", baz=[1, 2, 3])
print(d4)

# Opprett oppslagsverk fra en liste med tupler på størrelse 2
a = [("ku", 5), ("hund", 98), ("katt", 1), ("kanin", 999), ("mus", 2)]
d5 = dict(a)
print(d5)
Egenskaper ved oppslagsverk

Oppslagsverk knytter nøkler til verdier.

ages = dict()
key = "fred"
value = 38
ages[key] = value  # "fred" er nøkkelen, 38 er verdien
print(ages[key])

En nøkkel er unik, og er tilknyttet kun én verdi.

d = dict()
d[2] = 100
d[2] = 200
d[2] = 400
print(d)  # { 2:400 }

Rekkefølge betyr egentlig ingenting; men ved iterasjon er det den rekkefølgen nøklene ble først opprettet som teller.

d1 = dict()
d1["a"] = "foo" # Oppretter nøkkelen 'a' først i d1
d1["b"] = "B"
d1["a"] = "A"   # Selv om vi endrer på 'a' igjen, er den fremdeles først
print(d1)       # {'a':'A', 'b':'B'}

d2 = {"b":"B", "a":"A"} # Nøkkelen 'b' kommer først i d2
print(d2)       # {'b':'B', 'a':'A'}

print(d1 == d2) # True, rekkefølge betyr ingenting for likhet

Et oppslagsverk er muterbart.

d1 = { "foo": 42 }
d2 = d1

d2["foo"] = 95
print(d1["foo"]) # 95

Nøklene i et oppslagsverk kan være mange forskjellige slags typer; men de kan ikke være av en muterbar type. Verdiene i et oppslagsverk kan være hva som helst, inkludert muterbare verdier.

d = dict()

d["this key is a string"] = 42
d[95] = "this value has an int as key"
d[("this key", "is", "a tuple")] = ["this", "value", "is", "a", "list"]
d[False] = "booleans are also fine as keys"
d[None] = "even None is OK"

# Hent ut noen verdier
print(d["this key is a string"])  # 42
print(d[False])                   # booleans are also fine as keys

# Prøver å bruke en liste som nøkkel
d[["trying", "to", "use", "list", "as", "key"]] = "foo"  # Krasjer

Oppslagsverk er svært effektive.

# Vi kan bruke en liste av tupler som om det var et oppslagsverk
# Prøv å endre på n (hvor mye data vi har) og se effekten på kjøretiden
n = 200
trails = 100
a = [(i, i) for i in range(n)] + [("foo", 42), ("bar", 95)]

# La oss sammenligne hvor effektivt det er i forhold til et oppslagsverk
d = dict(a)

# Operasjonen vi skal sammenligne:
# Sjekk om vi et gitt et (key, value) -par eksisterer i samlingen
def contains_key_value_pair_list(a, key, value):
    return (key, value) in a

def contains_key_value_pair_dict(d, key, value):
    return key in d and value == d[key]

        
# Ta tiden på listen først
import time
time_before_start = time.time()
result = []
for _ in range(trails):
    val = contains_key_value_pair_list(a, "foo", 42)
time_when_done = time.time()
time_taken_list = (time_when_done - time_before_start) * 1000
print(f"Tid for oppslag på ('foo', 42) med liste: {time_taken_list:.0f}ms")

# Så det samme men med et oppslagsverk
time_before_start = time.time()
for _ in range(trails):
    val = contains_key_value_pair_dict(d, "foo", 42)
time_when_done = time.time()
time_taken_dict = (time_when_done - time_before_start) * 1000
print(f"Tid for oppslag på ('foo', 42) med oppslagsverk: {time_taken_dict:.0f}ms")
ratio = time_taken_list / time_taken_dict
print(f"For {n=} er oppslagsverk {ratio:.1f} ganger raskere enn lister")
print(f"Prøv med høyere verdi av n for å se større forskjeller")
Operatorer, funksjoner og metoder

Funksjoner og operatorer

d = { "a" : 1, "b" : 2, "c" : 3 }

print(len(d))       # Antall nøkler i oppslagsverket

print("a" in d)     # True
print(2 in d)       # False (in -operatoren sjekker kun nøkler)
print(2 not in d)   # True
print("a" not in d) # False

Metoder for å mutere oppslagsverk

d = { "a" : 1, "b" : 2, "c" : 3, "d" : 4}

# Fjern en nøkkel (og tilhørende verdi)
d.pop("d")            # Fjerner nøkkelen uten å bry seg om verdien
value = d.pop("b")    # Fjerner nøkkelen og tar vare på verdien
print(value)            # 2
print(d)                # {'a': 1, 'c': 3}

# Fjern en nøkkel og returner default-verdi dersom nøkkelen ikke finnes
print(d.pop("x", 42))   # 42
print(d.pop("c", 42))   # 3
print(d)                # {'a': 1}

# Legg til en nøkkel eller endre dens verdi
d["e"] = 5
d.update({"f": 6})
print(d)

# Slå sammen to oppslagsverk
d2 = {"f": 106, "g": 107}
d.update(d2)
print(f"{d=}")  # d bli mutert. Verdier fra d2 overskriver verdier fra d.
print(f"{d2=}") # d2 er urørt
Løkker over oppslagsverk
d = {"foo": 42, "bar": 25, "baz": 95}

# Løkke over nøklene
for key in d:
    print(key, end=" ")
print()

# Alternativ løkker over nøklene
for key in d.keys():
    print(key, end=" ")
print()

# Løkke over kun verdiene
for value in d.values():
    print(value, end=" ")
print()

# Løkke over både nøkler og verdier
for key in d:
    value = d[key]
    print(f"{key}:{value}", end=" ")
print()

# Alternativ løkke over både nøkler og verdier:
for key, value in d.items():
    print(f"{key}:{value}", end=" ")
print()