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

Optimització de Codi

Següent ►
►

El Mòdul 4 va acabar amb una promesa: ja sabem triar l'algorisme correcte, però entre aquesta tria i un programa ràpid encara hi ha un ofici pel mig. Aquesta lliçó ensenya la primera part d'aquest ofici: com fer que una implementació donada corri més de pressa sense canviar el que fa. I comença per la regla que ho governa tot: no s'optimitza allò que un creu que és lent, sinó allò que s'ha mesurat que és lent. Sobre aquesta base construirem una jerarquia de quatre nivells — del canvi d'estructura de dades que multiplica la velocitat per cent fins a la micro-optimització que esgarrapa un 20 % — i, tan important com saber optimitzar, aprendrem a reconèixer quan cal parar.

Contingut

  1. La regla d'or: mesurar, no endevinar
  2. Les eines de mesura: perf_counter, timeit i cProfile
  3. La jerarquia de l'optimització
  4. Nivell 1 — Millor algorisme o estructura de dades
  5. Nivell 2 — Treure feina invariant dels bucles
  6. Nivell 3 — No repetir feina: lru_cache
  7. Nivell 4 — Micro-optimitzacions idiomàtiques de Python
  8. Sortir com més aviat millor: early exit i curtcircuit
  9. Quan parar d'optimitzar

La regla d'or: mesurar, no endevinar

Donald Knuth va escriure el 1974 la frase més citada (i pitjor citada) de l'enginyeria de programari: "l'optimització prematura és l'arrel de tots els mals". La cita completa — que donem aquí en traducció de la cita clàssica original — és més matisada i més útil:

"Hauríem d'oblidar-nos de les petites eficiències, diguem que el 97 % de les vegades: l'optimització prematura és l'arrel de tots els mals. Tanmateix, no hauríem de deixar escapar les nostres oportunitats en aquest 3 % crític."

Knuth no diu "no optimitzis": diu que el 97 % del codi no mereix optimització i que el 3 % restant la mereix tota. El problema és que la intuïció és pèssima localitzant aquest 3 %. Els desenvolupadors assenyalen sistemàticament el bucle "amb mala pinta" mentre el temps real se'n va en una línia innocent — un in sobre una llista, una concatenació de strings — d'aquelles que ja vam desemmascarar a 02-01. D'aquí la regla d'or d'aquest mòdul:

  • Primer es mesura (amb dades de mida realista, no amb 10 elements de prova).
  • S'optimitza únicament allò que la mesura assenyala.
  • Es torna a mesurar per confirmar que la millora existeix i quantificar-la.

Optimitzar sense mesurar té dos finals possibles: complicar codi que no era el problema (cost de manteniment sense benefici) o, pitjor encara, "optimitzar" a cegues i fer el programa més lent.

Les eines de mesura: perf_counter, timeit i cProfile

Cronometrar un fragment: time.perf_counter

El cronòmetre bàsic. perf_counter() retorna un instant d'alta resolució; la resta de dos instants dona el temps transcorregut:

import time

inici = time.perf_counter()
resultat = assigna_trajectes(peticions, autobusos)   # el codi a mesurar
fi = time.perf_counter()
print(f"assigna_trajectes: {fi - inici:.4f} s")

És perfecte per mesurar operacions que triguen dècimes de segon o més. Per a fragments molt ràpids (microsegons) una sola execució és soroll pur: el sistema operatiu, la memòria cau o el recol·lector d'escombraries distorsionen la mesura.

Mesurar fragments ràpids: timeit

timeit resol aquest soroll executant el fragment milers de vegades i fent-ne la mitjana:

import timeit

# Quant costa buscar una parada en una llista comparat amb un set?
t_llista = timeit.timeit("'Universitat' in parades",
                         setup="parades = ['Parada %d' % i for i in range(5000)] + ['Universitat']",
                         number=10_000)
t_set = timeit.timeit("'Universitat' in parades",
                      setup="parades = set('Parada %d' % i for i in range(5000)) | {'Universitat'}",
                      number=10_000)
print(f"llista: {t_llista:.4f} s   set: {t_set:.4f} s")
# llista: 0.5410 s   set: 0.0004 s   (orientatiu: ~1000x de diferència)
  • setup prepara les dades (no es cronometra).
  • number és quantes vegades s'executa la sentència; el resultat és el temps total.

