La lliçó anterior va deixar dues preguntes pendents: per què accedir a llista[i] costa O(1), i quina reorganització oculta fa que append sigui O(1) només amortitzat? Per respondre-les cal baixar un nivell: entendre com s'organitza físicament la memòria de l'ordinador i què és un array, l'estructura més elemental de totes i el fonament sobre el qual es construeixen gairebé totes les altres. En acabar sabràs exactament què fa la list de Python per dins, quines operacions de TaskFlow resol bé un array... i quines no, cosa que ens obrirà la porta del mòdul 2.

1. La memòria com una filera de caselles numerades
2. Arrays estàtics: contigüitat i accés O(1)
3. El preu de la contigüitat: inserir i esborrar al mig
4. Arrays dinàmics i redimensionament amortitzat
5. La list de Python per dins (i una menció a array i NumPy)
6. TaskFlow: quan n'hi ha prou amb un array i quan es queda curt

Pots imaginar la memòria RAM d'un ordinador com una filera gegantina de caselles de la mateixa mida, numerades consecutivament. El número de cada casella és la seva adreça de memòria, i el processador pot llegir o escriure qualsevol casella només coneixent-ne l'adreça, sigui on sigui de "lluny": anar a la casella 4 i a la casella 40.000.000 costa el mateix. Per això aquesta memòria s'anomena RAM: Random Access Memory, memòria d'accés aleatori (directe).

Dues idees clau d'aquest model:

• Tota dada viu en alguna adreça. Quan en Python escrius x = 42, en algun lloc d'aquesta filera queda emmagatzemat el 42, i x és la manera humana de referir-se a la seva adreça. Python t'amaga les adreces (en C es gestionen a mà, amb punters), però pots donar-hi un cop d'ull amb id(x), que retorna un identificador basat en l'adreça de l'objecte.
• Accedir per adreça és O(1). És una operació de maquinari: el processador calcula l'adreça i hi va. No hi ha cerca, no hi ha recorregut.

Sobre aquest model hi ha una decisió fonamental que separa dos mons: desar les dades contigües (en caselles seguides) o disperses (cadascuna on hi hagi lloc, connectades per referències). Els arrays aposten per la contigüitat; les llistes enllaçades del mòdul 2 apostaran per la dispersió. Tota la lliçó gira al voltant de les conseqüències d'aquesta aposta.

Un array estàtic és un bloc de caselles contigües reservat d'una vegada, amb una mida fixa, on cada casella ocupa el mateix. És l'estructura nativa de llenguatges com C o Java.

La contigüitat té un premi enorme. Si l'array comença a l'adreça 1000 i cada element ocupa 8 bytes, on és l'element d'índex i? No cal buscar-lo: es calcula.

Una multiplicació i una suma, sigui i 3 o 3 milions: per això l'accés per índex és O(1). Aquesta fórmula és la resposta a la primera pregunta pendent de la lliçó 01-04, i és una de les idees més importants del curs: l'array no busca l'element i, calcula on ha de ser.

Simulem un array estàtic en Python per tocar-ne els límits (Python no en té de natius, així que imposem les restriccions nosaltres):

Punts del codi que mereixen atenció:

• [None] * capacitat reserva totes les caselles en el moment de la creació: això és el que significa "estàtic". La memòria queda compromesa encara que no es faci servir.
• afegir és O(1)... fins que l'array s'omple. Aleshores no hi ha res a fer: OverflowError. Un array estàtic no creix.
• Distingim _capacitat (caselles reservades) d'_usades (caselles amb dades reals). Aquesta distinció sembla menor ara, però és la clau de l'apartat d'arrays dinàmics.

Avantatge addicional de la contigüitat que convé conèixer: els processadors moderns llegeixen la memòria per blocs (memòria cau), de manera que recórrer dades contigües és encara més ràpid a la pràctica que recórrer dades disperses: en llegir l'element 0, els següents ja vénen "de regal" al mateix bloc.

Tot el que la contigüitat regala en l'accés ho cobra en les modificacions. Pensa en una fila de seients plens en un cinema: si algú es vol asseure al mig, tots els d'un costat s'han de córrer un seient.

Inserir a la posició i d'un array exigeix desplaçar una casella a la dreta tots els elements des d'i fins al final:

Esborrar la posició i és el moviment invers: els elements posteriors es desplacen a l'esquerra per no deixar forat (la contigüitat no admet buits).

El cost, amb el vocabulari de la lliçó anterior:

Fixa't en l'asimetria que defineix l'array: esplèndid llegint i modificant per posició, car reorganitzant. Inserir al principi és el cas més dolorós: es mouen tots els elements.

L'array estàtic té un problema pràctic evident: cal endevinar la mida per endavant. Quantes tasques tindrà un usuari de TaskFlow? 100? 100.000? Quedar-se curt és fatal (OverflowError) i passar-se malbarata memòria.

