5. Datastrukturer

I det här kapitlet beskrivs vissa saker som du redan har lärt dig mer ingående, och några nya saker läggs till.

5.1. Mer om listor

Datatypen list har några fler metoder. Här är alla metoder för listobjekt:

list.append(x)

Lägger till ett objekt i slutet av listan. Liknar a[len(a):] = [x].

list.extend(iterable)

Förläng listan genom att lägga till alla objekt från iterabeln. Liknar a[len(a):] = iterabel.

list.insert(i, x)

Infoga ett element på en given position. Det första argumentet är indexet för det element som ska infogas före, så a.insert(0, x) infogar längst fram i listan, och a.insert(len(a), x) är likvärdigt med a.append(x).

list.remove(x)

Tar bort det första objektet från listan vars värde är lika med x. Det ger upphov till ett ValueError om det inte finns något sådant objekt.

list.pop([i])

Tar bort objektet på den angivna positionen i listan och returnerar det. Om inget index anges, tar a.pop() bort och returnerar det sista objektet i listan. Den ger upphov till ett IndexError om listan är tom eller om indexet ligger utanför listintervallet.

list.clear()

Ta bort alla objekt från listan. Påminner om del a[:].

list.index(x[, start[, end]])

Returnerar nollbaserat index i listan för det första objektet vars värde är lika med x. Utlöser ett ValueError om det inte finns något sådant objekt.

De valfria argumenten start och end tolkas som i slice-notationen och används för att begränsa sökningen till en viss delsekvens av listan. Det returnerade indexet beräknas i förhållande till början av den fullständiga sekvensen i stället för argumentet start.

list.count(x)

Returnera antalet gånger x förekommer i listan.

list.sort(*, key=None, reverse=False)

Sortera objekten i listan på plats (argumenten kan användas för att anpassa sorteringen, se sorted() för deras förklaring).

list.reverse()

Backa tillbaka elementen i listan på plats.

list.copy()

Returnerar en ytlig kopia av listan. Liknar a[:].

Ett exempel som använder de flesta av listans metoder:

>>> fruits = ['orange', 'apple', 'pear', 'banana', 'kiwi', 'apple', 'banana']
>>> fruits.count('apple')
2
>>> fruits.count('tangerine')
0
>>> fruits.index('banana')
3
>>> fruits.index('banana', 4)  # Find next banana starting at position 4
6
>>> fruits.reverse()
>>> fruits
['banana', 'apple', 'kiwi', 'banana', 'pear', 'apple', 'orange']
>>> fruits.append('grape')
>>> fruits
['banana', 'apple', 'kiwi', 'banana', 'pear', 'apple', 'orange', 'grape']
>>> fruits.sort()
>>> fruits
['apple', 'apple', 'banana', 'banana', 'grape', 'kiwi', 'orange', 'pear']
>>> fruits.pop()
'pear'

Du kanske har märkt att metoder som insert, remove eller sort som bara ändrar listan inte har något returvärde utskrivet - de returnerar standardvärdet None. [1] Detta är en designprincip för alla föränderliga datastrukturer i Python.

En annan sak som du kanske märker är att inte alla data kan sorteras eller jämföras. Till exempel sorterar inte [None, 'hello', 10] eftersom heltal inte kan jämföras med strängar och None inte kan jämföras med andra typer. Det finns också vissa typer som inte har någon definierad ordningsrelation. Till exempel är 3+4j < 5+7j inte en giltig jämförelse.

5.1.1. Använda listor som staplar

Listmetoderna gör det mycket enkelt att använda en lista som en stapel, där det sista elementet som läggs till är det första elementet som hämtas (”sist in, först ut”). För att lägga till ett element överst i stapeln, använd append(). För att hämta ett objekt från toppen av stacken, använd pop() utan ett explicit index. Till exempel:

>>> stack = [3, 4, 5]
>>> stack.append(6)
>>> stack.append(7)
>>> stack
[3, 4, 5, 6, 7]
>>> stack.pop()
7
>>> stack
[3, 4, 5, 6]
>>> stack.pop()
6
>>> stack.pop()
5
>>> stack
[3, 4]

5.1.2. Använda listor som köer

