El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència

HOME

A 05-01 vam gastar memòria sense remordiments: un set auxiliar aquí, una memòria cau il·limitada allà — tot a canvi de temps. Aquesta lliçó presenta la factura. El cas que ens acompanyarà és el job nocturn de RutaBus: un procés que cada matinada llegeix el fitxer de fitxatges del dia — diversos milions de línies — i genera estadístiques per línia i parada. Funciona perfecte al portàtil del desenvolupador; en producció, dins d'un contenidor amb 512 MB, mor amb un lacònic Killed. Aprendrem per què la memòria importa fins i tot quan "en sobra", com mesurar-la de debò (que no és tan obvi com cronometrar), i un repertori de tècniques concretes — generadors, lots, __slots__, representacions compactes — perquè aquest job processi milions de fitxatges sense tenir-los mai tots alhora a la RAM.

Contingut

Per què importa la memòria encara que en "sobri"
Mesurar memòria (I): sys.getsizeof i les seves trampes
Mesurar memòria (II): tracemalloc
Generadors i iteradors: processar sense materialitzar
Processament per lots (chunks)
Objectes lleugers: __slots__, tuples, namedtuple i dataclass
Dades numèriques homogènies: array (i una menció a NumPy)
Interning i compartició de referències
La representació del graf segons la densitat
El trade-off invers: canviar temps per memòria

Per què importa la memòria encara que en "sobri"

"La meva màquina té 32 GB, què hi fa una llista d'un milió d'elements?" Quatre raons per les quals sí que hi fa:

Les memòries cau del processador. La RAM és lenta comparada amb les memòries cau L1/L2/L3 de la CPU (desenes contra centenars de cicles per accés). Un conjunt de dades compacte cap a la memòria cau i es recorre ràpid; un de dispers i voluminós provoca fallades de memòria cau constants. Menys memòria sol voler dir més velocitat, encara que l'algorisme sigui el mateix.
El recol·lector d'escombraries (GC). A Python, cada objecte viu és feina per al gestor de memòria. Milions d'objectes petits signifiquen més cicles de recol·lecció i pauses més llargues.
Contenidors i cloud amb límits. En producció el procés no té "tota la màquina": té el que declara el seu contenidor (512 MB, 1 GB...). Superar-ho no dona un error elegant: el sistema operatiu mata el procés (OOM kill — el Killed del nostre job). I al cloud, més memòria reservada és literalment més factura.
L'escala canvia tota sola. El job que avui processa 2 milions de fitxatges en processarà 10 d'aquí a dos anys. Un disseny O(n) en memòria té data de caducitat; un O(1), no.

I l'advertiment simètric al de 05-01: aquí tampoc no s'endevina. Primer es mesura.

Mesurar memòria (I): `sys.getsizeof` i les seves trampes

sys.getsizeof(objecte) retorna els bytes que ocupa aquest objecte... i aquí comencen les trampes:

import sys

sys.getsizeof(42)               # 28  — sí, un enter de Python ocupa 28 bytes
sys.getsizeof("Plaça Major")    # 84
sys.getsizeof([])               # 56  — una llista buida ja pesa
sys.getsizeof([1, 2, 3])        # 88

fitxatge = ["Plaça Major", "L1", 512, "AB-4471"]
sys.getsizeof(fitxatge)         # 88   només?!

Trampa 1: la mesura és superficial (shallow). Aquests 88 bytes són la llista — és a dir, la seva capçalera més les 4 referències — però no els objectes referenciats: l'string "Plaça Major" (84 bytes), el "L1", l'enter... no hi són inclosos. Per a un contenidor, getsizeof mesura l'embolcall, no el contingut. (És la distinció còpies-vs-referències de 02-02 aplicada a la mesura.)

Trampa 2: les referències poden estar compartides. Si un milió de fitxatges referencien el mateix string "Plaça Major", aquest string ocupa 84 bytes en total, no 84 milions. Sumar getsizeof recursivament pot sobreestimar tant com la mesura superficial subestima.

Trampa 3: els contenidors reserven de més. Una llista creix amb la reserva geomètrica que vam veure a 02-03 (l'anàlisi amortitzada d'append): després d'un milió d'appends, la llista té espai reservat per a més elements dels que conté.