Localitzar el coll d'ampolla: cProfile

Quan no saps què mesurar, cProfile ho mesura tot: executa el programa complet i reparteix el temps entre funcions.

import cProfile
cProfile.run("planifica_dia(peticions, xarxa)", sort="cumulative")

Sortida típica (retallada):

         2.847 seconds

   ncalls  tottime  cumtime  filename:lineno(function)
        1    0.002    2.847  planificador.py:12(planifica_dia)
    10000    0.011    2.790  planificador.py:31(valida_fitxatge)
 10000000    2.779    2.779  {built-in method 'in' on list}
    10000    0.041    0.055  planificador.py:48(calcula_tarifa)

Com llegir-la:

  • ncalls: vegades que es va cridar la funció.
  • tottime: temps dins de la funció, sense comptar les funcions a què crida.
  • cumtime: temps acumulat, incloent-hi allò que crida.

La lectura és un diagnòstic complet: planifica_dia acapara tot el cumtime però gairebé no té tottime — no és ella, és algú a qui crida. Aquest algú és valida_fitxatge, i dins seu els deu milions de crides a l'in sobre llista es mengen 2,78 dels 2,85 segons: el 97 % del temps és en una sola línia. calcula_tarifa, la funció que "semblava lenta" per les seves fórmules, costa 55 mil·lèsimes: irrellevant. Sense el perfil, oi que hauries començat per ella?

La jerarquia de l'optimització

No totes les optimitzacions valen el mateix. Convé atacar-les en ordre descendent d'impacte:

Nivell Què es canvia Guany típic Exemple
1 Algorisme o estructura de dades 10x – 1000x o més llista → set, lineal → binària (M4)
2 Feina invariant fora dels bucles 2x – 50x hoisting de càlculs repetits
3 No repetir feina (memòria cau de resultats) 2x – 100x lru_cache sobre funcions pures
4 Micro-optimitzacions idiomàtiques 1.1x – 3x comprehensions, join, built-ins

La conseqüència pràctica: no comencis mai pel nivell 4. Polir microsegons en un bucle que no hauria d'existir és abrillantar els cromats d'un cotxe sense motor.

Nivell 1 — Millor algorisme o estructura de dades

És el territori dels Mòduls 2–4, així que aquí només el situem a la jerarquia amb el cas del perfil anterior. RutaBus valida cada nit 10.000 fitxatges comprovant que el seu abonament és a la llista d'abonaments vàlids:

def valida_fitxatges(fitxatges, abonaments_valids):  # abonaments_valids: llista de 5.000
    correctes = []
    for fitxatge in fitxatges:                       # 10.000 voltes
        if fitxatge["abonament"] in abonaments_valids:   # 'in' en llista: O(m) — 02-01!
            correctes.append(fitxatge)
    return correctes

Cost: 10.000 × O(5.000) = 50 milions de comparacions. La correcció és una línia:

def valida_fitxatges(fitxatges, abonaments_valids):
    valids = set(abonaments_valids)                  # O(m), una sola vegada
    return [f for f in fitxatges if f["abonament"] in valids]   # 'in' en set: O(1)

D'O(n·m) a O(n + m): de 2,8 segons a 4 mil·lèsimes a la màquina del perfil. Cap optimització dels nivells següents no s'acosta a això — per això el nivell 1 va primer, i per això els mòduls d'anàlisi i disseny han precedit aquest.

Nivell 2 — Treure feina invariant dels bucles

Un càlcul és invariant de bucle (loop-invariant) si produeix el mateix resultat a totes les voltes. Dins del bucle es paga n vegades; a fora, una. Aquest trasllat s'anomena hoisting ("hissat"):

# ABANS — informe de fitxatges de les parades actualment en servei
def fitxatges_en_servei(fitxatges, parades):
    resultat = []
    for f in fitxatges:                                    # n voltes
        actives = {p["nom"] for p in parades               # es reconstrueix n vegades!
                   if p["en_servei"]}
        if f["parada"] in actives and f["minut"] < len(fitxatges) - 1:
            resultat.append(f)
    return resultat

El set actives no depèn de f: és idèntic a les n voltes. I len(fitxatges) - 1 tampoc no canvia. Tots dos s'hissen:

# DESPRÉS
def fitxatges_en_servei(fitxatges, parades):
    actives = {p["nom"] for p in parades if p["en_servei"]}   # una vegada
    ultim = len(fitxatges) - 1                                # una vegada
    return [f for f in fitxatges if f["parada"] in actives and f["minut"] < ultim]

D'O(n·p) a O(n + p). Les formes camuflades més freqüents de l'invariant: compilar una expressió regular dins del bucle (re.compile a fora), obrir/consultar un recurs a cada volta, ordenar una llista que no canvia, o cridar dins del bucle una funció pura amb els mateixos arguments — que és just el cas del nivell 3.

Nivell 3 — No repetir feina: lru_cache

A 03-03 vam escriure la memoïtzació a mà amb un diccionari memo, i una nota anticipava que Python la porta de sèrie. És el moment d'usar-la. La funció de tarifes de RutaBus calcula el preu entre dues parades, i per fer-ho llança un Dijkstra (04-05) que costa un bon pessic:

from functools import lru_cache

@lru_cache(maxsize=None)
def tarifa(origen, desti):
    dist, _ = dijkstra(xarxa, origen)        # car: es paga només la PRIMERA vegada
    minuts = dist[desti]
    return 100 + 15 * minuts                 # cèntims: fix + variable per minut

tarifa("Plaça Major", "Hospital Central")    # calcula: executa dijkstra → 235
tarifa("Plaça Major", "Hospital Central")    # memòria cau: retorna 235 sense executar RES
print(tarifa.cache_info())
# CacheInfo(hits=1, misses=1, maxsize=None, currsize=1)

El decorador @lru_cache embolcalla la funció amb un diccionari arguments → resultat: la primera crida amb uns arguments executa el cos i desa el resultat; les següents el retornen en O(1). Amb milers d'usuaris consultant els mateixos parells de parades populars, l'estalvi és massiu. Tres condicions per usar-lo amb seguretat:

  • La funció ha de ser pura: mateix resultat per a mateixos arguments, sense efectes secundaris. Si les tarifes canvien a mitjanit, cal invalidar amb tarifa.cache_clear().
  • Els arguments han de ser hashables (strings, nombres i tuples sí; llistes i dicts no).
  • maxsize=None vol dir memòria cau il·limitada — memòria a canvi de temps, el trade-off de 02-02. Un maxsize=1024 acota la memòria descartant allò menys usat recentment (això vol dir LRU, Least Recently Used); la cara i la creu d'aquesta moneda l'analitzarà 05-02.

Nivell 4 — Micro-optimitzacions idiomàtiques de Python

Quan l'algorisme ja és el correcte i el perfil continua assenyalant un bucle calent, queda esprémer l'intèrpret. Aquestes millores són modestes però reals, i tenen una cosa en comú: la versió ràpida sol ser també la més idiomàtica.

Patró lent Alternativa idiomàtica Millora orientativa*
bucle + append list comprehension 1.2x – 1.5x
s = s + tros en bucle "".join(trossos) 2x – 100x (creix amb n, 02-01)
bucle manual per sumar/buscar el màxim sum(), max(), min() 2x – 5x
ordenar amb comparacions manuals sorted(dades, key=...) 2x – 10x
atribut/global consultat en bucle calent còpia en variable local 1.1x – 1.3x

* Mesurats amb timeit en CPython 3.12 sobre llistes de 10⁵–10⁶ elements; els teus variaran — per això es mesuren.

Els quatre patrons sobre RutaBus:

# 1) Comprehension: el bucle corre en C, no en bytecode Python
temps = [f["minut"] for f in fitxatges if f["linia"] == "L1"]

# 2) join: una sola reserva de memòria en comptes de n còpies (l'O(n²) de 02-01)
informe = "\n".join(f"{f['parada']};{f['minut']}" for f in fitxatges)

# 3) Built-ins i sorted amb key: recorreguts en C, i Timsort (04-03) de regal
mes_matiner = min(fitxatges, key=lambda f: f["minut"])
per_parada = sorted(fitxatges, key=lambda f: f["parada"])

# 4) Variable local en bucle calent: les locals es resolen més ràpid
#    que els atributs (obj.metode) o les globals, i l'àlies es busca una sola vegada
def compta_per_linia(fitxatges):
    comptador = {}
    get = comptador.get                   # àlies local del mètode
    for f in fitxatges:
        linia = f["linia"]
        comptador[linia] = get(linia, 0) + 1
    return comptador