L'array dinàmic resol el dilema amb una estratègia elegant:

1. Comença amb un array estàtic d'una certa capacitat.
2. Manté el compte de caselles usades davant de capacitat total (els nostres _usades i _capacitat).
3. Quan un append troba l'array ple: reserva un array nou més gran (típicament el doble o similar), copia tots els elements al nou i allibera el vell.

El pas de còpia costa O(n), i aquí apareix la resposta a la segona pregunta pendent de la lliçó 01-04. Per què append és O(1) amortitzat i no O(n)? Per la política de duplicar la capacitat: després d'una còpia de n elements, queden n caselles lliures, és a dir, els següents n append seran O(1) garantit. El cost O(n) de la còpia, repartit entre aquests n append barats, surt a O(1) extra per operació.

Comptem-ho amb números perquè no quedi en paraules: partint de capacitat 1, fer 8 append provoca còpies d'1, 2 i 4 elements (en omplir les capacitats 1, 2 i 4): 7 còpies en total per a 8 insercions, menys d'una còpia per append. Amb 1.024 append, les còpies sumen 1.023: continua sortint a ~1 per operació. La mitjana no creix amb n: això és O(1) amortitzat, exactament la definició que vam donar a la lliçó anterior.

La contrapartida honesta: un append concret (el que dispara la còpia) sí que pot ser lent, i l'array dinàmic manté caselles de sobres reservades (memòria extra de fins al doble del que s'usa). Flexibilitat a canvi de pics puntuals i una mica de memòria: un altre intercanvi dels que ja saps reconèixer.

La gran revelació d'aquesta lliçó: la list de Python és exactament això, un array dinàmic. No és una "llista enllaçada" malgrat el seu nom (aquest serà just el tema del mòdul 2, i la confusió de noms és una trampa clàssica). Ara tota la taula de costos que vam donar a la lliçó 01-04 té explicació física:

Un matís tècnic que convé conèixer: com que una list pot barrejar tipus i els objectes de Python tenen mides diferents, les caselles de l'array no contenen els objectes en si, sinó referències (adreces) cap a ells, totes de la mateixa mida; per això la fórmula de l'accés continua funcionant. I la política de creixement de CPython no és duplicar exactament, sinó créixer ~1,125× amb un marge addicional; l'anàlisi amortitzada es manté amb qualsevol creixement proporcional.

Podem fins i tot observar el redimensionament des de fora amb sys.getsizeof, que dona els bytes que ocupa l'objecte:

Sortida típica (varia segons la versió de Python):

La mida no creix amb cada append, sinó a salts: cada salt és una reserva de capacitat extra, i entre salt i salt els append no demanen memòria. És el redimensionament amortitzat vist en directe.

Dos parents de la list que convé conèixer, només com a menció:

• array.array (mòdul de la biblioteca estàndard): array dinàmic homogeni que desa els números en si (no referències), estalviant força memòria quan tens milions de valors del mateix tipus.
• NumPy (numpy.ndarray): la llibreria estàndard del càlcul numèric; arrays homogenis, compactes i amb operacions vectoritzades enormement ràpides. Si algun dia TaskFlow calculés estadístiques sobre milions de registres de temps, NumPy seria l'eina. Queda fora d'aquest curs, però has de saber que existeix i que per dins és... un array contigu, com tot el d'aquesta lliçó.

Tanquem aplicant el criteri al nostre projecte. El tauler de TaskFlow, versió array (list):

Per a aquests tres usos —afegir al final, llistar en ordre, accedir per posició— la list és la tria correcta, i cap estructura del curs no la superarà en això. Que sigui la primera opció per defecte en Python està justificat.

Però mira què passa amb dos altres casos d'ús reals de TaskFlow:

Amb 50 tasques, res d'això no importa. Però imagina la llista d'activitat global d'un TaskFlow corporatiu amb centenars de milers d'entrades on el més normal és inserir per davant i esborrar pel mig: cada operació desplaçaria centenars de milers de referències. El diagnòstic, amb el vocabulari que ja domines:

I si existís una estructura on inserir o esborrar al mig no desplacés res, perquè els elements no viuen contigus sinó enllaçats els uns amb els altres, cadascun allà on li hagi tocat a la memòria? Existeix: és la llista enllaçada, l'altra gran aposta —dispersió en lloc de contigüitat— i el tema del mòdul 2. Com és de justícia, tindrà els seus propis costos: en perdre la contigüitat es perd la fórmula màgica de l'accés O(1). No hi ha dinars gratis; hi ha eleccions informades.