Det är också möjligt att använda en lista som en kö, där det första elementet som läggs till är det första elementet som hämtas (”först in, först ut”); listor är dock inte effektiva för detta ändamål. Det går snabbt att lägga till och ta bort element från slutet av en lista, men det går långsamt att lägga till eller ta bort element från början av en lista (eftersom alla andra element måste flyttas med ett).

För att implementera en kö, använd collections.deque som är utformad för att ha snabba appends och pops från båda ändar. Till exempel:

>>> from collections import deque
>>> queue = deque(["Eric", "John", "Michael"])
>>> queue.append("Terry")           # Terry arrives
>>> queue.append("Graham")          # Graham arrives
>>> queue.popleft()                 # The first to arrive now leaves
'Eric'
>>> queue.popleft()                 # The second to arrive now leaves
'John'
>>> queue                           # Remaining queue in order of arrival
deque(['Michael', 'Terry', 'Graham'])

5.1.3. Listförståelse

List Comprehensions ger ett kortfattat sätt att skapa listor. Vanliga tillämpningar är att skapa nya listor där varje element är resultatet av vissa operationer som tillämpas på varje medlem i en annan sekvens eller iterabel, eller att skapa en undersekvens av de element som uppfyller ett visst villkor.

Anta till exempel att vi vill skapa en lista med kvadrater, till exempel:

>>> squares = []
>>> for x in range(10):
...     squares.append(x**2)
...
>>> squares
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

Observera att detta skapar (eller skriver över) en variabel med namnet x som fortfarande existerar efter att slingan har avslutats. Vi kan beräkna listan med kvadrater utan några bieffekter med:

squares = list(map(lambda x: x**2, range(10)))

eller, på motsvarande sätt:

squares = [x**2 for x in range(10)]

som är mer kortfattad och läsbar.

En list comprehension består av parenteser som innehåller ett uttryck följt av en for-klausul, sedan noll eller fler for- eller if-klausuler. Resultatet blir en ny lista som är resultatet av utvärderingen av uttrycket i kontexten av for- och if-klausulerna som följer efter det. Till exempel kombinerar denna listcomp elementen i två listor om de inte är lika:

>>> [(x, y) for x in [1,2,3] for y in [3,1,4] if x != y]
[(1, 3), (1, 4), (2, 3), (2, 1), (2, 4), (3, 1), (3, 4)]

och det är likvärdigt med:

>>> combs = []
>>> for x in [1,2,3]:
...     for y in [3,1,4]:
...         if x != y:
...             combs.append((x, y))
...
>>> combs
[(1, 3), (1, 4), (2, 3), (2, 1), (2, 4), (3, 1), (3, 4)]

Observera att ordningen på for- och if-satserna är densamma i båda dessa utdrag.

Om uttrycket är en tupel (t.ex. (x, y) i föregående exempel) måste det vara inom parentes.

>>> vec = [-4, -2, 0, 2, 4]
>>> # create a new list with the values doubled
>>> [x*2 for x in vec]
[-8, -4, 0, 4, 8]
>>> # filter the list to exclude negative numbers
>>> [x for x in vec if x >= 0]
[0, 2, 4]
>>> # apply a function to all the elements
>>> [abs(x) for x in vec]
[4, 2, 0, 2, 4]
>>> # call a method on each element
>>> freshfruit = ['  banana', '  loganberry ', 'passion fruit  ']
>>> [weapon.strip() for weapon in freshfruit]
['banana', 'loganberry', 'passion fruit']
>>> # create a list of 2-tuples like (number, square)
>>> [(x, x**2) for x in range(6)]
[(0, 0), (1, 1), (2, 4), (3, 9), (4, 16), (5, 25)]
>>> # the tuple must be parenthesized, otherwise an error is raised
>>> [x, x**2 for x in range(6)]
  File "<stdin>", line 1
    [x, x**2 for x in range(6)]
     ^^^^^^^
SyntaxError: did you forget parentheses around the comprehension target?
>>> # flatten a list using a listcomp with two 'for'
>>> vec = [[1,2,3], [4,5,6], [7,8,9]]
>>> [num for elem in vec for num in elem]
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Listförståelser kan innehålla komplexa uttryck och nästlade funktioner:

