Nada

Föreläsning 4: Listor eller vektorer

Listor i programmet

Pythons listor kan innehålla vad som helst. Listan [17, 17.0, 'sjutton'] har tre objekt av olika typer: int, float, str. En lista av tal kallas ofta vektor, men Python har inga vektoroperationer som Matlab. Vissa vanliga listor skapas enkelt. 
   v = range(17,20)      => [17,18,19]
   len(v)                => 3
   tom = []              # En tom lista
   year = [2010]         # En lista med ett objekt
   txt = "Gott nytt år"  # En lista av tolv tecken
   wish = txt.split()    => ["Gott","nytt","år"]
   wish + year           => ["Gott","nytt","år",2010]
   print wish[2][1]      => y
Eftersom textsträngar är listor så är wish en lista av listor. Man skriver ut tredje ordets andra bokstav med dubbla index.

Man klipper och klistrar i listor precis som i text, men textsträngar skiljer sej på två sätt från allmänna listor. Textobjekt har trettio egna metoder, bland annat följande. 

   txt.split()  => lista av ord, blanktecknen delar txt
   txt.strip()  => samma text utan avslutande blank och nyrad
   txt.upper()  => smma text med stora bokstäver
Man kan inte gå in och ändra i ett textobjekt, men det kan man i allmänna listor. 
   v[0]=666
   wish[2]="hår"
Krångligare listor kan skapas så här. 
   leve = ["Hurra"]*4    => ["Hurra","Hurra","Hurra","Hurra"]
   for i in range(3):
       v[i]=i*i          => [0,1,4]
   for j in v:
       year = year+[2*j] => [2010,0,2,8]

Listobjekt i datorn

Efter satsen v=[17,18,19] finns v i namnlistan med adressen till ett listobjekt med tre platser. På första platsen finns inte talet 17 utan adressen till ett annat objekt som innehåller 17. Efter satsen v[0]=666 pekar v fortfarande på samma listobjekt, med dess första plats innehåller nu adressen till ett nytt objekt med 666.

Om man sätter in ett för stort index blir det förstås felavbrott. Men det obegripligaste fel som drabbar en ny pythonkramare är följande. 

   v = [17,18,19]
   u = v                   
   u[0]=666
   print v[0]         => 666
Efter satsen u=v pekar nämligen u och v på samma listobjekt. Om man menar att u ska vara en kopia av listobjektet kan man skriva u=v[0:3] eller enklare u=v[:].

Inläsning från fil till vektor

Vi tänker oss att filen data.reg innehåller personnummer och namn med en person per rad. Vi kan läsa in den i en lista på följande sätt. 
   pnrfil = open("data.reg")     # pnrfil pekar på ett filobjekt
   pers = datafil.readlines()    # en lista med raderna i filen
   n = len(pers)                 # antalet personer

Linjär sökning i vektor

Att söka efter en person bland n personer kan ta lång eller kort tid beroende på hur stor otur man har. I genomsnitt måste man kolla n/2 personer innan man hittar den rätta. Om man söker efter någon som inte finns måste man alltid kolla alla n personerna innan man kan ge upp.

Dessa båda tal anger komplexiteten för algoritmen linjär sökning. Genomsnittlig komplexitet är n/2 och värstafallskomplexiteten är n. Om man använder en for-slinga är det viktigt att bryta den så snart man funnit vad man söker, annars blir det alltid värstafallskomplexitet! 

    pnr = "420119-0818"
    for i in range(n):
        if pers[i][:11]==pnr:
            print pers[i]
            break
Om vektorn är ordnad på personnummer finns en mycket snabbare algoritm som heter binär sökning. Den tar vi nästa gång!
Sidansvarig: <henrik@nada.kth.se>
Senast ändrad 18 oktober 2009
Tekniskt stöd: <webmaster@nada.kth.se>