El patró 4 és l'únic que sacrifica una mica de naturalitat: reserva'l per a bucles que el perfil hagi assenyalat. Els altres tres haurien de ser el teu estil per defecte — rendeixen més i es llegeixen millor.

Sortir com més aviat millor: early exit i curtcircuit

L'operació més ràpida és la que no s'executa. Early exit (sortida anticipada) és retornar el resultat així que es coneix, en comptes de completar el recorregut:

# ABANS: recorre les 3.000 parades encara que trobi el problema a la primera
def hi_ha_parada_saturada(parades):
    saturada = False
    for p in parades:
        if p["ocupacio"] > 0.9:
            saturada = True
    return saturada

# DESPRÉS: surt a la primera troballa — i any() ho expressa en una línia
def hi_ha_parada_saturada(parades):
    return any(p["ocupacio"] > 0.9 for p in parades)

any() retorna True així que un element ho compleix; all() retorna False així que un falla. Amb un generador com a argument (sense claudàtors), ni tan sols es materialitza la llista. Això no canvia el pitjor cas — continua sent O(n), com vam veure a 02-03 — però transforma el cas mitjà.

El seu parent és el curtcircuit d'and/or: a A and B, si A és fals, B no s'avalua. Ordena les condicions de barata a cara:

# La comprovació O(1) primer; el Dijkstra només es llança si cal
if parada in xarxa and tarifa("Plaça Major", parada) < 300:
    ofereix_ruta(parada)

Quan parar d'optimitzar

