Cap. 26 - Colas (Queues)

Este capítulo presenta dos TDAs: la Cola y la Cola de Prioridad. - En la vida real, una cola es una línea de personas esperando por algo. - En la mayor parte de los casos, la primera persona en llegar es la primera en ser atendida. - Pero hay excepciones: en los aeropuertos, las personas cuyos vuelos están por salir muchas veces son tomadas del medio de la cola. En un supermercado, una persona educada puede permitir que alguien que lleva sólo unas pocas cosas pase primero. La regla que determina quién va primero se conoce como la política de colas. - La más simple política de colas se llama "Primero que entra, primero que sale" (FIFO por sus siglas en inglés: "First In, First Out"). - La política más general es la política de prioridad para colas, en la que a cada persona se asigna una prioridad y la persona con la mayor prioridad sale primero, sin importar su orden de llegada. - Decimos que esta política es la general porque la prioridad puede basarse en cualquier cosa: a qué hora sale el próximo vuelo, cuántos productos lleva la persona en su carrito de supermercado, cuán importante es la persona. - Por supuesto, no todas las políticas de prioridad son justas, pero determinar qué es justo escapa a nuestro asunto. El TDA Cola y el TDA Cola de Prioridad tienen el mismo conjunto de operaciones. La diferencia está en la semántica de las operaciones: una cola usa la política FIFO, y una cola de prioridad (como sugiere el nombre) usa una política de prioridad para colas.

26.1) El TDA Cola

El TDA Cola es definido por las siguientes operaciones: __init__ Inicializa una nueva cola vacía. insertar Agregar un nuevo item a la cola. remover Quitar y retornar un item de la cola. El item que es retornado es el primero que fue agregado. es_vacia Verifica si la cola está vacía.

26.2) Cola enlazada (Linked Queue)

La primera implementación del TDA Cola que veremos se llama Cola enlazada porque está formada de objetos Nodo enlazados. Aquí está la definición de clase: class Cola: def __init__(self): self.largo = 0 self.cabeza = None def es_vacia(self): return self.largo == 0 def insertar(self, cargo): nodo = Nodo(cargo) if self.cabeza is None: # Si la lista está vacía el nuevo nodo va primero self.cabeza = nodo else: # Encontrar el último nodo de la lista ultimo = self.cabeza while ultimo.next: ultimo = ultimo.next # Agregar el nuevo nodo al final ultimo.next = nodo self.largo += 1 def remover(self): cargo = self.cabeza.cargo self.cabeza = self.cabeza.next self.largo -= 1 return cargo Los métodos es_vacia y remover son idénticos a los similares que vimos para ListaEnlazada. (pendiente: en realidad no los vimos - sería bueno mejorar ListaEnlazada vista en el capítulo 24) - El método insertar es nuevo y un poco más complicado. Queremos insertar nuevos items al final de la lista. Si la cola es vacía, simplemente hacemos que la cabeza se refiera al nuevo nodo. En caso contrario, recorremos la lista hasta el último nodo y ubicamos al nuevo nodo al final. Podemos identificar al último nodo porque su atributo next será vacío. Hay dos invariantes para un objeto Cola bien formado. - El valor de largo debería ser la cantidad de nodos que hay en la cola, y el último nodo debería tener next igual a None. - Vale la pena que te tomes un tiempo para convencerte de que el método insertar que hemos implementado conserva ambos invariantes. - Observación: esto es así, siempre y cuando no ocurra que se origine un loop en la cola, lo que de todas formas correspondería al caso en que ya no es una cola "bien formada".

26.3) Características de rendimiento (performance)

Habitualmente cuando llamamos a un método no nos interesan los detalles de su implementación. - Pero hay un detalle que nos puede interesar: las características de performance del método. - ¿Cuánto tiempo lleva, y cómo cambia el tiempo necesario a medida que la cantidad de items en la colección crece? Primero veamos el método remover. No hay loops ni llamados a funciones aquí, lo que sugiere que el tiempo de ejecución de este método será siempre más o menos el mismo. - Un método de este tipo es llamado operación de tiempo constante. - En realidad, el método puede ser ligeramente más rápido cuando la lista es vacía dado que se salta el cuerpo del condicional, pero no es una diferencia significativa. En cambio, la performance de insertar es muy distinta. En el caso general, tenemos que recorrer toda la lista para encontrar el último elemento. Esta recorrida lleva un tiempo proporcional al largo de la lista. - Dado que el tiempo de ejecución es una función lineal del largo, este método es llamado operación de tiempo lineal. - Comparado con una operación de tiempo constante, es muy lenta (y por lo tanto muy mala).

26.4) Cola enlazada mejorada

Querríamos implementar un TDA Cola capaz de realizar todas sus operaciones en tiempo constante. - Una forma de conseguirlo es modificar la clase Cola para que mantenga una referencia tanto al primer como al último nodo, como se muestra en la figura: La implementación de ColaMejorada se ve así: class ColaMejorada: def __init__(self): self.largo = 0 self.cabeza = None self.ultimo = None def es_vacia(self): return self.largo == 0 Hasta aquí, el único cambio fue el atributo ultimo. Se usa en los métodos insertar y remover: class ColaMejorada: . . . def insertar(self, cargo): nodo = Nodo(cargo) if self.largo == 0: # Si la lista está vacía, el nuevo nodo es cabeza y ultimo self.cabeza = self.ultimo = None else: # Encontrar el último nodo ultimo = self.ultimo # Agregar el nuevo nodo ultimo.next = nodo self.ultimo = nodo self.largo += 1 Como ultimo lleva la cuenta del último nodo, no tenemos que buscarlo. Como consecuencia, este método es de tiempo constante. Pagamos un precio por esa velocidad. Tenemos que agregar un caso especial a remover para setear ultimo a None cuando el último nodo es eliminado: class ColaMejorada: . . . def remover(self): cargo = self.cabeza.cargo self.cabeza = self.cabeza.next self.largo -= 1 if self.largo == 0: self.ultimo = None return cargo Esta implementación es más complicada que la de Cola Enlazada, y es más difícil demostrar que es correcta. - Su ventaja es que nos ha permitido cumplir con la meta de que tanto insertar como remover sean operaciones de tiempo constante.

