|
|
|
|
|
|
|
Questo capitolo presenta due tipi di dati astratti (TDA): la Coda e la Coda con priorità. Nella vita reale un esempio di coda può essere la linea di clienti in attesa di un servizio di qualche tipo. Nella maggior parte dei casi il primo cliente della fila è quello che sarà servito per primo, anche se ci possono essere delle eccezioni. All'aeroporto ai clienti il cui volo sta per partire può essere concesso di passare davanti a tutti, indipendentemente dalla loro posizione nella fila. Al supermercato un cliente può scambiare per cortesia il suo posto con qualcuno che deve pagare solo pochi prodotti.
La regola che determina chi sarà il prossimo ad essere servito si chiama politica di accodamento. Quella più semplice è la FIFO ("first in, first out") dove il primo che arriva è il primo ad essere servito. La politica di accodamento più generale è l' accodamento con priorità dove a ciascun cliente è assegnata una priorità ed il cliente con la massima priorità viene servito per primo indipendentemente dall'ordine di arrivo. Diciamo che questa politica di accodamento è la più generale perché la priorità può essere basata su qualsiasi fattore: l'orario di partenza dell'aereo, la quantità di prodotti da pagare ad una cassa, l'importanza del cliente (!), la gravità dello stato di un paziente al pronto soccorso. Logicamente non tutte le politiche di accodamento sono "giuste"...
I tipi di dati astratti Coda e Coda con priorità condividono lo stesso insieme di operazioni. La differenza sta soltanto nella loro semantica: una Coda usa la politica FIFO, mentre la Coda con priorità, come suggerisce il nome stesso, usa la politica di accodamento con priorità.
Il TDA Coda è definito dalle operazioni seguenti:
La prima implementazione del TDA Coda a cui guarderemo è chiamata coda linkata perché è composta di oggetti Nodo linkati. Ecco una definizione della classe:
class Coda:
def __init__(self):
self.Lunghezza = 0
self.Testa = None
def EVuota(self):
return (self.Lunghezza == 0)
def Inserimento(self, Contenuto):
NodoAggiunto = Nodo(Contenuto)
NodoAggiunto.ProssimoNodo = None
if self.Testa == None:
# se la lista e' vuota il nodo e' il primo
self.Testa = Nodo
else:
# trova l'ultimo nodo della lista
Ultimo = self.Testa
while Ultimo.ProssimoNodo: Ultimo = Ultimo.ProssimoNodo
# aggiunge il nuovo nodo
Ultimo.ProssimoNodo = NodoAggiunto
self.Lunghezza = self.Lunghezza + 1
def Rimozione(self):
Contenuto = self.Testa.Contenuto
self.Testa = self.Testa.ProssimoNodo
self.Lunghezza = self.Lunghezza - 1
return Contenuto
I metodi EVuota e Rimozione sono identici a quelli usati in ListaLinkata. Il metodo Inserimento è nuovo ed un po' più complicato.
Vogliamo inserire nuovi elementi alla fine della lista: se la coda è vuota facciamo in modo che Testa si riferisca al nuovo nodo.
Altrimenti attraversiamo la lista fino a raggiungere l'ultimo nodo e attacchiamo a questo il nuovo nodo. Possiamo identificare facilmente l'ultimo nodo della lista perché è l'unico il cui attributo ProssimoNodo vale None.
Ci sono due invarianti per un oggetto Coda ben formato: il valore di Lunghezza dovrebbe essere il numero di nodi nella coda e l'ultimo nodo dovrebbe avere l'attributo ProssimoNodo uguale a None. Prova a studiare il metodo implementato verificando che entrambi gli invarianti siano sempre soddisfatti.
Normalmente quando invochiamo un metodo non ci interessa quali siano i dettagli della sua implementazione. Ma c'è uno di questi dettagli che invece dovrebbe interessarci: le performance del metodo. Quanto impiega ad essere eseguito? Come cambia il tempo di esecuzione man mano che la collezione aumenta di dimensioni?
Diamo un'occhiata a Rimozione. Non ci sono cicli o chiamate a funzione, e ciò suggerisce che il tempo di esecuzione sarà lo stesso ogni volta. Questo tipo di metodo è definito operazione a tempo costante. In realtà il metodo potrebbe essere leggermente più veloce quando la lista è vuota dato che tutto il corpo della condizione viene saltato, ma la differenza in questo caso non è molto significativa e può essere tranquillamente trascurata.
La performance di Inserimento è molto diversa. Nel caso generale dobbiamo attraversare completamente la lista per trovarne l'ultimo elemento.
Questo attraversamento impiega un tempo che è proporzionale alla grandezza della lista: dato che il tempo di esecuzione in funzione lineare rispetto alla lunghezza, diciamo che questo metodo è un'operazione a tempo lineare. Se confrontato ad un'operazione a tempo costante il suo comportamento è decisamente peggiore.
Logicamente un'implementazione del TDA Coda che può eseguire tutte le operazioni in un tempo costante è preferibile, dato che in questo caso il tempo di esecuzione è indipendente dalla grandezza della lista elaborata. Un modo per fare questo è quello di modificare la classe Coda per fare in modo che venga tenuta traccia tanto del primo che dell'ultimo elemento della lista, come mostrato in questa figura:
L'implementazione di CodaMigliorata potrebbe essere:
class CodaMigliorata:
def __init__(self):
self.Lunghezza = 0
self.Testa = None
self.UltimoNodo = None
def EVuota(self):
return (self.Lunghezza == 0)
Finora l'unico cambiamento riguarda l'aggiunta dell'attributo UltimoNodo.
Questo attributo è usato dai metodi Inserimento e Rimozione:
class CodaMigliorata:
...
def Inserimento(self, Contenuto):
NodoAggiunto = Nodo(Contenuto)
NodoAggiunto.ProssimoNodo = None
if self.Lunghezza == 0:
# se la lista e' vuota il nuovo nodo e'
# sia la testa che la coda
self.Testa = self.UltimoNodo = NodoAggiunto
else:
# trova l'ultimo nodo
Ultimo = self.UltimoNodo
# aggiunge il nuovo nodo
Ultimo.ProssimoNodo = NodoAggiunto
self.UltimoNodo = NodoAggiunto
self.Lunghezza = self.Lunghezza + 1
Dato che UltimoNodo tiene traccia dell'ultimo nodo non dobbiamo più attraversare la lista per cercarlo. Come risultato abbiamo fatto diventare questo metodo un'operazione a tempo costante.
Comunque dobbiamo pagare un prezzo per questa modifica: quando dobbiamo rimuovere l'ultimo nodo con Rimozione dovremo assegnare None a UltimoNodo:
class CodaMigliorata:
...
def Rimozione(self):
Contenuto = self.Testa.Contenuto
self.Testa = self.Testa.ProssimoNodo
self.Lunghezza = self.Lunghezza - 1
if self.Lunghezza == 0:
self.UltimoNodo = None
return Contenuto
Questa implementazione è più complessa di quella della coda linkata ed è più difficile dimostrare che è corretta, Il vantaggio che abbiamo comunque ottenuto è l'aver reso sia Inserimento che Rimozione operazioni a tempo costante.
Esercizio: scrivi un'implementazione del TDA Coda usando una lista di Python. Confronta le performance di questa implementazione con quelle di CodaMigliorata per una serie di lunghezze diverse della coda.
Il TDA Coda con priorità ha la stessa interfaccia del TDA Coda ma una semantica diversa. L'interfaccia è sempre:
La differenza di semantica è che l'elemento da rimuovere non è necessariamente il primo inserito in coda, ma quello che ha la priorità più alta. Cosa siano le priorità e come siano implementate sono fatti non specificati dall'implementazione, dato che questo dipende dal genere di elementi che compongono la coda.
Per esempio se gli elementi nella coda sono delle stringhe potremmo estrarle in ordine alfabetico. Se sono punteggi del bowling dal più alto al più basso, e viceversa nel caso del golf. In ogni caso possiamo rimuovere l'elemento con la priorità più alta da una coda soltanto se i suoi elementi sono confrontabili tra di loro.
Questa è un'implementazione di una coda con priorità che usa una lista Python come attributo per contenere gli elementi della coda:
class CodaConPriorita:
def __init__(self):
self.Elementi = []
def EVuota(self):
return self.Elementi == []
def Inserimento(self, Elemento):
self.Elementi.append(Elemento)
I metodi __init__, EVuota e Inserimento sono tutte maschere delle operazioni su liste. L'unico metodo "interessante" è Rimozione:
class CodaConPriorita:
...
def Rimozione(self):
Indice = 0
for i in range(1,len(self.Elementi)):
if self.Elementi[i] > self.Elementi[Indice]:
Indice = i
Elemento = self.Elementi[Indice]
self.Elementi[Indice:Indice+1] = []
return Elemento
All'inizio di ogni iterazione Indice contiene l'indice dell'elemento con priorità massima. Ad ogni ciclo viene confrontato questo elemento con l'i-esimo elemento della lista: se il nuovo elemento ha priorità maggiore (nel nostro caso è maggiore), il valore di Indice diventa i.
Quando il ciclo for è stato completato Indice è l'indice dell'elemento con priorità massima. Questo elemento è rimosso dalla lista e ritornato.
Testiamo l'implementazione:
>>> q = CodaConPriorita()
>>> q.Inserimento(11)
>>> q.Inserimento(12)
>>> q.Inserimento(14)
>>> q.Inserimento(13)
>>> while not q.EVuota(): print q.Rimozione()
14
13
12
11
Se la coda contiene solo numeri o stringhe questi vengono rimossi in ordine numerico o alfabetico, dal più alto al più basso. Python può sempre trovare il numero o la stringa più grande perché può confrontare coppie di questi operandi con operatori di confronto predefiniti.
Se la coda contenesse un oggetto di tipo non predefinito è necessario fornire anche un metodo __cmp__ per poter effettuare il confronto. Quando Rimozione usa l'operatore > per confrontare gli elementi in realtà invoca __cmp__ per uno degli operandi e passa l'altro come parametro. La Coda con priorità funziona come ci si aspetta solo se il metodo __cmp__ opera correttamente.
Come esempio di oggetto con una definizione inusuale di priorità implementiamo una classe chiamata Golf che tiene traccia dei nomi e dei punteggi di un gruppo di golfisti. Partiamo con la definizione di __init__ e __str__:
class Golf:
def __init__(self, Nome, Punteggio):
self.Nome = Nome
self.Punteggio = Punteggio
def __str__(self):
return "%-16s: %d" % (self.Nome, self.Punteggio)
__str__ usa l'operatore di formato per stampare i nomi ed i punteggi in forma tabellare su colonne ordinate.
Poi definiamo una versione di __cmp__ dove il punteggio minore ottiene la priorità più alta: come abbiamo già visto in precedenza __cmp__ ritorna 1 se self è più grande di Altro, -1 se self è minore di Altro, e 0 se i due valori sono uguali.
class Golf:
...
def __cmp__(self, Altro):
if self.Punteggio < Altro.Punteggio: return 1
if self.Punteggio > Altro.Punteggio: return -1
return 0
Ora siamo pronti a testare la coda con priorità sulla classe Golf:
>>> tiger = Golf("Tiger Woods", 61)
>>> phil = Golf("Phil Mickelson", 72)
>>> hal = Golf("Hal Sutton", 69)
>>>
>>> pq = CodaConPriorità()
>>> pq.Inserimento(tiger)
>>> pq.Inserimento(phil)
>>> pq.Inserimento(hal)
>>> while not pq.EVuota(): print pq.Rimozione()
Tiger Woods : 61
Hal Sutton : 69
Phil Mickelson : 72
Esercizio: scrivi un'implementazione di un TDA Coda con priorità facendo uso di una lista linkata. Dovrai tenere la lista sempre ordinata per fare in modo che la rimozione di un elemento sia un'operazione a tempo costante. Confronta le performance di questa implementazione con l'implementazione delle liste in Python.
|
|
|
|
|
|
|