1
Iteratori e
iteratore in una catena (capitolo 14)
SETTIMANA 9
2
Accedere a nodi di una catena
Per eseguire operazioni sulla catena che necessitano di accedere ai nodi è necessario aggiungere metodi all’interno della classe LinkedList
che è l’unica ad avere accesso ai nodi della catena
Potremmo volere, ad esempio
Contare i nodi nella catena
verificare la presenza di un particolare oggetto nella catena (algoritmo di ricerca)
aggiungere/togliere elementi alla catena, anche in posizioni intermedie
Questo limita molto l’utilizzo della catena come struttura dati definita una volta per tutte…
3
Accedere a nodi di una catena
Esempio: vogliamo contare i nodi della catena
È necessario scorrere tutta la catena
Il codice va scritto dentro la classe LinkedList
public class LinkedList { ...
public int getSize()
{ ListNode temp = head.getNext();
int size = 0;
while (temp != null) { size++;
temp = temp.getNext();
} //se la catena è vuota size = 0 (giusto!) return size;
} ....
}
4
Accedere a nodi di una catena
Vogliamo che la catena fornisca uno strumento per accedere ordinatamente a tutti i suoi elementi.
Idea: scriviamo un metodo getHead che restituisce un riferimento al nodo header
Questo approccio però non funziona
Se la classe ListNode è public in LinkedList si viola l'incapsulamento, perché diventa possibile modificare lo stato della catena dall'esterno
Se invece è private allora i nodi sono inaccessibili e il metodo getHead è totalmente inutile
public class LinkedList
{... public ListNode getHead() { return head; }
...}
5
Iteratore in una catena
Soluzione del problema
fornire all’utilizzatore della catena uno strumento con cui interagire con la catena per scandire i suoi nodi
Tale oggetto si chiama iteratore e ne definiamo prima di tutto il comportamento astratto
Un iteratore rappresenta in astratto il concetto di posizione all’interno di una catena
Un iteratore si trova sempre dopo un nodo e prima del nodo successivo (che può non esistere se l’iteratore si trova dopo l’ultimo nodo)
• In particolare, quando viene creato l’iteratore si trova dopo il nodo header
6
Iteratore in una catena
Un iteratore rappresenta in astratto il concetto di posizione all’interno di una catena
la posizione è rappresentata concretamente da un riferimento ad un nodo (il nodo precedente alla posizione dell’iteratore)
dato dato dato
null
inizio (head) fine (tail)
null
header
ITERATORE
7
L'ADT ListIterator
import java.util.NoSuchElementException;
public interface ListIterator
{ /*Una classe che realizza ListIterator per una catena avra` un costruttore del tipo NomeClasse(ListNode h), che crea un iteratore che si trova subito dopo il nodo h*/
/*Lancia NoSuchElementException se l'iteratore e` alla fine, altrimenti restituisce l'oggetto che si trova dopo la pos.
attuale e sposta l’iteratore di una pos. in avanti*/
Object next() throws NoSuchElementException;
/*verifica se si puo` invocare next()*/
boolean hasNext();
/*inserisce x in prima della posizione attuale, senza modificare la posizione dell'iteratore*/
void add(Object x);
/*Lancia IllegalStateException se invocato 2 volte consecutive altrimenti elimina l'ultimo oggetto esaminato da next() o inserito da add() senza modificare la pos. dell’iteratore*/
void remove() throws IllegalStateException;
}
8
L'ADT ListIterator
Possiamo immaginare un iteratore come un cursore in un elaboratore di testi
Un nodo della catena corrisponde ad un carattere
L’iteratore si trova sempre “tra due nodi”, come un cursore
9
Iteratore in una catena
A questo punto, è sufficiente che la catena fornisca un metodo per creare un iteratore
E si può scandire la catena senza accedere ai nodi
public class LinkedList { ...
public ListIterator getIterator()
{ ... }// dopo vediamo come scrivere questo metodo ...
}
LinkedList list = new LinkedList();
...ListIterator iter = list.getIterator();
while(iter.hasNext())
System.out.println(iter.next());
// notare similitudine con StringTokenizer e Scanner
10
L’interfaccia Iterator in Java
La libreria standard di Java definisce in java.util una interfaccia Iterator
Definisce in particolare i metodi next e hasNext
Sempre in java.util si trova l’interfaccia ListIterator
Estende Iterator
Definisce altri metodi, tra cui add e remove
L’interfaccia Iterator è implementata da una classe che abbiamo utilizzato molto spesso: Scanner
Ha il metodo next
Ha il metodo hasnext
11
Implementare ListIterator
getIterator restituisce un riferimento ad una interfaccia
Quindi in realtà deve creare un oggetto di una classe che realizzi tale interfaccia
Implementiamo ListIterator con la classe LinkedListIterator
I suoi oggetti sono costruiti solo all’interno di LinkedList e restituiti all’esterno solo tramite riferimenti a ListIterator
Per un corretto funzionamento dell’iteratore occorre concedere a tale oggetto il pieno accesso alla catena
• in particolare, alla sua variabile di esemplare head
Non vogliamo che l’accesso sia consentito ad altre classi
Tutto questo ci porta a definire LinkedListIterator come una classe interna privata di LinkedList
12
La classe interna LinkedListIterator
public class LinkedList
{ ... //codice di LinkedList come prima
... //incluso codice della classe privata ListNode public ListIterator getIterator() //metodo di LinkedList { //crea un iteratore posizionato al primo nodo della catena return new LinkedListIterator(head); }
private class LinkedListIterator implements ListIterator { //costruttore
public LinkedListIterator(ListNode h) { current = h;
previous = null;
}
//metodi pubblici (dobbiamo ancora realizzarli) public boolean hasNext() { ... }
public Object next() { ... } public void add(Object x) { ... } public void remove() { ... } //campi di esemplare
private ListNode current;//nodo che precede pos. attuale private ListNode previous;//nodo che precede current }}
13
I metodi di LinkedListIterator
import java.util.NoSuchElementException;
public class LinkedList { ...
private class LinkedListIterator implements ListIterator { ...
//metodi pubblici hasNext, next public boolean hasNext()
{ return current.getNext() != null;
}
public Object next()
{ if (!hasNext()) throw new NoSuchElementException();
previous = current;
current = current.getNext();
return current.getElement();
}
//metodi pubblici add,remove (dobbiamo ancora realizzarli) public void add(Object x) { ... }
public void remove() { ... } //campi di esemplare
private ListNode current;//nodo che precede pos. attuale private ListNode previous;//nodo che precede current }}
14
Il metodo add di LinkedListIterator
public void add(Object obj)
{ ListNode n = new ListNode(obj, current.getNext());
current.setNext(n);
previous = current; //aggiorno riferimenti iteratore current = current.getNext(); //a subito dopo nuovo nodo if (!hasNext()) // se ho aggiunto all'ultimo nodo LinkedList.this.tail = current; //aggiorno tail }
Aggiunge il nuovo nodo e avanza di una posizione
Se il nodo viene aggiunto alla fine della catena, allora bisogna anche aggiornare il riferimento tail della catena
Nota sintattica: il riferimento LinkedList.this punta all'oggetto LinkedList all'interno di cui è stato creato l'iterator
15
Il metodo add di LinkedListIterator
dato dato dato
null
inizio (head) fine (tail)
null
header
ITERATORE
(inizio esecuzione) obj
ITERATORE (fine esecuzione)
16
Il metodo remove di LinkedListIterator
/* Va sempre invocato dopo add o next, anche la prima volta */
public void remove() throws IllegalStateException { /*Se dalla costruzione dell'iteratore o dall'ultima invocazione di remove non e` stato invocato next o add, allora previous==null. Stato illegale! */
if (previous == null) throw new IllegalStateException();
previous.setNext(current.getNext());
current = previous; // aggiorno riferimenti iteratore previous = null; // a subito prima del nodo rimosso if (!hasNext()) // se ho rimosso l'ultimo nodo LinkedList.this.tail = current; //aggiorno tail }
L'iteratore non ha un riferimento al nodo prima di previous
Quindi non posso aggiornare correttamente previous dopo la rimozione: gli assegno valore null, con la conseguenza che l'iteratore si trova in uno stato illegale dopo la rimozione
Per questo motivo non si può invocare nuovamente remove.
Invocando next o add previous verrà riaggiornato
17
Il metodo remove di LinkedListIterator
dato dato dato
null
inizio (head) fine (tail)
null
header
ITERATORE (fine esecuzione)
ITERATORE (inizio esecuzione)
dato
null
18
Operazioni su catene mediante un iteratore
19
Catena: conteggio elementi
Problema: data una catena ed un riferimento ad essa, si vuole sapere il numero di nodi che la compongono
Soluzione: con un iteratore possiamo contare i nodi al di fuori del codice di LinkedList, in una classe qualsiasi
public class MyClass
{ public static void main(String[] args) { LinkedList list = new LinkedList();
... // operazioni sulla catena int listSize = getSize(list);
public static int getSize(LinkedList list)} { ListIterator iter = list.getIterator();
int size = 0;
while (iter.hasNext()) { size++;
iter.next(); // ignoro l’oggetto ricevuto } // perché devo solo contarli return size;
}} 20
Catena: inserimento e rimozione
Abbiamo visto l’inserimento e la rimozione di un elemento all’inizio e alla fine della catena, tramite i metodi addFirst, removeFirst, addLast, removeLast
Vogliamo estendere le modalità di funzionamento della catena per poter inserire e rimuovere elementi in
qualsiasi punto della catena stessa
abbiamo il problema di rappresentare il concetto di posizione nella catena in cui inserire (o da cui rimuovere) il nodo
Possiamo usare di nuovo l’iteratore, e in particolare i suoi metodi add e remove
21
Catena: osservazioni finali
Ci sono alcune differenze tra la nostra realizzazione della catena e la realizzazione della classe
LinkedList proposta sul libro di testo
Usiamo un primo nodo “vuoto”
“Sprechiamo” dello spazio in memoria
Ma semplifichiamo la realizzazione dei metodi (non bisogna trattare i casi limite diversamente dagli altri)
Usiamo un riferimento tail all’ultimo nodo
Questo migliora le prestazioni di addLast senza peggiorare le altre e non richiede molto spazio di memoria
22
Catena doppia (doubly linked list)
23
Catena doppia
La catena doppia (o lista doppiamente concatenata, doubly linked list) non è un nuovo ADT
Come la catena, è una struttura dati per la realizzazione di ADT
Una catena doppia è un insieme ordinato di nodi
ogni nodo è un oggetto che contiene
un riferimento ad un elemento (il dato)
un riferimento al nodo successivo della lista (next)
un riferimento al nodo precedente della lista (prev)
24
Catena doppia
next
dato
next
dato
next null
inizio (head) fine (tail)
null prev prev prev
null null
Dato che la struttura è simmetrica, si usano due nodi vuoti, uno a ciascun estremo della catena
Tutto quanto detto per la catena (semplice) può essere agevolmente esteso alla catena doppia
Il metodo removeLast diventa O(1) come gli altri metodi
Un iteratore su catena doppia avrà anche un metodo per retrocedere di una posizione, oltre a quello per avanzare
i metodi add e remove dell’iteratore si complicano
25
Il tipo di dato astratto Lista
26
Lista
Il concetto di iteratore su catena, esplicitato
nell'interfaccia ListIterator, definisce il comportamento astratto di un contenitore in cui
i dati sono disposti in sequenza (cioè per ogni dato è definito un precedente ed un successivo)
nuovi dati possono essere inseriti in ogni punto
dati possono essere rimossi da qualsiasi punto
Un contenitore con un tale comportamento può essere molto utile, per cui si definisce un tipo di dati astratto, detto lista, con la seguente interfaccia
public interface List extends Container { ListIterator getIterator();
}
27
Lista
Attenzione a non confondere la lista (che è un ADT) con la lista concatenata o catena (che è una
struttura dati)
La classe LinkedList può essere usata per realizzare l'interfaccia List:
ma non è necessario realizzare una lista mediante una catena, perché nella definizione della lista non
vengono menzionati i nodi
Ad esempio è possibile definire una lista che usa un array come struttura di memorizzazione dei dati public class LinkedList implements List { ... // codice tutto come prima
}
28
Collaudo di List e LinkedList (1)
public class SimpleListTester1
{ public static void main(String[] args) { LinkedList list = new LinkedList();
//posso usare tutti i metodi di LinkedList list.addFirst("A"); //A
list.addLast("B"); //AB list.addFirst("C"); //CAB
ListIterator iter = list.getIterator();
iter.next();
iter.add("I"); //CIAB while (iter.hasNext())
iter.next();
iter.remove(); //CIA list.addLast("O"); //CIAO iter = list.getIterator();
while (iter.hasNext())
System.out.println(iter.next());
} }
C I A O
29
Collaudo di List e LinkedList (2)
public class SimpleListTester2
{ public static void main(String[] args) { List list = new LinkedList();
//posso usare solo il metodo getIterator di List ListIterator iter = list.getIterator();
iter.add("A"); //A iter.add("B"); //AB iter = list.getIterator();
iter.add("C"); //CAB
iter.add("I"); //CIAB while (iter.hasNext())
iter.next();
iter.remove(); //CIA iter.add("O"); //CIAO iter = list.getIterator();
while (iter.hasNext())
System.out.println(iter.next());
} }
C I
A O 30
Liste posizionali e liste con rango (vettori)
31
Rango, posizione, liste, vettori
Le operazioni più generali che vogliamo effettuare su una lista riguardano l’inserimento e l’eliminazione di un nuovo elemento in una posizione qualsiasi
La posizione di un elemento nella lista può essere
indicata in modo relativo attraverso un iteratore
indicata in modo assoluto attraverso il rango di un elemento
Il rango è un indice che possiamo definire ricorsivamente
ha valore 0 per il primo elemento della lista
ha valore i+1 per l’elemento che segue l’elemento di rango i
Conveniamo di chiamare vettore una lista con rango
32
Gli ADT “lista” e “vettore”
Il tipo di dato astratto “vettore” e il tipo di dato astratto
“lista” hanno astrazioni diverse
Un vettore è una sequenza ordinata di dati, ciascuno accessibile mediante un indice intero (il rango)
Un vettore consente quindi l’accesso casuale a tutti gli elementi tramite l’uso di indici
Una lista è una sequenza ordinata di dati, accessibili in sequenza mediante un iteratore
Una lista consente solamente accesso sequenziale ai propri elementi
33
L'ADT “vettore”
L'ADT vettore è una generalizzazione del concetto di array:
Ha una lunghezza variabile
È possibile aggiungere e togliere elementi in qualsiasi posizione del vettore
È possibile accedere (in lettura e scrittura) al valore di un elemento noto il suo rango
Un modo naturale per realizzare l'ADT vettore è quello di utilizzare un array riempito solo in parte
In java.util esiste la classe ArrayList, che realizza una lista con rango e con una ricca dotazione di funzionalità
34
Vettori e liste: efficienza operazioni
L'efficienza delle operazioni fondamentali cambia se la posizione è specificata tramite rango o iteratore
Con rango: l'accesso richiede tempo costante, ma inserimenti e rimozioni comportano in media lo spostamento di n/2 elementi, cioè tempo O(n)
Con iteratore: l'accesso richiede tempo lineare O(n) (bisogna scorrere la lista dall'inizio), ma inserimenti e rimozioni comportano un numero costante di operazioni
35
Riassunto: dati in sequenza
Abbiamo fin qui visto diversi tipi di contenitori per dati in sequenza, rappresentati dagli ADT
pila
coda
lista con iteratore
lista con rango (vettore)
Per realizzare tali ADT, abbiamo usato diverse strutture dati
Array
Catena
Catena doppia
36
37
Mappe e Dizionari
(capitolo 15 ma la nostra trattazione è abbastanza diversa)
38
Mappa: definizione
Una mappa è un ADT con le seguenti proprietà
Contiene dati (non in sequenza) che sono coppie di tipo chiave/valore
Non può contenere coppie con identica chiave: ogni chiave deve essere unica nell’insieme dei dati memorizzati
Consente di inserire nuove coppie chiave/valore
Consente di effettuare ricerca e rimozione di valori usando la chiave come identificatore
39
Dizionario: definizione
L'ADT dizionario ha molte similitudini con l'ADT mappa
Valgono tutte le proprietà dell'ADT mappa, tranne una
Non si richiede che le chiavi siano uniche nel dizionario
C'è analogia con un dizionario di uso comune, in cui
le chiavi sono le singole parole
I valori sono le definizioni delle parole nel dizionario
le chiavi (parole) possono essere associate a più valori (definizioni) e quindi comparire più volte nel dizionario
la ricerca di un valore avviene tramite la sua chiave
Si distinguono dizionari ordinati e dizionari nonordinati
A seconda che sull'insieme delle chiavi sia o no definita una relazione totale di ordinamento, cioè (in Java) che le chiavi appartengano ad una classe che implementa Comparable
La nostra trattazione è limitata ad un caso ben preciso
Dizionari ordinati a chiave unica (cioè mappe) 40
L’interfaccia Dictionary
public interface Dictionary extends Container
{ // l'inserimento va sempre a buon fine; se la chiave non // esiste la coppia viene aggiunta al dizionario. Se esiste, // il valore ad essa associato viene sovrascritto dal nuovo // valore; se key e` null si lancia IllegalArgumentException void insert(Comparable key, Object value);
// la rimozione della chiave rimuove anche il corrispondente // valore dal dizionario. Se la chiave non esiste si lancia // DictionaryItemNotFoundException
void remove(Comparable key);
// la ricerca per chiave restituisce solo il valore ad essa // associato nel dizionario. Se la chiave non esiste si // lancia DictionaryItemNotFoundException
Object find(Comparable key);
}
//Eccezione che segnala il mancato ritrovamento di una chiave class DictionaryItemNotFoundException extends RuntimeException { }
41
Implementare Dictionary con array
Un dizionario può essere realizzato usando la struttura dati array
Ogni cella dell’array contiene un riferimento ad una coppia chiave/valore
La coppia chiave/valore sarà un oggetto di tipo Pair (da definire)
Generalmente si usa un array riempito solo in parte
A seconda degli ambiti applicativi ci sono due strategie possibili
mantenere le chiavi ordinate nell’array
mantenere le chiavi non ordinate nell’array
A seconda della strategia scelta, cambiano le
prestazioni dei metodi del dizionario 42
Dizionario con array ordinato
Se le n chiavi vengono conservate ordinate nell’array
La ricerca ha prestazioni O(log n)
Perché si può usare la ricerca per bisezione
la rimozione ha prestazioni O(n)
Perché bisogna effettuare una ricerca, e poi spostare mediamente n/2 elementi per mantenere l’ordinamento
L’inserimento ha prestazioni O(n)
Perché si può usare l’ordinamento per inserimento in un array ordinato
Usando un diverso algoritmo occorre riordinare l’intero array, con prestazioni almeno O(n log n)
43
Dizionario con array non ordinato
Se le n chiavi vengono conservate non ordinate
La ricerca ha prestazioni O(n)
Bisogna usare la ricerca lineare
La rimozione ha prestazioni O(n)
Bisogna effettuare una ricerca (lineare), e poi spostare nella posizione trovata l'ultimo elemento dell'array
(l’ordinamento non interessa)
L’inserimento ha prestazioni O(n)
Bisogna rimuovere (sovrascrivere) un elemento con la stessa chiave, se c'è, e poi inserire il nuovo elemento nella ultima posizione dell’array (l’ordinamento non interessa)
[Se non si richiede che le chiavi siano uniche nel dizionario,
la rimozione non è necessaria e l'inserimento è O(1) ] 44
Prestazioni di un dizionario
La scelta di una particolare realizzazione dipende dall’utilizzo tipico del dizionario nell’applicazione
Se si fanno frequenti inserimenti e sporadiche ricerche e rimozioni la scelta migliore è l’array non ordinato
Se il dizionario viene costruito una volta per tutte, poi viene usato soltanto per fare ricerche la scelta migliore è l’array ordinato
[O(1) per chiavi non uniche]
45
Realizzazione di un dizionario
46
La classe interna Pair
public class ArrayDictionary implements Dictionary { ...
protected class Pair //classe interna ad ArrayDictionary { public Pair(Comparable key, Object value)
{ setKey(key);
setValue(value); } //metodi pubblici
public String toString()
{ return key + " " + value; } public Comparable getKey() { return key; }
public Object getValue() { return value; }
public void setKey(Comparable key) { this.key = key; }
public void setValue(Object value) { this.value = value; }
//campi di esemplare private Comparable key;
private Object value;
} ...
}
47
La classe ArrayDictionary
public class ArrayDictionary implements Dictionary { public ArrayDictionary()
{ v = new Pair[INITSIZE]; // ... sempre uguale makeEmpty();
}
public boolean isEmpty()
{ return vSize == 0; } // ... sempre uguale public void makeEmpty()
{ vSize = 0; } // ... sempre uguale public String toString()
{ String s = "";
for (int i = 0; i < vSize; i++) s = s + v[i] + "\n";
return s;
}
public void insert(Comparable key, Object value)
{ if (key == null) throw new IllegalArgumentException();
try
{ remove(key); } //elimina elemento se gia` presente catch (DictionaryItemNotFoundException e)
{} //... ovvero sovrascrive elemento se gia` presente if (vSize == v.length) v = resize(2*vSize);
v[vSize++] = new Pair(key, value);
} //continua 48
La classe ArrayDictionary
//continua protected Pair[] resize(int newLength) //metodo ausiliario { ... } //solito codice
public void remove(Comparable key)
{ v[linearSearch(key)] = v[--vSize];
}
public Object find(Comparable key)
{ return v[linearSearch(key)].getValue();
}
private int linearSearch(Comparable key) //metodo ausiliario { for (int i = 0; i < vSize; i++)
if (v[i].getKey().compareTo(key) == 0)
//oppure if (v[i].getKey().equals(key)), se il //metodo equals e` stato realizzato correttamente return i;
throw new DictionaryItemNotFoundException();
}
//campi di esemplare protected Pair[] v;
protected int vSize;
protected final static int INITSIZE = 10;
protected class Pair
{ ... } // codice della classe Pair
49
Dizionario con array ordinato
Avendo usato un array non ordinato, i metodi remove e find effettuano una ricerca lineare sulle chiavi
Esercizio: realizzare un dizionario con un array ordinato
Il metodo insert deve mantenere ordinato l'array ad ogni inserimento (usando insertionSort...)
I metodi remove e find possono usare la ricerca binaria per trovare una chiave
Il metodo remove deve ricompattare l'array dopo la rimozione, mantenendolo ordinato
public class SortedArrayDictionary extends ArrayDictionary { // realizzazione con array non ordinato. Eredita campi di // esemplare e variabili statiche, la classe Pair, i metodi // isEmpty, makeEmpty, resize. Deve sovrascrivere i metodi // insert, remove, find
}
50 import java.util.Scanner;
import java.io.*;
public class SimpleDictionaryTester
{ public static void main(String[] args) throws IOException { //creazione dizionario: leggo dati da file e assumo che //il file abbia righe nel formato <numero int> <stringa>
Scanner infile = new Scanner(new FileReader("file.txt"));
Dictionary dict = new ArrayDictionary();
// ... oppure = new SortedArrayDictionary();
while (infile.hasNextLine())
{ Scanner linescan = new Scanner(infile.nextLine());
int key = Integer.parseInt(linescan.next());
String value = linescan.next();
dict.insert(key,value); //inserisco chiave e valore }
infile.close();
//ricerca/rimozione dati nel dizionario Scanner in = new Scanner(System.in);
boolean done = false; // continua
Collaudo di un dizionario
51
Collaudo di un dizionario
while (!done) // continua { System.out.println("**** Stampa dizionario ****");
System.out.println(dict +"\nF=find,R=remove,Q=quit");
String cmd = in.nextLine();//ho sovrascritto toString if (cmd.equalsIgnoreCase("Q"))
{ done = true; }
else if (cmd.equalsIgnoreCase("F"))
{ System.out.println("Chiave da trovare?");
int key = Integer.parseInt(in.nextLine());
try{ //cerca key chiave e restituisce il valore String value = (String)dict.find(key);
System.out.println("Valore: " + value); } catch(DictionaryItemNotFoundException e) { System.out.println("Chiave non trovata");}
}
else if (cmd.equalsIgnoreCase("R"))
{ System.out.println("Chiave da rimuovere?");
int key = Integer.parseInt(in.nextLine());
try{//rimuove la coppia identificata da key dict.remove(key);
System.out.println("Chiave rimossa"); } catch(DictionaryItemNotFoundException e) { System.out.println("Chiave non trovata");}
} } } }
52
Dizionari a chiavi numeriche
L'ADT Tabella
53
Chiavi numeriche
Supponiamo per un attimo che le chiavi di un dizionario siano numeri interi appartenenti ad un intervallo noto a priori
Allora si può realizzare molto semplicemente un dizionario con prestazioni O(1) per tutte le operazioni
Si usa un array che contiene soltanto i riferimenti ai valori delle coppie del dizionario
Le chiavi delle coppie vengono usate come indici nell’array
Le celle dell’array che hanno come indice una chiave che non è presente nel dizionario hanno il valore null
54
Tabella
Un dizionario con chiavi numeriche intere viene detto tabella o tavola (table)
L’analogia è la seguente
un valore è una riga nella tabella
le righe sono numerate usando le chiavi
alcune righe possono essere vuote (senza valore) chiave = 0 valore0
valore2null valore3
nullnull chiave = 2
chiave = 3
dato dato dato
55
L'interfaccia Table
Definiamo il tipo di dati astratto Table con un comportamento identico al dizionario
l’unica sostanziale differenza è che le chiavi non sono riferimenti a oggetti di tipo Comparable, ma sono numeri interi (che evidentemente sono confrontabili)
Potremmo (non lo facciamo) realizzarlo usando array (questa volta non riempiti solo in parte!)
public interface Table extends Container { void insert(int key, Object value);
void remove(int key);
Object find(int key);
}
56
Tabella
Una realizzazione dell'ADT tabella tramite array fornisce prestazioni ottime
tutte le operazioni sono O(1)
Prima limitazione: le chiavi devono essere numeri interi
Seconda limitazione (più pesante): la tabella non utilizza la memoria in modo efficiente
l’intervallo di variabilità delle chiavi deve essere noto a priori per dimensionare la tabella
• la memoria richiesta per contenere n dati dipende dal loro contenuto, in particolare dal valore della chiave massima
Se le chiavi sono molto “disperse”, ovvero se il fattore di riempimento è piccolo, si ha grande spreco di memoria
• fattore di riempimento di una tabella = (numero di dati contenuti nella tabella) / (dimensione della tabella)
57
Tabella con ridimensionamento
Se l’intervallo di variabilità delle chiavi non è noto a priori e si inserisce una chiave di valore superiore alla lunghezza dell’array bisogna ridimensionare l’array
Un inserimento richiede un tempo O(n) ogni volta che è necessario un ridimensionamento
• Qui non si può utilizzare l’analisi ammortizzata perché non si può prevedere il valore della nuova chiave
il ridimensionamento può avvenire ad ogni inserimento, e le prestazioni nel caso peggiore sono quindi O(n)
Può essere necessario un array di milioni di elementi per contenere poche decine di dati
58
La struttura dati
“tabella hash con bucket”
59
Tabella hash con bucket
Introduciamo una nuova struttura dati che ci permette di superare entrambe le limitazioni di una tabella realizzata tramite array
Limitazioni della tabella: le chiavi devono essere numeri interi in un intervallo prefissato
Introdurremo una funzione di hash che assegna dei valori numerici (interi in un intervallo prefissato) a delle chiavi generiche
Seconda limitazione della tabella: la memoria non viene utilizzata in maniera efficiente
Useremo un array di bucket (“secchi”), cosicché ogni indice dell'array possa essere associato a più elementi del dizionario
60
Funzioni di hash
61
Chiavi generiche e codici hash
Prima limitazione della tabella: le chiavi devono essere numeri interi
E se le chiavi non sono int ma sono invece oggetti arbitrari di tipo Object?
Esempio: contenitore di oggetti di tipo PersonaFisica, la cui chiave è il codice fiscale (cioè è di tipo String)
Vogliamo realizzare il dizionario tramite una tabella anche in questo caso
Dobbiamo “tradurre” le chiavi in valori numerici
Dobbiamo cioè progettare un codice hash
il codice hash è una funzione che ha come dominio l’insieme delle chiavi generiche in esame e come codominio un sottoinsieme dei numeri interi
62
Codice hash
Il codice hash è quindi una funzione così definita:
h1: {Chiavi} → {Interi}
In Java
la classe Object mette a disposizione il metodo hashCode che restituisce un int con buone proprietà di distribuzione uniforme
Se il metodo hashCode non viene ridefinito, esso associa ad un oggetto un valore numerico calcolato in base all’indirizzo dell’oggetto in memoria
L’esistenza di questo metodo rende possibile l’utilizzo di qualsiasi oggetto come chiave
63
Un codice hash per stringhe
Come si può trasformare una stringa in un numero intero?
Ricordiamo il significato della notazione posizionale nella rappresentazione di un numero intero
Ciascuna cifra rappresenta un numero che dipende dal suo valore intrinseco e dalla sua posizione
Usiamo la stessa convenzione per una stringa, dove ogni carattere rappresenta un numero che dipende
Dal suo valore intrinseco come carattere nella codifica Unicode
Dalla sua posizione nella stringa
434 = 4·102 + 3·101 + 4·100
64
Un codice hash per stringhe
Il valore numerico associato ad una stringa è quindi calcolato in questo modo
Che valore utilizziamo per la base?
Spesso si usa un numero primo come valore di base, perché questo “mescola” bene i valori
• Ovvero stringhe diverse hanno con buona probabilità codici hash diversi
In alternativa la base sarà (come per la notazione posizionale di interi) il numero di simboli diversi
• che per la codifica Unicode è 216 = 65536
"ABC" ⇒ 'A'·base2 + 'B'·base1 + 'C'·base0
"ABC" ⇒ 'A'·655362 + 'B'·655361 + 'C'·655360
65
Mappe di compressione
C'è ancora un problema: l’intervallo di variabilità delle chiavi deve essere noto a priori per dimensionare la tabella
Affrontiamo il problema in questo modo
Prefissiamo la dimensione della tabella in modo arbitrario
Quindi definiamo di conseguenza l’intervallo di variabilità delle chiavi utilizzabili: il valore massimo consentito è la lunghezza della tabella
Bisogna modificare la funzione h1 in modo che tutti i valori numerici associati alle chiavi ricadano all’interno dell’intervallo prefissato
Si usa una ulteriore funzione di trasformazione delle chiavi, detta mappa di compressione
66
Mappe di compressione
Abbiamo definito il codice hash h1: {Chiavi} {Interi}→
In Java la funzione h1 è realizzata dal metodo hashCode
Definiamo ora una funzione mappa di compressione:
h2 : {Interi} [0, N 1]→
Il codominio di h2 è il sottoinsieme [0, N 1] dei numeri interi, dove N coincide con la dimensione della tabella
Esempio di mappa di compressione
resto della divisione intera tra il codice hash di un oggetto e la dimensione N della tabella
h2(h1(x)) = h1(x) % N
Il valore calcolato è un intero nell’intervallo [0, N1]
67
Funzioni di hash
Siamo ora in grado di definire una funzione di hash h(x) come composizione delle funzioni h1 (codice hash) e h2 (mappa di compressione)
h : {Chiavi} [0, N 1]→ h(x) = h2(h1(x))
Una funzione di hash ha
come dominio l’insieme delle chiavi che identificano univocamente i dati da inserire nel dizionario
come codominio l’insieme degli indici validi per accedere ad elementi della tabella
• il risultato dell’applicazione della funzione di hash ad una chiave si chiama chiave ridotta
Una tabella che usa chiavi ridotte si chiama
tabella hash (hash table) 68
Funzioni di hash
La funzione di hash h(x) come composizione di h1 e h2
Chiavi arbitrarie Chiavi arbitrarie
Codice hash Codice hash
h h
11Mappa di compressione Mappa di compressione
h h
223 2 1 0 1 2 3 3 2 1 0 1 2 3
0 1 2 3 …. N1 0 1 2 3 …. N1
69
Bucket in una tabella hash
70
Collisioni in una tabella hash
Ora abbiamo un nuovo problema: Per come è definita, una funzione di hash è generalmente non biunivoca
chiavi diverse possono avere lo stesso valore per la funzione di hash
• In generale non si può definire una funzione h biunivoca, perché il dominio ha dimensione maggiore del codominio
Inseriamo nella tabella un elemento con chiave x1
Supponiamo che h(x1) = h(x2), dove x2 != x1 è la chiave di un elemento già presente nella tabella
• Ovvero x1 ed x2 hanno la stessa chiave ridotta
Il nuovo elemento sostituisce il vecchio nella tabella
• Questo non è corretto perché i due valori hanno, in realtà, chiavi diverse
71
Collisioni in una tabella hash
Se due elementi hanno chiavi diverse ma uguali chiavi ridotte si verifica una collisione nella tabella
In presenza di una collisione, bisognerebbe inserire il nuovo valore nella stessa cella della tabella
(dell’array) che già contiene un altro valore
ciascun valore deve essere memorizzato insieme alla sua vera chiave, per poter fare ricerche correttamente
Possiamo risolvere il problema usando una lista associata ad ogni cella dell’array
L’array è quindi un array di riferimenti a liste
Ciascuna lista contiene le coppie chiave/valore che hanno la stessa chiave ridotta
72
Tabella hash con bucket
Questo sistema di risoluzione delle collisioni si chiama tabella hash con bucket
un bucket è una delle liste associate ad una chiave ridotta
hash = 0 bucket0 bucket2null bucket3
nullnull hash = 2
hash = 3
coppia coppia coppia
coppia
coppia
73
Tabella hash con bucket: prestazioni
Le prestazioni della tabella hash con bucket non sono più, ovviamente, O(1) per tutte le operazioni
Effettuiamo ad esempio una ricerca su una chiave x
Il tempo per raggiungere il bucket di indice h(x) è O(1)
Il tempo per raggiungere l’elemento con chiave x nel bucket dipende dalla lunghezza della lista
Le prestazioni dipendono fortemente dalle caratteristiche della funzione di hash
Una “buona” funzione di hash minimizza le collisioni, cioè fornisce chiavi ridotte distribuite in maniera uniforme nella tabella
• In questo modo le liste in ogni bucket hanno tutte
approssivamente la stessa lunghezza (minima) 74
Tabella hash con bucket: prestazioni
Caso peggiore
La funzione di hash restituisce sempre la stessa chiave ridotta, per ogni chiave possibile
Allora tutti i dati vengono inseriti in un’unica lista
In questo caso le prestazioni della tabella hash degenerano in quelle di una lista
• tutte le operazioni sono O(n)
bucket2null
…
hash = 2
coppia coppia coppia
null null
75
Tabella hash con bucket: prestazioni
Caso migliore:
La funzione di hash restituisce chiavi ridotte che si distribuiscono uniformemente nella tabella
Tutte le liste hanno la stessa lunghezza media
Se N è la dimensione della tabella
La lunghezza media di ciascuna lista è n/N
Tutte le operazioni sono O(n/N)
Per avere prestazioni O(1) occorre dimensionare la tabella in modo che N sia dello stesso ordine di grandezza di n
76
Tabella hash con bucket: prestazioni
Riassumendo, in una tabella hash con bucket si ottengono prestazioni ottimali, ovvero O(1), se
La dimensione della tabella è circa uguale al numero di dati che saranno memorizzati nella tabella
• Ovvero se il fattore di riempimento è circa unitario (così si riduce al minimo anche lo spreco di memoria)
La funzione di hash genera chiavi ridotte che siano uniformemente distribuite
• Ovvero produce liste di lunghezza quasi uguale alla lunghezza media
• In particolare, se le chiavi vere sono uniformemente distribuite la funzione di hash h(x) = h1(x) % N genera chiavi ridotte uniformemente distribuite
Sotto queste ipotesi le liste hanno quasi tutte lunghezza uno!
77
Insiemi
(capitolo 15 ma la nostra trattazione è abbastanza diversa)
78
Il tipo di dati astratto Insieme (Set)
È un contenitore (eventualmente vuoto) di oggetti distinti (cioè non contiene duplicati)
Senza alcun particolare ordinamento o memoria dell’ordine in cui gli oggetti sono inseriti/estratti
Corrisponde alla nozione matematica di insieme
Definiamo la nostra astrazione di insieme tramite le seguenti operazioni
inserimento di un oggetto
• fallisce silenziosamente se l’oggetto è già presente
verifica della presenza di un oggetto
ispezione di tutti gli oggetti
• restituisce un array (in generale non ordinato) di riferimenti agli oggetti dell’insieme
Non definiamo un’operazione di rimozione
• useremo l'operazione di sottrazione tra insiemi (cfr. più avanti)
79
Operazioni sugli insiemi
Per due insiemi A e B, si definiscono le operazioni
unione, A ∪ B
• appartengono all’unione di due insiemi tutti e soli gli oggetti che appartengono ad almeno uno dei due insiemi
intersezione, A ∩ B
• appartengono all’intersezione di due insiemi tutti e soli gli oggetti che appartengono ad entrambi gli insiemi
sottrazione, A B (oppure anche A \ B)
• appartengono all’insieme sottrazione tutti e soli gli oggetti che appartengono ad A e non appartengono a B
• non è necessario che B sia un sottoinsieme di A
80
Insieme con array non ordinato
Scriviamo innanzitutto l’interfaccia Set
La classe ArraySet ha questa interfaccia pubblica
Abbiamo scritto enunciati return per metodi che non restituiscono void
• In questo modo la classe si compila da subito
public class ArraySet implements Set { public void makeEmpty() { }
public boolean isEmpty() { return true; } public void add(Object x) { }
public boolean contains(Object x) { return true; } public Object[] toArray() { return null; }
}
public interface Set extends Container { void add(Object obj);
boolean contains(Object obj);
Object[] toArray();
}
81
La classe ArraySet
public class ArraySet implements Set { public ArraySet()
{ v = new Object[INITSIZE];
vSize = 0;}
public void makeEmpty() { vSize = 0; }
public boolean isEmpty() { return (vSize == 0); }
public void add(Object x)//prestazioni O(n) (usa contains) { if (contains(x)) return;
if (vSize == v.length) v = resize(2*vSize);
v[vSize++] = x; }
public boolean contains(Object x) //metodo con prestaz. O(n) { for (int i = 0; i < vSize; i++)
if (v[i].equals(x)) return true;//non si puo` usare return false; //compareTo perche` x e` solo un Object public Object[] toArray() // metodo con prestazioni O(n).
{ Object[] x = new Object[vSize]; //Creiamo un nuovo array System.arraycopy(v, 0, x, 0, vSize);//altrimenti si viola return x; } //l’incapsulamento private Object[] resize(int n) { ... }//solito codice //campi di esemplare e var. statiche
private Object[] v;
private int vSize;
private static int INITSIZE = 100;
}
82
Operazioni su insiemi: unione
Prestazioni: se contains è O(n) (e, quindi, lo è anche add), questa operazione è O(n2)
public static Set union(Set s1, Set s2) { Set x = new ArraySet();
// inseriamo gli elementi del primo insieme Object[] v = s1.toArray();
for (int i = 0; i < v.length; i++) x.add(v[i]);
// inseriamo tutti gli elementi del // secondo insieme, sfruttando le
// proprietà di add (niente duplicati...) v = s2.toArray();
for (int i = 0; i < v.length; i++) x.add(v[i]);
return x;
}
83
Operazioni su insiemi: intersezione
Prestazioni: se contains è O(n) l’operazione di intersezione è O(n2)
public static Set intersection(Set s1, Set s2) { Set x = new ArraySet();
Object[] v = s1.toArray();
for (int i = 0; i < v.length; i++) if (s2.contains(v[i]))
x.add(v[i]);
// inseriamo solo gli elementi che // appartengono anche al secondo // insieme, sfruttando le proprieta’
// di add (niente duplicati...) return x;
}
84
Operazioni su insiemi: sottrazione
Prestazioni: se contains è O(n) l’operazione di intersezione è O(n2)
public static Set subtract(Set s1, Set s2) { Set x = new ArraySet();
Object[] v = s1.toArray();
for (int i = 0; i < v.length; i++) if (!s2.contains(v[i]))
x.add(v[i]);
// inseriamo solo gli elementi che // *non* appartengono al secondo // insieme, sfruttando le proprieta’
// di add (niente duplicati...) return x;
}
85
Insieme con array non ordinato
Riassumendo, realizzando un insieme con un array non ordinato
le prestazioni di tutte le operazioni primitive dell’insieme sono O(n)
le prestazioni di tutte le operazioni che agiscono su due insiemi sono O(n2)
Si può facilmente verificare che si ottengono le stesse prestazioni realizzando l’insieme con una catena (LinkedListSet)
86
Esercizio:
Insiemi di dati ordinabili
87
Insieme di dati ordinabili
Cerchiamo di capire se si possono avere prestazioni migliori quando l’insieme contiene dati ordinabili
Definiamo l’interfaccia “insieme ordinato”
Realizziamo SortedSet usando un array ordinato
dovremo definire due metodi add, uno dei quali impedisce l’inserimento di dati non ordinabili
public interface Set extends Container { void add(Object obj);
boolean contains(Object obj);
Object[] toArray();
} public interface SortedSet extends Set { void add(Comparable obj);
Comparable[] toSortedArray();
}
88
Esercizio: la classe ArraySortedSet
public class ArraySortedSet implements SortedSet { public ArraySortedSet()
{ v = new Comparable[INITSIZE]; vSize = 0; } public void makeEmpty()
{ vSize = 0; }
public boolean isEmpty() { return (vSize == 0); }
public void add(Object x) //metodo di Set { throw new IllegalArgumentException(); } public void add(Comparable x) // prestazioni O(n)
{ ... } //Da completare: riordinamento per inserimento //E` O(n), perche' inseriamo in un array ordinato public boolean contains(Object x) //prestaz. O(log n) { ... } // da completare: usare ricerca binaria e compareTo public Comparable[] toSortedArray() // prestaz. O(n)
{ ... } //da completare (v e’ gia` ordinato...)
public Object[] toArray() //Sovrascritto: l'array non deve { return toSortedArray(); } //essere per forza disordinato private Comparable[] resize(int newLength) //solito metodo { ... } // da completare
//campi di esemplare e variabili statiche private Comparable[] v;
private int vSize;
private static int INITSIZE = 100;
}
89
Operazioni su insiemi ordinati
Gli algoritmi di unione, intersezione, sottrazione per insiemi generici possono essere utilizzati anche per insiemi ordinati
infatti, un SortedSet è anche un Set
Quale è la complessità dell'algoritmo di unione?
Rimane O(n2) perché il metodo add è rimasto O(n), a causa del riordinamento (con insertionSort) dell’array
Sfruttiamo ciò che sappiamo delle realizzazioni di add e toSortedArray nella classe ArraySortedSet
l’array ottenuto con il metodo toSortedArray è ordinato
l’inserimento nell’insieme tramite add usa l’algoritmo di ordinamento per inserzione in un array ordinato
90
SortedSet: unione
Per realizzare l’unione, osserviamo che il problema è molto simile alla fusione di due array ordinati
come abbiamo visto in mergeSort, questo algoritmo di fusione (che abbiamo realizzato nel metodo ausiliario merge) è O(n)
L’unica differenza consiste nella contemporanea eliminazione (cioè nel non inserimento…) di eventuali oggetti duplicati
un oggetto presente in entrambi gli insiemi dovrà essere presente una sola volta nell’insieme unione
91
SortedSet: unione
Quali sono le prestazioni di questo metodo union?
public static SortedSet union(SortedSet s1,SortedSet s2) { SortedSet x = new ArraySortedSet();
Comparable[] v1 = s1.toSortedArray();
Comparable[] v2 = s2.toSortedArray();
int i = 0, j = 0;
while (i < v1.length && j < v2.length) // merge if (v1[i].compareTo(v2[j]) < 0)
x.add(v1[i++]);
else if (v1[i].compareTo(v2[j]) > 0) x.add(v2[j++]);
else // sono uguali { x.add(v1[i++]);
j++; }
while (i < v1.length) x.add(v1[i++]);
while (j < v2.length) x.add(v2[j++]);
return x;
}
92
SortedSet: unione
Effettuando la fusione dei due array ordinati secondo l’algoritmo visto in MergeSort, gli oggetti vengono via via inseriti nell’insieme unione che si va costruendo
Questi inserimenti avvengono con oggetti in ordine crescente
Quali sono le prestazioni di add in questo caso?
L’invocazione di contains ha prestazioni O(log n) per ogni inserimento
L’ordinamento per inserzione in un array ordinato, usato da add, ha prestazioni O(1) per ogni inserimento!
In questo caso add ha quindi prestazioni O(log n)
Quindi complessivamente il metodo statico union ha prestazioni O(n log n)