4.1. Análisis del Consumo TotalConsideremos el programa Java que aparece en la Figura 4.1. Consisteen una serie de clases Java que definen una estructura de datos del tipoabstract class List {abstract List copy();}class Nil extends List {List copy() {return new Nil();}}class Cons extends List {int elem;List next;List copy(){Cons aux = new Cons();aux.elem = m(this.elem);aux.next = this.next.copy();return aux;}static int m(int n) {Integer aux = new Integer(n);return aux.intValue();}} // class ConsFigura 4.1: Ejemplo de consumo de memoria lista enlazada, implementada en un estilo fuertemente orientado a objetos.La clase Cons se utiliza para los nodos de datos (en este caso númerosenteros), y la clase Nil juega el papel de null para indicar el final de lalista. Tanto Cons como Nil heredan de la clase abstracta List. Aśı, losobjetos del tipo List pueden ser bien instancias de Cons o de Nil. Ambassubclases implementan el método copy, el cual se utiliza para clonar elobjeto correspondiente. En el caso de Nil, copy simplemente devuelve unanueva instancia de śı mismo, pues es el último elemento de la lista. En el casode Cons, se devuelve una instancia clonada donde el dato se clona invocandoal método estático m, y la continuación se clona llamando recursivamenteal método copy sobre el objeto next.Nuestro análisis de consumo del heap infiere relaciones de coste (sim-plificadas) para el método copy de la clase Cons:Ccopy(a) = 12, a = 1Ccopy(a) = 12 + Ccopy(a-1), a > 1las cuales se pueden resolver usando el resolutor de COSTA dando comoresultado la siguiente cota en forma cerrada:Ccopy(a) = 12*nat(a-1) + 12Se puede observar que el consumo de heap es lineal respecto al parámetrode entrada a, que se corresponde con el tamaño del objeto this del método,es decir, la longitud de la lista a clonar. Esto ocurre gracias a que la abstrac-ción utilizada por nuestro análisis para referencias a objetos es la longitudde la cadena de referencias más larga, que en este caso se corresponde conla longitud de la lista. La constante numérica 12 se obtiene sumando 8 y 4,siendo 8 el número de bytes ocupados por una instancia de la clase Cons,y 4 los bytes ocupados por una instancia de Integer. Nótese, que estamosaproximando el tamaño de los objetos como la suma de los tamaños de to-dos sus atributos. En particular, asumimos que, tanto un entero (integer)como una referencia ocupan 4 bytes.