2.3 Ordbøker og mengder

Når lister ikke er nok

Lister er gode når du vil ha en ordnet sekvens. Men tenk deg at du vil slå opp en persons telefonnummer ut fra navnet, eller raskt finne ut hvilke elever som tar IT. Da blir det tungvint å lete gjennom en liste fra start til slutt. Det du trenger, er ordbøker og mengder.

En ordbok (dictionary, eller dict) er en samling av nøkkel-verdi-par, der hver nøkkel er unik og brukes til å slå opp verdien. En person kan beskrives som {"navn": "Anna", "alder": 18, "by": "Oslo"}. Du henter verdier med person["navn"] eller tryggere med person.get("land", "Norge"), som gir en standardverdi hvis nøkkelen mangler. Du legger til nye nøkler bare ved å skrive person["skole"] = "VG3", sjekker om en nøkkel finnes med in, og går gjennom alt med for nøkkel, verdi in person.items().

Det virkelig kraftige er hastigheten: oppslag i en ordbok skjer i O(1) tid – konstant, uansett hvor stor ordboken er. Med en liste må du i verste fall lete gjennom alt, O(n). For millioner av elementer er forskjellen enorm.

Hashtabellen bak kulissene

Hvordan kan oppslag være så raskt? Svaret er datastrukturen som ligger under ordboken: hashtabellen. Den fungerer i fire steg. Først kjører en hash-funksjon nøkkelen gjennom en beregning som gir et heltall – en hash-kode. Deretter brukes denne koden til å finne riktig «bøtte» i en intern array. Verdien lagres i den bøtten, og ved oppslag brukes nøyaktig samme prosess for å finne verdien lynraskt. Forenklet: hash("navn") gir et tall, tallet peker på en bøtte, og i den bøtten ligger «Anna». Noen ganger får to ulike nøkler samme hash-kode – det kalles en kollisjon – men Pythons dict håndterer det automatisk, så du trenger ikke bekymre deg.

Denne hastigheten gjør ordbøker perfekte til telling. Vil du telle hvor mange ganger hvert ord forekommer i en tekst, går du gjennom ordene og øker en teller per ord:

telling = {}
for ord in tekst.lower().split():
    telling[ord] = telling.get(ord, 0) + 1

Dette mønsteret er hjørnesteinen i tekstanalyse og statistikk. Ordbøker er også standard for strukturert data som JSON: en skole kan ha en liste av elever, der hver elev er en ordbok med navn, alder og en liste av fag. Du navigerer dypt med skole["elever"][0]["navn"] og kan enkelt finne alle som har IT ved å løkke gjennom elevene.

Mengder og mengdelære

Den andre nye strukturen er mengden (set) – en samling av unike elementer uten rekkefølge. Det aller første mengder gir deg gratis, er at duplikater forsvinner av seg selv. Du legger til med add, fjerner med remove (som gir feil om elementet mangler) eller discard (som ikke gir feil), og sjekker medlemskap med in.

Det virkelig elegante er at mengder støtter matematiske operasjoner rett fra mengdelæren. Med to mengder tall1 og tall2 får du union med | (alle unike elementer fra begge), snitt med & (elementene som finnes i begge), differanse med - (elementene i den første men ikke den andre), og symmetrisk differanse med ^ (elementene som er i nøyaktig én av dem). For eksempel gir {1, 2, 3} & {2, 3, 4} resultatet {2, 3}.

Dette gjør vanlige oppgaver triste enkle. Vil du finne duplikater i en liste, kan du sammenligne lengder: len(liste) != len(set(liste)) er sant hvis det finnes duplikater, fordi mengden fjerner dem. Vil du finne felles kunder i to lister, gjør du dem om til mengder og tar snittet: set(kunder1) & set(kunder2). Og fordi mengder også bygger på hashtabeller, er medlemskapssjekken lynrask – akkurat som oppslag i ordbøker.

Oppsummering

Når lister kommer til kort, trer ordbøker og mengder inn. Ordbøker lagrer nøkkel-verdi-par og gir O(1)-oppslag takket være hashtabeller, som bruker en hash-funksjon til å plassere verdier i bøtter. De er ideelle for telling, strukturert JSON-lignende data og caching. Mengder holder styr på unike elementer og støtter operasjoner fra mengdelæren: union (|), snitt (&), differanse (-) og symmetrisk differanse (^).

Med disse verktøyene blir oppgaver som å fjerne duplikater eller finne fellesnevnere mellom to lister både korte og lynraske. I neste kapittel skal vi bruke disse datastrukturene i designmønstre.