03 octubre 2009

Memory Limit Exceeded

Este es un pequeño truco para saber cuánta memoria ocupan las estructuras estáticas de nuestro programa. Esto es útil para competiciones de programación y podemos evitarnos el típico error de Memory Limit Exceeded.

Si definimos una array global en C y C++ por defecto está a 0.


typedef struct {
int x1, x2;
int y1, y2;
int area;
int valid;
int color;
} RECT;
RECT rects[500000]; // todo a 0


Si compilamos el programa así (añadiendo un main y todo eso). El ejecutable ocupa 11KB.

Pero en cambio si inicializamos aunque sólo sea un valor de la estructura


typedef struct {
int x1, x2;
int y1, y2;
int area;
int valid;
int color;
} RECT;
RECT rects[500000] = {{1,1,1,1,1,1,1}}; // inicializar el primer elemento


Al compilar ahora el programa el ejecutable contiene la estructura completa y ocupa 14MB.

Si inicializamos a 0 el ejecutable no aumenta de tamaño y se queda en 11K. Tiene que ser un valor distinto de 0.


RECT rects[500000] = {{0,0,0,0,0,0,0}};


Yo utilizo este pequeño "truco" para ver si el programa cumple los requisitos de memoria en la USACO o la UVa antes de enviarlo. También puedes calcularlo a mano pero yo soy más vago para eso...

Como curiosidad: Descubrí esto hace un montón de años cuando al enviar un programa a la USACO, el servidor de la USACO murió y no volvió a funcionar hasta 30 minutos después. Cuando miré el programa resulta que me había generado un ejecutable de más de 1GB.