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

Exercicis amb Taules Hash

Següent ►
►

Toca consolidar. En aquest mòdul has construït una taula hash des de zero (05-01 i 05-02) i has après a espremer dict i set amb els patrons professionals de 05-03: indexar, agrupar, comptar, invertir. Aquesta lliçó no introdueix teoria nova: són sis exercicis progressius, tots amb gust TaskFlow, que cobreixen els usos que amb més freqüència et trobaràs a la feina (i a les entrevistes tècniques): detectar duplicats, agrupar per clau derivada, cercar per etiquetes, desar a la memòria cau resultats cars, resoldre el clàssic two-sum i estendre la teva pròpia TaulaHash. Intenta resoldre cadascun abans de mirar la solució; l'enunciat sempre dona la pista de quina estructura fer servir — l'habilitat que entrenes és veure el per què.

Contingut

  1. Exercici 1: el primer id duplicat (i quant costa no fer servir hash)
  2. Exercici 2: agrupar títols anagramàtics
  3. Exercici 3: cercador d'etiquetes AND/OR
  4. Exercici 4: memòria cau de costos de projecte (memoïtzació)
  5. Exercici 5: two-sum sobre estimacions d'hores
  6. Exercici 6: estendre la TaulaHash de 05-02
  7. Errors comuns, solucions i tancament del mòdul

Exercicis

Exercici 1: el primer id duplicat (i quant costa no fer servir hash)

Una importació massiva ha ficat ids repetits a TaskFlow. Escriu dues versions de primer_duplicat(ids), que retorni el primer id que apareix per segona vegada (o None): una sense taula hash (només comparacions entre elements, O(n²)) i una altra amb un set de vistos (O(n)). Després mesura-les amb timeit (com a 01-02) per a n = 1.000, 10.000 i 20.000 ids amb el duplicat al final (pitjor cas). Anota el factor de millora a cada n: creix o es manté? Per què?

Exercici 2: agrupar títols anagramàtics

Control de qualitat editorial: volem detectar títols de tasques que són anagrames entre si (mateixes lletres, un altre ordre — típic de duplicats amb paraules reordenades, com ara "Pla web" i "Web pla"). Escriu agrupar_anagrames(titols) que retorni els grups de títols anagramàtics. Pista central del mòdul: agrupar és qüestió de triar la clau canònica correcta — una que sigui igual per a tots els membres del grup i hashable. Ignora majúscules i espais.

Exercici 3: cercador d'etiquetes AND/OR

Empaqueta l'índex invertit de 05-03 en una classe CercadorEtiquetes amb tres mètodes: indexar(tasca) (registra la tasca a l'índex invertit i a l'índex per id), cercar_and(*etiquetes) i cercar_or(*etiquetes), que retornen títols ordenats per id. Requisits: una etiqueta inexistent no ha de trencar res (en AND col·lapsa el resultat a buit; en OR simplement no aporta), i les tasques sense camp etiquetes s'han de poder indexar sense error.

Exercici 4: memòria cau de costos de projecte (memoïtzació)

TaskFlow modela projectes compostos: cada projecte té hores pròpies i una llista de subprojectes (que es poden repetir i compartir entre projectes). El cost total és recursiu (mòdul 3): hores pròpies + suma de costos dels subprojectes.

deps = {f"p{i}": [f"p{i+1}", f"p{i+1}"] for i in range(10)}  # cadascun fa servir DUES vegades el següent
deps["p10"] = []
hores_propies = {f"p{i}": 5 for i in range(11)}

Escriu cost(nom) recursiva i directa, amb un comptador global de crides. Després escriu cost_amb_cache(nom), que faci servir un dict com a memòria cau (patró memoïtzació): abans de calcular, mira si el resultat ja hi és; després de calcular, guarda'l. Compara el nombre de crides de totes dues per a "p0". Totes dues han de retornar el mateix total.

Exercici 5: two-sum sobre estimacions d'hores

Un clàssic absolut, en versió TaskFlow: tens parells (id, hores_estimades) i una jornada de 8 hores. Escriu parell_que_omple(tasques, jornada=8) que retorni els ids de dues tasques diferents les hores de les quals sumin exactament la jornada, o None. Dades de prova: [("T-01", 3), ("T-02", 7), ("T-03", 2), ("T-04", 5), ("T-05", 6)]. La versió evident compara totes les parelles (O(n²)); la bona fa una sola passada amb un dict. Pista: quan mires una tasca de h hores, la pregunta exacta és "ja n'he vist una de jornada - h hores?" — i respondre "ja he vist...?" en O(1) és l'especialitat d'aquest mòdul.

