2023-10-19 - radixsort-hashmaps

universityin-classsubject-2101

2023-10-19

Algoritmi

Counting & Radix Sort

Per ordinare un array sulla base di più chiavi è sufficiente ordinare per ogni chiave dalla meno importante alla più importante. È necessario che gli algoritmi di ordinamento utilizzati siano stabili, altrimenti il metodo non funziona.
L’ordinamento, anche se non è stabile, se utilizzato solo sulla prima iterazione, rende comunque l’algoritmo funzionante, ma non stabile.

Per ordinare numeri grossi con il counting sort si può utilizzare il metodo precedente, ordinando per ogni cifra separatamente.
Si può utilizzare n%10 per ottenere l’ultima cifra e utilizzare per ottenere l’i-esima cifra da destra.
Questo algoritmo è detto Radix Sort.

/*
se A=[8532, 2553, 2634] e i=2 il counting sort vede [5, 5, 6]
*/
void radixSort(int* A, int n) {
	int c = getMaxNumberOfDigits(A, n); // se max(A)=1'000'000   =>   c=7
	for (int i = 0; i < c; i++) {
		countingSort(A, n, i); // dove i è la posizione (da destra) della cifra su cui ordinare
	}
}

Dizionario

È importante avere una ricerca veloce, a costo di sacrificare tempi di inserimento e cancellazione.

Tabella a indirizzamento diretto

Si utilizza una tabella a indici da a dove il numero (compreso tra e ) si inserisce nella posizione .

void insert(int* A, int x) {
	A[x] = x;
}
void remove(int* A, int x) {
	A[x] = NULL; // pseudocodice
}
bool search(int* A, int x) {
	return A[x] != NULL;
}

Si può ottimizzare sostituendo il tipo dell’array da int in bool (mettendo 1 se l’elemento è presente, altrimenti 0).

Nota

Questa implementazione non funziona quando bisogna conservare numeri molto grandi (servirebbe un array di uguale dimensione).

Tabella Hash

Si consideri l’insieme delle chiavi da rappresentare.
Si utilizza una tabella (chiamata ) a indici da a .
La tabella contiene meno celle delle chiavi da rappresentare:

Si utilizza un oracolo: è una funzione, detta funzione hash, che prende in input un elemento di e restituisce un numero compreso tra e .

È importante che la funzione hash ritorni sempre lo stesso valore per lo stesso numero dato in input.

Essendo esistono delle collisioni: .
Esistono molti metodi per risolvere il problema e conservare e .

Metodo concatenazione

Si utilizzano le liste.
Ogni elemento di è in realtà una lista a cui vanno concatenati gli elementi man mano che vengono inseriti.
Con questo metodo bisogna effettuare la ricerca all’interno di una lista in tempo lineare (e non più costante).
Consideriamo chiamato fattore di carico, dove è il numero di elementi.
Ogni operazione di ricerca impiega in media , adattando si può considerare un tempo costante.

void insert(list* T, int k) {
	T[h(k)].insert(k);
}
void remove(list* T, int k) {
	T[h(k)].remove(k);
}
bool search(list* T, int k) {
	return T[h(k)].search(k);
}

Metodo indirizzamento aperto

prossima lezione

---

Proprietà della Hash Function

L’hashing uniforme semplice è una proprietà che indica la probabilità che la funzione di hash distribuisca in modo uguale gli elementi nelle celle.

Implementazione

Ci sono vari metodi per implementare la funzione hash.

Metodo divisione

Se consideriamo (con ) il metodo di divisione restituisce gli ultimi bit (meno significativi), aumentando il rischio di collisione. Per questo si consiglia di evitare potenze di due come valore di .

Metodo moltiplicazione

Si consideri .

Si prende , si moltiplica per e si ottiene un numero arbitrariamente grande () decimale. Con il si prende la parte decimale di quest’ultimo e si moltiplica per , ottenendo un numero compreso tra e .

A differenza del caso precedente, la scelta di non influenza l’ipotesi dell’hashing uniforme semplice. Si può quindi considerare e adattare l’algoritmo per ottimizzarlo.
Considerando come il numero di bit della parola della macchina, l’algoritmo diventa: