El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Importància de les estructures de dades en la programació

Següent ►
►

A la lliçó anterior vam definir què és una estructura de dades i vam deixar una pregunta oberta: si diverses estructures poden desar les mateixes dades, importa de debò quina triïs? En aquesta lliçó comprovaràs que sí, i no amb teoria, sinó amb el cronòmetre a la mà: veurem com la mateixa operació de TaskFlow —cercar una tasca— pot trigar microsegons o segons segons l'estructura triada. També veurem que la importància va més enllà del rendiment: afecta l'escalabilitat, la llegibilitat del codi i fins i tot la teva carrera professional.

Contingut

  1. Triar estructura és una decisió de disseny, no un detall
  2. Rendiment: l'experiment de la cerca a TaskFlow
  3. Escalabilitat: el que funciona amb 10 no funciona amb un milió
  4. Llegibilitat i mantenibilitat: codi que s'explica sol
  5. Impacte professional: entrevistes tècniques i feina real

Triar estructura és una decisió de disseny, no un detall

Quan un programa va lent o es torna difícil de mantenir, la intuïció del principiant és buscar el problema als algorismes o al llenguatge ("Python és lent"). Però molt sovint el problema és abans: en com s'han organitzat les dades. Una frase cèlebre de Linus Torvalds, creador de Linux, ho resumeix així: els bons programadors es preocupen per les estructures de dades i les seves relacions més que pel codi en si.

La tria d'estructura condiciona quatre aspectes del teu programari:

  • Rendiment: quant triga cada operació.
  • Escalabilitat: si aquest temps continua sent acceptable quan les dades creixen.
  • Llegibilitat: si el codi expressa amb claredat la intenció.
  • Mantenibilitat: si demà es pot canviar sense trencar-ho tot.

Vegem cadascun amb TaskFlow com a banc de proves.

Rendiment: l'experiment de la cerca a TaskFlow

TaskFlow necessita una operació aparentment trivial: donat l'identificador d'una tasca, recuperar-la. És l'operació més freqüent de l'aplicació: cada vegada que l'usuari obre una tasca, l'edita o la marca com a feta, primer cal trobar-la.

Primera aproximació: desem les tasques en una llista i cerquem recorrent-la.

def crear_tasques(n):
    """Genera n tasques d'exemple per a TaskFlow."""
    return [
        {"id": i, "titol": f"Tasca {i}", "estat": "pendent"}
        for i in range(n)
    ]

def cercar_en_llista(tasques, id_cercat):
    """Recorre la llista fins a trobar la tasca (cerca sequencial)."""
    for tasca in tasques:
        if tasca["id"] == id_cercat:
            return tasca
    return None

Expliquem el codi:

  • crear_tasques usa una comprensió de llista per fabricar n diccionaris de tasca, amb ids 0, 1, 2, .... Ens serveix per simular taulers de mides diferents.
  • cercar_en_llista examina les tasques una a una, en ordre, fins a trobar la que té l'id cercat. Si l'id és al final —o no existeix—, les haurà mirades totes.

Segona aproximació: a més de la llista, mantenim un índex: un diccionari que associa cada id amb la seva tasca.

def crear_index(tasques):
    """Construeix un diccionari id -> tasca."""
    return {tasca["id"]: tasca for tasca in tasques}

def cercar_en_index(index, id_cercat):
    """Demana la tasca directament per la seva clau."""
    return index.get(id_cercat)

Aquí crear_index recorre les tasques una única vegada i munta el diccionari; a partir d'aquell moment, index.get(id) retorna la tasca sense recórrer res (com ho aconsegueix el diccionari ho desvelarem al mòdul 5; de moment, tracta-ho com a màgia ben documentada).

Ara mesurem. Python porta el mòdul timeit, pensat justament per cronometrar fragments de codi repetint-los moltes vegades i donant un resultat fiable:

import timeit

tasques = crear_tasques(1_000_000)    # un milio de tasques
index = crear_index(tasques)
pitjor_id = 999_999                   # l'ultima: el pitjor cas per a la llista

t_llista = timeit.timeit(
    lambda: cercar_en_llista(tasques, pitjor_id), number=10
)
t_index = timeit.timeit(
    lambda: cercar_en_index(index, pitjor_id), number=10
)

