Informatica I - L'ADT Pila

Le pile (stack) nella programmazione

In una pila (stack) gli oggetti possono essere inseriti ed estratti secondo un comportamento definito LIFO (Last In, First Out): l'ultimo oggetto inserito è il primo ad essere estratto. L'unico oggetto che può essere ispezionato è quello che si trova in cima alla pila.

Per realizzare una pila si usa una struttura di tipo array "riempito solo in parte". Le operazioni (metodi) che caratterizzano una pila sono:

• push: inserisce un oggetto in cima alla pila
• pop: elimina l'oggetto che si trova in cima alla pila
• top: ispeziona l'oggetto in cima alla pila senza estrarlo

Inoltre una pila (come ogni Container) ha i metodi:

• size: per sapere quanti oggetti ci sono nel contenitore
• isEmpty: per sapere se il contenitore è vuoto

Pile nella Java Virtual Machine

Ciascun programma Java in esecuzione ha una propria pila chiamata Java Virtual Machine (JVM).

Stack che viene usata permantenere traccia delle variabili locali, dei parametri formali dei metodi e di altre importanti informazionirelative ai metodi, man mano che questi sono invocati. I descrittori sono denominati Frame. A un certoistante durante l'esecuzione, ciascun metodo sospeso ha un frame nel Java Stack.

Prestazioni dei metodi di una pila e "analisi ammortizzata"

L'analisi ammortizzata si usa per mostrare che, in una sequenza di operazioni, il costo medio di unaoperazione è piccolo, anche se una singola operazione della sequenza è "costosa". È diversa dall'analisi di caso medio vista in precedenza:

• Analisi di caso medio: si basa su stime statistiche dell'input
• Analisi ammortizzata: fornisce il costo medio di una singola operazione nel caso peggiore

Analisi aggregata

Ci sono varie tecniche di analisi ammortizzata: si stima il tempo T(n) per una sequenzadi n operazioni, nel caso peggiore. Allora il tempo

Il tempo medio per una operazione è T(n)/n. Noi applichiamo questa tecnica all'analisi dei tempi di esecuzione dei metodi di inserimento in struttura dati.

Il tempo di esecuzione di ogni operazione su una pila senza ridimensionamento è costante, cioè non dipende dalla dimensione n della struttura dati stessa (non ci sono cicli), e vale O(1).

Analizziamo i tempi di esecuzione nel caso di pila con ridimensionamento:

L'unica differenza con una pila senza ridimensionamento è l'operazione push: "Alcune volte" push richiede un tempo O(n) (perché all'interno del metodo resize è necessario copiare tutti gli n elementi nel nuovo array).

Cerchiamo di calcolare il tempo di esecuzione medio di n operazioni di push, delle quali:

• n-1 richiedono un tempo O(1)
• una richiede un tempo O(n)

Distribuendo il tempo speso per un ridimensionamento su n operazioni di push, si ottiene quindi ancora O(1).

push con ridimensionamento

ha prestazioni O(1) per qualsiasi costante moltiplicativa usata per calcolare la nuova dimensione, anche diversa da 2.

Se invece si usa una costante additiva k, cioè si ridimensiona l'array da n a n+k, allora su n operazioni di inserimento quelle "lente" sono n/k.

Aumentando la dimensione dell'array di 20 elementi (ovvero k = 20), 5 inserimenti su 100 (o 50 su 1000) richiedono di invocare resize.