Python nb-no:Datastrukturer

Introduksjon

Datastrukturer er egentlig akkurat det navnet sier; de er strukturer som holder noe data sammen. Med andre ord bruker man dem for å lagre en samling data som har sammenheng med hverandre.

Det er fire innebygde datastrukturer i Python - lister, tupler, oppslagsverk og sett. Vi skal se på hvordan vi kan bruke alle sammen og hvordan de gjør livene våre enklere.

Lister

En liste er en datastruktur som inneholder en ordnet samling med ting, det vil si at du kan lagre en sekvens med ting i en liste. Dette er lett å se for seg hvis man tenker på en handleliste der du har en rekke med ting du skal kjøpe; den eneste forskjellen er at du antakeligvis har hver eneste ting på en egen linje i handlelisten din, mens Python har dem på samme linje med komma mellom dem.

Listen med ting burde ha to hakeparenteser rundt seg, slik at Python forstår at du skriver ned en liste. Med en gang du har laget en liste kan du legge til, fjerne eller lete etter ting i listen. Siden vi kan legge til og fjerne ting, kan vi si lister er en foranderlig datatype, det vil si at man kan forandre den.

Rask innføring i objekter og klasser

Selv om jeg har ventet med å diskutere objekter og klasser hittil, trenger du en forklaring akkurat nå slik at du kan forstå lister bedre. Vi skal se nærmere på dette i et eget kapittel.

En liste er et eksempel på bruk av objekter og klasser. Når vi bruker en variabel i og gir er verdi til den, for eksempel heltallet 5, kan du tenke på det som å lage et objekt (det vil si instans) i av klassen (det vil si typen) int (heltall heter "integer" på engelsk). Du kan sjekke help(int) for å forstå dette bedre.

En klasse kan også ha definert metoder, det vil si funksjoner som kun skal brukes på den klassen. Du kan bare bruke slik funksjonalitet når du har et objekt av den klassen. For eksempel har Python en append-metode for list-klassen, som lar deg legge til en ting på slutten av listen. For eksempel legger minliste.append('en ting') strengen 'en ting' til listen minliste. Legg merke til at vi bruker punktum for å få tilgang til metoder til objekter

En klasse kan også ha 'felt, som ikke er noe annet enn variabler som bare er definert for bare å brukes med den klassen. Du kan bare bruke disse variablene/navnene når du har et objekt for den klassen. Du får også tak i felter ved a bruke punktum, for eksempel minliste.felt.

Eksempel:

#!/usr/bin/python
# Filnavn: bruke_lister.py
 
# Dette er handlelisten min
handleliste = ['eple', 'mango', 'gulrot', 'banan']
 
print('Jeg har', len(handleliste), 'ting jeg skal kjøpe.')
 
print('Disse tingene er:', end=' ')
for ting in handleliste:
    print(ting, end=' ')
 
print('\nJeg må også kjøpe ris.')
handleliste.append('ris')
print('Handlelisten min er nå', handleliste)
 
print('Nå skal jeg sortere listen min')
handleliste.sort()
print('Den sorterte handlelisten er', handleliste)
 
print('Det første jeg skal kjøpe er', handleliste[0])
gammelting = handleliste[0]
del handleliste[0]
print('Jeg kjøpte', gammelting)
print('Handlelisten min er nå', handleliste)

Output:

   $ python bruke_lister.py
   Jeg har 4 ting jeg skal kjøpe.
   Disse tingene er: eple mango gulrot banan
   Jeg må også kjøpe ris.
   Handlelisten min er nå ['eple', 'mango', 'gulrot', 'banan', 'ris']
   Nå skal jeg sortere listen min
   Den sorterte handlelisten er ['banan', 'eple', 'gulrot', 'mango', 'ris']
   Det første jeg skal kjøpe er banan
   Jeg kjøpte banan
   Handlelisten min er nå ['eple', 'gulrot', 'mango', 'ris']

Hvordan det virker:

