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
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
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");
"ciao"
alla lista:
Codice:
+----------+
| "ciao" |
+----------+
Successivamente, viene aggiunta la stringa
"hola"
.
Codice:
+----------+ +----------+
| "ciao" |-->| "hola" |
+----------+ +----------+
"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
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.