Estructures de dades de Python

Aquesta lliçó pretén donar una breu descripció de les estructures de dades més habituals que es poden utilitzar en Python3. La lliçó va dirigida principalment als estudiants que ja saben una mica de Python i que ja coneixen l’ús d’estructures de dades estàndards de C++ com ara stacks, maps, sets…

Les estructures de dades que s’estudien en aquesta lliçó són:

Existeixen moltes altres estructures de dades en Python, i les descrites aquí tenen encara més operacions que les esmentades. Per una explicació amb més profunditat, consulteu la documentació oficial.

Tipus bàsics

Recordem que els tipus bàsics més habituals de Python són:

Conversions

En Python es poden convertir explícitament diferents tipus utilitzant el nom del tipus com si fós una funció. Per exemple, per convertir a enter:

>>> int(6.66)
6
>>> int(9.99)
9
>>> int("23")
23
>>> int("dotze")
ValueError: invalid literal for int() with base 10: 'dotze'

O per convertir a real:

>>> float(12)
12.0
>>> float("12")
12.0
>>> float("12.24")
12.24
>>> float("dotze")
ValueError: could not convert string to float: 'dotze'

La majoria dels valors es poden convertir a text utilitzant la funció str:

>>> str(33)
'33'
>>> str(3.1416)
'3.1416'
>>> str(False)
'False'
>>> str([1, "un", []])
"[1, 'un', []]"

La crida a print() sol passar per str (o una cosa semblant anomenada __repr__).

Textos

Els textos (strings) en Python són de tipus str i consisteixen en seqüències de caràcters en Unicode (un estàndard internacional de codificació de caràcters). Els valors dels textos són immutables: un cop creats no es poden modificar. Però s’en poden crear de nous a partir d’ells.

Nota: No existeix el tipus caràcter en Python.

Representació

Els textos s’escriuen entre cometes simples o cometes dobles:

El fet de poder triar entre cometes dobles o simples és útil quan cal incloure un tipus de cometes en el text:

Per a combinacions més exòtiques es poden usar seqüències d’escapament:

També es poden utilitzar textos multilínia utilitzant tres cometes:

html = """
    <html>
        <head>
            <title>El títol de la meva pàgina web</</title>
        </head>
        <body>
            <h1>Introducció</h1>
            <p>
                Bla bla
            </p>
        </body>
    </html>
"""

Llargada

La funció len retorna el nombre de caràcters en un text:

>>> len("Sant Esteve de les Roures")
15
>>> len("ñ")
1
>>> len("🍏🍊")
2
>>> len("")
0

Fixeu-vos que len retorna el nombre de caràcters del text, no el nombre de bytes que utilitza: En Unicode els caràcters poden estar codificats en un nombre variable de bytes. A més, la seva amplada a la pantalla també és variable.

Operadors

Aquests són els operadors que es poden aplicar als textos:

Per exemple:

>>> "Carles" + " " + "Puigdemont"
'Carles Puigdemont'
>>> "a" * 5
'aaaaa'
>>> "cap" in "En cap cap cap el que cap en aquest cap"
True
>>> "a" not in "xyz"
True
>>> "joan" < "jordi"
True

Recorregut

Per iterar sobre tots els caràcters d’un text s’utilitza un bucle for:

def nombre_de_as(text):
    n = 0
    for c in text:
        if c == "A":
            n += 1
    return n

Subtextos

Es pot crear un subtext a partir d’un text utilitzant els operadors d’indexació [], tenint en compte que els índexos represeten les posicions dels caràcters dins del text, començant des de zero.

Per extreure un caràcter en una determinada posició, es passa com a paràmetre la posició desitjada:

>>> "Barça"[0]
'B'
>>> "Barça"[3]
'ç'
>>> "Barça"[5]
IndexError: string index out of range

Si la posició és negativa, es comença a comptar des del final:

>>> "Barça"[-1]
'a'
>>> "Barça"[-2]
'ç'
>>> "Barça"[-6]
IndexError: string index out of range

