Compromís espai-temps

Una compensació espai-temps, també coneguda com a compensació temps-memoria o continu algorítmic espai-temps en informàtica, és un cas en què un algorisme o programa intercanvia un ús més gran de l'espai amb una disminució del temps. Aquí, l'espai fa referència a l'emmagatzematge de dades consumit en realitzar una tasca determinada (RAM, HDD, etc.), i el temps fa referència al temps consumit en realitzar una tasca determinada (temps de càlcul o temps de resposta).^[1]

La utilitat d'un determinat equilibri espai-temps es veu afectada pels costos fixos i variables relacionats (per exemple, la velocitat de la CPU, l'espai d'emmagatzematge) i està subjecta a rendiments decreixents.^[2]

Història

L'ús biològic de les compensacions temps-memòria es pot veure en les primeres etapes del comportament animal. L'ús del coneixement emmagatzemat o la codificació de reaccions d'estímuls com a "instints" a l'ADN evita la necessitat de "càlculs" en situacions crítiques de temps. Més específicament per als ordinadors, les taules de cerca s'han implementat des dels primers sistemes operatius.

Tipus de compensació

Taules de cerca vs. recàlcul

Una situació habitual és un algorisme que implica una taula de cerca: una implementació pot incloure la taula sencera, la qual cosa redueix el temps de càlcul, però augmenta la quantitat de memòria necessària, o pot calcular les entrades de la taula segons sigui necessari, augmentant el temps de càlcul, però reduint els requisits de memòria.^[3]

Índexs de bases de dades versus exploracions de taules

Els sistemes de gestió de bases de dades ofereixen la capacitat de crear estructures de dades d'índex de bases de dades. Els índexs milloren la velocitat de les operacions de cerca a costa d'espai addicional. Sense índexs, de vegades es requereixen operacions d'exploració de taula completa que requereixen temps per localitzar les dades desitjades.

Dades comprimides vs. no comprimides

Es pot aplicar una compensació espai-temps al problema de l'emmagatzematge de dades. Si les dades s'emmagatzemen sense comprimir, ocupen més espai, però l'accés triga menys que si les dades s'emmagatzemen comprimides (ja que comprimir les dades redueix la quantitat d'espai que ocupa, però es necessita temps per executar l'algorisme de descompressió). Depenent de la instància concreta del problema, qualsevol de les maneres és pràctica. També hi ha casos excepcionals en què és possible treballar directament amb dades comprimides, com en el cas dels índexs de mapes de bits comprimits, on és més ràpid treballar amb compressió que sense compressió.

Tornar a renderitzar vs. imatges emmagatzemades

Emmagatzemar només la font SVG d'una imatge vectorial i representar-la com a imatge de mapa de bits cada vegada que es sol·licita la pàgina seria intercanviar temps per espai; més temps utilitzat, però menys espai. Renderitzar la imatge quan es canvia la pàgina i emmagatzemar les imatges renderitzades seria intercanviar espai per temps; més espai utilitzat, però menys temps. Aquesta tècnica es coneix més generalment com a memòria cau.

Codi més petit vs. desenrotllament de bucle

Es pot canviar una mida de codi més gran per una velocitat de programa més alta quan s'aplica el desenrotllament del bucle. Aquesta tècnica fa que el codi sigui més llarg per a cada iteració d'un bucle, però estalvia el temps de càlcul necessari per tornar al començament del bucle al final de cada iteració.^[4]

Altres exemples

Els algorismes que també fan ús de compensacions espai-temps inclouen:

• Algorisme de passos gegants baby-step per calcular logaritmes discrets.
• Taules de l'arc de Sant Martí en criptografia, on l'adversari intenta fer-ho millor que el temps exponencial necessari per a un atac de força bruta. Les taules Rainbow utilitzen valors parcialment precalculats a l'espai hash d'una funció hash criptogràfica per trencar contrasenyes en minuts en lloc de setmanes. Disminuir la mida de la taula de l'arc de Sant Martí augmenta el temps necessari per iterar sobre l'espai hash.
• L' atac de trobada al mig utilitza una compensació espai-temps per trobar només la clau criptogràfica ${\displaystyle 2^{n+1}}$ xifratge (i espai ${\displaystyle O(2^{n})}$) enfront de l'esperat ${\displaystyle 2^{2n}}$ xifratge (però només espai ${\displaystyle O(1)}$) de l'atac ingenu.
• Programació dinàmica, on la complexitat temporal d'un problema es pot reduir significativament utilitzant més memòria.
• Atac de compensació temps/memoria/dades que utilitza la compensació espai-temps amb el paràmetre addicional de dades.

Referències

1. «Time-Space Trade-Off in Algorithms» (en anglès americà), 29-10-2020. [Consulta: 17 maig 2024].
2. «Space–Time Tradeoffs» (en anglès). [Consulta: 17 maig 2024].
3. «Chapter 7: Space-for-time tradeoffs» (en anglès). [Consulta: 17 maig 2024].
4. «Algorithm complexity and time space trade off | Data Structures Using C Tutorials | Teachics» (en anglès americà), 03-06-2020. [Consulta: 17 maig 2024].