2.15.Lezione 15
Studiare le proprietà dei BST red-black consiste nel controllare la corrispondenza con alberi 2-3, e poi applicare l'analisi degli alberi 2-3.
L'altezza di un albero Rosso-Nero, è minore o uguale di 2 lg N
Il caso peggiore si verifica quando l'albero è costituito da tutti nodi 2, mentre il ramo più a sinistra ha un'alternanza di un nodo 2 e un nodo 3. In questo caso siccome l'altezza nera è quella che ci interessa, avremo che il percorso è lungo il doppio rispetto a tutti gli altri percorsi.
Nella maggior parte delle applicazioni, l'altezza è quasi sempre ~1.0 lg N
Gli alberi binari di ricerca Rosso-Nero ci garantiscono una complessità logaritmica, anche nel caso peggiore, questo è il motivo per cui questo tipo di strutture dati sono Molto usati nella pratica. Nelle operazioni di rimozione dei nodi si applicano gli stessi principi visti per l'inserimento anche se il codice è più complicato.
Con un costo computazionale minimo possiamo sempre garantire un tempo di completamento logaritmico.
Questa è l'ennesima prova che un algoritmo performante è frutto di una corretta e creativa modellazione del problema.
Questa implementazione fu presentata alla Xerox PARC, negli anni 70. Era una famosa divisione di ricerca fondata nel 1970 che aveva sede a Palo Alto. Questa divisione di ricerca ha dato diversi contributi per quanto riguarda lo sviluppo delle moderne tecnologie, come le Interfacce Grafiche, Text editors What you see is What you get ed altre tecnologie.
Da una di queste innovazioni, ovvero la Stampante laser a colori, nasce la scelta di usare i link rossi e neri proprio perché il rosso era il colore che veniva stampato meglio, quindi fu scelto questo tipo di colore per distinguere questo tipo di nodi.
Descriviamo ora quella che è l'estenzione degli algoritmi che operano sugli alberi bilanciati per supportare ricerche esterne in tabelle dei simboli che sono mantenute sul disco o sul web; questo vuol dire che sono potenzialmente più grandi rispetto a quelle mantenute nella memoria locale.
I metodi che andiamo a studiare dovrebbero supportare la ricerca ed inserimento in tabelle contenenti più di trilioni di dati, usando 4/5 reference o piccoli blocchi di dati.
Page: con il termine pagina ci riferiamo ad un blocco continuo di dati (come ad esempio un file)
Probe: è il primo accesso ad una pagina (ad esempio dal disco alla memoria, oppure al cashing, dove la prima volta che visito una pagina è un'operazione più pesante rispetto a quando vi accederò una seconda volta)
L'obbiettivo è quello di sviluppare implementazioni di ricerca che utilizzono un numero minimo di probes, per trovare ogni data chiave.
L'approccio consiste nell'estendere la struttura dati degli alberi 2-3 con una fondamentale differenza: piuttosto che memorizzare i dati all'interno dell'albero, andiamo a costruire un albero che ha le copie delle chiavi a cui associa ad ogni chiave, piuttosto che il dato, associa un link.
Quindi abbiamo:
- I nodi interni hanno copie delle chiavi con associati i link
- I nodi esterni hanno l'effettiva coppia chiave-valore.
Quando sono arrivato nelle foglie, ovvero i nodi esterni, troverò il dato valore. Utilizzo questa struttura dati per capire quale foglia devo caricare in memoria per avere la coppia chiave valore effettiva.
Questo approccio ci permette di separare l'indice dalla tabella. Lo stesso concetto è applicato con gli indici dei libri, quando l'indice ci dice che un dato capitolo è situato ad una data pagina.
Abbiamo quindi visto le diverse strutture dati, tra le più efficienti i BST ed i R-B BST, ma possiamo fare di meglio?
La risposta è "si", ma dobbiamo prevedere un diverso tipo di accesso ai dati; non dobbiamo più dipendere dai confronti, e quindi pensare ad un metodo alternativo di accesso ai dati.
Ci salviamo gli elementi all'interno di una tabella indicizzata da della chiavi. L'indice all'interno della struttura dati, è una funzione della chiave. Si utilizza una cosiddetta funzione di hash che ci permette di calcolare l'indice dell'array a partire dalla chiave.
Esempio: hash("it") = 3
- Il primo è sicuramente la computazione della funzione di hash. Quali sono funzioni buone e funzioni cattive?
- Test di uguaglianza: un metodo per verificare che due chiavi siano uguali
- Risoluzione delle collisioni. Due chiavi diverse che hanno la stessa funzione di hash, ovvero che mappano sulla stessa posizione dell'array, è un problema. Abbiamo quindi bisogno di algoritmi e strutture dati per andare a gestire i casi in cui due chiavi hanno lo stesso hash.
- Non abbiamo limitazioni di spazio: Possiamo usare funzioni di hash molto semplici, dove la chiave è l'indice dell'array.
- Non abbiamo limitazioni di tempo: Limitiamo le collisioni andando a fare una ricerca sequenziale.
- Abbiamo entrambe le limitazioni: hashing (mondo reale).
Il goal di una funzione di hash è quello di disporre le chiavi in maniera uniforme per produrre l'indice della tabella.
Inoltre una funzione di hash dovrebbe essere:
- Calcolabile in maniera efficiente.
- Ogni indice della tabella deve essere ugualmente probabile per ogni chiave.
Una scelta non intelligente sarebbe quella di usare le prime tre cifre del numero come hash, in quanto esse cambiano poco frequentemente; una scelta più sensata sarebbe quella di usare invece le ultime tre cifre.
Questo metodo ritorna un intero di 32 bit, ovvero una chiave di hash per il dato intero. Solitamente questo intero ritornato è l'indirizzo di memoria dell'intero.
Requirement: Se x.equals(y), allora (x.hashCode() == y.hashCode())
Ovvero: se x è uguale ad y, allora i loro hashcode devono essere uguali.
Altamente desiderabile: Se !x.equals(y) allora (x.hashCode != y.hashCode())
Ovvero: se x ed y sono diversi, allora anche i loro hashcode devono essere diversi.
- Implementazione di default: ritornare l'indirizzo di memoria dell'intero.
- Implementazione legale ma frivola: ritornare sempre "17".
- Tipi definiti dall'utente: Gli utenti scelgono la maniera che preferiscono.
public final class Integer{
private final int value;
public int hashCode(){
return value;
}
}Implementazione classe Integer java
public final class Boolean{
private final boolean value;
public int hashCode(){
if(value) return 1231;
return 1237;
}
}Implementazione classe Boolean java
public final class Double{
private final double value;
public int hashCode(){
long bits = doubleToLongBits(value);
return (int) (bits ^ (bits >>> 32)); //convertiamo una rappresentazione a 64 ad una a 32 bit, mettendo ad XOR i 32 bit più significativi con i 32 bit meno significativi.
}
}Implementazione class Double java
public final class String{
private final char[] s;
public int hashCode(){
int hash = 0;
for(int i = 0; i < length(); i++){
hash = s[i] + (31 * hash);
}
return hash;
}
}Implementazione classe String java
Il metodo utilizzato è il cosiddetto metodo di Hornet.
public final class String{
private int hash = 0; //cache dell'hash
private final char[] s;
public int hashCode(){
int h = hash;
if(h != 0) return h; // se è già presente un hash, lo ritorno senza calcolarlo
for(int i = 0; i < length(); i++){
hash = s[i] + (31 * hash);
}
hash = h; // salvo il valore calcolato
return hash;
}
}Implementazione ottimizzata per String
public final class Transaction{
private final String who;
private final Date when;
private double amount;
...
public int hashCode(){
int hash = 17; // una costante diversa da 0
hash = 31*hash + who.hashCode();
hash = 31*hash + when.hashCode();
hash = 31*hash + ((Double) amount).hashCode();
return hash;
}
}Classe Transaction vista nelle prime lezioni
Ricetta "standard" per i tipi definiti dall'utente:
- Combinare ogni campo significativo usando la regola:
31x + y - Se il campo è di tipo primitivo (ad esempio Double) usiamo il tipo wrapper chiamando hashCode();
- Se il campo è null, ritorniamo 0.
- Se il campo è tipo di dato reference (ad esempio String o Date) andiamo ad usare in modo ricorsivo la funzione hashCode().
- Se il campo è un array, applichiamo l'hashing ad ogni elemento dell'array, usando
deepHashCode().
Dobbiamo ovviamente gestire le collisioni: come ci comportiamo quando due elementi diversi, ma con hash uguale, si mappano sulla stessa posizione dell'array? La tecnica del separate chaining consiste nell'usare un array di M linked lists.
- Hash: mappo la chiave ad un intero i compreso tra 0 ed M-1
- Inserimento: pongo l'elemento all'inizio della i-esima catena
- Ricerca: ho bisogno di cercare solo nella i-esima catena, ignorando quindi tutto il resto delle posizioni.
public class SeparateChainingHashST<Key, Value>{
private int M = 97; //numero di catene
private Node[] st = new Node[M]; //array di catene
private static class Node{
private Object key; //non creo un array generico
private Object val; //dichiaro una chiave ed un valore
private Node next;
...
}
public Value get(Key key){
int i = hash(key); // trovo l'indice attraverso l'hashing della chiave
for(Node x = st[i]; x != null; x = x.next){
if(key.equals(x.key)) return (Value) x.val;
}
return null;
}
}Codice della search (get)
public void put(Key key, Val val){
int i = hash(key);
for(Node x = st[i] ; x != null; x = x.next){
if(key.equals(x.key)){ //se trovo nella catena proprio la chiave, aggiorno quel valore
x.val = val;
return:
}
st[i] = new Node(key,val,st[i]); //aggiungo nella TESTA della catena il nuovo nodo
}
}Le probabilità che il numero di chiavi in una lista è compreso tra un fattore costante di N / M è estremamente vicino ad 1, ovvero stiamo dicendo che è molto probabile che le chiavi di una lista siano ben distribuite lungo la collezione di catene.
Quindi, il numero di elementi che dobbiamo controllare durante l'inserimento o ricerca è proporzionale ad N/M:
- Se abbiamo un M troppo grande, avremo sprecato spazio, in quanto abbiamo troppe catene vuote.
- Se abbiamo un M troppo piccolo, le catene saranno troppo lunghe (meno veloce nella ricerca ed insert)
- Una scelta tipica è quella di usare un M pari a ~ N / 4. Questo garantisce delle operazioni che terminano in un tempo costante.
Con questi accorgimenti abbiamo accelerato di M volte le operazioni rispetto ad una ricerca sequenziale.