Per extreure el subtext entre dues posicions, s’utilitza la sintàxi t[inici:final] on inici és la primera posició i final és la darrera posició (que no s’inclourà). Fixeu-vos que, com és habitual en Python, els finals mai s’inclouen. Aquí en teniu alguns exemples:

>>> "Barça"[0:3]
'Bar'
>>> "Barça"[1:3]
'ar'
>>> "Barça"[2:3]
'r'
>>> "Barça"[3:3]
''

Si el primer element no es dóna, vol dir “des de l’inici”. Si el darrer element no es dóna, vol dir “fins al final”:

>>> "Barça"[:3]
'Bar'
>>> "Barça"[3:]
'ça'

També es pot especificar un pas amb la sintàxi t[inici:final:pas]:

>>> "Barça"[0:5:2]
'Bra'
>>> "Barça"[::-1]
'açraB'

Com ja s’ha dit, els textos són immutables i no es poden modificar els seus caràcters:

>>> "Barça"[3] = "c"
TypeError: 'str' object does not support item assignment

Per tant, per transformar "Barça" en "Barca", cal fer alguna cosa com ara:

>>> t = "Barça"
>>> t[0:3] + "c" + t[4:]
'Barca'

Mètodes

Els textos són objectes que disposen de molt mètodes. Per exemple, els mètodes upper() i lower() permeten obtenir el text original convertit a minúsucules i a majúscules respectivament. Els mètodes isupper() i islower indiquen si tots els caràcters del text són minúsucules o majúscules respectivament.

>>> nom = "Quim Monzó"
>>> nom.upper()
'QUIM MONZÓ'
>>> nom.lower()
'quim monzó'
>>> nom.islower()
False
>>> nom.upper().isupper()
True

Els mètodes lstrip(), rstrip() i strip() són útils per menjar-se els blancs d’un text (per l’esquerra, per la dreta i per ambdós, respectivament):

>>> "  no és no ".lstrip()
'no és no '
>>> "  no és no ".rstrip()
'  no és no'
>>> "  no és no ".strip()
'no és no'

El mètode find() permet trobar on comença un subtext en un text:

>>> "En cap cap cap el que cap en aquest cap".find("cap")
3
>>> "En cap cap cap el que cap en aquest cap".find("rap")
-1

El mètode count() permet comptar el nombre d’ocurrències d’un subtext en un text:

>>> "En cap cap cap el que cap en aquest cap".count("cap")
5

El mètode split() permet trencar un text en una llista de textos utilitzant un separador (espais per defecte):

>>> "888-564-787-1152".split("-")
['888', '564', '787', '1152']
>>> "és un elefant, que en bicicleta va".split()
['és', 'un', 'elefant,', 'que', 'en', 'bicicleta', 'va']

La taula següent llista alguns dels mètodes més útils dels textos. Consulteu la documentació de Python per més informació.

Mètode Descripció
capitalize() Converts first character to Capital Letter
count() returns occurrences of substring in string
endswith() Checks if String Ends with the Specified Suffix
expandtabs() Replaces Tab character With Spaces
find() Returns the Highest Index of Substring
format() formats string into nicer output
index() Returns Index of Substring
isalnum() Checks Alphanumeric Character
isalpha() Checks if All Characters are Alphabets
isdecimal() Checks Decimal Characters
isdigit() Checks Digit Characters
isidentifier() Checks for Valid Identifier
islower() Checks if all Alphabets in a String are Lowercase
isnumeric() Checks Numeric Characters
isprintable() Checks Printable Character
isspace() Checks Whitespace Characters
istitle() Checks for Titlecased String
isupper() returns if all characters are uppercase characters
join() Returns a Concatenated String
lower() returns lowercased string
upper() returns uppercased string
lstrip() Removes Leading Characters
rstrip() Removes Trailing Characters
strip() Removes Both Leading and Trailing Characters
replace() Replaces Substring Inside
split() Splits String from Left
startswith() Checks if String Starts with the Specified String
splitlines() Splits String at Line Boundaries

Substitucions i format

El mètode format() permet realitzar substitucions i format de variables dins d’un text. Consulteu la documentació sobre format de Python per a molta més informació sobre les opcions de format (incloent les noves fstrings de Python ≥3.6).