Conclusió: getsizeof serveix per comparar el pes unitari de dues representacions (l'usarem així a l'apartat 6), però no respon "quanta memòria fa servir el meu programa?". Per a això hi ha l'eina següent.

Mesurar memòria (II): `tracemalloc`

tracemalloc és a la memòria el que cProfile era al temps a 05-01: registra quina línia de codi va fer cada reserva. Mesurem la primera versió (ingènua) del job de fitxatges:

import tracemalloc

tracemalloc.start()

with open("fitxatges.txt", encoding="utf-8") as f:
    linies = f.readlines()                    # materialitza TOT el fitxer!
fitxatges = [linia.rstrip().split(";") for linia in linies]
total_l1 = sum(1 for f in fitxatges if f[1] == "L1")

actual, pic = tracemalloc.get_traced_memory()
print(f"actual: {actual/1e6:.1f} MB   pic: {pic/1e6:.1f} MB")
# actual: 812.4 MB   pic: 812.6 MB      (amb 2 milions de línies)

for stat in tracemalloc.take_snapshot().statistics("lineno")[:3]:
    print(stat)
# job.py:7: size=622 MiB, count=2000003, average=326 B     ← la comprehension
# job.py:6: size=154 MiB, count=2000001, average=81 B      ← readlines()
# job.py:8: size=0.4 KiB, count=4, average=112 B           ← el sum()

Com llegir-ho:

get_traced_memory() dona la memòria actual i el pic — el pic és el que mata el contenidor.
L'snapshot per lineno assenyala els culpables: la línia 7 (la llista de fitxatges trossejats: 2 milions de llistes petites amb els seus strings) reté 622 MiB, i la línia 6 (readlines) 154 MiB més. La línia 8, que és la que fa la feina útil, gasta 400 bytes.

El diagnòstic és demolidor: el 99,9 % de la memòria se'n va a materialitzar dades que només es recorren una vegada. Aquest és exactament el problema que resolen les dues tècniques següents.

Generadors i iteradors: processar sense materialitzar

A 02-02 vam veure que un generador ocupa O(1): és una recepta que produeix els valors d'un en un, no la col·lecció sencera. L'aplicació al job és directa, perquè els fitxers a Python ja són iteradors de línies:

def llegeix_fitxatges(ruta):
    """Genera fitxatges d'un en un: memòria O(1) respecte del fitxer."""
    with open(ruta, encoding="utf-8") as f:
        for linia in f:                        # línia a línia, sense readlines()
            parada, linia_bus, minut, abonament = linia.rstrip().split(";")
            yield {"parada": parada, "linia": linia_bus,
                   "minut": int(minut), "abonament": abonament}

total_l1 = sum(1 for f in llegeix_fitxatges("fitxatges.txt") if f["linia"] == "L1")

A cada instant hi ha un fitxatge viu en memòria: el que s'està processant. Mesurat amb tracemalloc, el pic baixa de 812 MB a menys d'1 MB — el job cap a qualsevol contenidor, i hi cabrà igual quan els fitxatges es quintupliquin. Mateix resultat, mateixa complexitat temporal, memòria d'O(n) a O(1).

Les agregacions típiques encaixen sense esforç en aquest motlle: sum, max, min, un diccionari de comptadors... totes consumeixen el flux d'un en un. Els límits són els que ja vam anotar a 02-02: un generador no s'indexa, no té len, i s'esgota quan es recorre — per fer-hi dues passades cal tornar-lo a cridar (rellegir el fitxer: temps a canvi de memòria, un altre cop el trade-off).

Processament per lots (chunks)

Entre "tot en memòria" i "d'un en un" hi ha un terme mitjà útil: processar per lots. És la solució quan la destinació de les dades prefereix grups — inserir en una base de dades de 1.000 en 1.000, enviar a una API en blocs — o quan convé amortir un cost fix per operació:

from itertools import islice

def per_lots(iterable, mida):
    """Agrupa qualsevol iterable en llistes de fins a `mida` elements."""
    iterador = iter(iterable)
    while lot := list(islice(iterador, mida)):   # islice: pren els `mida` següents
        yield lot