26.5) Cola de prioridad

El TDA Cola de prioridad tiene la misma interfaz que el TDA Cola, pero la semántica es distinta. Una vez más, la interfaz es: __init__ Inicializa una nueva cola vacía. insertar Agregar un nuevo item a la cola. remover Quitar y retornar un item de la cola. El item que es retornado es el que tiene mayor prioridad. es_vacia Verifica si la cola está vacía. La diferencia semántica es que el item que se elimina de la cola no es necesariamente el primero que se agregó. Es el item en la cola que tiene mayor prioridad. - Qué son las prioridades y cómo se comparan entre sí no se especifica en la implementación de la Cola de Prioridad. Depende de cuáles son los elementos de la cola. Por ejemplo, si los items en la cola tienen nombres, podemos elegirlos en orden alfabético. - Si son puntajes de bowling, podemos ir del mayor al menor, pero si son puntajes de golf, podemos ir del menor al mayor. - Siempre que podamos comparar a los items de la cola entre sí, podremos encontrar y remover el que tenga mayor prioridad. La implementación de una Cola de Prioridad tiene como atributo una lista de Python que contiene los items de la cola. class ColaPrioridad: def __init__(self): self.items = [] def es_vacia(self): return not self.items def insertar(self, item): self.items.append(item) El método de inicialización, es_vacia e insertar son enchapados sobre las operaciones de listas. El único método interesante es remover: class ColaPrioridad: . . . def remover(self): maxi = 0 for i in range(1, len(self.items)): if self.items[i] > self.items[maxi]: maxi = i item = self.items[maxi] del self.items[maxi] return item Al principio de cada iteración, maxi tiene el índice del mayor ítem (el de máxima prioridad) que se ha encontrado hasta ese momento. - En cada paso del loop, el programa compara el i-ésimo ítem con el campeón. Si el nuevo item es mayor, el valor de maxi se setea a i. Cuando se completa la sentencia for, maxi es el índice del ítem más grande. Este item es quitado de la lista y retornado. Testeemos la implementación: >>> q = ColaPrioridad() >>> for num in [11, 14, 13, 12]: ... q.insertar(num) ... >>> while not q.es_vacia(): ... print(q.remover()) ... 14 13 12 11 Si la cola contiene números o strings, serán quitados en orden numérico o alfabético, desde el mayor al menor. - Python puede encontrar el mayor entero o string porque puede compararlos utilizando los operadores de comparación incorporados (built-in). Si la cola contiene un objeto, éste deberá proveer un método __gt__. - Cuando remover usa el operador > para comparar items, llama al método __gt__ para uno de los items y pasa el otro como parámetro. - Siempre que __gt__ funcione correctamente, la ColaPrioridad también lo hará.

26.6) La clase Golfista

Como ejemplo de un objeto con una definición inusual de prioridad, implementemos una clase llamada Golfista que lleva la cuenta de los nombres y puntajes de varios golfistas. - Como siempre, comenzamos definiendo __init__ y __str__. class Golfista: def __init__(self, name, puntaje): self.name = name self.puntaje = puntaje def __str__(self): return "{0:16}: {1}".format(self.name, self.puntaje) El método __str__ utiliza al método format (de string) para poner los nombres y puntajes en dos columnas. Ahora definimos una versión de __gt__ en que los puntajes más bajo obtienen la mayor prioridad. - Como siempre, __gt__ retorna True si self es mayor que otro, y falso en caso contrario. class Golfista: . . . def __gt__(self, otro): return self.puntaje < otro.puntaje # Menos es más Ahora podemos testear la cola de prioridad con la clase Golfista: >>> tiger = Golfista("Tiger Woods", 61) >>> phil = Golfista("Phil Mickelsson", 72) >>> hal = Golfista("Hal Sutton", 69) >>> >>> cp = ColaPrioridad() >>> for g in [tiger, phil, hal]: ... cp.insertar(g) ... >>> while not cp.es_vacia(): ... print(cp.remover()) ... Tiger Woods : 61 Hal Sutton : 69 Phil Mickelsson : 72

26.7) Glosario

- tiempo constante, tiempo lineal, cola, cola enlazada, cola de prioridad, política de cola, TDA Cola, TDA Cola de Prioridad - FIFO (First In, First Out; primero que entra, primero que sale)

26.8) Ejercicios

1) Escribir una implementación del TDA Cola que use una lista Python. Comparar la performance de esta implementación con la de ColaMejorada para un rango de largos de cola. (hacerlo) 2) Escribir una implementación del TDA Cola de Prioridad que use una lista enlazada. (hacerlo) - Deberías mantener la lista ordenada de modo que la remoción sea una operación de tiempo constante. - Comparar la performance de esta implementación con la implementación basada en listas (comunes) de Python. (hacerlo)