Exercici 6: estendre la TaulaHash de 05-02

Dos encàrrecs sobre la teva pròpia taula d'encadenament. (a) Afegeix el mètode claus(), que retorni una llista amb totes les claus emmagatzemades (recorre les cubetes; recorda que la LlistaEnllacada és iterable i cada dada és un parell [clau, valor]). (b) Comprova experimentalment el redimensionament automàtic: insereix els parells (i, str(i)) per a i de 0 a 99 partint de capacitat 8, i verifica tres coses — que la capacitat final és l'esperada (calcula-la a mà primer: en quines insercions se supera 0.75?), que el factor de càrrega final queda per sota del llindar, i que després de tots els redimensionaments cap clau no s'ha perdut (les 100 recuperables amb obtenir i claus() complet).

Solucions

Solució 1: primer duplicat, amb mesura

import random, timeit

def primer_duplicat_quadratic(ids):
    """Sense hash: per a cada id, havia aparegut abans? Cost: O(n²)."""
    for i in range(len(ids)):
        for j in range(i):                 # compara amb TOTS els anteriors
            if ids[j] == ids[i]:
                return ids[i]
    return None

def primer_duplicat_set(ids):
    """Amb hash: un set de vistos. Cost: O(n)."""
    vistos = set()
    for id_ in ids:
        if id_ in vistos:                  # O(1): hash, casella, resposta
            return id_
        vistos.add(id_)                    # O(1)
    return None