for lot in per_lots(llegeix_fitxatges("fitxatges.txt"), 10_000):
    desa_a_bd(lot)          # 200 insercions massives en comptes de 2.000.000 d'individuals

La memòria passa d'O(1) a O(mida del lot) — controlada i constant, triada per nosaltres, independent del total. El paràmetre mida és un dial entre memòria i sobrecost per operació: s'ajusta mesurant, com tot en aquest mòdul.

Objectes lleugers: `slots`, tuples, `namedtuple` i `dataclass`

Encara que el flux sigui mandrós, de vegades cal retenir-ne una part: els 200.000 fitxatges de la línia L1 per a una anàlisi posterior, per exemple. Llavors el pes unitari de cada objecte es multiplica per 200.000, i la representació importa. Comparem les opcions per a un Fitxatge de 4 camps (bytes superficials per instància, CPython 3.12, 64 bits):

Representació	Bytes/instància*	Accés	Mutable
`dict` `{"parada": ..., ...}`	184	`f["parada"]`	sí
classe normal	48 (+ el seu `__dict__`: 296)	`f.parada`	sí
`class Fitxatge` amb `__slots__`	72	`f.parada`	sí
`tuple`	72	`f[0]` (posicional)	no
`namedtuple`	72	`f.parada`	no
`@dataclass(slots=True)`	72	`f.parada`	sí