print(f"Llista: {t_llista:.4f} s en 10 cerques")
print(f"Index:  {t_index:.6f} s en 10 cerques")

Detalls de l'experiment:

  • number=10 indica a timeit que executi la cerca 10 vegades i sumi els temps.
  • Cerquem l'id 999_999 a propòsit: com que és al final, obliga la llista a recórrer-ho tot. (Els guionets baixos d'1_000_000 són només separadors visuals de Python; no canvien el nombre.)
  • La funció lambda embolcalla la crida perquè timeit la pugui executar repetidament.

Resultats típics en un portàtil corrent (els teus variaran en xifres, no en la conclusió):

Nre. de tasques Cerca en llista (pitjor cas) Cerca amb índex Diferència aproximada
10 0,0000005 s 0,00000005 s ~10×
10.000 0,0004 s 0,00000005 s ~8.000×
1.000.000 0,04 s 0,00000005 s ~800.000×

Llegeix la taula amb calma, perquè conté la lliçó sencera:

  • Amb 10 tasques, totes dues solucions són instantànies. Qualsevol estructura serveix.
  • Amb un milió, la llista triga unes 800.000 vegades més que l'índex a cada cerca. I una aplicació real cerca constantment: si TaskFlow atén 100 cerques per segon, la versió amb llista senzillament no pot.
  • L'índex ni s'immuta quan les dades creixen: triga pràcticament el mateix amb 10 que amb un milió.

Encara no necessites vocabulari formal per anomenar aquest fenomen (aquest vocabulari, la notació Big O, és el tema de la lliçó 01-04). La intuïció és suficient: una estructura obliga a mirar-ho tot; l'altra hi va directa.

Escalabilitat: el que funciona amb 10 no funciona amb un milió

L'experiment anterior il·lustra l'error més traïdor del desenvolupament de programari: el codi que funciona perfectament en proves i s'ensorra en producció. És traïdor perquè no hi ha cap avís: no hi ha error de sintaxi, no hi ha excepció, els tests passen. Només que amb dades reals, tot s'arrossega.

graph LR
    A[Desenvolupament: 10 tasques de prova] -->|tot va bé| B[Demo: 500 tasques]
    B -->|tot va bé| C[Producció: 1.000.000 de tasques]
    C -->|l'aplicació s'arrossega| D[Reescriure? Més servidors?]
    D -->|la causa era| E[Una estructura mal triada el primer dia]

