|
|
|
|
|
|
|
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.
|
|
|
|
|
|
|