Guida String interning - Part 2

driverfury

Utente Electrum
26 Agosto 2015
326
14
147
150
Ultima modifica:
Introduzione
Questa guida è il seguito di String interning - Part 1.

La scorsa volta abbiamo implementato la seguente interfaccia:
C:
extern char *strintern(char *s);
extern unsigned int strinternlen(char *s);

Abbiamo visto che la tecnica dello string interning può risultare molto utile quando si vogliono confrontare delle stringhe. Normalmente (senza string interning) si fa una cosa del genere:
C:
strcmp(str1, str2) == 0
Ma a volte, la funzione strcmp può risultare dispendiosa in quanto confronta carattere per carattere.

Grazie allo string interning, invece, avendo una copia unica di ogni stringa differente è possibile effettuare un confronto tra due stringhe mediante un semplice:
C:
str1 == str2
Dove str1 e str2 sono due stringhe già "interned".

Nella parte 1 abbiamo implementato l'interfaccia di sopra facendo uso delle liste concatenate (linked list). Ovvero ogni volta che viene aggiunta una stringa nuova, viene messa in coda alla lista. Ad esempio, se scriviamo il seguente codice:
C:
strintern("ciao");
strintern("hola");
strintern("miao");
Si parte, con la lista vuota. Dopodiché viene aggiunta la stringa "ciao" alla lista:
Codice:
+----------+
|  "ciao"  |
+----------+
admire my ASCII skillz! ;)
Successivamente, viene aggiunta la stringa "hola".
Codice:
+----------+   +----------+
|  "ciao"  |-->|  "hola"  |
+----------+   +----------+
Ed, infine, viene "internata" la stringa "miao"
Codice:
+----------+   +----------+   +----------+
|  "ciao"  |-->|  "hola"  |-->|  "miao"  |
+----------+   +----------+   +----------+

Fin qui ci siamo. Cosa succede, però quando vogliamo aggiungere una nuova stringa?

L'implementazione scritta la scorsa volta cerca nella linked list per verificare se esiste già la stringa che vogliamo aggiungere: ovvero parte dalla prima, confronta carattere per carattere con la stringa che vogliamo aggiungere, se sono diverse si passa alla successiva e così via.

Ed è proprio questo tipo di ricerca a risultare abbastanza dispendioso. Nel peggiore dei casi, devono essere effettuati n confronti di stringhe (dove n è la lunghezza della linked list, ovvero il numero di stringhe "internate"). Quindi, se abbiamo molte stringhe nel nostro database tale algoritmo risulterebbe troppo lento.

Come possiamo risolvere?

Hashing

Utilizzeremo la tecnica dell'hashing. Tale tecnica consiste nel trasformare una qualsiasi stringa in una chiave (un numero) che la rappresenti.

Per noi sarà una funzione di questo tipo:
C:
static int strhash(char *s);

Data una stringa in input, restituisce un numero, che sarà la nostra chiave.

In pratica, l'idea è quella di avere un array, anziché una linked list. Il nostro nuovo database sarà di questo tipo:

C:
static strinterned _strinterns[128];

Perché un array di 128 elementi? Fra poco capirete il perché.

Vogliamo realizzare la più semplice implementazione possibile della funzione int strhash(char *s);.

La più semplice a cui riesco a pensare in questo momento è una funzione che restituisce il valore ASCII del primo carattere della stringa. Sai già che ogni carattere corrisponde ad un numero, vero? Nel caso in cui non lo sapessi, ecco una tabella (ogni carattere corrisponde ad un numero):
Codice:
00    NUL  |  1A    SUB    |  34    4  |  4E    N  |  68    h
01    SOH  |  1B    ESC    |  35    5  |  4F    O  |  69    i
02    STX  |  1C    FS     |  36    6  |  50    P  |  6A    j
03    ETX  |  1D    GS     |  37    7  |  51    Q  |  6B    k
04    EOT  |  1E    RS     |  38    8  |  52    R  |  6C    l
05    ENQ  |  1F    US     |  39    9  |  53    S  |  6D    m
06    ACK  |  20    space  |  3A    :  |  54    T  |  6E    n
07    BEL  |  21    !      |  3B    ;  |  55    U  |  6F    o
08    BS   |  22    "      |  3C    <  |  56    V  |  70    p
09    HT   |  23    #      |  3D    =  |  57    W  |  71    q
0A    LF   |  24    $      |  3E    >  |  58    X  |  72    r
0B    VT   |  25    %      |  3F    ?  |  59    Y  |  73    s
0C    FF   |  26    &      |  40    @  |  5A    Z  |  74    t
0D    CR   |  27    '      |  41    A  |  5B    [  |  75    u
0E    SO   |  28    (      |  42    B  |  5C    \  |  76    v
0F    SI   |  29    )      |  43    C  |  5D    ]  |  77    w
10    DLE  |  2A    *      |  44    D  |  5E    ^  |  78    x
11    DC1  |  2B    +      |  45    E  |  5F    _  |  79    y
12    DC2  |  2C    ,      |  46    F  |  60    `  |  7A    z
13    DC3  |  2D    -      |  47    G  |  61    a  |  7B    {
14    DC4  |  2E    .      |  48    H  |  62    b  |  7C    |
15    NAK  |  2F    /      |  49    I  |  63    c  |  7D    }
16    SYN  |  30    0      |  4A    J  |  64    d  |  7E    ~
17    ETB  |  31    1      |  4B    K  |  65    e  |  7F    DEL
18    CAN  |  32    2      |  4C    L  |  66    f       
19    EM   |  33    3      |  4D    M  |  67    g

Il carattere 'A' ad esempio corrisponde al numero (in esadecimale) 0x41 mentre 'x' corrisponde a 0x78.

Infatti se facciamo il confronto:
C:
'x' == 0x78
Il risultato di tale confronto in C assume valore true (vero, non zero).

L'ultimo carattere corrisponde a 0x7f, ovvero in decimale 127. Ecco spiegato il motivo per cui l'array ha 128 elementi.

L'implementazione (molto rudimentale) della nostra funzione di hashing sarà quindi:

C:
static int strhash(char *s)
{
    if(s)
    {
        return((int)*s);
    }
    else
    {
        return(0);
    }
}

Ovvero, ritorna il primo carattere della stringa (facendo anche il casting da char a int).

Vogliamo che ogni stringa venga memorizzata nell'array _strinterns nella posizione strhash(s), in questo caso la posizione corrispondente al valore ASCII del primo carattere.

Occorre cambiare la struttura struct strinterned in qualcosa che faccia al caso nostro:

C:
struct strinterned
{
    unsigned int len;
    char str[33];
};

Per il momento abbiamo limitato la lunghezza delle stringhe internate a 32 caratteri + 1 carattere terminatore.

Dobbiamo anche cambiare la funzione extern char *strintern(char *s); perché non abbiamo più a che fare con le liste concatenate ma con un array:

C:
extern char *strintern(char *s)
{
    int hashkey;

    hashkey = strhash(s);

    assert(hashkey >= 0 && hashkey < 128);
    assert(strlen(s) <= 32);

    strcpy(_strinterns[hashkey].str, s);
    _strinterns[hashkey].len = strlen(s);

    return((char *)_strinterns[hashkey].str);
}

In questo modo, quando runniamo il codice di prima, ovvero:

C:
strintern("ciao");
strintern("hola");
strintern("miao");

Abbiamo inizialmente un array "vuoto" (tutti i valori settati a zero).

Quando aggiungiamo la stringa "ciao" l'array diventa:

Codice:
...
0x63 => "ciao"
...

dove 0x63 è il valore ASCII (in esadecimale) del primo carattere della stringa, ovvero 'c'.

Successivamente, viene aggiunta la stringa "hola" e l'array diventa:

Codice:
...
0x63 => "ciao"
...
0x68 => "hola"
...

Ed, infine, viene aggiunta la stringa "miao":

Codice:
...
0x63 => "ciao"
...
0x68 => "hola"
...
0x6D => "miao"
...

In questo modo, quando vogliamo cercare una stringa nel database ci basta calcolare la posizione nell'array mediante la funzione strhash e confrontare la stringa da cercare con la stringa a tale posizione. Ovvero, nel peggiore (e anche nel migliore) dei casi effettuiamo un solo confronto!

Not bad, uh?

Il vero "peggiore dei casi"

In realtà il vero peggiore dei casi si presenta in una maniera differente.

Per fare un esempio concreto, si pensi che si vuole aggiungere la stringa "hello" la cui chiave corrisponde a 0x68. Ma tale posizione risulta già occupata dalla stringa "hola". Col codice scritto finora si rischia di sovrascrivere la precedente stringa con la nuova.

Per evitare il più possibile questi "conflitti" (ovvero due stringhe differenti che hanno chiavi uguali) occorre scrivere una funzione di hashing "migliore" ovvero che presenta la minor probabilità di conflitto.

Inoltre, siccome nessuna funzione di hashing è perfetta, occorre escogitare un modo per risolvere anche quei casi (improbabili se la funzione di hashing è buona) di conflitto.

Lo vedremo nella prossima puntata. Ritorneranno le linked list (usate in maniera più intelligente), vedremo le strutture ad albero e tante altre belle cose.

Inoltre, c'è anche un altro problema... cosa succede se il carattere non è ASCII? Ovvero se non è compreso tra 0 e 127 ma è, ad esempio, è numero negativo? Perché vorrei ricordare a tutti, soprattutto a me stesso, che un char in C può avere anche il segno e quindi essere un numero negativo.

Stay tuned.
 
Non so se sto spoilerando troppo, magari hai intenzione di parlarne in part 3, ma il modo semplice per gestire le collisioni si chiama chaining: tieni buono tutto il codice scritto in part 1 e gli piazzi sopra la funzione di hash che divide in buckets.
C:
// come in part 1
struct strinterned { ... };

// come in part 2
static strinterned table[128];

// part 1 con _strinterns parametrico ovunque usato
extern char *strintern(char *s) { return strintern_part1(s, &table[strhash(s)]); }

Le funzioni di hash perfette esistono, ma quelle dinamiche sono complicate e poco pratiche.
 
  • Mi piace
Reazioni: driverfury
Non so se sto spoilerando troppo, magari hai intenzione di parlarne in part 3, ma il modo semplice per gestire le collisioni si chiama chaining: tieni buono tutto il codice scritto in part 1 e gli piazzi sopra la funzione di hash che divide in buckets.
C:
// come in part 1
struct strinterned { ... };

// come in part 2
static strinterned table[128];

// part 1 con _strinterns parametrico ovunque usato
extern char *strintern(char *s) { return strintern_part1(s, &table[strhash(s)]); }

Le funzioni di hash perfette esistono, ma quelle dinamiche sono complicate e poco pratiche.
Sì, esatto.

Ogni elemento dell’array diventerà una linked list. E poi si trasformerà in qualcosa di ancora più performante.

Riguardo alle funzioni di hashing perfette, a quale ti riferisci? Mi hai incuriosito… (sono un newbie in materia).
 
Riguardo alle funzioni di hashing perfette, a quale ti riferisci? Mi hai incuriosito… (sono un newbie in materia).
Si chiamano proprio perfect hash functions e più che funzioni di hash vere e proprie si possono vedere come un implementazione delle hash tables: quelle statiche ti permettono di fare solo accessi, mentre quelle dinamiche ti permettono anche di inserire e rimuovere elementi; in termini di funzioni, $$\(h : K \to V$$\) è statica se l'insieme di chiavi K è finito ed è dinamica altrimenti.

Una delle principali tecniche utilizzate per creare funzioni di hash statiche e perfette consiste nell'inserire hash tables dentro la hash table principale, laddove in part 3 tu andrai a usare linked lists o alberi di ricerca. Scegliendo opportunamente le funzioni di hash, una per la prima tabella e una per ogni tabella di secondo livello, si può garantire che anche nel caso peggiore il risultato finale sia senza collisioni e che lo spazio complessivo lineare. Se la vuoi rendere dinamica, fai rehashing (la distruggi e la ricostruisci più grande o più piccola) nel momento opportuno e ti accontenti di ammortizzare i costi.

Le funzioni di hash statiche perfette sono utilizzate nella vita reale (per i grafi del web, ad esempio), quelle dinamiche non credo... come anche il cuckoo hashing: molto bello dal punto di vista teorico, molto brutto dal punto di vista pratico. I computer sono molto bravi a fare ricerche lineari, cache friendly, e le hash tables fanno l'esatto opposto.
 
Si chiamano proprio perfect hash functions e più che funzioni di hash vere e proprie si possono vedere come un implementazione delle hash tables: quelle statiche ti permettono di fare solo accessi, mentre quelle dinamiche ti permettono anche di inserire e rimuovere elementi; in termini di funzioni, $$\(h : K \to V$$\) è statica se l'insieme di chiavi K è finito ed è dinamica altrimenti.

Una delle principali tecniche utilizzate per creare funzioni di hash statiche e perfette consiste nell'inserire hash tables dentro la hash table principale, laddove in part 3 tu andrai a usare linked lists o alberi di ricerca. Scegliendo opportunamente le funzioni di hash, una per la prima tabella e una per ogni tabella di secondo livello, si può garantire che anche nel caso peggiore il risultato finale sia senza collisioni e che lo spazio complessivo lineare. Se la vuoi rendere dinamica, fai rehashing (la distruggi e la ricostruisci più grande o più piccola) nel momento opportuno e ti accontenti di ammortizzare i costi.

Le funzioni di hash statiche perfette sono utilizzate nella vita reale (per i grafi del web, ad esempio), quelle dinamiche non credo... come anche il cuckoo hashing: molto bello dal punto di vista teorico, molto brutto dal punto di vista pratico. I computer sono molto bravi a fare ricerche lineari, cache friendly, e le hash tables fanno l'esatto opposto.
Grazie mille. Spunti interessantissimi.

Vado a studiare in merito.