Variabelen handleliste er en handleliste for noen som skal i butikken. I handleliste lagrer vi bare strenger med navnet på ting vi skal kjøpe, men du kan legge hva du vil til en liste, inkludert tall og til og med andre lister.

Vi brukte også for..in-loopen for å behandle tingene i listen. Nå har du sikkert skjønt at en liste også er en sekvens. Det som er spesielt med sekvenser skal vi diskutere senere.

Legg merke til hvordan vi bruker nøkkelordargumentet end på print-funksjonen for å vise at vi vil avslutte outputen med mellomrom i stedet for linjeskift.

Så legger vi en ting til listen ved å bruke append-metoden for objekter, som vi allerede har sett på. Så sjekker vi at tingen faktisk har blitt lagt til listen ved å skrive opp innholdet i listen ved å bruke print.

Så sorterer vi listen ved å bruke sort-metoden for lister. Det er viktig at du forstår at denne metoden påvirker listen i seg selv og ikke bare gir deg en forandret liste - dette er forskjellig fra måten strenger fungerer på. Dette er det vi mener med at lister er foranderlige og strenger er uforanderlige.

Når vi er ferdige med å kjøpe en ting i butikken, fjerner vi den fra listen. Vi gjør dette med del-påstanden. Her nevner vi hvilken ting i listen vi vil ha fjernet, og så utfører del-påstanden det. Vi spesifiserer at vi vil ha fjernet den første tingen fra listen, og derfor bruker vi del handleliste[0] (husk på at Python starter med å telle fra 0).

Hvis du vil alle metodene som er definert for objektet "list", sjekk help(list).

Tupler

Tupler er akkurat som lister, med unntak av at de er uforanderlige, som strenger. Det betyr at du ikke kan endre på tupler. Du definerer tupler ved å skrive ting adskilt av kommaer innenfor et par med vanlige parenteser. Du bruker vanligvis tupler i tilfeller der en påstand eller en brukerdefinert funksjon trygt kan anta at samlingen med verdier (tuppelen) ikke kommer til å forandre seg.

Eksempel:

#!/usr/bin/python
# Filnavn: bruke_tuppel.py
 
zoo = ('python', 'elefant', 'pingvin')
print('Antallet dyr i dyrehagen er', len(zoo))
 
ny_zoo = ('ape', 'kamel', zoo)
print('Antall bur i den nye dyrehagen er', len(ny_zoo))
print('Dyrene i den nye dyrehagen er', ny_zoo)
print('De dyrene vi tok fra den gamle dyrehagen var', ny_zoo[2])
print('Det siste dyret vi tok fra den gamle dyrehagen var', ny_zoo[2][2])
print('Antallet dyr i den nye dyrehagen er', len(ny_zoo)-1+len(ny_zoo[2]))

Output:

   $ python bruke_tuppel.py
   Antallet dyr i dyrehagen er 3
   Antall bur i den nye dyrehagen er 3
   Dyrene i den nye dyrehagen er ('ape', 'kamel', ('python', 'elefant', 'pingvin'))

   De dyrene vi tok fra den gamle dyrehagen var ('python', 'elefant', 'pingvin')
   Det siste dyret vi tok fra den gamle dyrehagen var pingvin
   Antallet dyr i den nye dyrehagen er 5

Hvordan det virker:

Variabelen zoo referer til en tuppel med ting. Vi ser at vi kan bruke len-funksjonen for å få lengden på tuppelen. Dette indikerer at tupler også er sekvenser.

Så flytter vi dyrene til en ny dyrehage siden den gamle dyrehagen blir stengt. Derfor inneholder tuppelen ny_zoo noen dyr som allerede er i den nye dyrehagen og dyrene fra den gamle. Vel, la oss holde opp med å leke; legg merke til at tuppelen innenfor tuppelen ikke mister identiteten sin.