Aquests senzills exemples mostren com aplicar substitucions en un text:

"Peso {} kilos.".format(85)
'Peso 85 kilos.'
"Peso {} kilos i tinc {} anys.".format(85, 19)
'Peso 85 kilos i tinc 19 anys.'

En el cas que es vulgui formatar un real, es poden especificar opcions addicionals:

>>> "{}".format(3.65)
'3.65'
>>>
>>> "{:.10f}".format(3.65)      # Posa 10 dígits darrera el punt decimal
'3.6500000000'
"{:7.3f}".format(3.65)          # Utilitza 7 caràcters, posant-ne 3 darrera el punt decimal
'  3.650'

Tuples

Les tuples permeten agregar diferents valors en un únic valor. Per exemple la tupla (2.5, 5.6) pot representar un punt en l’espai a través de les seves dues coordenades reals.

Una tupla s’escriu posants els seus diferents camps entre parèntesis, separats per comes:

En el cas de voler fer una tupla amb un sol volor (ja són ganes! 😱), cal posar-hi una coma al final:

Es pot utilitzar l’operador d’indexació [] per accedir a un determinat camp d’una tupla, sabent que el primer és a la posició 0 i que no es pot anar més enllà de la darrera posició:

>>> (2.5, 5.6)[0]
2.5
>>> (2.5, 5.6)[1]
5.6
>>> (2.5, 5.6)[2]
IndexError: tuple index out of range

La funció len dóna el nombre de camps en una tupla:

>>> len((2.5, 5.6))
2
>>> len(("Bi", "Ba", "Butzemann"))
3
>>> len((66,))
1

Es poden recórrer tots els camps d’una tupla utilitzant un bucle for:

Les tuples són immutables: un cop creades no es poden modificar:

>>> t = (1,2)
>>> t[0]
1
>>> t[0] = 55
TypeError: 'tuple' object does not support item assignment

Tuples amb noms

El mòdul estàndard collections conté una funció namedtuple que permet definir noves tuples on els camps tenen identificadors enlloc de posicions. Això resulta molt útil perquè de seguida es perd de vista què era t[3].

El següent fragment de codi defineix un nou tipus Point com una tupla amb dos camps anomenats x i y:

from collections import namedtuple

Point = namedtuple('Point', ['x', 'y'])

Un cop definit el tipus Point, es poden crear diferents valors de variables que representen punts:

p1 = Point(4, 5)
p2 = Point(x=3, y=9)
p3 = Point(y=2, x=1.1)

La manera d’accedir ara a un camp és a través de l’operador punt:

>>> p1.x
4
>>> p2.x + p2.y
12
>>> p3.x
1.1

Les tuples amb noms continuen sent immutables.

Llistes

En Python, les llistes són probablament l’estructura de dades més usada. Però el nom ‘llista’ és probablament enganyós, ja que des del punt de vista de les seves operacions (i el seu temps d’execució) es tracta més aviat de vectors (o arrays).

Una llista permet emmagatzemar seqüencialment un nombre variable de dades (de qualssevol tipus).

Representació

Les llistes s’ecriuen posant els seus diferents camps entre claudàtors, separats per comes:

Les llistes també poden contenir altres llistes, fet que permet descriure matrius i arbres fàcilment:

Llargada

La funció len dóna el nombre d’elements d’una llista:

>>> len(["Bi", "Ba", "Butzemann"])
3
>>> len([66])
1
>>> len([])
0
>>> len([1, [2, None, None], [3, None, None]])
3

Accés

Es pot utilitzar l’operador d’indexació [] per accedir a un determinat camp d’una llista, sabent que el primer és a la posició 0 i que no es pot anar més enllà de la darrera posició:

>>> [2.5, 5.6][0]
2.5
>>> [2.5, 5.6][1]
5.6
>>> [2.5, 5.6][2]
IndexError: list index out of range

Amb la matriu m definida anteriorment es pot utilitzar doble la indexació m[i][j] per arribar a l’element de la i-èsima fila i j-èsima columna.

