Dizionari in C

Fino ad ora abbiamo visto che una delle cose più costose è sempre stata la ricerca. Cercare un elemento da qualche parte è sempre difficile. Abbiamo visto che per cercarlo in una lista disordinata ci mettiamo al caso pessimo la lunghezza della stringa: $O(n)$ E abbiamo visto che la ricerca è un po’ più facile quando dobbiamo cercare un elemento in una lista già ordinata, in quel caso possiamo usare la ricerca binaria che impiega solamente $O(log(n))$. C’è un modo di essere più veloci? SI In realtà possiamo fare talmente meglio da far paura. I dizionari, infatti, ci permettono di cercare le cose in tempo costante: $O(1)$

Cos’è un dizionario

Se sai già cos’è un dizionario salta questa parte. Un dizionario è una struttura dati che contiene un insieme di coppie Chiave/valore.

Una cosa del genere:

Chiave	Valore
”Biondi”	6
”Mori”	12
”Rossi”	2
Questo è un dizionario che ci dice quante persone ci sono con un determinato colore di capelli.
Se vogliamo sapere quanti biondi ci sono, ci basta chiedere al dizionario d[“Biondi”] e lui ci restituirà il valore “6”.

Figo, ma perché ci interessa? Beh il dizionario ci mette tempo costante a cercare qual’è il valore associato a “Biondi”. Cioè, a differenza di come abbiamo sempre visto, quando io gli chiedo “Dammi il valore associato alla chiave Biondi”, lui NON SI VA A SCORRERE LA LISTA DELLE CHIAVI finché non ha trovato “Biondi”. Assolutamente no. Lui va a colpo sicuro. Vediamo come

Il trucco: La funzione hash

Il trucco sta che invece di conservare queste coppie chiave/valore in modo classico, quindi una di fila all’altra tipo così (se le avessimo così al caso pessimo ci metteremmo O(n) a cercare in questa lista di coppie):

Inseriamo queste coppie in sparse all’interno di una lista quasi tutta vuota:

Già sento gli scettici che diranno: Hai solo peggiorato le cose! Adesso dobbiamo cercare in una lista ancora più lunga NO. Perché il posto dove mettere le coppie non è stato scelto a caso. Il posto dove mettere “Rossi”, “Biondi” e “Mori” non è stato scelto da me, ma da una funzione chiamata “Funzione hash”. La funzione hash mi ha detto di inserire “Biondi” al primo posto, “Mori” al secondo posto, e “Rossi” al penultimo. Con che criterio? La cosa più bella è che del criterio con cui la funzione hash sceglie queste posizioni non ce ne può fregare di meno. “Bella merda”, direte voi, “a sto punto era meglio scegliere a caso i posti”. NO. Perchè la funzione hash SA ESATTAMENTE DOVE LI HA MESSI, ricordatevi, la funzione hash non li ha scelti a caso. La prossima volta che andrò a chiedere alla funzione hash “hey ti ricordi dove sta la chiave Rossi?” Lei ci risponderà “Certamente, è in penultima posizione”. Quindi quando dovrò cercare qualcosa, mi basterà chiederlo alla funzione hash! e lei mi risponderà con l’esatta posizione.

Così facendo il tempo di ricerca diventa costante: $O(1)$.

Se devo inserire un nuovo elemento?

Se devi inserire un nuovo elemento, di nuovo, non saremo noi a decidere dove va, sarà la funzione hash. Supponiamo di voler aggiungere il numero di persone con i capelli castani

Chiave	Valore
”Biondi”	6
”Mori”	12
”Rossi”	2
”Castani”	23
Interrogo la funzione “hash” e mi dice che “castani” va in quarta posizione

Di nuovo, se ci servirà sapere quante persone hanno i capelli castani ci basterà chiedere alla funzione hash “dove sta la chiave Castani?” e lei risponderà “è il quarto elemento della lista”. Impiegando quindi tempo costante nella ricerca.

Il vero problema

Il vero problema si pone quando avviene un fatto terribile: la collisione. Se ad un certo punto io volessi aggiungere i “Pelati”

Chiave	Valore
”Biondi”	6
”Mori”	12
”Rossi”	2
”Castani”	23
”Pelati”	3
Adesso può accadere che quando chiediamo alla funzione hash dove inserire la nuova chiave, quella ci risponda una casella già presa: tipo la numero quattro

C’è già “Castani” in posizione 4!

Come la gestiamo? La soluzione è abbastanza semplice: prendiamo “Pelati” e lo attacchiamo a “Castani”

Adesso se cerchiamo il numero di Pelati o di Castani la funzione hash ci dirà che sono in posizione 4, ma dovremmo comunque scorrere la lista: Per trovare quello che cerchiamo.

Quindi le collisioni fanno aumentare il tempo di ricerca. L’idea è quindi di cercare di tenere queste liste il più piccole possibile. Ovviamente più è grande la lista principale, meno probabilità ci sarà che avvenga una collisione: Di contro abbiamo che sprechiamo un botto di spazio per delle caselle vuote.

Il caso estremo contrario sarebbe quello in cui abbiamo una sola casella nella lista principale e tutte le coppie sono concatenate come in una lista concatenata.

In questo caso la ricerca sarebbe ovviamente $O(n)$ come in una lista concatenata, ma non staremmo sprecando nessuna casella.

Il giusto equilibrio