Optimitzar té rendiments decreixents i costos creixents. Criteris de parada:

  • Quan es compleix el requisit. Si l'informe nocturn ha d'estar en menys de 5 minuts i triga 40 segons, ja està. Optimitzar més és cost sense benefici.
  • Quan la millora següent costa llegibilitat. El codi optimitzat sol ser codi més difícil d'entendre, provar i modificar. Un 15 % de velocitat a canvi que el proper desenvolupador (tu d'aquí a sis mesos) necessiti una tarda per entendre la funció gairebé mai no compensa.
  • Quan el perfil s'aplana. Si ja cap funció no domina el temps (tot es reparteix en un 5–10 %), els guanys fàcils s'han acabat; el que queda són els nivells de memòria (05-02) i paral·lelització (05-03), o acceptar el rendiment actual.
  • Documenta allò no evident. Si una optimització obliga a escriure codi estrany, un comentari amb la mesura que la justifica (# join: de 12 s a 0.3 s amb 10⁶ fitxatges) evita que algú la "netegi" de tornada cap a la versió lenta.

Errors Comuns i Consells

  • Optimitzar sense perfil. L'error número u, del qual descendeixen tots els altres. La intuïció assenyala el codi complex; el temps sol ser al codi simple executat milions de vegades.
  • Mesurar amb dades de joguina. Amb 10 fitxatges, llista i set triguen el mateix i l'O(n²) és invisible. Mesura amb mides de l'ordre real de producció.
  • Mesurar una sola execució d'una cosa ràpida. El soroll del sistema domina. Per a microsegons, timeit; per a segons, perf_counter amb diverses repeticions.
  • lru_cache sobre funcions impures. Si la funció depèn d'estat que canvia (tarifes actualitzables, hora actual), la memòria cau servirà resultats obsolets. Puresa primer, decorador després.
  • Confondre l'excepció amb la regla. El nivell 4 existeix, però un programa no se salva a base de micro-optimitzacions: si el perfil mostra un problema estructural, torna als nivells 1–3.
  • Consell: desa les mesures d'abans/després juntament amb el canvi (al commit o en un comentari). Una optimització sense números és una anècdota; amb números és enginyeria.

Exercicis

Exercici 1. Aquest fragment genera l'informe diari de RutaBus. Identifica —sense executar-lo— els problemes de rendiment que conté, classifica'ls per nivell de la jerarquia (1–4) i reescriu-lo aplicant les correccions:

def informe_diari(fitxatges, parades_vip):        # parades_vip: llista de 200 noms
    informe = ""
    for f in fitxatges:                           # ~100.000 fitxatges
        if f["parada"] in parades_vip:            # ?
            linia = f["parada"] + ";" + str(f["minut"]) + "\n"
            informe = informe + linia             # ?
    return informe

Exercici 2. La funció tarifa(origen, desti) de l'apartat de lru_cache té un defecte d'eficiència subtil fins i tot amb la memòria cau: cada parell (origen, destí) nou llança un Dijkstra complet, encara que ja se n'hagi llançat un des d'aquest mateix origen cap a un altre destí. Redissenya la memòria cau perquè Dijkstra s'executi com a màxim una vegada per origen. Pista: aplica la memòria cau a una altra funció.

Exercici 3. Amb timeit, escriu una mesura que compari "".join(...) amb la concatenació amb += per construir un string a partir de 10.000 fragments. Abans d'executar-la, anota la teva predicció de la diferència; després, compara-la amb el resultat i amb la fila corresponent de la taula del nivell 4.

Solucions

Solució 1. Tres problemes: (a) in sobre la llista parades_vip dins del bucle — nivell 1, canviar a set; (b) el set s'ha de construir fora del bucle — nivell 2, hoisting (construir-lo a dins recauria en el problema); (c) concatenació de strings en bucle, l'O(n²) de 02-01 — nivell 4, join:

def informe_diari(fitxatges, parades_vip):
    vip = set(parades_vip)                               # nivells 1+2: set, i fora del bucle
    return "\n".join(f"{f['parada']};{f['minut']}"       # nivell 4: join + generador
                     for f in fitxatges if f["parada"] in vip)

Amb 100.000 fitxatges i 200 parades VIP es passa de ~20 milions de comparacions més còpies quadràtiques a un recorregut lineal. Fixa't en l'ordre de la correcció: primer estructura (1), després col·locació (2), al final l'idiom (4).

Solució 2. La unitat de feina cara és "Dijkstra des d'un origen", no "un parell". Es posa la memòria cau en aquesta unitat:

@lru_cache(maxsize=None)
def distancies_des_de(origen):
    dist, _ = dijkstra(xarxa, origen)
    return dist                          # dict desti → minuts, calculat UNA vegada per origen

def tarifa(origen, desti):
    return 100 + 15 * distancies_des_de(origen)[desti]

Amb V parades, abans es feien fins a V² Dijkstras (un per parell); ara, com a màxim V. La lliçó general: posa la memòria cau en la granularitat de la feina cara, no en la de la consulta. (Et sona? És la discussió Dijkstra-per-origen vs Floyd-Warshall de 04-06 que reapareix com a política de memòria cau.)

Solució 3.

import timeit

t_concat = timeit.timeit(
    "s = ''\nfor x in trossos:\n    s = s + x",
    setup="trossos = ['tram;%d\\n' % i for i in range(10_000)]",
    number=100)
t_join = timeit.timeit(
    "''.join(trossos)",
    setup="trossos = ['tram;%d\\n' % i for i in range(10_000)]",
    number=100)
print(f"concatenació: {t_concat:.3f} s   join: {t_join:.3f} s   ràtio: {t_concat/t_join:.0f}x")
# Orientatiu en CPython 3.12: concatenació ~0.9 s, join ~0.02 s → ~40x

La ràtio exacta depèn de la màquina i de la versió de Python (CPython optimitza alguns casos de +=), i creix amb el nombre de fragments: la concatenació és O(n²) i join és O(n). Si la teva predicció ha fallat de molt, aquesta és exactament la lliçó: per això es mesura.

Conclusió

Aquesta lliçó ha establert el mètode que governa tot el mòdul: mesurar primer (perf_counter per a allò lent, timeit per a allò ràpid, cProfile per saber on mirar), i optimitzar després seguint la jerarquia — estructura de dades (el salt de 1000x del set de fitxatges), hissat d'invariants, memòria cau de resultats amb lru_cache, i només al final les micro-optimitzacions idiomàtiques amb join, comprehensions i any/all. I ha posat límits: es para quan es compleix el requisit, quan la llegibilitat comença a pagar la factura, o quan el perfil s'aplana. Hi ha tanmateix un recurs que avui hem gastat alegrement: lru_cache(maxsize=None), el set auxiliar, la llista materialitzada de l'informe... tot estalvia temps pagant amb memòria. La propera lliçó gira la truita: què fer quan la que escasseja és la memòria — com mesurar-la de debò, i com un job nocturn de RutaBus pot processar milions de fitxatges sense tenir-los mai tots alhora a la RAM.

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