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:
Referències