Vi får tilgang til tingene innenfor tuppelen ved å skrive tingens posisjon innenfor et par med hakeparenteser, akkurat som med lista fra i stad. Dette kalles indekseringsoperatoren. Vi får tak i den tredje tingen i ny_zoo ved å skrive ny_zoo[2], og vi får tak i den tredje tingen innenfor den tredje tingen i tuppelen ny_zoo ved å skrive ny_zoo[2][2]. Det er ganske enkelt med en gang du har skjønt det.

Tuppel med 0 eller 1 ting

Du lager en tom tupper med et tomt par med parenteser, for eksempel mintomme = (). En tuppel med bare en ting er ikke like enkel. Du må skrive den med et komma etter den første (og eneste) tingen, slik at Python kan skille mellom en tuppel og et par med parenteser som omringer objektet i et uttrykk, for eksempel må du skrive eneboer = (2 , ) hvis du har lyst på en tuppel som bare inneholder tingen 2.

Bemerkning til Perl-programmerere

En liste innenfor en liste mister ikke identiteten sin, det vil si at lister ikke blir flatet ut, som i Perl. Det samme gjelder for en tuppel innenfor en tuppel, en tuppel innenfor en liste eller en liste innenfor en tuppel og så videre. For alt Python vet er de bare objekter lagret innenfor andre objekter.

Oppslagsverk

Et oppslagsverk er som en adressebok der du kan finne adressen eller kontaktdetaljene til en person selv om du bare vet navnet hans/hennes, det vil si at vi assosierer nøklene (navn) med verdier (detaljer). Legg merke til at nøklene må være unike, siden du ikke kan finne den riktige informasjonen dersom du har to personer med samme navn.

Legg merke til at du bare kan bruke uforanderlige objekter (som strenger) som nøkler i et oppslagsverk, men du kan bruke enten foranderlige eller uforanderlige objekter som verdier i oppslagsverket. Dette betyr at du bare burde bruke enkle objekter som nøkler.

Par med nøkler og verdier skrives i et oppslagsverk ved å bruke følgende notasjon: d = {nøkkel1 : verdi1, nøkkel2 : verdi2}. Legg merke til at nøkkel/verdi-parene skilles med kolon og at parene blir adskilt av kommaer, og at det hele er innenfor et par med sløyfeparenteser.

Husk også på at nøkkel/verdi-par i oppslagsverk ikke er sortert på noen måte. Hvis du vil ha en spesiell rekkefølge må du sortere dem selv.

Oppslagsverkene du kommer til å bruke er instanser/objekter i dict-klassen.

Eksempel:

#!/usr/bin/python
# Flinavn: bruke_oppslag.py
 
# 'ab' er en forkortelse for 'a'dresse'b'bok
 
ab = {	'Swaroop'    : 'swaroop@swaroopch.com',
        'Larry'      : 'larry@wall.org',
        'Matsumoto'  : 'matz@ruby-lang.org',
        'Spammer'    : 'spammer@hotmail.com'
    }
 
print('Swaroops adresse er', ab['Swaroop'])
 
# Å slette et nøkkel/verdi-par
del ab['Spammer']
 
print('\nDet er {0} kontakter i adresseboka\n'.format(len(ab)))
 
for navn, adresse in ab.items():
    print('Kontakt {0} på {1}'.format(navn, adresse))
 
# Legge til et nøkkel/verdi-par
ab['Guido'] = 'guido@python.org'
 
if 'Guido' in ab: # ELLER ab.has_key('Guido'):
    print('\nGuidos adresse er', ab['Guido'])

Output:

   $ python using_dict.py
   Swaroops adresse er swaroop@swaroopch.com

   Det er 3 kontakter i adresseboka

   Kontakt Swaroop på swaroop@swaroopch.com
   Kontakt Matsumoto på matz@ruby-lang.org
   Kontakt Larry på larry@wall.org

   Guidos adresse er guido@python.org

Hvordan det virker:

Vi lager oppslagsverket ab ved å bruke notasjonen som vi allerede har sett på. Så får vi tak i nøkkel/verdi-parene ved å skrive opp nøkkelen med indekseringsoperatoren som vi så på i sammenheng med lister og tupler. Legg merke til den enkle syntaksen.