for n in (1_000, 10_000, 20_000):
    ids = random.sample(range(10 * n), n)  # n ids únics...
    ids.append(ids[n // 2])                # ...i el duplicat al final (pitjor cas)
    t_quad = timeit.timeit(lambda: primer_duplicat_quadratic(ids), number=3) / 3
    t_set = timeit.timeit(lambda: primer_duplicat_set(ids), number=3) / 3
    print(f"n={n:>6}: quadràtic={t_quad:.4f} s   set={t_set:.6f} s   x{t_quad / t_set:,.0f}")

Resultats en una màquina de referència (els teus variaran en valor absolut, no en forma):

n=  1000: quadràtic=0.0176 s   set=0.000063 s   x277
n= 10000: quadràtic=1.8647 s   set=0.000812 s   x2297
n= 20000: quadràtic=7.5529 s   set=0.002274 s   x3322

Comentari: el factor de millora creix amb n — de ×277 a ×3.322 — i havia de ser així: O(n²) davant O(n) vol dir que l'avantatge és proporcional a n, no una constant. Duplicar n (10.000 → 20.000) quadruplica el temps del quadràtic (1,86 → 7,55 s: ×4,05, la firma exacta del O(n²) que vas aprendre a 01-04) i només duplica el del set. Amb el milió de registres de l'experiment de 01-02, el quadràtic necessitaria hores; el set, una fracció de segon. És el mateix veredicte d'aquell experiment, però ara entens el mecanisme complet: cada in vistos és un càlcul de casella, no un recorregut.

Solució 2: anagrames per clau canònica

from collections import defaultdict

def clau_anagrama(titol):
    """Forma canònica: les lletres normalitzades i ORDENADES, com a tupla (hashable)."""
    return tuple(sorted(titol.lower().replace(" ", "")))

def agrupar_anagrames(titols):
    grups = defaultdict(list)             # clau canònica → títols del grup
    for titol in titols:
        grups[clau_anagrama(titol)].append(titol)
    return [grup for grup in grups.values() if len(grup) > 1] + \
           [grup for grup in grups.values() if len(grup) == 1]

titols = ["Roma", "Amor", "Ramo", "Mora", "Pla web", "Web pla", "Esprint"]
print(agrupar_anagrames(titols))
# [['Roma', 'Amor', 'Ramo', 'Mora'], ['Pla web', 'Web pla'], ['Esprint']]

Comentari: tota la intel·ligència és a clau_anagrama. Dos títols són anagrames si i només si, després de normalitzar (minúscules, sense espais) i ordenar-ne les lletres, produeixen la mateixa seqüència: "roma" i "amor" es converteixen tots dos en ('a','m','o','r'). Aquesta forma canònica compleix els dos requisits d'una bona clau d'agrupació: és igual per a tot el grup i és hashable (tupla de caràcters — una llista de sorted a seques fallaria amb TypeError, exercici 1 de 05-03). La resta és el patró defaultdict(list) d'agrupació de 05-03, en O(n · k log k) amb k = longitud del títol. Nota fina: aquest és exactament el defecte que feia dolenta hash_suma a 05-02 (ignorar l'ordre), fet servir aquí a propòsit — quan vols que els anagrames coincideixin, una clau insensible a l'ordre és l'eina correcta. La mateixa propietat és virtut o defecte segons el contracte que necessitis.

Solució 3: cercador AND/OR

class CercadorEtiquetes:
    """Els dos índexs de 05-03 (directe i invertit) empaquetats i sincronitzats."""

    def __init__(self):
        self.per_id = {}                   # id → tasca
        self.per_etiqueta = {}             # etiqueta → set d'ids

    def indexar(self, tasca):
        self.per_id[tasca["id"]] = tasca
        for etiqueta in tasca.get("etiquetes", []):        # tolera camp absent
            self.per_etiqueta.setdefault(etiqueta, set()).add(tasca["id"])

    def _ids(self, etiqueta):
        return self.per_etiqueta.get(etiqueta, set())      # inexistent → buit

    def cercar_and(self, *etiquetes):
        if not etiquetes:
            return []
        resultat = set(self._ids(etiquetes[0]))            # còpia defensiva
        for etiqueta in etiquetes[1:]:
            resultat &= self._ids(etiqueta)                # intersecció: només encongeix
        return self._titols(resultat)

    def cercar_or(self, *etiquetes):
        resultat = set()
        for etiqueta in etiquetes:
            resultat |= self._ids(etiqueta)                # unió: només creix
        return self._titols(resultat)

    def _titols(self, ids):
        return [self.per_id[i]["titol"] for i in sorted(ids)]

cercador = CercadorEtiquetes()
for t in [
    {"id": 2, "titol": "Migrar la BD", "prioritat": 1, "estat": "en curs",
     "etiquetes": ["backend", "urgent"]},
    {"id": 4, "titol": "Apedaçar l'API", "prioritat": 1, "estat": "pendent",
     "etiquetes": ["backend", "urgent", "api"]},
    {"id": 3, "titol": "Revisar els textos", "prioritat": 3, "estat": "pendent",
     "etiquetes": ["web"]},
    {"id": 9, "titol": "Nota solta", "prioritat": 3, "estat": "pendent"},
]:
    cercador.indexar(t)

print(cercador.cercar_and("backend", "urgent"))   # ['Migrar la BD', "Apedaçar l'API"]
print(cercador.cercar_and("backend", "web"))      # []
print(cercador.cercar_or("web", "api"))           # ['Revisar els textos', "Apedaçar l'API"]
print(cercador.cercar_and("backend", "res"))      # [] — la inexistent buida l'AND

Comentari: la classe reuneix les peces soltes de 05-03 en un objecte amb els índexs sempre sincronitzats — indexar toca tots dos, complint la regla de manteniment que hi vam enunciar. _ids centralitza la defensa get(..., set()): l'etiqueta desconeguda es comporta com a conjunt buit, que és neutre en l'OR (| amb buit no afegeix res) i aniquilador en l'AND (& amb buit dona buit) — exactament la semàntica demanada, sense ni un sol if especial. La tasca 9, sense etiquetes, s'indexa sense error gràcies a t.get("etiquetes", []) i simplement no apareix a les cerques. Cada consulta costa O(suma de mides dels conjunts implicats), independent del total de tasques indexades.

Solució 4: memoïtzació amb un dict

crides = 0

def cost(nom):
    """Recursiva directa: recalcula cada subprojecte CADA vegada que apareix."""
    global crides
    crides += 1
    return hores_propies[nom] + sum(cost(sub) for sub in deps[nom])

crides = 0
print(cost("p0"), crides)              # 10235 hores, 2047 crides

cache = {}                             # nom → cost ja calculat

def cost_amb_cache(nom):
    global crides
    if nom in cache:                   # O(1): ja l'hem calculat?
        return cache[nom]              # sí → resposta immediata, sense recursió
    crides += 1
    resultat = hores_propies[nom] + sum(cost_amb_cache(sub) for sub in deps[nom])
    cache[nom] = resultat              # guardar ABANS de retornar
    return resultat

crides = 0
print(cost_amb_cache("p0"), crides)    # 10235 hores, 11 crides

Comentari: mateix resultat (10.235 hores), però 2.047 crides contra 11. La versió directa explota perquè cada projecte fa servir dues vegades el següent: p0 provoca 2 càlculs de p1, 4 de p2... 1024 de p10 — total 2¹¹−1 = 2047, creixement exponencial. La memòria cau ho desactiva: cada projecte es calcula una sola vegada (11 projectes, 11 crides); les aparicions repetides es resolen amb una consulta O(1) al dict. El patró s'anomena memoïtzació i la seva recepta és sempre la mateixa: és a la memòria cau? torna-ho; calcula; guarda; retorna. Requisit imprescindible: la clau de la memòria cau ha de ser hashable i identificar completament l'entrada (aquí el nom basta perquè el cost només depèn del projecte). Aquest duo funció-recursiva-més-memòria-cau reapareixerà amb els recorreguts d'arbres (mòdul 6) i grafs (mòdul 7), on "no repetir feina ja feta" és la diferència entre l'instantani i l'intractable. Python ho porta empaquetat a functools.lru_cache, que pots explorar pel teu compte: és exactament aquest dict, com a decorador.

Solució 5: two-sum en una passada

def parell_que_omple(tasques, jornada=8):
    """Dues tasques les hores de les quals sumen la jornada exacta. Cost: O(n), una passada."""
    vistes = {}                            # hores → id d'una tasca amb aquestes hores
    for id_, hores in tasques:
        falta = jornada - hores            # el complement exacte que necessitem
        if falta in vistes:                # alguna tasca anterior el tenia? O(1)
            return (vistes[falta], id_)
        vistes[hores] = id_                # registrar l'actual per a les següents
    return None

tasques = [("T-01", 3), ("T-02", 7), ("T-03", 2), ("T-04", 5), ("T-05", 6)]
print(parell_que_omple(tasques))           # ('T-01', 'T-04'): 3 + 5 = 8
print(parell_que_omple([("T-09", 4)]))     # None

Comentari: la versió O(n²) provaria les 10 parelles; aquesta fa una passada i per cada tasca una consulta O(1). El gir mental és l'important: en comptes de preguntar "quina parella suma 8?" (pregunta sobre parelles: quadràtica), preguntem per cada tasca "existeix ja el meu complement exacte?" (pregunta sobre una clau: l'especialitat del hash). La traça: T-01 (3 h) busca 5 — no hi és — i es registra; T-02 (7) busca 1 — no; T-03 (2) busca 6 — no; T-04 (5) busca 3 — sí, és T-01 → ('T-01', 'T-04'). Detalls fins: registrar la tasca després de cercar impedeix aparellar-la amb ella mateixa (amb jornada 8, una tasca de 4 h només encaixa amb una altra de 4 h, i així passa); i si hi ha diverses respostes vàlides, retorna la primera assolible, amb els seus dos membres tan primerencs com sigui possible. Aquest truc del complement resol una família sencera de problemes ("dos elements amb diferència d?", "dues etiquetes que cobreixin el filtre?") i és probablement l'exercici de taula hash més preguntat a les entrevistes.