>>> from math import pi
>>> [str(round(pi, i)) for i in range(1, 6)]
['3.1', '3.14', '3.142', '3.1416', '3.14159']

5.1.4. Förståelse av nästlade listor

Det första uttrycket i en listkomprehension kan vara vilket godtyckligt uttryck som helst, inklusive en annan listkomprehension.

Betrakta följande exempel på en 3x4-matris som implementerats som en lista med 3 listor med längden 4:

>>> matrix = [
...     [1, 2, 3, 4],
...     [5, 6, 7, 8],
...     [9, 10, 11, 12],
... ]

Följande listförståelse kommer att transponera rader och kolumner:

>>> [[row[i] for row in matrix] for i in range(4)]
[[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]

Som vi såg i föregående avsnitt utvärderas den inre listförståelsen i kontexten för det for som följer efter den, så det här exemplet är likvärdigt med:

>>> transposed = []
>>> for i in range(4):
...     transposed.append([row[i] for row in matrix])
...
>>> transposed
[[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]

vilket i sin tur är detsamma som:

>>> transposed = []
>>> for i in range(4):
...     # the following 3 lines implement the nested listcomp
...     transposed_row = []
...     for row in matrix:
...         transposed_row.append(row[i])
...     transposed.append(transposed_row)
...
>>> transposed
[[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]

I den verkliga världen bör du föredra inbyggda funktioner framför komplexa flödesbeskrivningar. Funktionen zip() skulle göra ett bra jobb för detta användningsfall:

>>> list(zip(*matrix))
[(1, 5, 9), (2, 6, 10), (3, 7, 11), (4, 8, 12)]

Se Uppackning av argumentlistor för detaljer om asterisken i den här raden.

5.2. del-satsen

Det finns ett sätt att ta bort ett objekt från en lista genom att ange dess index istället för dess värde: del statement. Detta skiljer sig från metoden pop() som returnerar ett värde. Satsen del kan också användas för att ta bort delar från en lista eller rensa hela listan (vilket vi gjorde tidigare genom att tilldela en tom lista till delen). Till exempel:

>>> a = [-1, 1, 66.25, 333, 333, 1234.5]
>>> del a[0]
>>> a
[1, 66.25, 333, 333, 1234.5]
>>> del a[2:4]
>>> a
[1, 66.25, 1234.5]
>>> del a[:]
>>> a
[]

del kan också användas för att radera hela variabler:

>>> del a

Att referera till namnet a i fortsättningen är ett fel (åtminstone tills ett annat värde tilldelas det). Vi kommer att hitta andra användningsområden för del senare.

5.3. Tupler och sekvenser

Vi såg att listor och strängar har många gemensamma egenskaper, t.ex. indexerings- och skivningsoperationer. De är två exempel på sekvens-datatyper (se Sekvenstyper — list, tuple, range). Eftersom Python är ett språk under utveckling kan andra sekvensdatatyper komma att läggas till. Det finns också en annan standardsekvensdatatyp: tuple.

En tuple består av ett antal värden som separeras med kommatecken, till exempel:

>>> t = 12345, 54321, 'hello!'
>>> t[0]
12345
>>> t
(12345, 54321, 'hello!')
>>> # Tuples may be nested:
>>> u = t, (1, 2, 3, 4, 5)
>>> u
((12345, 54321, 'hello!'), (1, 2, 3, 4, 5))
>>> # Tuples are immutable:
>>> t[0] = 88888
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment
>>> # but they can contain mutable objects:
>>> v = ([1, 2, 3], [3, 2, 1])
>>> v
([1, 2, 3], [3, 2, 1])

Som du ser är tupler alltid inneslutna i parenteser vid utmatning, så att nästlade tupler tolkas korrekt; de kan matas in med eller utan omgivande parenteser, även om parenteser ofta är nödvändiga ändå (om tupeln är en del av ett större uttryck). Det är inte möjligt att tilldela de enskilda objekten i en tupel, men det är möjligt att skapa tuplar som innehåller föränderliga objekt, t.ex. listor.

Även om tupler kan tyckas likna listor används de ofta i olika situationer och för olika syften. Tuples är immutable, och innehåller vanligtvis en heterogen sekvens av element som nås via uppackning (se senare i detta avsnitt) eller indexering (eller till och med via attribut i fallet namedtuples). Listor är mutable, och deras element är vanligtvis homogena och nås genom att iterera över listan.

Ett speciellt problem är konstruktionen av tupler som innehåller 0 eller 1 objekt: syntaxen har några extra finesser för att hantera dessa. Tomma tupler konstrueras med ett tomt par parenteser; en tupel med ett objekt konstrueras genom att följa ett värde med ett kommatecken (det räcker inte att omsluta ett enda värde med parenteser). Fult, men effektivt. Till exempel:

>>> empty = ()
>>> singleton = 'hello',    # <-- note trailing comma
>>> len(empty)
0
>>> len(singleton)
1
>>> singleton
('hello',)

Satsen t = 12345, 54321, 'hello!' är ett exempel på tuple packing: värdena 12345, 54321 och 'hello!' packas ihop till en tuple. Den omvända operationen är också möjlig:

>>> x, y, z = t

Detta kallas, passande nog, sequence unpacking och fungerar för alla sekvenser på höger sida. Sekvensuppackning kräver att det finns lika många variabler på vänster sida om likhetstecknet som det finns element i sekvensen. Observera att multipel tilldelning egentligen bara är en kombination av tupelpackning och sekvensuppackning.

5.4. Uppsättningar

Python innehåller också en datatyp för sets. En set är en oordnad samling utan duplicerade element. Grundläggande användningsområden inkluderar medlemskapstestning och eliminering av dubbla poster. Set-objekt stöder också matematiska operationer som union, intersektion, differens och symmetrisk differens.

Curly braces eller funktionen set() kan användas för att skapa uppsättningar. Observera: för att skapa en tom uppsättning måste du använda set(), inte {}; den senare skapar en tom ordbok, en datastruktur som vi diskuterar i nästa avsnitt.

Här är en kort demonstration:

>>> basket = {'apple', 'orange', 'apple', 'pear', 'orange', 'banana'}
>>> print(basket)                      # show that duplicates have been removed
{'orange', 'banana', 'pear', 'apple'}
>>> 'orange' in basket                 # fast membership testing
True
>>> 'crabgrass' in basket
False

>>> # Demonstrate set operations on unique letters from two words
>>>
>>> a = set('abracadabra')
>>> b = set('alacazam')
>>> a                                  # unique letters in a
{'a', 'r', 'b', 'c', 'd'}
>>> a - b                              # letters in a but not in b
{'r', 'd', 'b'}
>>> a | b                              # letters in a or b or both
{'a', 'c', 'r', 'd', 'b', 'm', 'z', 'l'}
>>> a & b                              # letters in both a and b
{'a', 'c'}
>>> a ^ b                              # letters in a or b but not both
{'r', 'd', 'b', 'm', 'z', 'l'}

På samma sätt som listförståelse, stöds även setförståelse:

>>> a = {x for x in 'abracadabra' if x not in 'abc'}
>>> a
{'r', 'd'}

5.5. Ordböcker

En annan användbar datatyp som är inbyggd i Python är ordboken (se Mappningstyper — dict). Ordböcker finns ibland i andra språk som ”associativa minnen” eller ”associativa matriser”. Till skillnad från sekvenser, som indexeras av ett talområde, indexeras ordböcker av nycklar, som kan vara vilken oföränderlig typ som helst; strängar och tal kan alltid vara nycklar. Tupler kan användas som nycklar om de bara innehåller strängar, tal eller tupler; om en tupel innehåller något föränderligt objekt, antingen direkt eller indirekt, kan den inte användas som nyckel. Du kan inte använda listor som nycklar, eftersom listor kan ändras på plats med hjälp av indextilldelningar, slice-tilldelningar eller metoder som append() och extend().

Det är bäst att tänka på en ordbok som en uppsättning nyckel: värde-par, med kravet att nycklarna är unika (inom en ordbok). Ett par hakparenteser skapar en tom ordbok: {}. Om du placerar en kommaseparerad lista med nyckel:värde-par inom hakparenteserna läggs de första nyckel:värde-paren till i ordboken; det är också så ordböcker skrivs på utdatasidan.

De viktigaste operationerna i en ordbok är att lagra ett värde med en nyckel och att extrahera värdet med hjälp av nyckeln. Det är också möjligt att ta bort ett nyckel:värde-par med del. Om du lagrar med en nyckel som redan används, glöms det gamla värdet som är associerat med den nyckeln bort. Det är ett fel att extrahera ett värde med en icke-existerande nyckel.

Om du utför list(d) på en ordbok returneras en lista över alla nycklar som används i ordboken, i inmatningsordning (om du vill ha den sorterad använder du sorted(d) istället). Om du vill kontrollera om en enskild nyckel finns i ordlistan använder du nyckelordet in.

Här är ett litet exempel med hjälp av en ordbok:

>>> tel = {'jack': 4098, 'sape': 4139}
>>> tel['guido'] = 4127
>>> tel
{'jack': 4098, 'sape': 4139, 'guido': 4127}
>>> tel['jack']
4098
>>> del tel['sape']
>>> tel['irv'] = 4127
>>> tel
{'jack': 4098, 'guido': 4127, 'irv': 4127}
>>> list(tel)
['jack', 'guido', 'irv']
>>> sorted(tel)
['guido', 'irv', 'jack']
>>> 'guido' in tel
True
>>> 'jack' not in tel
False

Konstruktören dict() bygger upp lexikon direkt från sekvenser av nyckel-värde-par:

>>> dict([('sape', 4139), ('guido', 4127), ('jack', 4098)])
{'sape': 4139, 'guido': 4127, 'jack': 4098}

Dessutom kan dict comprehensions användas för att skapa ordböcker från godtyckliga nyckel- och värdeuttryck:

>>> {x: x**2 for x in (2, 4, 6)}
{2: 4, 4: 16, 6: 36}

När nycklarna är enkla strängar är det ibland enklare att ange par med hjälp av nyckelordsargument:

>>> dict(sape=4139, guido=4127, jack=4098)
{'sape': 4139, 'guido': 4127, 'jack': 4098}

5.6. Looping-tekniker

Vid loopning genom lexikon kan nyckeln och motsvarande värde hämtas samtidigt med hjälp av metoden items().

>>> knights = {'gallahad': 'the pure', 'robin': 'the brave'}
>>> for k, v in knights.items():
...     print(k, v)
...
gallahad the pure
robin the brave

Vid loopning genom en sekvens kan positionsindex och motsvarande värde hämtas samtidigt med hjälp av funktionen enumerate().

>>> for i, v in enumerate(['tic', 'tac', 'toe']):
...     print(i, v)
...
0 tic
1 tac
2 toe

För att loopa över två eller flera sekvenser samtidigt kan posterna kopplas ihop med funktionen zip().

>>> questions = ['name', 'quest', 'favorite color']
>>> answers = ['lancelot', 'the holy grail', 'blue']
>>> for q, a in zip(questions, answers):
...     print('What is your {0}?  It is {1}.'.format(q, a))
...
What is your name?  It is lancelot.
What is your quest?  It is the holy grail.
What is your favorite color?  It is blue.

För att loopa över en sekvens i omvänd riktning anger du först sekvensen i framåtriktad riktning och anropar sedan funktionen reversed().

>>> for i in reversed(range(1, 10, 2)):
...     print(i)
...
9
7
5
3
1

För att loopa över en sekvens i sorterad ordning, använd funktionen sorted() som returnerar en ny sorterad lista medan källan lämnas oförändrad.

>>> basket = ['apple', 'orange', 'apple', 'pear', 'orange', 'banana']
>>> for i in sorted(basket):
...     print(i)
...
apple
apple
banana
orange
orange
pear

Genom att använda set() på en sekvens elimineras duplicerade element. Användningen av sorted() i kombination med set() över en sekvens är ett idiomatiskt sätt att loopa över unika element i sekvensen i sorterad ordning.

>>> basket = ['apple', 'orange', 'apple', 'pear', 'orange', 'banana']
>>> for f in sorted(set(basket)):
...     print(f)
...
apple
banana
orange
pear

Det är ibland frestande att ändra i en lista medan man går igenom den, men det är ofta enklare och säkrare att skapa en ny lista istället:

>>> import math
>>> raw_data = [56.2, float('NaN'), 51.7, 55.3, 52.5, float('NaN'), 47.8]
>>> filtered_data = []
>>> for value in raw_data:
...     if not math.isnan(value):
...         filtered_data.append(value)
...
>>> filtered_data
[56.2, 51.7, 55.3, 52.5, 47.8]

5.7. Mer om villkor

De villkor som används i while och if-satser kan innehålla alla operatorer, inte bara jämförelser.

Jämförelseoperatorerna in och not in är medlemskapstester som avgör om ett värde finns i (eller inte finns i) en container. Operatorerna is och is not jämför om två objekt verkligen är samma objekt. Alla jämförelseoperatorer har samma prioritet, som är lägre än för alla numeriska operatorer.

Jämförelser kan kedjas. Till exempel testar a < b == c om a är mindre än b och dessutom om b är lika med c.

Jämförelser kan kombineras med hjälp av de booleska operatorerna and och or, och resultatet av en jämförelse (eller av något annat booleskt uttryck) kan negeras med not. Dessa har lägre prioritet än jämförelseoperatorer; mellan dem har not högst prioritet och or lägst, så att A and not B or C är ekvivalent med (A and (not B)) or C. Som alltid kan parenteser användas för att uttrycka den önskade sammansättningen.

De booleska operatorerna and och or är så kallade kortslutningsoperatorer: deras argument utvärderas från vänster till höger, och utvärderingen avslutas så snart resultatet har bestämts. Om t.ex. A och C är sanna men B är falsk, utvärderar A and B and C inte uttrycket C. När en kortslutningsoperator används som ett allmänt värde och inte som en booleansk operator, är returvärdet det senast utvärderade argumentet.

Det är möjligt att tilldela resultatet av en jämförelse eller ett annat booleskt uttryck till en variabel. Till exempel

>>> string1, string2, string3 = '', 'Trondheim', 'Hammer Dance'
>>> non_null = string1 or string2 or string3
>>> non_null
'Trondheim'

Observera att i Python, till skillnad från C, måste tilldelning inuti uttryck göras explicit med walrus-operatorn :=. Detta undviker en vanlig typ av problem som uppstår i C-program: att skriva = i ett uttryck när == var avsett.

5.8. Jämförelse mellan sekvenser och andra typer

Sekvensobjekt kan typiskt sett jämföras med andra objekt av samma sekvenstyp. Jämförelsen använder lexikografisk ordning: först jämförs de två första objekten, och om de skiljer sig åt avgör detta resultatet av jämförelsen; om de är lika jämförs nästa två objekt, och så vidare tills någon av sekvenserna är uttömd. Om två objekt som ska jämföras själva är sekvenser av samma typ, utförs den lexikografiska jämförelsen rekursivt. Om alla element i två sekvenser jämförs lika, anses sekvenserna vara lika. Om den ena sekvensen är en initial subsekvens av den andra, är den kortare sekvensen den mindre (lesser). Lexikografisk ordning för strängar använder Unicodes kodpunktsnummer för att ordna enskilda tecken. Några exempel på jämförelser mellan sekvenser av samma typ:

(1, 2, 3) < (1, 2, 4)
[1, 2, 3] < [1, 2, 4]
'ABC' < 'C' < 'Pascal' < 'Python'
(1, 2, 3, 4) < (1, 2, 4)
(1, 2) < (1, 2, -1)
(1, 2, 3) == (1.0, 2.0, 3.0)
(1, 2, ('aa', 'ab'))   < (1, 2, ('abc', 'a'), 4)

Observera att det är lagligt att jämföra objekt av olika typer med < eller >, förutsatt att objekten har lämpliga jämförelsemetoder. Till exempel jämförs blandade numeriska typer enligt deras numeriska värde, så 0 är lika med 0,0 osv. Annars kommer tolken, i stället för att tillhandahålla en godtycklig ordning, att ge upphov till ett TypeError-undantag.

Fotnoter