Clasele 9-10 lecția 4 - 8 oct 2014

Liste (operații și probleme)

Lecția trecută pare să fi adus lucruri noi pentru majoritatea elevilor. De aceea, astăzi fiecare din voi va implementa câteva dintre operațiile și problemele următoare. Operațiile sunt în general cărămizi de bază, iar problemele combină operații multiple în scopuri mai complexe.

Vă recomand să alternați implementările cu pointeri propriu-ziși cu implementările cu pointeri numerici într-un vector prealocat. Astfel vă veți familiariza cu ambele.

Pentru toate problemele, alegeți-vă un format rezonabil al datelor de intrare (șiruri de numere, în principiu).

Puteți folosi liste simplu/dublu înlănțuite, liste circulare, cu sau fără pointer suplimentar la ultimul element din listă etc.

Nu fiți leneși! Alegeți-vă probleme care să vă provoace. Dacă aud că toată lumea a implementat parcurgerea unei liste, ne certăm. :-)

Operații

• creare
• parcurgere
• inserare de element
• ștergere de element
• întoarcere pe dos
• concatenare
• dealocare

Extra-credit: scrieți aceste operații ca funcții. Aceasta creează niște cazuri particulare, în special când afectează pointerul la începutul listei.

Probleme ușoare

• eliminarea duplicatelor dintr-o listă sortată
• intersecția / reuniunea a două liste sortate cu elemente distincte
  • Varianta ușoară: creați o a treia listă.
  • Varianta mai grea: distrugeți prima listă și modificați-o pe a doua pentru a obține rezultatul.
• numărătoare în cerc ca la v-ați ascunselea. Se dau n, numărul de copii, și k, distanța între doi copii eliminați. Să se tipărească copiii în ordinea eliminării.
• întoarcerea unei liste pe dos printr-o funcție recursivă
• sortarea unei liste prin metoda bulelor (bubble sort)
• sortarea unei liste prin selecție (select sort)

Probleme moderate

Se dă un număr n. Să se tipărească al n-lea număr de forma $2^{i}3^{j}5^{k}$, cu i, j, k ≥ 0. De exemplu, primele 10 numere sunt 1, 2, 3, 4, 5, 6, 8, 9, 10, 12.

Găsiți un algoritm pentru a depista dacă o listă este liniară sau în formă de 6 (lista circulară este un caz particular al listei în formă de 6). Dacă lista are formă de 6, aflați la ce poziție începe perioada și care este lungimea ei.

Se dau două liste. Să se depisteze dacă ele se unesc și care este primul lor element comun. Prin „primul element comun” înțelegem elementul care aparține ambelor liste și care este cât mai apropiat de începutul primei liste. Atenție, problema are multe cazuri particulare delicate. Intersecția în „Y” este simplă, dar oricare dintre liste poate fi în formă de „6”.

Problemă grea: LRU cache

O tabelă hash admite următoarele trei operații în O(1):

• inserarea unei perechi (cheie, valoare);
• ștergerea unei perechi, dându-se cheia;
• căutarea unei chei și returnarea valorii asociate (sau a unui cod special dacă cheia nu este găsită).

Clasa unordered_map din STL implementează o tabelă hash. Pentru această problemă, nu este nevoie să știți cum exact funcționează.

Un cache este în esență o tabelă hash. Cache-urile sunt folosite pretutindeni în practică:

• Un server web, odată ce a calculat conținutul unei pagini, îl poate salva într-un cache pentru a răspunde instantaneu la următoarele cereri pentru aceeași pagină. El inserează în cache perechea (URL, conținut pagină).
• Un browser poate stoca versiuni recente ale paginilor vizitate pentru a le prezenta offline (în absența rețelei).
• Un calculator, după ce caută în DNS adresa IP corespunzătoare unui hostname, poate salva perechea (hostname, IP) într-un cache pentru accesări mai rapide în viitor.
• Procesorul poate salva în cache-ul local pagini de memorie, pentru a le accesa mai repede.

În practică, orice cache are o dimensiune limită N, un număr maxim de perechi (cheie, valoare) pe care le poate stoca. Cum procedăm când se umple? Dacă cache-ul conține deja N înregistrări și dorim să inserăm încă una, trebuie să ștergem una din înregistrările existente. O politică cu rezultate bune în practică este evacuarea LRU (engl. least recently used): ștergem înregistrarea care a fost accesată ultima oară cel mai demult. Scopul evacuării LRU este să țină în cache înregistrările accesate frecvent.

Să se implementeze un cache LRU care să efectueze operațiile de inserare, ștergere și căutare în O(1).

Breviar: unordered_map

Iată un scurt program care exemplifică folosirea lui unordered_map: media:maptest.cpp. Compilați-l cu

g++ -std=c++11 -o maptest maptest.cpp

Temă

• Tema 3 juniori