21 Datastrukturer og algoritmer

Når dataene hoper seg opp

Tenk deg at sensoren din har målt temperaturen hvert femte minutt i et helt døgn. Det blir nesten 300 tall. Eller at du bygger en værstasjon som logger temperatur, fuktighet, trykk og vind. Plutselig drukner du i data. Hvordan holder du orden på alt? Og hvordan finner du raskt den ene målingen du leter etter, eller de ti varmeste timene?

Dette er hjertet i informatikken: datastrukturer, måtene vi organiserer data på, og algoritmer, oppskriftene vi bruker for å bearbeide dem. I dette kapittelet skal vi lære de viktigste verktøyene. Vi starter med lister, som holder data i rekkefølge, og ordbøker, som lar oss slå opp data med en nøkkel. Så går vi over til algoritmer for å søke og sortere, og oppdager noe overraskende: to algoritmer som løser samme oppgave kan ha enormt ulik fart. Til slutt lærer vi språket for å snakke om denne farten -- den såkalte Big-O-notasjonen. Når du er ferdig, vet du ikke bare hvordan du lagrer data, men hvordan du gjør det smart.

Lister og ordbøker -- to måter å holde orden

La oss starte med den mest grunnleggende datastrukturen: listen. En liste er en ordnet samling av elementer du kan endre. Du lager den enkelt, for eksempel sensorer = [23.5, 24.1, 22.8, 25.0], og henter elementer med en indeks som starter på 0: sensorer[0] gir det første, mens sensorer[-1] gir det siste. Du kan endre elementer, legge til på slutten med append(), sette inn på en posisjon med insert(), og fjerne med remove() eller pop(). Et nyttig triks er slicing: tall[2:5] plukker ut elementene fra indeks 2 til og med 4, og tall[::2] tar annethvert element.

Men lister passer ikke alltid. Hva om du vil slå opp data ut fra et navn i stedet for et tall? Da bruker du en ordbok (dictionary), som lagrer data som nøkkel-verdi-par. Du kan skrive sensor_data = {"temperatur": 23.5, "fuktighet": 65} og hente verdien direkte med sensor_data["temperatur"]. Et tips er metoden get(), som lar deg angi en standardverdi hvis nøkkelen ikke finnes -- sensor_data.get("vind", 0) gir 0 hvis vind mangler. Du kan legge til nøkler, sjekke om en finnes med in, og du kan til og med ha ordbøker inni ordbøker for å bygge strukturerte data.

Når skal du velge hva? Tommelregelen er enkel: bruk en liste når du har ordnede elementer du vil indeksere numerisk og løkke gjennom, og bruk en ordbok når du vil slå opp data med beskrivende nøkler og holde strukturerte data samlet. Riktig datastruktur gjør halve jobben for deg.

Å lete smart

Nå har vi dataene -- men hvordan finner vi noe i dem? Den enkleste metoden er lineært søk: vi går gjennom listen element for element, fra start til slutt, til vi finner det vi leter etter. Det er enkelt og fungerer alltid, men i verste fall må vi sjekke alle elementene.

Finnes det noe smartere? Ja -- men det krever en betingelse: listen må være sortert. Da kan vi bruke binært søk, som er en av de vakreste idéene i informatikken. I stedet for å lete fra start, ser vi på elementet i midten. Er det vi leter etter mindre, vet vi at det må ligge i den nedre halvdelen, så vi kan kaste bort hele den øvre. Er det større, kaster vi den nedre. For hvert eneste steg halverer vi søkeområdet. Tenk på det som å lete i en ordbok: du slår ikke opp side for side, du åpner på midten og halverer.

Forskjellen i fart er forbløffende. I en liste med 1000 elementer trenger lineært søk rundt 500 sammenligninger i snitt, mens binært søk klarer seg med rundt 10. Og blir listen større, vokser forspranget dramatisk: i en liste med en million elementer trenger lineært søk opptil en million sammenligninger, mens binært søk klarer seg med bare rundt 20. Lærdommen er klar: hvis dataene dine er sortert og du søker ofte, er binært søk i en helt annen liga. Prisen er at du må holde listen sortert -- og det leder oss naturlig over til hvordan vi sorterer.

Å sortere -- og å måle effektivitet

For å kunne søke binært må vi kunne sortere. La oss se på den klassiske, men trege metoden først: boblesortering. Den sammenligner to naboelementer, og bytter dem hvis de står i feil rekkefølge. Så gjentar den dette igjen og igjen, og store verdier «bobler» langsomt oppover til alt er sortert. Den er lett å forstå, men ikke spesielt rask.

Hvor rask -- eller treg -- en algoritme er, beskriver vi med Big-O-notasjon. Den forteller hvordan kjøretiden vokser når datamengden $n$ øker. Lineært søk er $O(n)$: dobler du datamengden, dobler du tiden. Boblesortering er $O(n^2)$, kvadratisk tid: dobler du datamengden, firedobler du tiden, fordi den har en løkke inni en løkke. Binært søk derimot er $O(\log n)$, som vokser nesten ikke i det hele tatt. Forskjellen blir voldsom for store datasett: for 1000 elementer trenger boblesortering rundt en million operasjoner.

Heldigvis trenger du sjelden å skrive sorteringen selv. Python har innebygd, effektiv sortering: sorted(tall) gir en ny sortert liste, mens tall.sort() sorterer på stedet. Du kan sortere synkende med reverse=True, eller etter en egendefinert nøkkel -- for eksempel sortere en liste med par etter temperatur med key=lambda x: x[1]. Denne innebygde sorteringen, kalt Timsort, er $O(n \log n)$ -- for 1000 elementer rundt 10 000 operasjoner, altså hundre ganger raskere enn boblesortering. Når du for eksempel skal finne de ti varmeste målingene blant tusen, kan du derfor bare sortere synkende og ta de ti første. Å velge riktig algoritme er ofte forskjellen på et program som svarer på et øyeblikk og ett som henger.

Oppsummering

Vi har lært å organisere og bearbeide data smart. Lister holder ordnede elementer du indekserer numerisk og kan skive opp med slicing, mens ordbøker lar deg slå opp data med beskrivende nøkler og bygge strukturerte data.

For å finne data brukte vi søkealgoritmer: lineært søk ($O(n)$) som sjekker alt, og binært søk ($O(\log n)$) som halverer søkeområdet hvert steg -- men krever en sortert liste. For å sortere så vi den trege boblesorteringen ($O(n^2)$) og den raske innebygde Timsort ($O(n \log n)$). Det viktigste grepet var Big-O-notasjonen, språket for å forstå hvordan kjøretiden vokser med datamengden. Riktig datastruktur og riktig algoritme er forskjellen på et program som svarer lynraskt og ett som henger -- og nå har du verktøyene til å velge klokt.