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