Ci deve essere quindi il giusto equilibrio tra la lunghezza della lista principale, ed il numero di coppie chiave valore inserite. Generalmente, se la funzione hash è buona, ci basta tenere il numero delle coppie chiave/valore proporzionale alla lunghezza della lista principale per assicurarci che la ricerca sia costante.

Il dizionario in C

Ora che abbiamo chiaro cos’è un dizionario, e come funziona cominciamo ad implementarlo.

Quindi, un dizionario è fatto da una lunga lista, e da “nodi” ad essa attaccati

In verde c’è la lista principale ed in rosso uno dei nodi. Vediamo in C:

struct dict {
	nodo **a; //lista principale
	int m; // numero di liste (dimensione della lista principale)
	int n; // numero di elementi nel dizionario
};
typedef struct dict dict;

Questo è il dizionario: una lista di liste di nodi. Nel dizionario teniamo anche m (la lunghezza della lista principale (quella a sinistra in verticale)), ed n, cioè il numero di elementi. Dobbiamo fare in modo che n non cresca troppo rispetto ad m, altrimenti ci saranno troppe collisioni, per questo ce lo conserviamo. Ma per ora non preoccupiamocene.

com'è fatto un nodo?

Un nodo è ovviamente fatto da una coppia chiave/valore, ma anche da un puntatore ad un nodo successivo.

In verde c’è il nodo. In blu la coppia chiave-valore in rosso il puntatore all’elemento successivo.

In C:

 
struct nodo { //il nodo (in verde nell'immagine sopra)
	d_item info; // la coppia chiave-valore (in blu)
	struct nodo *succ; //il puntatore al nodo successivo (in rosso)
};
typedef struct nodo nodo;
 
struct d_item { // la coppia chiave-valore
	char *k; //la chiave (una stringa)
	float v; // il valore (un float)
};
typedef struct d_item d_item;
 

Creiamo il dizionario

Adesso che abbiamo definito le struct necessarie possiamo finalmente creare il nostro primo dizionario.

dict init

dict dict_init(int m){
	/*
	 * Ritorna un dizionario vuoto con m liste
	 * */
	dict d;
	int i;
	
	d.a = malloc(m*sizeof(nodo*));
	d.m = m;
	d.n = 0;
	for(i = 0; i < m; i++){
		d.a[i] = NULL;
	}
	
	return d;
}

Il prof ha sviluppato questa funzione per creare un nuovo dizionario di lunghezza m. Vuoto.

int main(int n, char *args[]){
	dict d = dict_init(5);
}

Se chiamiamo questa funzione nel main quello che avremo sarà un dizionario di cinque elementi. Vuoto. Praticamente una cosa del genere: Un dizionario chiamato “d” di cinque elementi. Come vediamo ancora non c’è nessuna coppia chiave valore.

Adesso magari vorremmo inserire un elemento.

Inseriamo un elemento nel dizionario

Supponiamo di voler inserire l’elemento

Pelati	3

Non manca qualcosa? SI. Ci serve la funzione hash, per chiedergli “dove devo inserire la chiave Pelati?”.

è arrivato il momento di fare i conti con la funzione hash.

La funzione hash prende in input una chiave e restituisce una posizione della lista principale (quella verticale), nel nostro caso ci darà un numero da uno a cinque.

int h(char *x, dict d){ //prende in input la chiave (e il dizionario)
	
	return out % d.m; //restituisce un numero che va da 0 a d.m
}
 

La funzione hash prende in input la chiave e restituisce un numero compreso tra 0 e la lunghezza della lista principale (da 0 a d.m)

out % d.m 

è l’operazione “modulo” (se non la conoscete studiate matematica discreta, bestie!). Fare il modulo ci assicura che il numero non superi d.m (la lunghezza della lista principale).

“out” è ottenuto facendo lo xor di ogni bit della stringa. Ma questo ci interessa fino ad un certo punto. Quello che ci interessa è che ora abbiamo una funzione che ci dice dove mettere le coppie!

int h(char *x, dict d){
	int out = 0;
	int i = 0;
	
	while( x[i] != '\0'){ //per ogni bit di x (la chiave)
		out = x[i]^out; //fai lo xor con out
		i++; // prossimo bit
	}
	
	return out % d.m;
}

Ora che abbiamo una funzione hash sviluppiamo l’algoritmo per inserire un elemento.

L’algoritmo a grandi linee sarà questo:

1. prendo il nuovo nodo da aggiungere

2. chiedo alla funzione hash qual’è la sua posizione nella lista principale

3. vado a vedere se c’è già un elemento con quella chiave (in caso sia già lì aggiorno il valore)

4. se la chiave non è già lì allora aggiungo il nodo alla sua casella

Vediamo in C:

dict dict_update(dict d, d_item e){ 
 
	nodo *p; // nuovo nodo
	int lis = h(e.k, d); //chiedo alla funzione hash dove lo devo mettere, lei mi risponde "mettilo in lis"
	
	
	p = lista_cerca_k(d.a[lis], e.k);  // in lis ci potrebbero già essere una lista di nodi! Cerco se c'è già la mia chiave
	
	if ( p == NULL ) { // la chiave non è nel dizionario
	
		 d.a[lis] = lista_in0(d.a[lis], e); // inserisco il mio elemento
		 d.n++;
	} else { //la chiave è già nel dizionario !
 
		p->info.v = e.v; // aggiorno il valore
	}
	
	return d; //ritorno il dizionario aggiornato
}