Solució 6: claus() i el redimensionament, auditat

    # --- mètode nou dins la classe TaulaHash de 05-02 ---
    def claus(self):
        """Totes les claus emmagatzemades. Cost: O(n + capacitat)."""
        resultat = []
        for cubeta in self.cubetes:        # totes les cubetes...
            for parell in cubeta:          # ...i cada parell [clau, valor] de la seva llista
                resultat.append(parell[0])
        return resultat

# --- auditoria del redimensionament ---
taula = TaulaHash(capacitat=8)
for i in range(100):
    taula.inserir(i, str(i))

print(taula.capacitat)                     # 256
print(len(taula) / taula.capacitat)        # 0.390625  (< 0.75, correcte)
print(len(taula.claus()))                  # 100
print(sorted(taula.claus()) == list(range(100)))           # True
print(all(taula.obtenir(i) == str(i) for i in range(100))) # True: res no s'ha perdut

Comentari: (a) claus() recorre l'array de cubetes i, dins de cadascuna, la LlistaEnllacada (el seu __iter__ del mòdul 2 entrega cada parell; ens quedem parell[0]). El cost O(n + capacitat) té el seu matís: amb la taula molt buida, el terme capacitat domina — visitar 256 cubetes per a 3 claus. Per això el dict real manté estructura extra per iterar només l'ocupat. (b) La capacitat final es prediu a mà amb la regla "després d'inserir, si n/capacitat > 0.75, duplicar": se supera amb n = 7 (7/8 = 0,875 → 16), n = 13 (→ 32), n = 25 (→ 64), n = 49 (→ 128) i n = 97 (→ 256). Cinc redimensionaments, capacitat final 256 i factor 0,39 — i les tres comprovacions en True: cada rehashing va reinserir els parells amb la capacitat nova sense perdre'n cap. Fixa't en l'elegància de l'última línia: obtenir funciona després que totes les claus hagin canviat de cubeta fins a cinc vegades, perquè guardar i cercar sempre comparteixen el mateix _index. La teva taula, construïda amb la LlistaEnllacada del mòdul 2, supera la mateixa auditoria que passaria un dict.

Errors Comuns i Consells

  • Triar claus d'agrupació no hashables (exercici 2): sorted(text) retorna una llista — embolcalla-la en tuple abans de fer-la servir com a clau. És l'ensopegada més repetida en agrupacions per clau derivada.
  • Desar a la memòria cau funcions que depenen de més del que diu la clau (exercici 4): si cost depengués també d'una tarifa global mutable, la memòria cau retornaria resultats obsolets en canviar-la. La clau de memoïtzació ha de capturar tota l'entrada — o la memòria cau s'ha d'invalidar quan el context canviï.
  • En two-sum, registrar abans de cercar (exercici 5): permet aparellar una tasca amb ella mateixa (una de 4 h "trobant-se" per sumar 8). L'ordre cercar-i-després-registrar no és estil: és correcció.
  • Mesurar amb dades que amaguen el pitjor cas (exercici 1): amb el duplicat al principi, totes dues versions semblen instantànies i la mesura no ensenya res. En comparar algorismes, construeix l'entrada que força la feina màxima — com vam fer col·locant-lo al final.
  • Oblidar la còpia defensiva en intersecar (exercici 3): arrencar l'AND amb resultat = self._ids(et[0]) sense copiar i després fer servir &=... muta el conjunt de l'índex, corrompent-lo per a consultes futures. set(...) primer, operar després.
  • Consell final del mòdul: guarda el CercadorEtiquetes i la memòria cau de memoïtzació; tots dos tornen als projectes del mòdul 8, i el patró "ho he vist ja?" de l'exercici 1 és literalment el conjunt visitats del BFS del mòdul 7.

Conclusió

Fi del mòdul 5 — i d'un deute que arrossegàvem des de la lliçó 01-02. Ja no només saps que el dict és O(1): saps per què (clau → hash → casella, sobre l'accés directe de l'array de 01-05), saps què l'amenaça (col·lisions, funcions hash dolentes, factor de càrrega desbocat) i saps què el defensa (encadenament, hash uniforme, redimensionament) — fins al punt d'haver construït i auditat la teva pròpia TaulaHash. En aquests exercicis el hash ha demostrat el seu rang: ha convertit un O(n²) en O(n) dues vegades (duplicats i two-sum), un cost exponencial en lineal (memoïtzació), i ha donat a TaskFlow un cercador d'etiquetes i un detector d'anagrames en un grapat de línies. Però no oblidis la frontera que vam traçar a 05-03: tot aquest poder respon a preguntes de clau exacta. Demana-li al teu índex "les tasques ordenades per id" o "totes les de prioritat entre 1 i 3" i el hash emmudeix — les seves claus estan escampades a propòsit, sense noció de veïnatge ni d'ordre. Per respondre a això cal una estructura que mantingui les claus organitzades jeràrquicament, on cada pas descarti la meitat de l'espai: els arbres, protagonistes del mòdul 6. Allà ens hi espera, a més, una promesa pendent del mòdul 4: obrir per fi la caixa negra de heapq i veure el monticle per dins (06-07). Ens veiem als arbres.

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