Note de curs, clasele 9-10, 1 martie 2013

Diverse

Discuție despre ce important este să-mi trimită minim un program pe săptămână

• pentru ca eu să am încredere că ei lucrează individual
• pentru că este important ca altcineva decât ei înșiși să se uite pe codul lor

Tabele hash

• proprietate fundamentală: dorim căutare rapidă
• exemplu: se dau V(n), S, să se spună dacă există a, b în V pentru care a + b = S
  • rezolvare naivă: sortare + n căutări binare
  • rezolvare ceva mai deșteaptă: sortare + parcurgere de la ambele capete
  • ar fi frumos să avem o structură magică în care să stocăm numerele, apoi să căutăm S - x pentru fiecare x
• reprezentare cu vector direct (pentru spațiu mic de chei)
  • problemă: Se dă un arbore cu rădăcină reprezentat printr-un vector de tați. Să se găsească înălțimea arborelui
• când spațiul de chei este foarte mare, convertirea cheii k în h(k)
• coliziuni -> înlănțuire
• inserare: O(1) dacă nu trebuie căutat în prealabil
• căutare cu succes: O($\alpha$).
  • listele mai lungi (acolo unde există mai multe coliziuni) vor fi căutate mai des, dar tot O($\alpha$)
• funcții hash, proprietăți: să fie independente de pattern-uri în date, să folosească toți biții
  • rele: % 9 (permutarea cifrelor), % 2^p (numai ultimii doi biți)
  • împărțire: un număr prim nu prea apropiat de puteri ale lui 2.
  • înmulțire: $\lfloor m(kA\mod 1)\rfloor$, A recomandat golden ratio
• compromisuri pentru mărimea tabelei: mică -> coliziuni, mare -> risipă de memorie
• birthday paradox: când mă aștept să am prima coliziune?
  • exemplu: URL fingerprinting la Google, perechi de URL-uri cu același fingerprint
• open address hashing
  • avantaj: evită pointerii, deci este mult mai rapid
  • dezavantaj: load factor maxim 1
  • h(k, i) trebuie să itereze mulțimea 0 ... m - 1 când i variază
  • linear probing: alegem h'(k), apoi h(k, i) = (h'(k) + i) mod m
  • suferă de primary clustering
  • quadratic probing: h(k, i) = (h'(k) + c1 * i + c2 * i2) mod m
  • suferă de secondary clustering, mai bine ceva ca primary clustering
  • double hashing: h(k) = (h1(k) + i * h2(k)) mod m
  • h2(k) trebuie să fie prim cu m ca să itereze prin tot tabelul
    • variantă: m putere a lui 2, h2(k) impar
    • variantă: m prim, h2(k) < m
  • complexitate ${\frac {1}{1-\alpha }}$ căci este (probabilistic) $1+\alpha +\alpha ^{2}+...$
  • inserarea cere întotdeauna o căutare fără succes (găsirea unui slot liber)
  • căutare cu succes: ${\frac {1}{\alpha }}\ln {\frac {1}{1-\alpha }}$
    • e.g. sunt necesare doar 2.6 verificări când tabela este 90% plină

Temă

• design la un LRU cache care să facă operațiile de inserare / căutare / evacuare în O(1)