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

Com Triar l'Estructura de Dades Adequada

Següent ►
►

Al final del mòdul anterior vam donar el curs per complet pel que fa a estructures: TaskFlow ja té tauler (arrays i llistes), desfer (piles), notificacions (cues i monticles), índexs (taules hash), jerarquies (arbres) i dependències (grafs). Ara toca el pas que separa qui "coneix estructures" de qui "dissenya amb estructures": aprendre a triar. En aquesta lliçó construirem un mètode de decisió en forma de preguntes, reunirem tota la matèria en una gran taula comparativa i raonarem en veu alta diversos casos pràctics d'estil entrevista. L'estructura perfecta no existeix; existeix l'estructura adequada per a les teves operacions dominants.

Contingut

  1. El mètode: triar per operacions, no per dades
  2. Les set preguntes clau
  3. Arbre de decisió
  4. La gran taula del curs
  5. Casos pràctics resolts
  6. Errors de tria típics i els seus símptomes
  7. Combinar estructures: el patró que fa servir TaskFlow

El mètode: triar per operacions, no per dades

L'error més habitual del desenvolupador júnior és preguntar-se "quina estructura escau a aquestes dades?". La pregunta correcta és una altra:

Quines operacions faré amb més freqüència, i quin cost em puc permetre en cadascuna?

Les mateixes dades (les tasques de TaskFlow, que són dict amb id, titol, prioritat, estat...) han viscut durant el curs dins de llistes, piles, cues, monticles, taules hash, arbres i grafs. La dada no va canviar; va canviar l'operació dominant:

  • Per cercar per id: taula hash (dict), O(1) de mitjana.
  • Per desfer l'última acció: pila, O(1) a l'extrem.
  • Per atendre la més prioritària: monticle, O(log n).
  • Per demanar "prioritat entre 1 i 3": ABC/AVL, O(log n + k).
  • Per ordenar per dependències: graf + ordre topològic, O(V + E).

El procediment, sempre el mateix:

  1. Llista les operacions del problema (inserir, cercar, esborrar, recórrer, mínim, interval...).
  2. Estima la freqüència de cadascuna (milions de cerques i poques insercions, o a l'inrevés?).
  3. Consulta els costos (la gran taula de més avall) i tria l'estructura que abarateix les operacions freqüents, acceptant encarir les rares.
  4. Si dubtes entre dues, mesura amb timeit (mòdul 1): les dades reals manen.

Les set preguntes clau

Fes-te aquestes preguntes en ordre. La primera que responguis amb un "sí" rotund sol assenyalar l'estructura.

# Pregunta Si la resposta és sí... Exemple a TaskFlow
1 Accedeixo per clau exacta (id, nom, email)? Taula hash: dict / set tasques_per_id[42]
2 Necessito mantenir un ordre total i fer consultes per interval ("entre X i Y", "el següent a...")? ABC/AVL (o bisect sobre llista ordenada estable) "tasques amb prioritat entre 1 i 3"
3 Només treballo pels extrems? LIFO o FIFO? LIFO → pila; FIFO → cua; tots dos extrems → deque desfer (LIFO), notificacions (FIFO)
4 Només m'interessa el més prioritari en cada moment, no l'ordre complet? Monticle (heapq) SafataUrgencies
5 Les dades tenen jerarquia (pare-fills, contenció)? Arbre general projectes → tasques → subtasques
6 Hi ha relacions molts-a-molts (dependències, xarxes, camins)? Graf DAG de dependències entre tasques
7 Res de tot això: només seqüència amb accés per posició o recorreguts complets? list (array dinàmic); llista enllaçada si hi ha moltes insercions/esborrats al mig amb referència al node el tauler, llistats en pantalla

Dos matisos importants:

  • Les preguntes no són excloents: un problema real sol respondre "sí" a diverses. Aquí entra la secció de combinar estructures.
  • La pregunta 2 i la 1 es confonen sovint. El hash respon "existeix la clau 42?" en O(1), però no pot respondre "quines claus hi ha entre 1 i 3?" sense recórrer-ho tot — va ser el límit del hash que vam veure al final del mòdul 5, i la porta per on van entrar els arbres.

Arbre de decisió

El mateix mètode, en forma de diagrama. Llegeix-lo de dalt a baix i atura't a la primera fulla que encaixi:

flowchart TD
    A[Quina operació domina?] --> B{Cercar per<br/>clau exacta?}
    B -- Sí --> B1{Necessito també<br/>intervals o ordre?}
    B1 -- No --> H[Taula hash: dict / set<br/>O 1 de mitjana]
    B1 -- Sí --> T[ABC / AVL<br/>O log n]
    B -- No --> C{Treballo només<br/>pels extrems?}
    C -- LIFO --> P[Pila<br/>O 1]
    C -- FIFO --> Q[Cua / deque<br/>O 1]
    C -- Tots dos extrems --> D[deque<br/>O 1 a tots dos]
    C -- No --> E{Només el més<br/>prioritari?}
    E -- Sí --> M[Monticle heapq<br/>O log n]
    E -- No --> F{Jerarquia<br/>pare-fills?}
    F -- Sí --> AR[Arbre general<br/>recorreguts O n]
    F -- No --> G{Relacions<br/>molts a molts?}
    G -- Sí --> GR[Graf<br/>BFS/DFS O V+E]
    G -- No --> L{Moltes insercions<br/>al mig amb node<br/>a la mà?}
    L -- Sí --> LE[Llista enllaçada<br/>O 1 amb referència]
    L -- No --> LI[list de Python<br/>accés O 1 per índex]

Aquest arbre és una brúixola, no una llei: quan el volum de dades és petit (desenes d'elements), gairebé qualsevol estructura serveix i guanya la més simple, que gairebé sempre és list o dict.

La gran taula del curs

Totes les estructures que hem construït o fet servir, amb les seves operacions clau, quan brillen i quan són una trampa.

Estructura Operacions clau (Big O) Quan fer-la servir Quan NO Exemple a TaskFlow
Array / list accés per índex O(1); append/pop final O(1) amortitzat; insert/pop(0) O(n); cerca O(n) Seqüències amb accés per posició, recorreguts, mida moderada Moltes insercions/esborrats al principi o al mig; cerques freqüents per valor Llistat de tasques en pantalla
Llista enllaçada simple inserir/esborrar al cap O(1); accés per posició O(n) Insercions/esborrats freqüents al cap; construir-hi piles i cues al damunt Necessites accés per índex o recorregut enrere Primer tauler (LlistaEnllacada, mòdul 2)
Llista doblement enllaçada inserir/esborrar amb referència al node O(1); navegar en tots dos sentits O(1) per pas Navegació endavant/enrere; esborrar un node que ja tens localitzat Quan list o deque cobreixen el cas amb menys codi HistorialTasques navegable
Llista circular avançar "al següent" indefinidament O(1) Torns rotatoris, round-robin Gairebé qualsevol altre cas RepartidorTasques
Pila push/pop/peek O(1) L'últim que entra és el primer que importa: desfer, backtracking, parsing Necessites accés al fons o a posicions intermèdies GestorDesferRefer (dues piles)
Cua encuar/desencuar O(1) Ordre d'arribada just: torns, missatgeria, BFS L'ordre d'atenció no és el d'arribada (→ prioritat) CuaNotificacions
Cua circular (ring buffer) encuar/desencuar O(1), memòria fixa Buffers de mida acotada: els últims N esdeveniments La mida no està acotada RegistreEsdeveniments
Cua de prioritat / monticle inserir O(log n); extreure mínim O(log n); veure mínim O(1) "Dona'm sempre el més urgent"; top-k; planificadors Necessites cercar elements arbitraris o recórrer en ordre complet sovint SafataUrgencies amb heapq
deque append/pop a tots dos extrems O(1); accés al mig O(n) Cues, historials amb límit (maxlen), finestres lliscants Accés per índex al mig freqüent HistorialAmbLimit, FinestraProductivitat
Taula hash / dict / set inserir/cercar/esborrar O(1) de mitjana; sense ordre ni intervals Accés per clau exacta, comptar, agrupar, memoitzar, deduplicar Intervals, ordre, "el següent més gran que..."; claus no hashables tasques_per_id, índex etiqueta→ids
ABC (sense equilibrar) inserir/cercar O(log n) de mitjana, O(n) en el pitjor cas (degenerat); interval O(log n + k) Prototips, dades d'arribada aleatòria Dades que arriben ordenades (degenera en llista) Primera versió de cerca per interval
AVL inserir/cercar/esborrar O(log n) garantit; recorregut inordre O(n) ordenat Ordre + intervals + rendiment predictible Només cerques per clau exacta (el hash és més simple i ràpid) "Prioritat entre 1 i 3" en producció
Arbre B / B+ cerca/interval O(log n) amb nodes amples, optimitzat per a disc Índexs en disc, bases de dades Estructures en memòria (AVL/hash ja fan el fet) L'índex SQLite on TaskFlow persistiria
Graf BFS/DFS O(V+E); Dijkstra O((V+E) log V); ordre topològic O(V+E) Dependències, xarxes, camins, abastabilitat Les dades són una simple seqüència o jerarquia estricta DAG de dependències, planificador

Consell de lectura: no memoritzis la taula; memoritza les files que et sorprenen. Que insert(0) en una list és O(n) i que un dict no sap respondre intervals són les dues dades d'aquesta taula que més errors eviten al món real.

Casos pràctics resolts

Raonem quatre escenaris tal com es plantejarien en una entrevista tècnica. Fixa't que el raonament sempre segueix el mètode: operacions → freqüències → costos.

Cas 1: "Dissenya la funció d'autocompletar"

En escriure "reun" al cercador de TaskFlow han d'aparèixer els títols que comencen per aquest prefix.

  • Operació dominant: cerca per prefix, no per clau exacta. La pregunta 1 (hash) falla: dict només troba claus completes.
  • La pregunta 2 (ordre) sí que encaixa: en una col·lecció ordenada alfabèticament, tots els títols que comencen per "reun" són contigus. Amb una list ordenada i bisect localitzem el primer candidat en O(log n) i recorrem mentre el prefix coincideixi.
  • Alternativa amb el que sabem de hash: un dict prefix→llista d'ids, precalculat (per a cada títol en guardem els prefixos). Consulta O(1), a canvi de molta memòria. L'estructura especialitzada en això és el trie, que traurà el cap a la lliçó de recursos.
import bisect

def autocompletar(titols_ordenats, prefix, limit=10):
    """titols_ordenats: list ordenada alfabèticament."""
    i = bisect.bisect_left(titols_ordenats, prefix)  # O(log n)
    resultat = []
    while i < len(titols_ordenats) and titols_ordenats[i].startswith(prefix):
        resultat.append(titols_ordenats[i])
        if len(resultat) == limit:
            break
        i += 1
    return resultat

bisect_left fa una cerca binària (la mateixa idea que l'ABC, sobre un array): troba on començaria el prefix. Després només avancem mentre hi hagi coincidència: O(log n + k) amb k resultats.

Cas 2: "Els 10 esdeveniments més recents"

TaskFlow ha de mostrar els últims 10 esdeveniments d'activitat, descartant els antics.

  • Operacions: afegir per un extrem, descartar per l'altre, mida fixa. Pregunta 3: extrems, FIFO amb límit.
  • És exactament un ring buffer, i a Python ja el tenim fet: deque(maxlen=10). Afegir és O(1) i el descart del més antic és automàtic.
from collections import deque

esdeveniments = deque(maxlen=10)
esdeveniments.append({"tipus": "crear", "tasca_id": 7})   # O(1); si n'hi ha 10, expulsa el més vell

Triar aquí una list amb pop(0) funcionaria... a O(n) per descart: el símptoma seria una app que es va alentint a mesura que creix el registre històric.

Cas 3: "Detecta si el projecte té dependències circulars"

Abans de planificar, TaskFlow ha d'avisar si A depèn de B, B de C i C d'A.

  • "Depèn de" és una relació molts-a-molts: pregunta 6, graf. Un cicle al graf de dependències fa impossible l'ordre topològic.
  • Solució del mòdul 7: DFS amb tres colors (blanc/gris/negre). Trobar una aresta cap a un node gris (encara a la pila de recursió) delata el cicle. Cost O(V + E). Alternativa equivalent: si Kahn no aconsegueix processar tots els vèrtexs, hi ha cicle.
  • L'error típic és intentar resoldre-ho amb llistes i bucles imbricats "seguint cadenes de dependències": acaba en O(n²) o en bucles infinits. Quan vegis relacions creuades, modela el graf explícitament.

Cas 4: "Cerca per id" davant de "llista ordenada per prioritat"

TaskFlow necessita (a) obrir una tasca pel seu id a l'instant i (b) mostrar el backlog ordenat per prioritat.

  • Són dues operacions dominants diferents i cap estructura no guanya en totes dues:
Necessitat dict per id list ordenada per prioritat AVL per prioritat
Cercar per id O(1) O(n) O(n) (la clau és la prioritat, no l'id!)
Llistar per prioritat O(n log n) (ordenar cada cop) O(n) (ja ordenada) O(n) inordre
Inserir O(1) O(n) (forat) O(log n)
  • Resposta madura: totes dues. Un dict id→tasca com a magatzem principal, i una estructura ordenada (monticle si només atens la més urgent; AVL o llista+bisect si llistes intervals) que guarda referències. Això ens porta directes a l'última secció.

Errors de tria típics i els seus símptomes

Cada mala tria té una signatura de rendiment recognoscible. Aprèn a llegir-la:

Error Símptoma Diagnòstic Remei
Cercar per valor en una list dins d'un bucle Tot va bé amb 100 elements i s'arrossega amb 100 000 x in llista és O(n) → el bucle és O(n²) set o dict: x in conjunt és O(1)
insert(0) / pop(0) sobre list Encuar es torna lent quan creix la cua Desplaça tots els elements: O(n) deque (mòdul 4)
Ordenar tota la llista "per treure el mínim" sort() a cada iteració: O(n log n) per operació Només necessites l'extrem, no l'ordre total heapq: O(log n)
ABC amb dades que arriben ja ordenades Rendiment "logarítmic" que es comporta com a lineal L'arbre ha degenerat en una llista AVL, o barrejar/fer servir bisect
dict quan necessites intervals Codi ple de for k in d: if a <= k <= b El hash destrueix l'ordre a propòsit AVL / llista ordenada + bisect
Graf "simulat" amb llistes de llistes i cerques creuades Bucles imbricats fràgils, cicles que pengen el programa Relacions molts-a-molts sense modelar Graf amb llista d'adjacència + BFS/DFS
Optimitzar sense mesurar Dies perduts en una estructura exòtica per a 50 elements n minúscul: les constants dominen timeit primer; simple per defecte

Combinar estructures: el patró que fa servir TaskFlow

Les aplicacions reals gairebé mai no fan servir una sola estructura: en fan servir diverses de coordinades, cadascuna pagant l'operació que millor sap fer. TaskFlow és l'exemple que hem construït durant vuit mòduls:

import heapq

class NucliTaskFlow:
    """Esquelet de com TaskFlow combina estructures (versió mínima)."""

    def __init__(self):
        self.tasques = {}           # dict id -> tasca         : cercar per id O(1)
        self.per_etiqueta = {}      # dict etiqueta -> set ids : índex invertit O(1)
        self.urgencies = []         # heap (prioritat, comptador, id) : més urgent O(log n)
        self._comptador = 0         # desempat estable al monticle

    def crear(self, tasca):
        self.tasques[tasca["id"]] = tasca                      # O(1)
        for etiqueta in tasca.get("etiquetes", []):
            self.per_etiqueta.setdefault(etiqueta, set()).add(tasca["id"])  # O(1)
        self._comptador += 1
        heapq.heappush(self.urgencies, (tasca["prioritat"], self._comptador, tasca["id"]))  # O(log n)

    def mes_urgent(self):
        while self.urgencies:
            prioritat, _, id_ = self.urgencies[0]
            tasca = self.tasques.get(id_)
            # Entrada obsoleta: la tasca s'ha esborrat o ha canviat de prioritat
            if tasca is None or tasca["prioritat"] != prioritat:
                heapq.heappop(self.urgencies)   # la descartem i continuem
                continue
            return tasca
        return None

Punts que convé entendre bé d'aquest patró:

  • El dict és el magatzem canònic: l'única font de veritat. Les altres estructures guarden només ids (referències barates), mai còpies de la tasca.
  • El monticle fa servir la tupla (prioritat, comptador, id) del mòdul 4: el comptador desempata prioritats iguals mantenint l'ordre d'arribada i evita comparar dicts.
  • Esborrat mandrós: esborrar del mig d'un monticle és incòmode, així que no esborrem; en consultar, descartem entrades la tasca de les quals ja no existeix o ha canviat. És un truc estàndard en planificadors reals.
  • El preu de combinar és la coherència: cada escriptura toca diverses estructures. Centralitza les modificacions en mètodes (crear, esborrar...) perquè cap estructura no quedi dessincronitzada.

Exercicis

Exercici 1

Per a cada necessitat de TaskFlow, tria estructura i justifica-ho amb el seu Big O: (a) comprovar en O(1) si un email ja està registrat; (b) mostrar les tasques amb hores entre 2 i 5; (c) processar accions de "desfer" de l'usuari; (d) repartir tasques entre 3 persones per torns rotatoris; (e) mitjana mòbil d'hores treballades els últims 7 dies.

Exercici 2

Aquest codi cerca les tasques urgents sense assignar. Identifica els dos problemes de tria d'estructura i reescriu-lo:

def urgents_sense_assignar(tasques, assignades):   # tasques: list de dicts; assignades: list d'ids
    resultat = []
    for t in tasques:
        if t["prioritat"] == 1 and t["id"] not in assignades:
            resultat.append(t)
    resultat.sort(key=lambda t: t["hores"])
    return resultat[:3]

Exercici 3

Dissenya (només el disseny: estructures i cost de cada operació, sense codi) el "mode repàs" de TaskFlow: guarda les últimes 50 tasques visitades sense duplicats; si en visites una que ja hi era, puja a la posició més recent; consultar si una tasca és a l'historial ha de ser O(1). Pista: és el mateix compromís que una memòria cau LRU.

Solucions

Exercici 1. (a) set — pertinença O(1); (b) AVL amb clau hores (o list ordenada + bisect si hi ha poques escriptures) — interval O(log n + k); (c) pila — LIFO pur, O(1); (d) llista circular (RepartidorTasques) — "següent" O(1) sense fi; (e) deque(maxlen=7) amb suma incremental — O(1) per dia, com la FinestraProductivitat del mòdul 4.

Exercici 2. Problema 1: t["id"] not in assignades sobre una list és O(n), cosa que fa el bucle O(n·m); converteix-la un sol cop en set → O(1) per consulta. Problema 2: ordenar-ho tot per quedar-te amb 3 és O(k log k); per a un top-k petit fes servir heapq.nsmallest, O(k log 3):

import heapq

def urgents_sense_assignar(tasques, assignades):
    ids_assignades = set(assignades)                     # O(m), un sol cop
    candidates = [t for t in tasques
                  if t["prioritat"] == 1 and t["id"] not in ids_assignades]  # O(n)
    return heapq.nsmallest(3, candidates, key=lambda t: t["hores"])          # O(n log 3)

Exercici 3. Combina dues estructures coordinades: una llista doblement enllaçada amb l'ordre de visita (el més recent al cap) i un dict id→node. Visitar una tasca nova: crear node al cap + entrada al dict, O(1); si supera les 50, treure el node de la cua i la seva entrada del dict, O(1). Visitar-ne una d'existent: el dict localitza el seu node en O(1) i, en ser doblement enllaçada, es desenganxa i es mou al cap en O(1) — justament l'operació que una list no sap fer barata. Consultar pertinença: id in dict, O(1). Cap de les dues estructures per separat no ho aconsegueix; juntes, tot és O(1).

Conclusió

Ja tens el criteri que perseguia tot el curs: primer les operacions, després l'estructura, i davant del dubte, mesurar. Les set preguntes i l'arbre de decisió et porten a la candidata; la gran taula et dona els seus costos; els símptomes de rendiment t'avisen quan t'has equivocat; i el patró de combinació (magatzem dict + índexs i monticles auxiliars) t'ensenya com ho fan les aplicacions reals, TaskFlow inclosa. A la propera lliçó farem el viatge invers: repassarem mòdul a mòdul tot el que hem construït, per consolidar el mapa complet abans dels projectes finals.

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