* Mesurats amb getsizeof (superficial: els valors a part, però són els mateixos en tots els casos — el que canvia és l'embolcall).

La clau és a la segona fila: una classe normal desa els seus atributs en un diccionari intern (__dict__), flexible però car. __slots__ declara els atributs per endavant i elimina aquest diccionari:

class Fitxatge:
    __slots__ = ("parada", "linia", "minut", "abonament")   # atributs fixos, sense __dict__

    def __init__(self, parada, linia, minut, abonament):
        self.parada, self.linia, self.minut, self.abonament = parada, linia, minut, abonament

Per a 200.000 instàncies: ~69 MB amb classe normal, ~14 MB amb __slots__ — unes 5 vegades menys, amb la mateixa sintaxi d'ús. El preu: no es poden afegir atributs no declarats (f.extra = 1 → AttributeError), cosa que en un objecte-registre és més virtut que limitació. Criteri ràpid:

Dades internes, posicionals i fugaces → tupla.
Registre immutable amb noms → namedtuple.
Registre mutable amb noms i milions d'instàncies → __slots__ o @dataclass(slots=True) (aquesta última afegeix __init__, repr i comparació de franc).
dict per defecte per a dades massives, no: és l'opció més pesant de la taula.

Dades numèriques homogènies: `array` (i una menció a NumPy)

Quan allò que es reté són nombres del mateix tipus — els minuts de cada fitxatge, per exemple — hi ha un salt més. Una llista de Python desa referències a objectes enters (28+ bytes cadascun, dispersos per la RAM); el mòdul array de la biblioteca estàndard desa els valors en cru, contigus:

from array import array

minuts_llista = [f.minut for f in fitxatges_l1]      # 200.000 enters-objecte
minuts_array = array("i", minuts_llista)             # "i": int de 4 bytes, en cru

# llista: ~1.6 MB de referències + ~5.6 MB d'objectes int ≈ 7.2 MB
# array: 200.000 × 4 bytes ≈ 0.8 MB   (9x menys, i contigu → amable amb la memòria cau)

La mateixa idea, amb esteroides, és NumPy: arrays n-dimensionals compactes amb operacions vectoritzades en C (minuts.mean(), matriu @ vector). Per a la feina numèrica seriosa — la matriu D de Floyd-Warshall a gran escala, estadístiques massives — és l'eina estàndard de l'ecosistema; aquí en tenim prou de saber que existeix, per què guanya (la mateixa raó que array: dades en cru i contigües) i que la seva part vectoritzada tornarà a treure el cap a 05-03.

Interning i compartició de referències

Última volta de rosca al job: cada fitxatge porta el nom de la seva parada com a string. Dos milions de fitxatges, però només ~3.000 parades diferents: llegint el fitxer, Python crea dos milions d'objectes string, gairebé tots còpies repetides dels mateixos 3.000 valors. La solució és compartir referències: que tots els fitxatges de la Plaça Major apuntin al mateix string. sys.intern manté aquesta taula d'exemplars únics:

from sys import intern

parada = intern(parada)     # dins de llegeix_fitxatges: retorna l'exemplar canònic

Amb això els dos milions de camps parada pesen el que pesen 3.000 strings, no el que pesarien 2.000.000 (desenes de MB recuperats), i de regal les comparacions parada == altra entre strings internats es resolen comparant referències. El mateix efecte s'aconsegueix amb una memòria cau casolana (vistos.setdefault(parada, parada)). Dos matisos honestos: Python ja interna pel seu compte alguns strings petits i identificadors (per això de vegades "no es nota" el problema), i aquesta és la raó profunda de la trampa 2 de getsizeof — amb referències compartides, sumar mides unitàries sobreestima.

La representació del graf segons la densitat

Aquest criteri de "representació segons les dades" ja el vam aplicar al graf de RutaBus a 04-06, llavors amb la vista posada en el temps. Repassem la mateixa taula des de l'angle de la memòria:

Representació	Memòria	Xarxa urbana (V=300, E≈900)	Xarxa metropolitana (V=20.000, E≈60.000)
dict d'adjacència (04-05)	O(V + E)	~1.200 entrades: KB	~80.000 entrades: pocs MB
matriu d'adjacència `D` (04-06)	O(V²)	90.000 cel·les: encara MB	400 milions de cel·les: ~3 GB

La matriu paga una cel·la per parell possible, existeixi o no el tram; el diccionari paga només pels trams reals. En un graf dispers (E ≪ V², com tota xarxa de transport: cada parada connecta amb 2–4 veïnes, no amb les 20.000) la matriu malbarata gairebé totes les cel·les en INF. En un de dens, la matriu compensa: sense el cost per entrada dels dicts i amb accés O(1) a qualsevol parell — i si a més la sortida que es vol és tots-amb-tots (Floyd-Warshall), l'O(V²) és irreductible perquè és la mida de la resposta, com ja vam notar a 04-06. La moralitat generalitza l'apartat 6: la representació correcta depèn de la forma de les dades — densitat aquí, homogeneïtat a array, repetició a l'interning.

El trade-off invers: canviar temps per memòria

A 02-02, construeix_index gastava memòria per guanyar temps, i a 05-01 lru_cache va fer el mateix. Aquesta lliçó ha recorregut el sentit contrari del mateix eix, i convé dir-ho explícitament: de vegades la jugada correcta és pagar temps per alliberar memòria.

Recalcular en comptes de desar a la memòria cau. Si distancies_des_de (05-01, exercici 2) desa les distàncies des de 20.000 orígens, són 20.000 diccionaris de 20.000 entrades: gigabytes. Si cada origen es consulta poques vegades, millor recalcular: Dijkstra triga mil·lisegons i la memòria cau il·limitada era un OOM en diferit. El terme mitjà és acotar: lru_cache(maxsize=500) reté els 500 orígens més consultats i recalcula la resta.
Rellegir en comptes de retenir. El generador que s'esgota i obliga a una segona lectura del fitxer és aquest trade-off: dues passades de 30 segons contra 800 MB retinguts.
El criteri és el de sempre: mesurar totes dues magnituds i mirar quin és el recurs escàs al teu entorn. Al contenidor de 512 MB, escasseja la memòria; a l'informe que ha de sortir en 5 minuts i va sobrat de RAM, escasseja el temps. L'error no és triar l'una o l'altra: és triar sense haver mesurat cap de les dues.

Errors Comuns i Consells

Confiar en getsizeof per a contenidors. Mesura l'embolcall, no el contingut. Per a "quant fa servir el meu programa i qui?", tracemalloc; getsizeof, només per comparar pesos unitaris.
Materialitzar per costum. readlines(), list(...) o una comprehension "per veure-ho millor" converteixen O(1) en O(n) sense necessitat. Pregunta't: recorreré això més d'una vegada? Necessito indexar-ho? Si no, deixa el generador en pau.
Recórrer dues vegades un generador. La segona passada no dona error: dona buit, silenciosament. Si necessites dues passades, materialitza a consciència o regenera el flux.
Optimitzar memòria que no importa. L'avís de 02-02 continua vigent: si el job processa 5.000 fitxatges, els 800 MB no arriben mai i __slots__ és soroll. Aquestes tècniques es justifiquen amb un tracemalloc a la mà, igual que 05-01 exigia un perfil.
Oblidar el pic. tracemalloc dona la memòria actual i el pic; el contenidor mor pel pic. Una còpia temporal enorme dins d'una funció (un sorted(...) de tot el flux, per exemple) pot no deixar rastre en la memòria final i tot i així matar el procés.
Consell: en jobs de dades, decideix primer el contracte de memòria ("aquest procés fa servir O(1)/O(lot), mai O(n)") i protegeix-lo: qualsevol list(...) sobre el flux complet és una violació del contracte que ha de saltar a la revisió de codi.

Exercicis

Exercici 1. Aquest job calcula el minut mitjà de fitxatge per línia. Assenyala tots els punts on materialitza dades innecessàriament i reescriu-lo amb memòria O(L), on L és el nombre de línies d'autobús (3), independent del nombre de fitxatges:

def minut_mitja_per_linia(ruta):
    with open(ruta, encoding="utf-8") as f:
        linies = f.readlines()
    fitxatges = [l.rstrip().split(";") for l in linies]
    resultat = {}
    for nom in {f[1] for f in fitxatges}:
        minuts = [int(f[2]) for f in fitxatges if f[1] == nom]
        resultat[nom] = sum(minuts) / len(minuts)
    return resultat

Exercici 2. Amb getsizeof, estima quanta memòria superficial estalviarien 500.000 fitxatges retinguts si passessin de dict de 4 claus (184 B) a @dataclass(slots=True) (72 B). Després explica per què l'estalvi real mesurat amb tracemalloc seria encara més gran si a més s'aplica intern als noms de parada. Pot getsizeof detectar aquest segon estalvi?

Exercici 3. RutaBus vol publicar la matriu de temps mínims tots-amb-tots de la xarxa metropolitana (V = 20.000, E ≈ 60.000, dispersa). Un company proposa: "Floyd-Warshall sobre matriu, com a 04-06". Rebat la proposta o dona-hi suport amb números de memòria (cel·les de la matriu a 8 bytes cadascuna), i proposa quina representació i estratègia faries servir si només l'1 % dels parells es consulta realment. (És la tercera vegada que aquest dilema apareix al curs — 04-06 el va mirar en temps, aquí toca memòria.)

Solucions

Solució 1. Materialitza tres vegades: readlines() (tot el fitxer), la llista fitxatges (tot trossejat) i les llistes minuts (una passada extra per línia d'autobús, rellegint la llista completa). Versió d'una sola passada amb acumuladors:

def minut_mitja_per_linia(ruta):
    suma, recompte = {}, {}                        # O(L): 3 línies d'autobús
    for f in llegeix_fitxatges(ruta):              # generador d'aquesta lliçó: O(1)
        suma[f["linia"]] = suma.get(f["linia"], 0) + f["minut"]
        recompte[f["linia"]] = recompte.get(f["linia"], 0) + 1
    return {l: suma[l] / recompte[l] for l in suma}

Memòria: dos diccionaris de 3 entrades més el fitxatge en curs. Tant li fa que el fitxer tingui dues mil o dos mil milions de línies. (De regal, també és més ràpid: una passada en comptes de L+1.)

Solució 2. Estalvi superficial: 500.000 × (184 − 72) = 56.000.000 bytes = 56 MB, només en embolcalls. L'estalvi addicional de l'interning és als valors: sense ell hi ha fins a 500.000 objectes string per a ~3.000 parades diferents (~60 B cadascun ≈ 30 MB → ~0,2 MB amb interning). getsizeof no pot detectar-lo: és una mesura superficial que no segueix referències, així que no distingeix si dos fitxatges comparteixen l'string o en tenen còpies (trampes 1 i 2). Només una mesura global com tracemalloc veu la diferència.

Solució 3. La matriu necessita V² = 400.000.000 cel·les × 8 B = 3,2 GB — només la matriu de distàncies; amb la matriu sig de reconstrucció de 04-06, el doble. Inviable en un contenidor normal, i el 99 % de les cel·les ni es consultarà. Alternativa coherent amb la densitat del graf: dict d'adjacència (O(V+E) ≈ pocs MB) + Dijkstra sota demanda des de l'origen consultat, amb una memòria cau acotada de resultats per origen (lru_cache(maxsize=...) sobre distancies_des_de, exercici 2 de 05-01) per als orígens populars. Es canvia un precàlcul O(V²) en memòria per un recàlcul O((V+E) log V) en temps — exactament el trade-off invers de l'apartat 10, triat perquè aquí el recurs escàs és la memòria i les consultes són disperses.

Conclusió

El job nocturn de RutaBus ha passat de morir amb 812 MB a córrer en O(1) de memòria, i pel camí ha deixat un mètode: mesurar (tracemalloc per al global i el pic, getsizeof només per comparar embolcalls unitaris), no materialitzar allò que només es recorre (generadors, línia a línia, lots quan convé amortir), compactar allò que sí que es reté (__slots__, namedtuple, array, interning) i triar la representació segons la forma de les dades — la densitat del graf va decidir entre dict i matriu igual que l'homogeneïtat va decidir entre llista i array. I hem tancat el cercle obert a 02-02: temps i memòria són dos plats de la mateixa balança, i saber quin carregar exigeix haver-los mesurat tots dos. Amb el codi afinat (05-01) i la memòria sota control, queda un recurs sense explotar: els altres nuclis del processador, que durant tot aquest mòdul han estat mirant com treballa un de sol. La propera lliçó — paral·lelització — reparteix la feina entre ells, i de passada desmunta el mite més persistent de Python: per què els fils no sempre acceleren res, i què fer servir quan no ho fan.

Ús Eficient de Memòria

Contingut

Per què importa la memòria encara que en "sobri"

Mesurar memòria (I): `sys.getsizeof` i les seves trampes

Mesurar memòria (II): `tracemalloc`

Generadors i iteradors: processar sense materialitzar

Processament per lots (chunks)

Objectes lleugers: `slots`, tuples, `namedtuple` i `dataclass`

Dades numèriques homogènies: `array` (i una menció a NumPy)

Interning i compartició de referències

La representació del graf segons la densitat

El trade-off invers: canviar temps per memòria

Errors Comuns i Consells

Exercicis

Solucions

Conclusió

Curs d'Anàlisi i Disseny d'Algorismes

Mòdul 1: Introducció als Algorismes

Mòdul 2: Anàlisi d'Algorismes

Mòdul 3: Estratègies de Disseny d'Algorismes

Mòdul 4: Algorismes Clàssics

Mòdul 5: Optimització d'Algorismes

Mòdul 6: Pràctiques i Exercicis

Ús Eficient de Memòria

Contingut

Per què importa la memòria encara que en "sobri"

Mesurar memòria (I): sys.getsizeof i les seves trampes

Mesurar memòria (II): tracemalloc

Generadors i iteradors: processar sense materialitzar

Processament per lots (chunks)

Objectes lleugers: __slots__, tuples, namedtuple i dataclass

Dades numèriques homogènies: array (i una menció a NumPy)

Interning i compartició de referències

La representació del graf segons la densitat

El trade-off invers: canviar temps per memòria

Errors Comuns i Consells

Exercicis

Solucions

Conclusió

Curs d'Anàlisi i Disseny d'Algorismes

Mòdul 1: Introducció als Algorismes

Mòdul 2: Anàlisi d'Algorismes

Mòdul 3: Estratègies de Disseny d'Algorismes

Mòdul 4: Algorismes Clàssics

Mòdul 5: Optimització d'Algorismes

Mòdul 6: Pràctiques i Exercicis

Mesurar memòria (I): `sys.getsizeof` i les seves trampes

Mesurar memòria (II): `tracemalloc`

Objectes lleugers: `slots`, tuples, `namedtuple` i `dataclass`

Dades numèriques homogènies: `array` (i una menció a NumPy)