Vi kan slette nøkkel/verdi-par ved å bruke vår gamle venn del-påstanden. Vi bare skriver oppslagsverket og indekseringsoperatoren for nøkkelen vi har lyst til å ta vekk og gir det til del-påstanden. Du trenger ikke å vite verdien som hører til nøkkelen for å gjøre dette.

Så får vi tilgang til hvert eneste nøkkel/verdi-par i oppslagsverket ved å bruke items-metoden til oppslagsverket, som gir oss en liste med tupler der hver tuppel inneholder ett par med ting - nøkkelen fulgt av verdien. Vi henter tilbake dette paret og gir den til variablene navn og adresse ved å bruke for..in-loopen, og så skriver vi disse verdiene innenfor for-blokken.

Vi kan legge til nye nøkkel/verdi-par ved bare å bruke indekseringsoperatoren for å få tilgang til en nøkkel og gi den verdien vi har lyst til, som vi gjorde med Guido ovenfor.

Vi kan sjekke om et nøkkel/verdi-par er i oppslagsverket ved å bruke in-operatoren, eller til og med has_key-metoden for dict-klassen (oppslagsverk heter dictionary på engelsk). Sjekk dokumentasjonen for alle metodene til dict-klassen ved å bruke help(dict).

Nøkkelordargumenter og oppslagsverk

Hvis du allerede har brukt nøkkelordargumenter i funksjonene dine, har du også brukt oppslagsverk! Bare tenk på det - nøkkel/verdi-parene skrives av deg i parameterlisten når du definerer funksjonen, og når du får tilgang til variabler innenfor funksjonen er det akkurat som å få tilgang til en nøkkel i et oppslagsverk (som kalles symboltabellen i terminologi for design av kompilatorer).

Sekvenser

Lister, tupler, strenger og filer er eksempler på sekvenser, men hva er egentlig sekvenser, og hva er så spesielt med dem? To kjennetegn for sekvenser er indeksering, som gjør at vi kan få tak i en spesiell ting i sekvensen og slicing, som gjør at vi kan hente en slice av sekvensen, det vil si en del av sekvensen.

Eksempel:

#!/usr/bin/python
# Filnavn: sek.py
 
handleliste = ['eple', 'mango', 'gulrot', 'banan']
navn = 'swaroop'
 
# Indeksering- eller 'abonnements'-operasjon
print('Ting 0 er', handleliste[0])
print('Ting 1 er', handleliste[1])
print('Ting 2 er', handleliste[2])
print('Ting 3 er', handleliste[3])
print('Ting -1 er', handleliste[-1])
print('Ting -2 er', handleliste[-2])
print('Tegn 0 er', navn[0])
 
# Slicing på en liste
print('Ting 1 til 3 er', handleliste[1:3])
print('Ting 2 til slutten er', handleliste[2:])
print('Ting 1 til -1 er', handleliste[1:-1])
print('Tingene fra start til slutt er', handleliste[:])
 
# Slicing på en streng
print('tegn 1 til 3 er', navn[1:3])
print('tegn 2 til slutten er', navn[2:])
print('tegn 1 til -1 er', navn[1:-1])
print('tegnene fra start til slutt er', navn[:])

Output:

   $ python seq.py
   Ting 0 er eple
   Ting 1 er mango
   Ting 2 er gulrot
   Ting 3 er banan
   Ting -1 er banan
   Ting -2 er gulrot
   Tegn 0 er s
   Ting 1 til 3 er ['mango', 'gulrot']
   Ting 2 til slutten er ['gulrot', 'banan']
   Ting 1 til -1 er ['mango', 'gulrot']
   Tingene fra start til slutt er ['eple', 'mango', 'gulrot', 'banan']
   tegn 1 til 3 er wa
   tegn 2 til slutten er aroop
   tegn 1 til -1 er waroo
   tegnene fra start til slutt er swaroop

Hvordan det virker:

Først ser vi hvordan man bruker indekser for å hente enkelte ting ut fra sekvenser. Dette kaller man også for abonnementsoperasjonen. Når du skriver et tall til en sekvens innenfor hakeparenteser, som ovenfor, vil Python hente tingen som står på den plassen i sekvensen. Husk nok en gang på at Python starter å telle fra 0. Derfor henter handleliste[0] den første tingen og handleliste[3} den fjerde tingen i sekvensen handleliste.

Indeksen kan også være et negativt tall, og da blir posisjonen regnet ut fra slutten av sekvensen. Derfor henter handleliste[-1] den siste tingen i sekvensen og handleliste[-2] den nest siste tingen.

Slicing-operasjonen bruker man ved å skrive navnet på sekvenser etterfulgt av et valgfritt par med tall adskilt av et kolon med hakeparenteser. Legg merke til at det er veldig likt indeksering, som du har brukt til nå. Husk på at bare tallene er valgfrie; kolonet er ikke valgfritt.

Det første tallet (før kolonet) i slicing-operasjonen forteller hvilken posisjon slicingen starter fra, og det andre tallet (etter kolonet) forteller hvor slicingen skal stoppe. Hvis den første plassen er tom vil Python starte på starten av sekvensen, og hvis det andre tallet ikke er der vil Python stoppe på slutten. Legg merke til at slicen starter på den første og slutter rett før slutten, det vil si at den første tingen er inkludert, men den siste er ikke det.

Derfor gir handleliste[1:3] en slice fra sekvensen som starter på den første tingen, tar med posisjon 2, men stopper på posisjon tre. Derfor gir den oss kun en slice med to ting. handleliste[:] gir oss en kopi av hele sekvensen.

Du kan også ha negative posisjoner i slicing. Negative posisjoner brukes for å beskrive posisjoner fra slutten av sekvensen, akkurat som i indeksering. For eksempel vil handleliste[:-1] gi en slice som har alt annet enn den siste tingen i sekvensen.

Du kan også gi et tredje argument til slicen, som er steg i slicingen, og hvis ikke annet er oppgitt er denne på 1):

>>> handleliste = ['eple', 'mango', 'gulrot', 'banan']
>>> handleliste[::1]
['eple', 'mango', 'gulrot', 'banan']
>>> handleliste[::2]
['eple', 'gulrot']
>>> handleliste[::3]
['eple', 'banan']
>>> handleliste[::-1]
['banan', 'gulrot', 'mango', 'eple']

Legg merke til at når størrelsen steget er 2 får vi tingene i posisjon 0, 2 og så videre. Når størrelsen på steget er 3 får vi tingene med posisjon 0, 3, og så videre.

Prøv forskjellige kombinasjoner ved å bruker tolkeren interaktivt i kommandolinjen, så får du se resultatene med en gang. Det som er så bra med sekvenser er at man får tilgang til tupler, lister og strenger på helt samme måte!

Sett

Sett er uordnete samlinger med enkle ting. Disse bruker man når det er viktigere at en ting finnes i en samling enn hvor eller hvor mange ganger den er i samlingen.

Når du bruker sett kan du se etter om en ting er der, enten det er i et undersett i et annet sett, finne krysningen mellom to sett og så videre.

>>> bri = set(['brasil', 'russland', 'india'])
>>> 'india' in bri
True
>>> 'usa' in bri
False
>>> brik = bri.copy()
>>> brik.add('kina')
>>> brik.issuperset(bri)
True
>>> bri.remove('russland')
>>> bri & brik # OR bri.intersection(brik)
{'brasil', 'india'}

Hvordan det virker:

Dette eksempelet er ganske selvforklarende siden det bare tar for seg grunnleggende teorier om sett som man har om i skolematematikken.

Referanser

Når du lager et objekt og gir den til en variabel bare refererer til objektet, og ikke representerer objektet i seg selv. Det betyr at navnet på variabelen bare peker til den delen av datamaskinens minne der objektet er lagret. Dette kalles binding av navnet til objektet.

Generelt trenger du ikke å bekymre deg for dette, men det er en underliggende effekt som du må være klar over:

