3.3 Rekursjon og dynamisk programmering

Riktig boks for jobben

En datastruktur er en måte å organisere og lagre data på, slik at vi kan bruke dem effektivt. Tenk på forskjellen mellom å lete etter et ord i en usortert bunke lapper og å slå opp i en ordbok. Begge inneholder de samme ordene, men organiseringen gjør en enorm forskjell. Valg av riktig datastruktur kan avgjøre både ytelse og lesbarhet i koden din.

Når vi vurderer en datastruktur, spør vi hvor raskt vi kan sette inn, slette, søke og hente data, om rekkefølgen må bevares, og om vi tillater duplikater. Python gir oss fem innebygde verktøy: list (ordnet, indeksert, tillater duplikater), dict (nøkkel-verdi-par med raske oppslag), set (uordnet, ingen duplikater), tuple (ordnet og uforanderlig) og deque (en dobbel-endet kø fra modulen collections).

Lista er den mest brukte. Den er lynrask til indekstilgang liste[i] (O(1)), til å legge til på slutten med append (O(1)) og fjerne fra slutten med pop (O(1)). Men den er treg i den andre enden: insert(0, x) og pop(0) er O(n), fordi alle elementene må skyves. Og medlemssjekken x in liste er O(n), fordi den må gå gjennom alt. Denne innsikten – rask i enden, treg i starten – er nøkkelen til å forstå når lista ikke er nok.

Stakker, køer og en parentes-vakt

Når lista kommer til kort, har vi spesialstrukturer. En stakk følger LIFO – siste inn, første ut – som en tallerkenstabel. I Python bruker vi en vanlig liste: append for push og pop for pop, begge O(1). En kø følger FIFO – første inn, første ut – som en kø i butikken. For køer bør du bruke collections.deque, ikke en vanlig liste, fordi deque.popleft() er O(1) mens list.pop(0) er O(n). En deque er rask i begge ender, mens en liste er rask bare i den ene.

Valget mellom stakk og kø følger problemet. Angre-funksjonen og nettleserens tilbake-knapp er stakker, fordi du alltid vil reversere den siste handlingen først. Printerens skrivekø og behandling av kundehenvendelser i ankomstrekkefølge er køer, fordi rettferdighet betyr først til mølla.

Et elegant eksempel på en stakk i arbeid er å sjekke balanserte parenteser. Du går gjennom teksten, og hver gang du møter en åpningsparentes pusher du den på stakken. Møter du en lukkeparentes, popper du toppen og sjekker at den matcher. Hvis stakken er tom når du møter en lukkeparentes, eller hvis den ikke er tom til slutt, er noe ubalansert. For (a + [b]) ender stakken tom – alt stemmer. For ((a + b) blir det igjen en åpningsparentes – ubalansert.

Ordbøker og mengder for fart

De to siste verktøyene gir lynrask tilgang via hashtabeller. En ordbok lagrer nøkkel-verdi-par med O(1) oppslag, innsetting og sletting i snitt. Nøklene må være unike og uforanderlige (strenger, tall, tupler), verdiene kan være hva som helst, og fra Python 3.7 bevares innsettingsrekkefølgen. Internt bruker ordboken en hashtabell: nøkkelen omdannes til et tall som peker rett på hvor verdien ligger. Ordbøker er perfekte for oppslag (brukernavn til brukerdata), telling av forekomster og caching.

En mengde er en uordnet samling av unike elementer, med O(1) medlemssjekk. Den fjerner duplikater automatisk og støtter mengdeoperasjonene union (|), snitt (&), differanse (-) og symmetrisk differanse (^). For eksempel gir {1,2,3,4,5} & {4,5,6,7,8} resultatet {4,5} – elementene som finnes i begge.

Forskjellen i fart kan være svimlende. En medlemssjekk x in samling er O(n) for en liste, men O(1) for en mengde eller ordbok. På en million elementer kan mengden være titusenvis av ganger raskere. Et konkret eksempel: skal du sjekke om to lister har felles elementer, er den naive løsningen med element in liste2 O(n·m). Konverterer du liste2 til en mengde først, blir hver sjekk O(1), og hele algoritmen O(n+m) – ofte tusenvis av ganger raskere bare ved den ene endringen.

Å velge riktig

Med alle verktøyene på bordet blir spørsmålet: hvilket velger du? Et lite beslutningstre hjelper. Trenger du nøkkel-verdi-par? Velg dict. Trenger du bare unike elementer og raske medlemssjekker? Velg set. Trenger du en ordnet sekvens? Da avhenger det: skal den ikke endres, velg tuple; legger du til og fjerner mest i endene, velg deque; ellers en vanlig list.

Ta en nettbutikk som eksempel. Produktinformasjon med unik ID hører hjemme i en ordbok, så du kan slå opp et produkt på ID-en i O(1). Handlekurven passer i en liste – ordnet, og samme produkt kan legges til flere ganger. Hvilke produkter en kunde har sett, lagres i en mengde, så du unngår duplikater og kan sjekke medlemskap raskt. Og en «sist sett»-funksjon der det nyeste vises først, er en stakk – gjerne en deque(maxlen=10) som automatisk begrenser seg til de ti siste.

De viktigste ytelsesgrepene er enkle å huske. Bruk en mengde, ikke en liste, til medlemssjekker. Bruk en deque, ikke en liste, til køer. Bruk en ordbok, ikke nøstede løkker, til oppslag. Og aller viktigst: velg riktig datastruktur før du begynner å kode, ikke etterpå.

Oppsummering

Valg av datastruktur er valg av riktig boks for jobben. Lister er raske i enden (append, pop) men trege i starten og på medlemssjekk. Stakker (LIFO, via list) og køer (FIFO, via deque) løser problemer med reversering og rettferdig rekkefølge – og en stakk kan til og med vokte balanserte parenteser. Ordbøker gir O(1)-oppslag via hashtabeller og er ideelle for nøkkelbasert tilgang og telling, mens mengder gir unike elementer, lynrask medlemssjekk og mengdeoperasjoner.

Den store gevinsten ligger i å velge riktig: en mengde kan være titusenvis av ganger raskere enn en liste på medlemssjekk, og et lite beslutningstre – nøkkel-verdi, unikhet, eller ordnet sekvens – peker deg mot dict, set, tuple, deque eller list. Bestem deg før du koder. I neste kapittel utforsker vi rekursjon.