Pensar en escalabilitat significa preguntar-se, davant de cada estructura que tries: què passarà amb aquesta operació quan les dades es multipliquin per mil? De vegades la resposta és "res de greu, aquesta col·lecció no creixerà mai" (els tres estats d'una tasca de TaskFlow sempre seran tres), i una estructura simple és la tria correcta. Altres vegades la resposta obliga a canviar el disseny. L'important és fer-se la pregunta a temps: canviar una estructura el primer dia costa minuts; canviar-la amb l'aplicació en producció pot costar setmanes.

Un matís honest: l'estructura indexada tampoc no surt de franc. Construir l'índex porta temps i ocupa memòria addicional (estem desant referències a cada tasca dues vegades!). En el nostre cas compensa amb escreix, perquè es construeix una vegada i es consulta milions de vegades. Aquesta mena de balanç —pagar una mica de memòria o de temps de preparació a canvi d'operacions ràpides— apareixerà una vegada i una altra durant el curs.

Llegibilitat i mantenibilitat: codi que s'explica sol

El rendiment no és l'únic motiu per triar bé. Una estructura adequada fa que el codi digui el que fa. Compara aquestes dues maneres de gestionar els estats que pot tenir una tasca a TaskFlow:

# Opcio A: estats "a ma" amb variables soltes
pendents = ["Dissenyar el logo", "Enviar la factura"]
en_curs = ["Escriure l'informe"]
fetes = []

def moure_a_en_curs(titol):
    if titol in pendents:
        pendents.remove(titol)
        en_curs.append(titol)
# Opcio B: un diccionari d'estat -> tasques
tauler = {
    "pendent": ["Dissenyar el logo", "Enviar la factura"],
    "en curs": ["Escriure l'informe"],
    "feta": [],
}

def moure(titol, origen, desti):
    if titol in tauler[origen]:
        tauler[origen].remove(titol)
        tauler[desti].append(titol)

Totes dues funcionen, però fixa't en les diferències:

  • A l'opció A, afegir un quart estat ("bloquejada", per exemple) implica crear una altra variable i escriure noves funcions de moviment per a cada combinació. A la B, n'hi ha prou d'afegir una clau al diccionari: moure ja serveix per a qualsevol parell d'estats.
  • L'opció B expressa la relació real del domini: "cada estat té la seva llista de tasques". Qui llegeixi el codi entén el model de dades d'un cop d'ull.
  • L'opció A reparteix l'estat del programa entre variables soltes, cosa que multiplica els llocs on hi pot haver inconsistències.

La regla general: quan l'estructura de dades reflecteix l'estructura del problema, el codi se simplifica sol. Molts condicionals enrevessats i funcions duplicades són el símptoma d'una estructura que no encaixa amb el domini.

Impacte professional: entrevistes tècniques i feina real

Convé ser clars sobre això, perquè afecta directament la teva carrera com a desenvolupador júnior:

  • Entrevistes tècniques. Les estructures de dades són el cor dels processos de selecció tècnics a la majoria d'empreses, des de startups fins a les grans tecnològiques. És habitual que et demanin resoldre un problema i justificar quina estructura fas servir i per què; plataformes de pràctica com LeetCode o HackerRank estan organitzades, literalment, per estructura de dades. No es tracta de memoritzar solucions, sinó de demostrar el raonament que estàs aprenent en aquest curs: identificar les relacions i operacions del problema, i triar en conseqüència.
  • Revisions de codi. En equips professionals, comentaris com "això és una cerca lineal dins d'un bucle, fes servir un set" són el pa de cada dia. Entendre'ls —i poder fer-los tu— marca la diferència entre executar tasques i participar en el disseny.
  • Depuració de rendiment. Bona part dels problemes de lentitud en aplicacions reals es resolen sense tocar algorismes sofisticats: només canviant una estructura mal triada, exactament com al nostre experiment de l'índex.
  • Vocabulari comú. Quan un company diu "això és una cua de prioritat" o "modelem-ho com un graf", està comprimint hores d'explicació en una frase. Les estructures de dades són l'idioma compartit de la professió.

I un apunt per a l'era actual: encara que els assistents d'IA generin codi per tu, decidir si aquest codi organitza bé les dades continua sent feina teva. De fet, revisar codi aliè (humà o generat) exigeix més criteri sobre estructures, no menys.

Errors Comuns i Consells

  • "Amb poques dades tant és" convertit en hàbit. És cert que amb 10 elements qualsevol estructura serveix, i no cal sobreoptimitzar. L'error és no deixar anotat el supòsit. Un comentari com # COMPTE: cerca lineal, valida mentre hi hagi poques desenes de tasques és or pur quan l'aplicació creix.
  • Optimitzar sense mesurar. El reflex oposat també és un error: reescriure estructures "perquè segur que va lent" sense haver-ho cronometrat. Acostuma't des d'ara a usar timeit: les intuïcions sobre rendiment fallen moltíssim.
  • Mesurar malament. Compte en cronometrar: executa les operacions moltes vegades (number=...), no mesuris una sola execució (el sistema operatiu hi fica soroll), i no incloguis en la mesura el cost de preparar les dades.
  • Confondre "estructura més ràpida" amb "estructura millor". L'índex del nostre experiment gasta memòria extra i cal mantenir-lo actualitzat quan s'afegeixen o s'esborren tasques. Gairebé tota tria d'estructura és un balanç; la teva feina és conèixer els termes de l'intercanvi.

Exercicis

Exercici 1: reproduir l'experiment

Copia les funcions crear_tasques, cercar_en_llista, crear_index i cercar_en_index d'aquesta lliçó i mesura amb timeit la cerca del pitjor cas per a mides 100, 10.000 i 1.000.000. Construeix la teva pròpia taula de resultats. A partir de quina mida comença a ser perceptible la diferència a la teva màquina?

Exercici 2: detectar el punt feble

Aquest codi comprova quins usuaris d'una llista de convidats ja estan registrats a TaskFlow:

def convidats_registrats(convidats, usuaris_registrats):
    resultat = []
    for convidat in convidats:
        if convidat in usuaris_registrats:   # usuaris_registrats es una llista
            resultat.append(convidat)
    return resultat

Sabent que convidat in usuaris_registrats sobre una llista recorre la llista sencera en el pitjor cas: (a) explica amb les teves paraules per què aquest codi escalarà malament si totes dues col·leccions creixen; (b) proposa una millora usant set (els conjunts de Python responen a la pregunta "hi és, aquest element?" gairebé a l'instant, com el diccionari de l'experiment); (c) comprova-la amb timeit per a 10.000 convidats i 10.000 registrats.

Exercici 3: argumentar com en una revisió de codi

Un company proposa desar l'historial d'accions de TaskFlow (per poder desfer) en un diccionari {numero_accio: accio} i portar a part un comptador. Escriu, en 3-5 frases i sense codi, què li preguntaries sobre les operacions que necessita l'historial i quins riscos de mantenibilitat veus a portar el comptador separat de les dades. (No cal que proposis l'estructura ideal: això arribarà al mòdul 3.)

