|
|
|
|
|
|
|
Este cap�tulo presenta dos TADs: la Cola y la Cola Priorizada. En la vida real, una cola es una fila de clientes esperando un servicio de alg�n tipo. En la mayor�a de los casos, el primer cliente de la fila es el primero al que se va a servir. Sin embargo, hay excepciones. En los aeropuertos, a veces se saca de la cola a los clientes cuyos vuelos van a salir pronto. En los supermercados, un cliente educado puede dejar que alguien que lleva pocos productos pase antes.
La regla que determina qui�n va primero se llama t�ctica de encolamiento. La t�ctica de encolamiento m�s simple se llama FIFO, de "first-in-first-out", "el primero que entra es el primero que sale". La t�ctica de encolamiento m�s general es el encolamiento priorizado, en la que a cada cliente se le asigna una prioridad y el cliente con la prioridad m�s alta pasa primero, sin importar el orden de llegada. Decimos que es la t�ctica m�s general porque la prioridad se puede basar en cualquier cosa: a qu� hora sale el vuelo; cu�ntos productos lleva el cliente; cu�n importante es el cliente. Por supuesto, no todas las t�cticas de prioridad son "justas", pero la justicia siempre es subjetiva.
El TAD Cola y el TAD Cola Priorizada tienen el mismo conjunto de operaciones. La diferencia est� en la sem�ntica de las operaciones: una cola usa la t�ctica FIFO, y una cola priorizada (como su propio nombre indica) usa una t�ctica de encolamiento priorizado.
El TAD Cola se define a trav�s de las siguientes operaciones:
La primera implementaci�n del TAD Cola al que vamos a echar un vistazo se llama cola enlazada porque est� hecha de ojetos Nodoenlazados. He aqu� la definici�n de la clase:
class Cola:
def __init__(self):
self.longitud = 0
self.cabeza = None
def estaVacia(self):
return (self.longitud == 0)
def inserta(self, carga):
nodo = Nodo(carga)
nodo.siguiente = None
if self.cabeza == None:
# si la lista est� vac�a el nuevo nodo va el primero
self.cabeza = nodo
else:
# encuentra el �ltimo nodo de la lista
ultimo = self.cabeza
while ultimo.siguiente: ultimo = ultimo.siguiente
# a�adir el nuevo nodo
ultimo.siguiente = nodo
self.longitud = self.longitud + 1
def quita(self):
carga = self.cabeza.carga
self.cabeza = self.cabeza.siguiente
self.longitud = self.longitud - 1
return carga
Los m�todos estaVacia y quita son id�nticos a los m�todos estaVacia y quitaPrimero de ListaEnlazada. El m�todo inserta es nuevo y un poco m�s complicado.
Queremos insertar nuevos elementos al final de la lista. Si la cola est� vac�a, simplemente hacemos que cabeza se refiera al nuevo nodo.
En caso contrario, recorremos la lista hasta el �ltimo nodo y lo fijamos al final. Podemos reconocer el �ltimo nodo porque su atributo siguiente es None.
En un objeto Cola correctamente construido hay dos invariantes. El valor de longitud deber�a ser el n�mero de nodos en la cola, y el �ltimo nodo deber�a tener siguiente igual a None. Cr�ase que este m�todo cumple con ambas invariantes.
Normalmente cuando invocamos un m�todo, no nos importan los detalles de su implementaci�n. Pero hay un "detalle" que podr�a interesarnos: el rendimiento t�pico del m�todo. �Cu�nto tarda, y c�mo var�a el tiempo de ejecuci�n al aumentar el n�mero de elementos de la colecci�n?
Primero mire quita. Ah� no hay bucles ni llamadas a funciones, dando a entender que el tiempo de ejecuci�n de este m�todo es siempre el mismo. Un m�todo as� se llama operaci�n de tiempo constante. En realidad, el m�todo podr�a ser ligeramente m�s r�pido cuando la lista est� vac�a porque se salta el cuerpo de la condici�n, pero esa diferencia no es significativa.
El rendimiento de inserta es muy diferente. En el caso general, tenemos que recorrer la lista para encontrar el �ltimo elemento.
Este recorrido cuesta un tiempo proporcional a la longitud de la lista. Como el tiempo de ejecuci�n es funci�n lineal de la longitud, este m�todo se llama de tiempo lineal. Comparado con el tiempo constante, es muy pobre.
Nos gustar�a una implementaci�n del TAD Cola capaz de realizar todas las operaciones en tiempo constante. Una forma de hacerlo es modificar la clase Cola de modo que mantenga una referencia tanto al primero como al �ltimo nodo, como se muestra en la figura:
La implementaci�n de ColaMejorada es as�:
class ColaMejorada:
def __init__(self):
self.longitud = 0
self.cabeza = None
self.ultimo = None
def estaVacia(self):
return (self.longitud == 0)
Hasta ahora, el �nico cambio es el atributo ultimo. Se usa en los m�todos inserta y quita:
class ColaMejorada:
...
def inserta(self, carga):
nodo = Nodo(carga)
nodo.siguiente = None
if self.longitud == 0:
# si la lista est� vac�a, el nuevo nodo es cabeza y �ltimo
self.cabeza = self.ultimo = nodo
else:
# encontrar el �ltimo nodo
ultimo = self.ultimo
# a�adir el nuevo nodo
ultimo.siguiente = nodo
self.ultimo = nodo
self.longitud = self.longitud + 1
Como ultimo sigue el rastro del �ltimo nodo, no necesitamos buscarlo. A causa de esto, este m�todo funciona en tiempo constante.
Debemos pagar un precio por esa velocidad. Tenemos que a�adir un caso especial a quita para apuntar ultimo a None cuando quitamos el �ltimo nodo:
class ColaMejorada:
...
def quita(self):
carga = self.cabeza.carga
self.cabeza = self.cabeza.siguiente
self.longitud = self.longitud - 1
if self.longitud == 0:
self.ultimo = None
return carga
Esta implementaci�n es m�s complicada que la de la Lista Enlazada, y es m�s dif�cil demostrar que es correcta. La ventaja es que hemos alcanzado la meta: tanto inserta como quita son operaciones de tiempo constante.
Como ejercicio, escriba una implementaci�n del TAD Cola usando una lista de Python. Compare el rendimiento de esta implementaci�n con la de la ColaMejorada para varias longitudes de cola.
El TAD Cola Priorizada tiene el mismo interfaz que el TAD Cola, pero diferente sem�ntica. De nuevo, el interfaz es:
La diferencia sem�ntica es que el elemento eliminado de la cola no es necesariamente el primero que se a�adi�. En su lugar, es el elemento con la prioridad m�s alta. Lo que son las prioridades y c�mo se comparan con las otras no se especifica en la implementaci�n de la Cola Priorizada. Depende de los elementos de la cola.
Por ejemplo, si los elementos de la cola tienen nombres, podemos elegirlos en orden alfab�tico. Si son puntuaciones de bolos, podemos ir de mayor a menor, pero si son puntuaciones de golf, iremos de menor a mayor. Siempre que podamos comparar los elementos de la cola, podremos encontrar y quitar el elemento con mayor prioridad.
Esta implementaci�n de Cola Priorizada tiene como atributo una lista de Python que contiene los elementos de la cola.
class ColaPriorizada:
def __init__(self):
self.elementos = []
def estaVacia(self):
return self.elementos == []
def inserta(self, elemento):
self.elementos.append(elemento)
El m�todo de inicializaci�n, estaVacia, e inserta son todos calcados de las operaciones sobre listas. El �nico m�todo interesante es quita:
class ColaPriorizada:
...
def quita(self):
maxi = 0
for i in range(1,len(self.elementos)):
if self.elementos[i] > self.elementos[maxi]:
maxi = i
elemento = self.elementos[maxi]
self.elementos[maxi:maxi+1] = []
return elemento
Al principio de cada iteraci�n, maxi contiene el �ndice del elemento m�s grande (prioridad m�s alta) que hemos visto hasta el momento. Cada vez que se completa el bucle, el programa compara el i�simo elemento con el campe�n. Si el nuevo elemento es mayor, el valor de maxi se fija a i.
Cuando la sentencia for completa su ejecuci�n, maxi es el �ndice del elemento mayor. Este elemento se elimina de la lista y se devuelve.
Vamos a probar la implementaci�n:
>>> c = ColaPriorizada()
>>> c.inserta(11)
>>> c.inserta(12)
>>> c.inserta(14)
>>> c.inserta(13)
>>> while not c.estaVacia(): print c.quita() # ver cu�l se quita
14
13
12
11
Si la cola contiene n�meros o cadenas simples, se eliminan en orden num�rico o alfab�tico, de mayor a menor. Python puede encontrar el entero o la cadena mayor porque puede compararlos usando los operadores de comparaci�n internos.
Si la cola contiene un tipo de objeto, debe proporcionar un m�todo __cmp__. Cuando quita usa el operador > para comparar elementos, invoca al __cmp__ de uno de los elementos y le pasa el otro como par�metro. Siempre que el m�todo __cmp__trabaje adecuadamete, la Cola Priorizada funcionar�.
Como ejemplo de un objeto con una definici�n inusual de prioridad, vamos a implementar una clase llamada Golfista que mantiene los nombres y puntuaciones de golfistas. Como es habitual, empezamos por definir __init__ y __str__:
class Golfista:
def __init__(self, nombre, puntos):
self.nombre = nombre
self.puntos = puntos
def __str__(self):
return "%-16s: %d" % (self.nombre, self.puntos)
__str__ usa el operador de formato para poner los nombres y las puntuaciones en bonitas columnas.
A continuaci�n definimos una versi�n de __cmp__ en la que la puntuaci�n m�s baja tiene la prioridad m�s alta. Como siempre, __cmp__ devuelve 1 si self es "mayor que" otro, -1 si selfes "menor que" otro, y 0 si son iguales.
class Golfista:
...
def __cmp__(self, otro):
if self.puntos < otro.puntos: return 1 # menos es m�s
if self.puntos > otro.puntos: return -1
return 0
Ya estamos listos para probar la cola priorizada con la clase Golfista:
>>> tiger = Golfista("Tiger Woods", 61)
>>> cabr = Golfista("�ngel Cabrera", 72)
>>> ola = Golfista("J.M. Olaz�bal", 69)
>>>
>>> cp = ColaPriorizada()
>>> cp.inserta(tiger)
>>> cp.inserta(cabr)
>>> cp.inserta(ola)
>>> while not cp.estaVacia(): print cp.quita()
Tiger Woods : 61
J.M. Olaz�bal : 69
�ngel Cabrera : 72
Como ejercicio, escriba una implementaci�n del TAD Cola Priorizada usando una lista enlazada. Deber�a usted mantener la lista ordenada de modo que la eliminaci�n sea una operaci�n de tiempo constante. Compare el rendimiento de esta implementaci�n con la implementaci�n con la lista de Python.
|
|
|
|
|
|
|