Eksempel:

#!/usr/bin/python
# Filnavn: referanse.py
 
print('Enkel tildeling')
handleliste = ['eple', 'mango', 'gulrot', 'banan']
minliste = handleliste # minliste er bare et annet navn som peker til det samme objektet!
 
del handleliste[0] # Jeg har kjøpt den første tingen, så jeg fjernet det fra listen
 
print('handlelisten er', handleliste)
print('minliste er', minliste)
# legg merke til at både handleliste og minliste skriver den samme listen uten
# eplet, som bekrefter at de begge to peker til den samme tingen
 
print('Kopier ved å gjøre en full slice')
minliste = handleliste[:] # lag en kopi ved å gjøre en full slice
del minliste[0] # fjern den første tingen
 
print('handlelisten er', handleliste)
print('minliste er', minliste)
# legg merke til at de to listene nå er forskjellige

Output:

   $ python reference.py
   Enkel tildeling
   handlelisten er ['mango', 'gulrot', 'banan']
   minliste er ['mango', 'gulrot', 'banan']
   Kopier ved å gjøre en full slice
   handlelisten er ['mango', 'gulrot', 'banan']
   minliste er ['gulrot', 'banan']

Hvordan det virker:

Mesteparten av forklaringen står i kommentarene i selve programmet.

Det du må huske på er at hvis du vil lage en kopi av en liste eller en lignende type sekvens eller komplekst objekt (ikke enkle objekter, som heltall), må du bruke slicing for å lage en kopi. Hvis du bare gir variabelnavnet til et annet navn vil begge to referere til det samme objektet, og det kan bli trøbbel av dette om du ikke er forsiktig.

Bemerkning til Perl-programmerere

Legg merke til at tildelingspåstander for lister 'ikke lager en kopi. Du må bruke slicing for å lage en kopi av sekvensen.

Mer om strenger

Vi har allerede sett nærme på strenger. Hva mer kan det være å vite? Vel, visste du at strenger også er objekter og har metoder, slik at du kan gjøre alt mulig fra å sjekke en del av strengen til å fjerne mellomrom?

Strengene du bruker programmene dine er alle sammen objekter av klassen str. Noen nyttige metoder for denne klassen blir demonstert i det neste eksemplet. For å få en full liste over metoder, sjekk help(str).

Eksempel:

#!/usr/bin/python
# Filnavn str_metoder.py
 
navn = 'Swaroop' # Dette er en streng
 
if navn.startswith('Swa'):
    print('Ja, strengen starter med "Swa"')
 
if 'a' in navn:
    print('Ja, strengen inneholder strengen "a"')
 
if navn.find('war') != -1:
    print('Ja, den inneholder strengen "war"')
 
avgrenser = '_*_'
minliste = ['Brasil', 'Russland', 'India', 'Kina']
print(avgrenser.join(minliste))

Output:

   $ python str_methods.py
   Ja, strengen starter med "Swa"
   Ja, strengen inneholder strengen "a"
   Ja, den inneholder strengen "war"
   Brasil_*_Russland_*_India_*_Kina

Hvordan det virker:

Her ser vi mange metoder vi kan bruke på strenger i aksjon. startswith-metoden bruker vi for å finne ut om strengen starter med den oppgitte strengen. in-operatoren bruker vi for å sjekke om en gitt streng er en del av strengen.

find-metoden bruker vi for å finne posisjonen til den gitte strengen i strengen, eller gir -1 hvis den ikke klarer å finne denne understrengen. str-klassen har også en nett måte å slå sammen (join) tingene i et sekvens med en oppgitt streng som et skille mellom hver ting i sekvensen.

Sammendrag

Vi har sett nærme på de forskjellige innebygde datastrukturene i Python. Disse datastrukturene kommer til å være essensielle når du skriver programmer av en viss størrelse.

Nå som vi har fått på plass mye av det grunnleggende i Python skal vi se på hvordan man skal designe og skrive et ekte Python-program.