• Creure que la list de Python és una llista enllaçada. El nom enganya: és un array dinàmic. Aquest malentès porta a assumir que inserir al principi és barat, quan és O(n). Al mòdul 2 la comparació quedarà cristal·lina.
• Usar llista.insert(0, x) o llista.pop(0) dins de bucles. És l'O(n²) accidental més comú de Python: n operacions O(n). Si necessites afegir i treure per davant habitualment, hi ha una estructura pensada per a això (collections.deque, que estudiarem al mòdul 4).
• Alarmar-se pel pic del redimensionament. Que un append ocasional costi O(n) gairebé mai no és un problema real: l'amortitzat O(1) és el que compta a la pràctica. Només en sistemes amb restriccions estrictes de latència importen els pics.
• Ignorar la memòria de reserva. Un array dinàmic pot tenir fins al doble de caselles de les que usa. Amb milions d'elements numèrics, array.array o NumPy redueixen dràsticament el consum davant de list.
• Consell: davant de qualsevol estructura nova, pregunta sempre "és contigua o dispersa per dins?". La resposta et dirà, sense mirar documentació, quines operacions seran barates (accés si és contigua; reorganització si és dispersa) i quines cares.

Un array d'enters de 8 bytes comença a l'adreça 5000. (a) A quina adreça és l'element d'índex 12? (b) Si un element és a l'adreça 5096, quin índex té? (c) Explica en una frase per què aquesta fórmula deixa de funcionar si els elements ocupessin mides diferents.

Partint de l'array [10, 20, 30, 40, 50] (capacitat 8, 5 caselles usades), indica quants elements es desplacen en cada operació i l'estat final de l'array després d'aplicar-les en ordre: (a) insert(0, 5); (b) append(60); (c) esborrar l'element d'índex 2; (d) insert(3, 35).

Escriu un programa que compari amb timeit construir una llista de 50.000 elements de dues maneres: (a) amb append (afegint al final) i (b) amb insert(0, x) (afegint al principi). Prediu abans d'executar quina serà més lenta i per què, i comprova si la diferència creix en passar a 100.000 elements.

Solució 1:

• (a) 5000 + 12 × 8 = 5096.
• (b) (5096 − 5000) / 8 = 12: el mateix element de l'apartat anterior, calculat a la inversa.
• (c) La fórmula multiplica l'índex per una mida fixa; amb mides variables no es pot calcular on comença l'element i sense recórrer i sumar les mides de tots els anteriors (per això la list de Python desa referències de mida fixa als objectes, no els objectes en si).

Solució 2:

• (a) insert(0, 5): es desplacen els 5 elements → [5, 10, 20, 30, 40, 50].
• (b) append(60): se'n desplacen 0 (hi ha forat lliure, capacitat 8) → [5, 10, 20, 30, 40, 50, 60].
• (c) esborrar l'índex 2 (el valor 20): es desplacen a l'esquerra els 4 posteriors → [5, 10, 30, 40, 50, 60].
• (d) insert(3, 35): es desplacen els 3 elements des de l'índex 3 → [5, 10, 30, 35, 40, 50, 60].

Moralitat de l'exercici: el cost de cada operació depèn de quants elements queden a la dreta del punt de modificació; per això el pitjor cas és sempre el principi.

Solució 3:

Predicció: la versió (b) serà molt més lenta, perquè cada insert(0, x) desplaça tots els elements ja presents: el cost total és 0 + 1 + 2 + ... + (n−1) ≈ n²/2 desplaçaments, és a dir, O(n²); la versió (a) són n append d'O(1) amortitzat, o sigui O(n) total.

Resultat típic: amb 50.000 elements, append triga mil·lèsimes i insert(0, ...) de l'ordre de segons; en duplicar a 100.000, append es duplica (lineal) però insert(0, ...) es quadruplica (quadràtica), confirmant la predicció. És la física de l'array —els desplaçaments— manifestant-se exactament com la teoria anuncia.

Has arribat al fons de la qüestió: la memòria és una filera de caselles numerades d'accés directe, i l'array —dades contigües, caselles iguals— explota aquesta organització per oferir accés per índex O(1) mitjançant una simple fórmula, pagant-ho amb desplaçaments O(n) en inserir o esborrar al mig. Els arrays dinàmics afegeixen creixement automàtic amb redimensionament proporcional, el cost repartit del qual dona el famós append O(1) amortitzat; i la list de Python és exactament això, amb array.array i NumPy com a variants compactes per a dades numèriques massives. Per a TaskFlow, l'array és perfecte com a tauler que creix pel final i es llegeix en ordre, i es queda curt quan abunden les insercions i els esborrats per davant o pel mig.

Amb això es tanca el mòdul 1: ja saps què és una estructura de dades, per què importa triar-la bé, quines famílies existeixen, com mesurar-ne l'eficiència amb Big O i sobre quina base física es construeix tot. Al mòdul 2 comencem a construir de veritat: la llista enllaçada, la primera estructura que fabricarem des de zero, que renuncia a la contigüitat precisament per fer barates les operacions on l'array fluixeja, i que convertirem en el tauler de tasques definitiu de TaskFlow.