Solucions

Solució 1:

Un programa de mesura complet:

import timeit

for n in (100, 10_000, 1_000_000):
    tasques = crear_tasques(n)
    index = crear_index(tasques)
    pitjor = n - 1
    t_llista = timeit.timeit(lambda: cercar_en_llista(tasques, pitjor), number=10)
    t_dict = timeit.timeit(lambda: cercar_en_index(index, pitjor), number=10)
    print(f"n={n:>9}: llista {t_llista:.6f} s | index {t_dict:.6f} s")

Resultats orientatius: amb n=100 totes dues estan per sota del mil·lisegon (diferència imperceptible); amb n=10_000 la llista ja triga de l'ordre de mil·lisegons; amb n=1_000_000 la diferència és de diversos ordres de magnitud. La xifra exacta depèn de la teva màquina; la tendència no.

Solució 2:

(a) Per cada convidat es recorre potencialment tota la llista de registrats: si hi ha 10.000 convidats i 10.000 registrats, es fan fins a 100 milions de comparacions. En duplicar totes dues col·leccions, la feina es multiplica per quatre, no per dos: el creixement es dispara.

(b) N'hi ha prou de convertir els registrats a conjunt una sola vegada:

def convidats_registrats_v2(convidats, usuaris_registrats):
    registrats = set(usuaris_registrats)   # conversio unica
    return [conv for conv in convidats if conv in registrats]

conv in registrats sobre un set no recorre res: respon gairebé a l'instant (el perquè, al mòdul 5).

(c) Mesura:

import timeit
convidats = [f"user{i}" for i in range(10_000)]
registrats = [f"user{i}" for i in range(5_000, 15_000)]

t1 = timeit.timeit(lambda: convidats_registrats(convidats, registrats), number=3)
t2 = timeit.timeit(lambda: convidats_registrats_v2(convidats, registrats), number=3)
print(t1, t2)   # tipic: ~2-4 s davant de ~0,003 s

Solució 3:

Una bona resposta hauria d'incloure preguntes com: quines operacions farà l'historial (afegir l'última acció, recuperar l'última, potser les N últimes)? Necessitem accedir a accions antigues per número, o només a la més recent? Riscos del comptador separat: és estat duplicat, de manera que si el diccionari i el comptador es dessincronitzen (per un esborrat, un error o un oblit), l'historial queda corromput sense avisar; a més, qui llegeixi el codi ha de descobrir pel seu compte que tots dos van junts. La conclusió raonable: el patró d'ús "l'últim que entra és el primer que surt" demana una estructura que ho garanteixi per contracte, que és just el que veurem al mòdul 3.

Conclusió

En aquesta lliçó has vist, amb mesures reals, que la tria d'estructura de dades importa: la cerca de tasques a TaskFlow va passar de trigar dècimes de segon a ser instantània en canviar una llista per un índex, i la diferència creix brutalment amb la mida de les dades. També has vist que la importància no és només de rendiment: una estructura que reflecteix el domini fa el codi més llegible i mantenible, i dominar aquest raonament és del més valorat en entrevistes tècniques i en la feina diària.

Ara bé: per triar estructura cal conèixer el catàleg. Quines famílies d'estructures existeixen i per a què serveix cadascuna? Aquest panorama —lineals i no lineals, estàtiques i dinàmiques, i el mapa complet del que veurem al curs— és el tema de la propera lliçó.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2026. Tots els drets reservats