Es poden seleccionar subllistes d’una llista amb la mateixa sintàxi que per a textos:

>>> L = [66, 33, 22, 11, 88, 99, 44]
>>> L[2:]
[22, 11, 88, 99, 44]
>>> L[:2]
[66, 33]
>>> L[2:5]
[22, 11, 88]
>>> L[::2]
[66, 22, 88, 44]
>>> L[::-1]
[44, 99, 88, 11, 22, 33, 66]

Operacions habituals

Aquestes són algunes operacions senzilles ben habituals sobre les llistes:

Modificació

Al contrari de les tuples, les llistes són mutables. Observeu:

>>> L = [1, 2, 3, 4]
>>> L[2] = 99
>>> L
[1, 2, 99, 4]

Es pot afegir un element al final d’una llista aplicant el mètode append: Per exemple,

>>> L = [1, 2, 3, 4]
>>> L.append(5)
>>> L
[1, 2, 3, 4, 5]

Es pot afegir una llista al final d’una altra llista aplicant el mètode extend:

>>> L1 = [1, 2, 3, 4]
>>> L2 = [5, 6, 7]
>>> L1.extend(L2)
>>> L1
[1, 2, 3, 4, 5, 6, 7]

És millor extendre les llistes amb append i extend que no amb +, ja que + crea una nova llista.

També es poden esborrar elements d’una llista a través de la seva posició amb la funció del: Per exemple,

>>> L = [1, 2, 3, 4]
>>> del(L[2])
>>> L
[1, 2, 4]

Per esborrar el darrer element d’una llista es pot utilitzar el mètode pop: Per exemple,

>>> L = [1, 2, 3, 4]
>>> L.pop()
>>> L
[1, 2, 3]

Per esborrar un element en particular d’una llista es pot utilitzar el mètode remove:

>>> L = [1, 2, 3, 2, 4]
>>> L.remove(2)
>>> L
[1, 3, 2, 4]

(Fixeu-vos que només ha esborrat el primer).

No modifiqueu una llista mentre l’esteu iterant!

La funció range

La funció range() és útil per definir subseqüències d’enters:

En realitat, en Python3, range() no retorna una llista de debò, sinó un objecte iterable. Si us cal, apliqueu list() sobre el range per obtenir la llista en sí:

>>> range(10)
range(0, 10)
>>> list(range(10))
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Llistes per comprehensió

Les llistes per comprehensió proporcionen una manera concisa de crear llistes tot utilitzant una sintàxi semblant a la de la definició de conjunts en matemàtiques:

>>> [x**2 for x in range(10)]
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
>>> [x**2 for x in range(10) if x**2 % 3 == 1]
[1, 4, 16, 25, 49, 64]

També podem tenir combinacions de generadors per definir tuples:

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

Referències

Les llistes de Python contenen referències als seus elements i no pas còpies dels elements en sí. Això pot crear alguns comportaments curiosos:

>>> A = [1, 2]
>>> B = [A, A]
>>> B
[[1, 2], [1, 2]]
>>> A[0] = 9
>>> B
[[9, 2], [9, 2]]

Piles

Utilitzant les operacions append, pop i [-1] sobre llistes de Python ja s’obté una pila d’estar per casa.

Cues

Les llistes també es podrien utilitzar per definir cues, però aquestes tindrien costos ineficients. És millor usar el tipus deque del mòdul estàndard collections, que ofereix accés eficient per entrada, consulta i sortida als dos extrems d’una seqüencia.

Aquest n’és un exemple copiat de la documentació de Python:

>>> 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'])

Conjunts

Un conjunt és una estructura de dades que enmagatzema elements, sense ordre ni repeticions.

Representació

Els elements d’un conjunt es poden escriure entre claus, separant els diferents elements per comes.

Per exemple, aquest és el conjunt dels 10 primers nombres primers:

s = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}

Cal remarcar, però, que el conjunt buit s’ha d’escriure amb set() perquè {} representa el diccionari buit.

Operacions habituals

Aquí en podeu veure alguns exemples:

>>> s1 = {1,2,3,4}
>>> s2 = {3,4,5,6}
>>> len(s1)
4
>>> 2 in s1
True
>>> 2 in s2
False
>>> s1 - s2
{1, 2}
>>> s2 - s1
{5, 6}
>>> s1 | s2
{1, 2, 3, 4, 5, 6}
>>> s1 & s2
{3, 4}

Recorregut

Per iterar sobre tots els elements d’un diccionari s’utilitza (com si no?) un bucle for:

>>> for x in {1, 5, 2, 4}: print(x)
5
1
2
4

L’ordre en el qual es recorren els elements d’un conjunt no està determinat (però és sempre el mateix fins que es modifica). No afegiu o elimineu elements a un conjunt mentre l’esteu iterant!

Conjunts per comprehensió

Igual que amb les llistes, es poden definir conjunts per comprehensió. En aquest exemple es genera el conjunt dels primers fins a 100:

>>> {x for x in range(2, 101) if all(x%y for y in range(2, min(x, 11)))}
{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}

Diccionaris

Un diccionari és una estructura de dades que enmagatzema parells d’elements, on cada element té una clau i una informació. En un diccionari, no poden haver-hi dues claus iguals.

Les informacions dels diccionaris poden ser de tipus qualssevol, però les claus han de ser de tipus immutables.

Representació

Els elements d’un diccionari es poden escriure entre claus, separant els diferents elements per comes i, per a cada element, cal donar la seva clau i la seva informació separades per dos punts.

Per exemple, a continuació, el diccionari d1 representa un petit traductor d’anglès a català, el diccionari d2 representa els preus de diferents productes i d3 és un diccionari buit:

d1 = {"hola": "hello", "adéu": "bye", "gos": "dog", "gat": "cat"}
d2 = {"menú": 11.99, "aigua": 1.50, "cafè": 1.0}
d3 = {}

Accés

Donada una clau, es pot accedir eficientment a la seva informació associada utilitzant l’operador d’indexació []:

>>> d1["hola"]
'hello'
>>> d2["cafè"]
1.0
>>> d3[55]
KeyError: 55

També es pot utilitzar el mètode get, al qual se li pot donar un valor per defecte que es retorna quan la clau no és present al diccionari:

>>> d3[55]
KeyError: 55
>>> d3.get(55, "No hi és")
"No hi és"

Fixeu-vos que és un error consultar la informació d’una clau no present en un diccionari.

Modificació

L’operador d’indexació [] també permet modificar la informació associada a una clau ja present o afegir una nova clau amb la seva informació associada:

>>> d = {1: 2, 2: 4, 3: 6}
>>> d[2] = 44
>>> d
{1: 2, 2: 44, 3: 6}
>>> d[5] = 10
>>> d
{1: 2, 2: 44, 3: 6, 5: 10}

Amb del es pot esborrar una clau, juntament amb la seva informació:

>>> d = {1: 2, 2: 4, 3: 6}
>>> del d[2]
>>> d
{1: 2, 3: 6}

Recorreguts

Per iterar sobre totes les claus d’un diccionari s’utilitza un bucle for:

>>> for k in {1:2, 2:3}: print(k, d[k])
1 2
2 3

Per evitar tornar a cercar cada clau al diccionari, es pot iterar directament sobre parells de claus i valors sobre els items d’un diccionari:

>>> for k, v in d.items(): print(k, v)
1 2
2 3

L’ordre en el qual es recorren les claus d’un diccionari no està determinat (però és sempre el mateix fins que es modifica). No afegiu o elimineu claus d’un diccionari mentre l’esteu iterant!

Diccionaris per comprehensió

Igual que amb les llistes, es poden definir diccionaris per comprehensió:

>>> {x: 2*x for x in range(10)}
{0: 0, 1: 2, 2: 4, 3: 6, 4: 8, 5: 10, 6: 12, 7: 14, 8: 16, 9: 18}

Altres operacions

Aquestes són algunes operacions senzilles ben habituals sobre les diccionaris:


Fòrum







Lliçons.jutge.org
Jordi Petit
Universitat Politècnica de Catalunya, 2018

Prohibit copiar. Tots els drets reservats.
No copy allowed. All rights reserved.