Appunti di Ingegneria degli Algoritmi

ESEMPIO BI-DIMENSIONALE:

double a[10][20];

i = 4; j = 3;

x = a[i][j];

In C e linguaggi derivati, viene effettuata una memorizzazione per righe.

Per accedere a[i][j] il compilatore ha bisogno di conoscere:

• L'indirizzo di partenza in memoria dell'array a
• La dimensione di ciascun elemento dell'array (double ha 8 byte)
• L'indirizzo iniziale di ciascuna dimensione xb (in C è zero)
• Il numero di elementi NC in ciascuna riga (in questo caso 20)

Allora il calcolatore può calcolare:

addr = start(a) + size * ((i - xb) * NC + (j - xb) = start(a) + 8 * (4 - 0) * 20 + (3 - 0))

Gli array multidimensionali possono essere anche memorizzati per colonne.

Il primo indice potrebbe essere 1 invece che 0 (questo in Matlab, Fortran...) e la funzione di indice deve essere modificata usando il numero di righe invece che il numero di colonne:

addr = start(a) + size * ((i - xb) * NR + (j - xb) = start(a) + ...

----------------------------------------------------------------------

SE IL NUMERO DI RIGHE O COLONNE NON E' NOTO AL MOMENTO DI COMPILAZIONE

----------------------------------------------------------------------

Potremmo avere la necessità di scrivere un programma che lavora su array bidimensionali ma le cui dimensioni non sono fissate a tempo di compilazione.

Nel linguaggio C il compilatore interpreta l'espressione "x = mat[i][j]" in modo completamente diverso a seconda che le dimensioni siano note o meno al tempo di compilazione.

Se le dimensioni sono note solo a runtime:

• mat è un puntatore ad un array di puntatori; con mat[i] si seleziona l'elemento puntatore all'indice [i]
• Ciascun puntatore identifica un distinto array di riga; gli elementi di ciascuna riga sono indirizzati da [j]
• Ciascuna riga è allocata indipendentemente, e non c'è alcuna ovvia relazione tra le posizioni in memoria degli elementi di

2 qualsiasi righe

Utilizzare memorizzazione access table (ogni elemento del vettore punta ad un altro elemento oppure ad un altro vettore).

SUPPORTO ARRAY MULTIDIMENSIONALI CONTIGUI

In Fortran, Matlab, Julia si possono definire facilmente array contigui

In Java non è possibile

In C o C++ si possono usare gli array come se fossero 1-dimensionali per poter realizzare la funzione di indirizzamento a mano:

void compute(int nr, int nc, double mat[]){
    x = mat[my2dindex(i,j,nr,nc)]
}

int my2Dindex(i,j,nr,nc){
    return(i*nc+j);
}

SALVATAGGIO IN TABELLA

Supponiamo di avere una certa quantità di dati, con chiavi numeriche e che possano avere delle ripetizioni (ossia diversi record possono contenere la stessa chiave). Si potrebbero memorizzare i puntatori ai record in una tabella bidimensionale:

R1 R2 NIL NIL
R3 NIL NIL NIL
R4 R5 NIL NIL

Supponiamo di avere una certa

quantità di dati, con chiavi memorizzate su 8bytes, quindi con valori nell’insieme da 1 a 2⁶⁴- Usare le chiavi come indici in una tabella consente di fare ricerche in tempo O(1)- L’idea potrebbe essere generalizzata al caso di chiavi non numeriche come le stringhe, usando la loro rappresentazione binaria.Il problema con questa implementazione è la gestione delle possibili quantità enormi di dati (perciò righe e colonne della tabella). Se l’insieme delle chiavi è più piccolo dell’insieme universo, allora avremo uno spreco di memoria.

FUNZIONI INDICE

Data una chiave K appartenente all’universo U delle chiavi, cerchiamo una funzione h(K): U → {1,…,m} iniettiva, ossia tale che per K != K si abbia sempre h(K ) != h(K )

L’iniettitivà richiede che i valori di h(K) appartengano ad un insieme di stessa cardinalità di U. Rilassando la condizione di iniettività,

è possibile diminuire la dimensione della tabella, aumentando però la probabilità di collisione.

-------------------FUNZIONI DI HASHING-------------------

La dimensione della tabella può essere molto più piccola dell’universo, ma occasionalmente si può avere una collisione. Utilizziamo la funzione di hash.

Le collisioni avvengono nel caso in cui per elementi K diversi, i loro hash siano uguali.

Requisiti per una tabella hash:

• Che sia disponibile una funzione di hash h() calcolabile velocemente O(1)
• Che la funzione h() sia tale che i valori calcolati sull’insieme delle chiavi (attese) siano ben distribuiti
• Che sia disponibile un metodo per la risoluzione delle collisioni
• Che la dimensione m della tabella sia una sovrastima della cardinalità dell’insieme delle chiavi da gestire, in modo da evitare un riempimento completo (questo requisito è necessario per almeno una tipologia di tabelle hash)

La funzione h dovrebbe

essere uniforme, ossia la probabilità che una chiavequalsiasi K venga inserita nella posizione i della tabella (di dimensione m)dovrebbe corrispondere ad una distribuzione uniforme

Le funzioni di hash si costruiscono in 2 modi: troncamento e folding.

Molto spesso per gestire le chiavi si usa la loro rappresentazione numerica.

- Troncamento: Si usa solo un sottoinsieme del valore della chiave

- Folding: Si spezza una chiave in più parti, e le parti vengono combinateattraverso una funzione ausiliaria

In molte applicazioni si usano degli identificatori con parti comuni e partivarianti, come Type1, Type2, Type3, etc. Nel troncamento si elimina la partecomune, in questo caso “Type” e tenendo solamente 1,2,3 (valori hash).

Alcuni esempi di funzioni hash:

- Estrazione: h(K) = int(b) dove b è un sottoinsieme dei bit dellarappresentazione binaria di K, di solito la parte centrale

- Xor: h(K) = int(b), b = p (k) ⊕ p (k) ⊕ … ⊕ p (k) dove p(k)

è una1 2 npartizione della chiave K e ⊕ è l’operatore OR-inclusivo bit a bit- Moltiplicazione: h(k) = ⌊m(iC - ⌊iC ⌋) ⌋, dove m è un numero interoqualsiasi, i è int(bin(k)), C è un numero reale 0<C<1.

- Divisione: si usa il resto della divisione h(k) = int(bin(k)) mod m

Nota: funzione floor moltiplicazione Materiale approfondimento tabelle hash

Notare che int(b) = valore numerico di b e bin(k) = valore binario dik. Se definiamo int(bin(k)) otteniamo il valore numerico dellaconversione binaria di k. Esempio: int(bin(2)) = 10

-------------------------------------

NOTE PER MOLTIPLICAZIONE E DIVISIONE:

--------------------------------------

Nel metodo della moltiplicazione si può scegliere un valore m arbitrario maserve una buona scelta di C; Knuth propone C = (sqrt(5)-1)/2.

- Nel metodo della divisione serve un valore m dispari, preferibilmente primo;infatti assumendo la rappresentazione binaria dei dati con

bit, scegliendom = 2 tutti i valori che hanno gli stessi p bit finali andranno a collidere.p- Nel metodo di divisione si usano spesso dei valori primi distanti dallepotenze di due (13, 23, 47, 97, 193, 383…), ma maggiori di 2 p

------------------------------------------------------ESEMPIO DI COLLISIONE DELLE CHIAVI E METODI RISOLUTIVI------------------------------------------------------

Un esempio di funzione h (non molto efficiente): dato un cognome, la funzione hprende il valore 0 se la prima lettera è A, 1 se B e così via. Moltoprobabilmente dati alcuni cognomi, incontreremo una collisione.

Ci sono 2 metodi principali per la risoluzione delle collisioni:

- Metodi interni: scansione interna (open addressing)

- Metodi esterni: liste di trabocco (chaining)

---------------------------SCANSIONE INTERNA (LINEARE) NOTA: k mod m = resto di k/m---------------------------

Si estende la funzione h con un secondo argomento: h(K,i) con i = 0...m-1.

Se l'elemento della

La tabella indirizzata da h(K,i) è occupato, si passa al valore successivo di i, fin quando si sia scandita tutta la tabella; se la ricerca di una posizione libera è infruttuosa, la tabella è piena.

Definiamo scansione lineare: h(k,i) = (h'(k)+i) mod m. In fase di inserimento, se la posizione è occupata, andare nella prima disponibile a destra. Parte i=0.

Attenzione: se si cancella un elemento non si può marcare una posizione come libera. È necessario segnalare quella cella come eliminata. Se la tabella è piena, è necessario ripartire da zero costruendo una tabella espansa.

Se un gruppo di elementi sono vicini, si crea un cluster (o assembramento). Gli assembramenti tendono ad espandersi, cosa che vogliamo evitare poiché rallenta i tempi di ricerca della scansione. È opportuno che la funzione di scansione tocchi tutti i valori tra 0 e m-1, in modo che se esista una posizione vuota nella tabella essa venga opportunamente utilizzata.