Psihologia concursurilor de informatică/4 Heap-uri și tabele de dispersie

From Algopedia
Revision as of 08:36, 7 March 2018 by Cata (talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

⇦ înapoi la Psihologia concursurilor de informatică

Capitolul IV: Heap-uri și tabele de dispersie

Vom încheia prezentarea structurilor de date mai speciale cu două structuri care se fac folositoare în problemele de căutare și sortare. Ele nu sunt dificil de implementat și se mulează peste orice structuri de date care conțin multe înregistrări ce pot fi ordonate după anumite criterii.

Heap-uri

Să pornim de la o problemă interesantă mai mult din punct de vedere teoretic:

ENUNȚ: Un vector se numește k-sortat dacă orice element al său se găsește la o distanță cel mult egală cu k de locul care i s-ar cuveni în vectorul sortat. Iată un exemplu de vector 2-sortat cu 5 elemente:

{\begin{aligned}V&=(6\;2\;7\;4\;10)\\V_{{sortat}}&=(2\;4\;6\;7\;10)\end{aligned}}

Se observă că elementele 4 și 6 se află la două poziții distanță de locul lor în vectorul sortat, elementele 2 și 7 se află la o poziție distanță, iar elementul 10 se află chiar pe poziția corectă. Distanța maximă este 2, deci vectorul V este 2-sortat. Desigur, un vector k-sortat este în același timp și un vector (k+1)-sortat, și un vector (k+2)-sortat etc., deoarece, dacă orice element se află la o distanță mai mică sau egală cu k de locul potrivit, cu atât mai mult el se va afla la o distanță mai mică sau egală cu k+1, k+2 etc. În continuare, când vom spune că vectorul este k-sortat, ne vom referi la cel mai mic k pentru care afirmația este adevărată. Prin urmare, un vector cu N elemente poate fi N-1 sortat în cazul cel mai defavorabil. Mai facem precizarea că un vector 0-sortat este un vector sortat în înțelesul obișnuit al cuvântului, deoarece fiecare element se află la o distanță egală cu 0 de locul său.

Problema este: dându-se un vector k-sortat cu N elemente numere întregi, se cere să-l sortăm într-un timp mai bun decât O(N\log N).

Intrarea: Fișierul INPUT.TXT conține pe prima linie valorile lui N și K (2 ≤ K < N și N ≤ 10000), despărțite printr-un spațiu. Pe a doua linie se dau cele N elemente ale vectorului, despărțite prin spații.

Ieșirea: În fișierul OUTPUT.TXT se vor tipări pe o singură linie elementele vectorului sortat, separate prin spații.

Exemplu:

INPUT.TXT OUTPUT.TXT
5[1]
6 2 7 4 10
2 4 6 7 10

Timp de implementare: 45 minute.

Timp de rulare: 5 secunde.

Complexitate cerută: O(N\log K).

REZOLVARE: Vom începe prin a defini noțiunea de HEAP. Un heap (engl. grămadă) este un vector care poate fi privit și ca un arbore binar, așa cum se vede în figura de mai jos:

Psycho-fig13.png

Lângă fiecare nod din arbore se află câte un număr, reprezentând poziția în vector pe care ar avea-o nodul respectiv. Pentru cazul considerat, vectorul echivalent ar fi:

V=(12\;10\;11\;10\;7\;9\;3\;2\;8\;1\;4\;3)

Se observă că nodurile sunt parcurse de la stânga la dreapta și de sus în jos. O proprietate necesară pentru ca un arbore binar să se poată numi heap este ca toate nivelele să fie complete, cu excepția ultimului, care se completează începând de la stânga și continuând până la un punct. De aici de ducem că înălțimea unui heap cu N noduri este

h=\lfloor \log _{2}N\rfloor

(reamintim că înălțimea unui arbore este adâncimea maximă a unui nod, considerând rădăcina drept nodul de adâncime 0). Reciproc, numărul de noduri ale unui heap de înălțime h este:

N\in [2^{h},2^{{h+1}}-1]

Tot din această organizare mai putem deduce că tatăl unui nod k>1 este nodul \lceil k/2\rceil , iar fiii nodului k sunt nodurile 2k și 2k+1. Dacă 2k=N, atunci nodul 2k+1 nu există, iar nodul k are un singur fiu; dacă 2k>N, atunci nodul k este frunză și nu are nici un fiu. Exemple: tatăl nodului 5 este nodul 2, iar fiii săi sunt nodurile 10 și 11. Tatăl nodului 6 este nodul 3, iar unicul său fiu este nodul 12. Tatăl nodului 9 este nodul 4, iar fii nu are, fiind frunză în heap.

Dar cea mai importantă proprietate a heap-ului, cea care îl face util în operațiile de căutare, este aceea că valoarea oricărui nod este mai mare sau egală cu valoarea oricărui fiu al său. După cum se vede mai sus, nodul 2 are valoarea 10, iar fiii săi - nodurile 4 și 5 - au valorile 10 și respectiv 7. Întrucât operatorul „≥” este tranzitiv, putem trage concluzia că un nod este mai mare sau egal decât oricare din nepoții săi și, generalizând, va rezulta că orice nod este mai mare sau egal decât toate nodurile din subarborele a cărui rădăcină este el.

Această afirmație nu decide în nici un fel între valorile a două noduri dispuse astfel încât nici unul nu este descendent al celuilalt. Cu alte cuvinte, nu înseamnă că orice nod de pe un nivel mic are valoare mai mare decât nodurile mai apropiate de frunze. Este cazul nodului 7, care are valoarea 3 și este mai mic decât nodul 9 de valoare 8, care este totuși așezat mai jos în heap. În orice caz, o primă concluzie care rezultă din această proprietate este că rădăcina are cea mai mare valoare din tot heap-ul.

Structura de heap permite efectuarea multor operații într-un timp foarte bun:

  • Căutarea maximului în O(1);
  • Crearea unei structuri de heap dintr-un vector oarecare în O(N);
  • Eliminarea unui element în O(\log N);
  • Inserarea unui element în O(\log N);
  • Sortarea în O(N\log N)
  • Căutarea (singura care nu este prea eficientă) în O(N).

Desigur, toate aceste operații se fac menținând permanent structura de heap a arborelui, adică respectând modul de repartizare a nodurilor pe nivele și „înălțarea” elementelor de valoare mai mare. Este de la sine înțeles că datele nu se vor reprezenta în memorie în forma arborescentă, ci în cea vectorială. Să le analizăm pe rând.

Căutarea maximului

Practic operația aceasta nu are de făcut decât să întoarcă valoarea primului element din vector:

typedef int Heap[10001];
void Max(Heap H, int N)
{
  return H[1];
}

Crearea unei structuri de heap dintr-un vector oarecare

Pentru a discuta acest aspect, vom vorbi mai întâi despre două proceduri specifice heap-urilor, Sift (engl. a cerne) și Percolate (engl. a se infiltra). Să presupunem că un vector are o structură de heap, cu excepția unui nod care este mai mic decât unul din fiii săi. Este cazul nodului 3 din figura de mai jos, care are o valoare mai mică decât nodul 6:

Psycho-fig14.png

Ce e de făcut? Desigur, nodul va trebui coborât în arbore, iar în locul lui vom aduce alt nod, mai exact unul dintre fiii săi. Întrebarea este: care din fiii săi? Dacă vom aduce nodul 7 în locul lui, acesta fiind mai mic decât nodul 6, inegalitatea se va păstra. Trebuie deci să schimbăm nodul 3 cu nodul 6:

Psycho-fig15.png

Problema nu este însă rezolvată, deoarece noul nod 6, proaspăt „retrogradat”, este încă mai mic decât fiul său, nodul 12. De data aceasta avem un singur fiu, deci o singură opțiune: schimbăm nodul 6 cu nodul 12 și obținem o structură de heap corectă:

Psycho-fig16.png

Procedura Sift primește ca parametri un heap H cu N noduri și un nod K și presupune că ambii subarbori ai nodului K au structură de heap corectă. Misiunea ei este să „cearnă” nodul K până la locul potrivit, interschimbând mereu nodul cu cel mai mare fiu al său până când nodul nu mai are fii (ajunge pe ultimul nivel în arbore) sau până când fiii săi au valori mai mici decât el.

void Sift(Heap H, int N, int K)
{ int Son;

  /* Alege un fiu mai mare ca tatal */
  if (K<<1<=N)
    { Son=K<<1;
      if (K<<1<N && H[(K<<1)+1]>H[(K<<1)])
        Son++;
      if (H[Son]<=H[K]) Son=0;
    }
    else Son=0;
  while (Son)
    { /* Schimba H[K] cu H[Son] */
      H[K]=(H[K]^H[Son])^(H[Son]=H[K]);
      K=Son;
      /* Alege un alt fiu */
      if (K<<1<=N)
        { Son=K<<1;
          if (K<<1<N && H[(K<<1)+1]>H[(K<<1)])
            Son++;
          if (H[Son]<=H[K]) Son=0;
        }
        else Son=0;
    }
}

Procedura Percolate se va ocupa tocmai de fenomenul invers. Să presupunem că un heap are o „defecțiune” în sensul că observăm un nod care are o valoare mai mare decât tatăl său. Atunci, va trebui să interschimbăm cele două noduri. Este cazul nodului 10 din figura care urmează. Deoarece fiul care trebuie urcat este mai mare ca tatăl, care la rândul lui (presupunând că restul heap-ului e corect) este mai mare decât celălalt fiu al său, rezultă că după interschimbare fiul devenit tată este mai mare decât ambii săi fii. Trebuie totuși să privim din nou în sus și să continuăm să urcăm nodul în arbore fie până ajungem la rădăcină, fie până îi găsim un tată mai mare ca el. Iată ce se întâmplă cu nodul 10:

Psycho-fig17.png

Psycho-fig18.png

Psycho-fig19.png

void Percolate(Heap H, int N, int K)
{ int Key;

  Key = H[K];
  while ((K>1) && (Key > H[K>>1]))
    { H[K]=H[K>>1];
      K>>=1;
    }
  H[K] = Key;
}

Acum ne putem ocupa efectiv de construirea unui heap. Am spus că procedura Sift presupune că ambii fii ai nodului pentru care este ea apelată au structură de heap. Aceasta înseamnă că putem apela procedura Sift pentru orice nod imediat superior nivelului frunzelor, deoarece frunzele sunt arbori cu un singur nod, și deci heap-uri corecte. Apelând procedura Sift pentru toate nodurile de deasupra frunzelor, vom obține deja o structură mai organizată, asigurându-ne că pe ultimele două nivele avem de-a face numai cu heap-uri. Apoi apelăm aceeași procedură pentru nodurile de pe al treilea nivel începând de la frunze, apoi pentru cele de deasupra lor și așa mai departe până ajungem la rădăcină. În acest moment, heap-ul este construit. Iată cum funcționează algoritmul pentru un arbore total dezorganizat:

Psycho-fig20.png

Psycho-fig21.png

Psycho-fig22.png

Psycho-fig23.png

void BuildHeap(Heap H, int N)
{ int i;

  for (i=N/2; i; Sift(H, N, i--));
}

S-a apelat căderea începând de la al N/2 - lea nod, deoarece s-a arătat că acesta este ultimul nod care mai are fii, restul fiind frunze. Să calculăm acum complexitatea acestui algoritm. Un calcul sumar ar putea spune: există N noduri, fiecare din ele se „cerne” pe O(\log N) nivele, deci timpul de construcție a heap-ului este O(N\log N). Totuși nu este așa. Presupunem că ultimul nivel al heap-ului este plin. În acest caz, jumătate din noduri vor fi frunze și nu se vor cerne deloc. Un sfert din noduri se vor afla deasupra lor și se vor cerne cel mult un nivel. O optime din noduri se vor putea cerne cel mult două nivele, și așa mai departe, până ajungem la rădăcina care se află singură pe nivelul ei și va putea cădea maxim h nivele (reamintim că h=\lfloor \log N\rfloor ). Rezultă că timpul total de calcul este dat de formula:

O{\biggl (}\sum _{{k=0}}^{{\lfloor \log _{2}N\rfloor }}k\cdot {\frac  {N}{2^{{k+1}}}}{\biggr )}

Demonstrarea egalității se poate face făcând substituția N=2^{h} și continuând calculele. Se va obține tocmai complexitatea O(2^{h}); lăsăm această verificare ca temă cititorului.

Eliminarea unui element

Dacă eliminăm un element din heap, trebuie numai să refacem structura de heap. În locul nodului eliminat s-a creat un gol, pe care trebuie să îl umplem cu un alt nod. Care ar putea fi acela? Întrucât trebuie ca toate nivelele să fie complet ocupate, cu excepția ultimului, care poate fi gol numai în partea sa dreaptă, rezultă că singurul nod pe care îl putem pune în locul celui eliminat este ultimul din heap. Odată ce l-am pus în gaura făcută, trebuie să ne asigurăm că acest nod „de umplutură” nu strică proprietatea de heap. Deci vom verifica: dacă nodul pus în loc este mai mare ca tatăl său, vom apela procedura Percolate. Altfel vom apela procedura Sift, în eventualitatea că nodul este mai mic decât unul din fiii săi. Iată exemplul de mai jos:

Psycho-fig24.png

Să presupunem că vrem să eliminăm nodul de valoare 9, aducând în locul lui nodul de valoare X. Însă X poate fi orice număr mai mic sau egal cu 18. Spre exemplu, X poate fi 16, caz în care va trebui urcat deasupra nodului de valoare 10, sau poate fi 1, caz în care va trebui cernut până la nivelul frunzelor. Deoarece căderea și urcarea se pot face pe cel mult \log N nivele, rezultă o complexitate a procedeului de O(\log N).

void Cut(Heap H, int N, int K)
{ H[K] = H[N--];

  if ((K>1) && (H[K] > H[K>>1]))
    Percolate(H, N, K);
    else Sift(H, N, K)
}

Inserarea unui element

Dacă vrem să inserăm un nou element în heap, lucrurile sunt mult mai simple. Nu avem decât să-l așezăm pe a N+1-a poziție în vector și apoi să-l „promovăm” până la locul potrivit. Din nou, urcarea se poate face pe maxim \log N nivele, de unde complexitatea logaritmică.

void Insert(Heap H, int N, int Key)
{
  H[++N] = Key;
  Percolate(H, N, N);
}

Sortarea unui vector (heapsort)

Acum, că am stabilit toate aceste lucruri, ideea algoritmului de sortare vine de la sine. Începem prin a construi un heap. Apoi extragem maximul (adică vârful heap-ului) și refacem heap-ul. Cele două operații luate la un loc durează O(1)+O(\log N)=O(\log N). Apoi extragem din nou maximul, (care va fi al doilea element ca mărime din vector) și refacem din nou heap-ul. Din nou, complexitatea operației compuse este O(\log N). Dacă facem acest lucru de N ori, vom obține vectorul sortat într-o complexitate de O(N\log N).

Partea cea mai frumoasă a acestui algoritm, la prima vedere destul de mare consumator de memorie, este că el nu folosește deloc memorie suplimentară. Iată explicația: când heap-ul are N elemente, vom extrage maximul și îl vom ține minte undeva în memorie. Pe de altă parte, în locul maximului (adică în rădăcina arborelui) trebuie adus ultimul element al vectorului, adică H[N]. După această operație, heap-ul va avea N-1 noduri, al N-lea rămânând liber. Ce alt loc mai inspirat decât acest al N-lea nod ne-am putea dori pentru a stoca maximul? Practic, am interschimbat rădăcina, adică pe H[1] cu H[N]. Același lucru se face la fiecare pas, ținând cont de micșorarea permanentă a heap-ului.

void HeapSort(Heap H, int N)
{ int i;

  /* Construieste heap-ul */
  for (i=N>>1; i; Sift(H, N, i--));
  /* Sorteaza vectorul */
  for (i=N; i>=2;)
    { G[1]=(G[1]^G[i])^(G[i]=G[1]);
      Sift(H, --i, 1);
    }
}

Căutarea unui element

Această operație este singura care nu poate fi optimizată (în sensul reducerii complexității sub O(N)). Aceasta deoarece putem fi siguri că un nod mai mic este descendentul unuia mai mare, dar nu putem ști dacă se află în subarborele stâng sau drept; din această cauză, nu putem face o căutare binară. Totuși, o oarecare îmbunătățire se poate aduce față de căutarea secvențială. Dacă rădăcina unui subarbore este mai mică decât valoarea căutată de noi, cu atât mai mult putem fi convinși că descendenții rădăcinii vor fi și mai mici, deci putem să renunțăm la a căuta acea valoare în tot subarborele. În felul acesta, se poate întâmpla ca bucăți mari din heap să nu mai fie explorate inutil. Pe cazul cel mai defavorabil, însă, parcurgerea întregului heap este necesară. Lăsăm scrierea unei proceduri de căutare pe seama cititorului.


Sperând că am reușit să explicăm modul de funcționare al unui heap, să încercăm să rezolvăm și problema propusă. Chiar faptul că ni se cere o complexitate de ordinul O(N\log k) ne sugerează construirea unui heap cu O(k) noduri. Să ne închipuim că am construi un heap H format din primele k+1 elemente ale vectorului V. Diferența față de ce am spus până acum este că orice nod va trebui să fie mai mic decât fiii săi. Acest heap va servi deci la extragerea minimului.

Deoarece vectorul este k-sortat, rezultă că elementul care s-ar găsi pe prima poziție în vectorul sortat se poate afla în vectorul nesortat pe oricare din pozițiile 1, 2, ..., k+1. El se află așadar în heap-ul H; în plus, fiind cel mai mic, știm exact de unde să-l luăm: din vârful heap-ului. Deci vom elimina acest element din heap și îl vom trece „undeva” separat (vom vedea mai târziu unde). În loc să punem în locul lui ultimul element din heap, însă, vom aduce al k+2-lea element din vector și îl vom lăsa să se cearnă. Acum putem fi siguri că al doilea element ca valoare în vectorul sortat se află în heap, deoarece el se putea afla în vectorul nesortat undeva pe pozițiile 1, 2, ..., k+2, toate aceste elemente figurând în heap (bineînțeles că minimul deja extras se exclude din discuție). Putem să mergem la sigur, luând al doilea minim direct din vârful heap-ului.

Vom proceda la fel până când toate elementele vectorului vor fi adăugate în heap. Din acel moment vom continua să extragem din vârful heap-ului, revenind la vechea modalitate de a umple locul rămas gol cu ultimul nod disponibil. Continuăm și cu acest procedeu până când heap-ul se golește. În acest moment am obținut vectorul sortat „undeva” în memorie. De fapt, dacă ne gândim puțin, vom constata că, odată ce primele k+1 elemente din vector au fost trecute în heap, ordinea lor în vectorul V nu mai contează, ele putând servi chiar la stocarea minimelor găsite pe parcurs. Pe măsură ce aceste locuri se vor umple, altele noi se vor crea prin trecerea altor elemente în heap. Iată deci cum nici acest algoritm nu necesită memorie suplimentară.

Să urmărim evoluția metodei pe exemplul din enunț:

V=(6\;2\;7\;4\;10)

Psycho-fig25.png

Psycho-fig26.png

Psycho-fig27.png

Psycho-fig28.png

Psycho-fig29.png

#include <stdio.h>
#include <mem.h>
int V[10001], H[10001], N, K;

void ReadData(void)
{ FILE *F=fopen("input.txt","rt");
  int i;

  fscanf(F,"%d %d\n",&N, &K);
  for (i=1; i<=N; fscanf(F, "%d", &V[i++]));
  fclose(F);
}

void Sift(int X, int N)
/* Cerne al X-lea element dintr-un heap de N elemente */
{ int Son;

  /* Alege un fiu mai mare ca tatal */
  if (X<<1<=N)
    { Son=X<<1;
      if (X<<1<N && H[(X<<1)+1]<H[(X<<1)])
        Son++;
      if (H[Son]>=H[X]) Son=0;
    }
    else Son=0;
  while (Son)
    { /* Schimba H[X] cu H[Son] */
      H[X]=(H[X]^H[Son])^(H[Son]=H[X]);
      X=Son;
      /* Alege un alt fiu */
      if (X<<1<=N)
        { Son=X<<1;
          if (X<<1<N && H[(X<<1)+1]<H[(X<<1)])
            Son++;
          if (H[Son]>=H[X]) Son=0;
        }
        else Son=0;
    }
}

void SortVector(void)
{ int i;

  /* Construieste heap-ul de K+1 elemente */
  for (i=1; i<=K+1; H[i++]=V[i]);
  for (i=(K+1) >> 1; i; Sift(i--, K+1));

  for (i=1; i<=N; i++)
    { V[i] = H[1]; // minimul trece in vector
      /* Se adauga un element din vector sau din heap */
      H[1] = (i<=N-K-1) ? V[i+K+1] : H[K+1];
      /* Daca vectorul s-a terminat, heap-ul incepe
         sa se micsoreze */
      if (i>N-K-1) K--;
      /* Cerne noul element */
      Sift(1, K+1);
    }
}

void WriteSolution(void)
{ FILE *F=fopen("con","wt");
  int i;

  for (i=1; i<=N; fprintf(F, "%d ", V[i++]));
  fprintf(F, "\n");
  fclose(F);
}

void main(void)
{
  ReadData();
  SortVector();
  WriteSolution();
}

Tabele HASH

În multe aplicații lucrăm cu structuri mari de date în care avem nevoie să facem căutări, inserări, modificări și ștergeri. Aceste structuri pot fi vectori, matrice, liste etc. În cazurile mai fericite ale vectorilor, aceștia pot fi sortați, caz în care localizarea unui element se face prin metoda înjumătățirii intervalului, adică în timp logaritmic. Chiar dacă nu avem voie să sortăm vectorul, tot se pot face anumite optimizări care reduc foarte mult timpul de căutare. De exemplu, probabil că mulți dintre cititori au idee despre ce înseamnă indexarea unei baze de date. Dacă avem o bază de date cu patru elemente de tip string, și anume

B = ( „bac”, „zugrav”, „abac”, „zarva”)

putem construi un vector Ind care să ne indice ordinea în care s-ar cuveni să fie așezate cuvintele în vectorul sortat. Ordinea alfabetică (din cartea de telefon) a cuvintelor este: „abac”, „bac”, „zarva”, „zugrav”, deci vectorul Ind este:

Ind = (3, 1, 4, 2)

semnificând că primul cuvânt din vectorul sortat ar trebui să fie al treilea din vectorul B, respectiv „abac” și așa mai departe. În felul acesta am obținut un vector sortat, care presupune o indirectare a elementelor. Vectorul sortat este

B’ = (B(Ind(1)), B(Ind(2)), B(Ind(3)), B(Ind(4)).

Această operație se numește indexare. Ce-i drept, construcția vectorului Ind nu se poate face într-un timp mai bun decât O(N\log N), dar după ce acest lucru se face (o singură dată, la începutul programului), căutările se pot face foarte repede. Dacă pe parcurs se fac adăugări sau ștergeri de elemente în/din baza de date, se va pierde câtva timp pentru menținerea indexului, dar în practică timpul acesta este mult mai mic decât timpul care s-ar pierde cu căutarea unor elemente în cazul în care vectorul ar fi neindexat. Nu vom intra în detalii despre indexare, deoarece nu acesta este obiectul capitolului de față.

În unele situații nu se poate face nici indexarea structurii de date. Să considerăm cazul unui program care joacă șah. În esență, modul de funcționare al acestui program se reduce la o rutină care primește o poziție pe tablă și o variabilă care indică dacă la mutare este albul sau negrul, rutina întorcând cea mai bună mutare care se poate efectua din acea poziție. Majoritatea programelor de șah încep să expandeze respectiva poziție, examinând tot felul de variante ce pot decurge din ea și alegând-o pe cea mai promițătoare, așa cum fac și jucătorii umani. Pozițiile analizate sunt stocate în memorie sub forma unei liste simplu sau dublu înlănțuite. Memorarea nu se poate face sub forma unui vector, deoarece numărul de poziții analizate este de ordinul sutelor de mii sau chiar al milioanelor, din care câteva zeci de mii sunt reținute în permanență în memorie.

Să ne închipuim acum următoarea situație. Este posibil ca, prin expandarea unei configurații inițiale a tablei să se ajungă la aceeași configurație finală pe două căi diferite. Spre exemplu, dacă albul mută întâi calul la f3, apoi nebunul la c4, poziția rezultată va fi aceeași ca și când s-ar fi mutat întâi nebunul și apoi calul (considerând bineînțeles că negrul dă în ambele situații aceeași replică). Dacă configurația finală a fost deja analizată pentru prima variantă, este inutil să o mai analizăm și pentru cea de-a doua, pentru că rezultatul (concluzia la care se va ajunge) va fi exact același. Dar cum își poate da programul seama dacă poziția pe care are de gând s-o analizeze a fost analizată deja sau nu?

Cea mai simplă metodă este o scanare a listei de configurații examinate din memorie. Dacă în această listă se află poziția curentă de analizat, înseamnă că ea a fost deja analizată și vom renunța la ea. Dacă nu, o vom analiza acum. Ideea în mare a algoritmului este:

procedura Analizeaza(Pozitie P)
  cauta P in lista de pozitii deja analizate
  daca P nu exista in lista
    expandeaza P si afla cea mai buna mutare M
    adauga P la lista de pozitii analizate
    intoarce M
  altfel
    intoarce valoarea M atasata pozitiei P gasite in lista
sfarsit

Nu vom insista asupra a cum se expandează o poziție și cum se calculează efectiv cea mai bună mutare. Noi ne vom interesa de un singur aspect, și anume căutarea unei poziții în listă. Tehnica cea mai „naturală” este o parcurgere a listei de la cap la coadă, comparând pe rând poziția căutată cu fiecare poziție din listă. Dacă lista are memorate N poziții, atunci în cazul unei căutări cu succes (poziția este găsită), numărul mediu de comparații făcute este N/2, iar numărul cel mai defavorabil ajunge până la N. În cazul unei căutări fără succes (poziția nu există în listă), numărul de comparații este întotdeauna N. De altfel, cazul căutării fără succes este mult mai frecvent pentru problema jocului de șah, unde numărul de poziții posibile crește exponențial cu numărul de mutări. Același număr de comparații îl presupun și ștergerea unei poziții din listă (care presupune întâi găsirea ei) și adăugarea (care presupune ca poziția de adăugat să nu existe deja în listă).

Pentru îmbunătățirea practică a acestui timp sunt folosite tabelele de dispersie sau tabelele hash (engl. hash = a toca, tocătură). Menționăm de la bun început că tabelele hash nu au nici o utilitate din punct de vedere teoretic. Dacă suntem rău intenționați, este posibil să găsim exemple pentru care căutarea într-o tabelă hash să dureze la fel de mult ca într-o listă simplu înlănțuită, respectiv O(N). Dar în practică timpul căutării și al adăugării de elemente într-o tabelă hash coboară uneori până la O(1), iar în medie scade foarte mult (de mii de ori).

Iată despre ce este vorba. Să presupunem pentru început că în loc de poziții pe tabla de șah, lista noastră memorează numere între 0 și 999. În acest caz, tabela hash ar fi un simplu vector H cu 1000 de elemente booleene. Inițial, toate elementele lui H au valoarea False (sau 0). Dacă numărul 473 a fost găsit în listă, nu avem decât să setăm valoarea lui H(473) la True (sau 1). La o nouă apariție a lui 473 în listă, vom examina elementul H(473) și, deoarece el este True, înseamnă că acest număr a mai fost găsit. Dacă dorim ștergerea unui element din hash, vom reseta poziția corespunzătoare din H. Practic, avem de-a face cu un exemplu rudimentar de ceea ce se cheamă funcție de dispersie, aidcă h(x)=x. O proprietate foarte importantă a acestei funcții este injectivitatea; este imposibil ca la două numere distincte să corespundă aceeași intrare în tabelă. Să încercăm o reprezentare grafică a metodei:

Psycho-fig30.png

Iată primul set de proceduri de gestionare a unui Hash.

#define M 1000 // numarul de "intrari" //
typedef int Hash[M];
typedef int DataType;
Hash H;

void InitHash1(Hash H)
{ int i;

  for (i=0; i<M; H[i++]=0);
}

inline int h(DataType K)
{
  return K;
}

int Search1(Hash H, DataType K)
/* Intoarce -1 daca elementul nu exista in hash
   sau indicele in hash daca el exista */
{
  return H[h(K)] ? h(K) : -1;
}

void Add1(Hash H, DataType K)
{
  H[h(K)]=1;
}

void Delete1(Hash H, DataType K)
{
  H[h(K)]=0;
}

Prin „număr de intrări” în tabelă se înțelege numărul de elemente ale vectorului H; în general, orice tabelă hash este un vector. Pentru ca funcțiile să fie cât mai generale, am dat tipului de dată int un nou nume - DataType. În principiu, tabelele Hash se aplică oricărui tip de date. În realitate, fenomenul este tocmai cel invers: orice tip de date trebuie „convertit” printr-o metodă sau alta la tipul de date int, iar funcția de dispersie primește ca parametru un întreg. Funcțiile hash prezentate în viitor nu vor mai lucra decât cu variabile de tip întreg. Vom vorbi mai târziu despre cum se poate face conversia. Acum să generalizăm exemplul de mai sus.

Într-adevăr, cazul anterior este mult prea simplu. Să ne închipuim de pildă că în loc de numere mai mici ca 1000 avem numere de până la 2.000.000.000. În această situație posibilitatea de a reprezenta tabela ca un vector caracteristic iese din discuție. Numărul de intrări în tabelă este de ordinul miilor, cel mult al zecilor de mii, deci cu mult mai mic decât numărul total de chei (numere) posibile. Ce avem de făcut? Am putea încerca să adăugăm un număr K într-o tabelă cu M intrări (numerotate de la 0 la M-1) pe poziția K\,{\bmod  \,}M, adică h(K)=K\,{\bmod  \,}M. Care va fi însă rezultatul? Funcția h își va pierde proprietatea de injectivitate, deoarece mai multor chei le poate corespunde aceeași intrare în tabelă, cum ar fi cazul numerelor 1234 și 2001234, ambele dând același rest la împărțirea prin M=1000. Nu putem avea însă speranța de a găsi o funcție injectivă, pentru că atunci numărul de intrări în tabelă ar trebui să fie cel puțin egal cu numărul de chei distincte. Vrând-nevrând, trebuie să rezolvăm coliziunile (sau conflictele) care apar, adică situațiile când mai multe chei distincte sunt repartizate la aceeași intrare.

Vom reveni ulterior la oportunitatea alegerii funcției modul și a numărului de 1000 de intrări în tabelă. Deocamdată vom folosi aceste date pentru a explica modul de funcționare a tabelei hash pentru funcții neinjective. Să presupunem că avem două chei K_{1} și K_{2} care sunt repartizate de funcția h la aceeași intrare X, adică h(K_{1})=h(K_{2})=X. Soluția cea mai comodă este ca H(X) să nu mai fie un număr, ci o listă liniară simplu sau dublu înlănțuită care să conțină toate cheile găsite până acum și repartizate la aceeași intrare X. Prin urmare vectorul H va fi un vector de liste:

Psycho-fig31.png

Să analizăm acum complexitatea noilor proceduri de căutare, adăugare și ștergere. Căutarea nu se va mai face în toată lista, ci numai în lista corespunzătoare din H. Altfel spus, o cheie K se va căuta numai în lista H(h(K)), deoarece dacă cheia K a mai apărut, ea a fost în mod sigur repartizată la intrarea H(h(K)). De aceea, căutarea poate ajunge, în cazul cel mai defavorabil când toate cheile din listă se repartizează la aceeași intrare în hash, la o complexitate O(N). Dacă reușim însă să găsim o funcție care să distrbuie cheile cât mai aleator, timpul de intrare se va reduce de M ori. Avantajele sunt indiscutabile pentru M=10000 de exemplu.

Întrucât operațiile cu liste liniare sunt în general cunoscute, nu vom insista asupra lor. Prezentăm aici numai adăugarea și căutarea, lăsându-vă ca temă scrierea funcției de ștergere din tabelă.

#include <stdio.h>
#include <stdlib.h>
#define M 1000 // numarul de "intrari"
typedef struct _List {
          long P;
          struct _List * Next;
        } List;
typedef List * Hash[M];
Hash H;

void InitHash2(Hash H)
{ int i;

  for (i=0; i<M; H[i++]=NULL);
}

int h2(int K)
{
  return K%M;
}

int Search2(Hash H, int K)
/* Intoarce 0 daca elementul nu exista in hash
   sau 1 daca el exista */
{ List *L;

  for (L=H[h2(K)]; L && (L->P != K); L = L->Next);
  return L!=NULL;
}

void Add2(Hash H, int K)
{ List *L = malloc(sizeof(List));
  L->P = K;
  L->Next = H[h2(K)];
  H[h2(K)] = L;
}

Am spus că funcțiile de dispersie sunt concepute să lucreze numai pe date de tip întreg; celelalte tipuri de date trebuie convertite în prealabil la tipuri de date întregi. Iată câteva exemple:

  • Variabilele de tip string pot fi transformate în numere în baza 256 prin înlocuirea fiecărui caracter cu codul său ASCII. De exemplu, șirul „abac” poate fi privit ca un număr de 4 cifre în baza 256, și anume numărul (97 98 97 99). Conversia lui în baza 10 se face astfel:
X=((97\times 256+98)\times 256+97)\times 256+99=1.633.837.411
Pentru stringuri mai lungi, rezultă numere mai mari. Uneori, ele nici nu mai pot fi reprezentate cu tipurile de date ordinale. Totuși, acest dezavantaj nu este supărător, deoarece majoritatea funcțiilor de dispersie presupun o împărțire cu rest, care, indiferent de mărimea numărului de la intrare, produce un număr controlabil.
  • Variabilele de tip dată se pot converti la întreg prin formula:
A\times 366+L\times 30+Z[2]
unde A, L și Z sunt respectiv anul, luna și ziua datei considerate. De fapt, această funcție aproximează numărul de zile scurse de la începutul secolului I. Ea nu are pretenții de exactitate (ca dovadă, toți anii sunt considerați a fi bisecți și toate lunile a avea 31 de zile), deoarece s-ar consuma timp inutil cu calcule mai sofisticate, fără ca dispersia însăși să fie îmbunătățită cu ceva. Condiția care trebuie neapărat respectată este ca funcția de conversie dată « întreg să fie injectivă, adică să nu se întâmple ca la două date D_{1} și D_{2} să li se atașeze același întreg X; dacă acest lucru se întâmplă, pot apărea erori la căutarea în tabelă (de exemplu, se poate raporta găsirea datei D_{1} când de fapt a fost găsită data D_{2}). Pentru a respecta injectivitatea, s-au considerat coeficienții 366 și 31 în loc de 365 și 30. Dacă numărul de zile scurse de la 1 ianuarie anul 1 d.H. ar fi fost calculat cu exactitate, funcția de conversie ar fi fost și surjectivă, dar, după cum am mai spus, acest fapt nu prezintă interes.
  • Analog, variabilele de tip oră se pot converti la întreg cu formula:
X=(H\times 60+M)\times 60+S
unde H, M și S sunt respectiv ora, minutul și secunda considerate, sau cu formula
X=((H\times 60+M)\times 60+S)+100[3]
dacă se ține cont și de sutimile de secundă. De data aceasta, funcția este surjectivă (oricărui număr întreg din intervalul 0 - 8.639.999 îi corespunde în mod unic o oră).
  • În majoritatea cazurilor, datele sunt structuri care conțin numere și stringuri. O bună metodă de conversie constă în alipirea tuturor acestor date și în convertirea la baza 256. Caracterele se convertesc prin simpla înlocuire cu codul ASCII corespunzător, iar numerele prin convertirea în baza 2 și tăierea în „bucăți” de câte opt biți. Rezultă numere cu multe cifre (prea multe chiar și pentru tipul longint), care sunt supuse unei operații de împărțire cu rest. Funcția de conversie trebuie să fie injectivă. De exemplu, în cazul tablei de șah despre care am amintit mai înainte, ea poate fi transformată într-un vector cu 64 de cifre în baza 16, cifra 0 semnificând un pătrat gol, cifrele 1-6 semnificând piesele albe (pion, cal, nebun, turn, regină, rege) iar cifrele 7-12 semnificând piesele negre. Prin trecerea acestui vector în baza 256, rezultă un număr cu 32 de cifre. La acesta se mai pot adăuga alte cifre, respectiv partea la mutare (0 pentru alb, 1 pentru negru), posibilitatea de a efectua rocada mică/mare de către alb/negru, numărul de mutări scurse de la începutul partidei și așa mai departe.

Vom termina prin a prezenta două funcții de dispersie foarte des folosite.

Metoda împărțirii cu rest

Despre această metodă am mai vorbit. Funcția hash este

h(x)=x\,{\bmod  \,}M

unde M este numărul de intrări în tabelă. Problema care se pune este să-l alegem pe M cât mai bine, astfel încât numărul de coliziuni pentru oricare din intrări să fie cât mai mic. De asemenea, trebuie ca M să fie cât mai mare, pentru ca media numărului de chei repartizate la aceeași intrare să fie cât mai mică. Totuși, experiența arată că nu orice valoare a lui M este bună.

De exemplu, la prima vedere s-ar putea spune că o bună valoare pentru M este o putere a lui 2, cum ar fi 1024, pentru că operația de împărțire cu rest se poate face foarte ușor în această situație. Totuși, funcția h(x)=x\,{\bmod  \,}1024 are un mare defect: ea nu ține cont decât de ultimii 10 biți ai numărului x. Dacă datele de intrare sunt numere în mare majoritate pare, ele vor fi repartizate în aceeași proporție la intrările cu număr de ordine par, pentru că funcția h păstrează paritatea. Din aceleași motive, alegerea unei valori ca 1000 sau 2000 nu este prea inspirată, deoarece ține cont numai de ultimele 3-4 cifre ale reprezentării zecimale. Multe valori pot da același rest la împărțirea prin 1000. De exemplu, dacă datele de intrare sunt anii de naștere ai unor persoane dintr-o agendă telefonică, iar funcția este h(x)=x\,{\bmod  \,}1000, atunci majoritatea cheilor se vor îngrămădi (termenul este sugestiv) între intrările 920 și 990, restul rămânând nefolosite.

Practic, trebuie ca M să nu fie un număr rotund în nici o bază aritmetică, sau cel puțin nu în bazele 2 și 10. O bună alegere pentru M sunt numerele prime care să nu fie apropiate de nici o putere a lui 2. De exemplu, în locul unei tabele cu M=10000 de intrări, care s-ar comporta dezastruos, putem folosi una cu 9973 de intrări. Chiar și această alegere poate fi îmbunătățită; între puterile lui 2 vecine, respectiv 8192 și 16384, se poate alege un număr prim din zona 11000-12000. Risipa de memorie de circa 1000-2000 de intrări în tabelă va fi pe deplin compensată de îmbunătățirea căutării.


Metoda înmulțirii

Pentru această metodă funcția hash este

h(x)=\lfloor M(x\times A\,{\bmod  \,}1)\rfloor

Aici A este un număr pozitiv subunitar, 0<A<1, iar prin x\times A\,{\bmod  \,}1 se înțelege partea fracționară a lui x\times A, adică x\times A-\lfloor x\times A\rfloor . De exemplu, dacă alegem M=1234 și A=0,3, iar x=1997, atunci avem

h(x)=\lfloor 1234\times (599,1\,{\bmod  \,}1)\rfloor =\lfloor 1234\times 0,1\rfloor =123

Se observă că funcția h produce numere între 0 și M-1. Într-adevăr,

0\leq x\times A\,{\bmod  \,}1<1\implies 0\leq M(x\times A\,{\bmod  \,}1)<M

În acest caz, valoarea lui M nu mai are o mare importanță. O putem deci alege cât de mare ne convine, eventual o putere a lui 2. În practică, s-a observat că dispersia este mai bună pentru unele valori ale lui A și mai proastă pentru altele. Donald Knuth propune valoarea

A={\frac  {{\sqrt  {5}}-1}{2}}\approx 0.618034

Ca o ultimă precizare necesară la acest capitol, menționăm că funcția de căutare e bine să nu întoarcă pur și simplu 0 sau 1, după cum cheia căutată a mai apărut sau nu înainte între datele de intrare. E recomandabil ca funcția să întoarcă un pointer la zona de memorie în care se află prima apariție a cheii căutate. Vom da acum un exemplu în care această valoare returnată este utilă. Dacă, în cazul prezentat mai sus al unui program de șah, se ajunge la o anumită poziție P după ce albul a pierdut dreptul de a face rocada, această poziție va fi reținută în hash. Reținerea nu se va face nicidecum efectiv (toată tabla), pentru că s-ar ocupa foarte multă memorie. Se va memora în loc numai un pointer la poziția respectivă din lista de poziții analizate. Pe lângă economia de memorie în cazul cheilor de mari dimensiuni, mai există și alt avantaj. Să ne închipuim că, analizând în continuare tabla, programul va ajunge la aceeași poziție P, dar în care albul are încă dreptul de a face rocada. E limpede că această variantă este mai promițătoare decât precedenta, deoarece albul are o libertate mai mare de mișcare. Se impune deci fie ștergerea vechii poziții P din listă și adăugarea noii poziții, fie modificarea celei vechi prin setarea unei variabile suplimentare care indică dreptul albului de a face rocada. Această modificare este ușor de făcut, întrucât căutarea în hash va returna chiar un pointer la poziția care trebuie modificată. Bineînțeles, în cazul în care poziția căutată nu se află în hash, funcția de căutare trebuie să întoarcă NULL.

În încheiere, prezentăm un exemplu de funcție de dispersie pentru cazul tablei de șah.

#define M 9973 // numarul de "intrari"
typedef struct {
          char b_T[8][8];
            /* tabla de joc, cu 0<= T[i][j] <=12 */
          char b_CastleW, b_CastleB;
            /*  ultimii doi biti ai lui b_CastleW
                indica daca albul are dreptul de a
                efectua rocada mare, respectiv pe cea
                mica. Analog pentru b_CastleB */
          char b_Side;
            /* 0 sau 1, dupa cum la mutare este albul
               sau negrul */
          char b_EP;
            /* 0..8, indicand coloana (0..7) pe care
               partea la mutare poate efectua o
               captura "en passant". 8 indica ca nu
               exista aceasta posibilitate */
          int b_NMoves;
            /* Numarul de mutari efectuate */
        } Board;
Board B;

int h3(Board *B)
{ int i,j;
  /* Valoarea initiala a lui S este un numar pe 17 biti care
     inglobeaza toate variabilele suplimentare pe langa T.
     S se va lua apoi modulo M */
  long S = (B->b_NMoves           /* 8 biti */
          +(B->b_CastleW << 8)    /* 2 biti */
          +(B->b_CastleB << 10)   /* 2 biti */
          +(B->b_Side << 12)      /* 1 bit */
          +B->b_EP<<13) % M;      /* 4 biti */

  for (i=0; i<=7; i++)
    for (j=0; j<=7; j++)
      S=(16*S+B->b_T[i][j])%M;

  return S;
}
  1. Greșeală în original.
  2. Greșeală în original
  3. Greșeală în original.