Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.
Ambele părți revizuirea anterioară Versiuni anterioare Urmatoarea versiune | Versiuni anterioare Urmatoarea versiune Ambele părți următoarea reviziune | ||
laboratoare:laborator-02 [2017/03/02 20:52] iulian.matesica |
laboratoare:laborator-02 [2017/03/04 09:28] iulian.matesica |
||
---|---|---|---|
Linia 54: | Linia 54: | ||
Pentru laboratorul de liste inlantuite vom porni de la o arhiva cu un schelet de laborator. Nu veti scrie codul de la zero ci veti implementa cateva functii in fisierul '' | Pentru laboratorul de liste inlantuite vom porni de la o arhiva cu un schelet de laborator. Nu veti scrie codul de la zero ci veti implementa cateva functii in fisierul '' | ||
- | Descarcati arhiva de [[laboratoare: | + | Descarcati arhiva de {{ :laboratoare: |
<code bash> | <code bash> | ||
student@sda-ab-vm: | student@sda-ab-vm: | ||
Linia 118: | Linia 118: | ||
| | ||
- | | + | |
+ | |||
+ | | ||
+ | |||
+ | **O soluţie**: -Ei consideră că două carţi “seamană” între ele dacă titlurile lor încep cu aceeaşi literă, aşa că au nevoie de câte un sector pentru fiecare literă cu care ar putea începe titlul unei cărţi. Folosind această regulă, angajaţii nu au nevoie de mai mult de 32 de sectoare(26 pentru engleză), adică de atâtea sectoare câte litere sunt în alfabet, deci fiecarui sector îi va corespunde o literă. | ||
+ | |||
+ | | ||
+ | *O carte poate fi pusă într-un raft imediat după ce identificăm ce sector are aceeaşi literă cu prima literă din titlul cărţii, putem lua această decizie fără a ţine cont de celelalte cărţi, deci vom avea nevoie de mai puţin timp. | ||
+ | *Când cineva vrea să găsească o carte din bibliotecă, | ||
+ | |||
+ | | ||
+ | |||
+ | | ||
+ | |||
+ | ===Folosind o abordare mai tehnică, să urmărim aceleaşi detalii: | ||
+ | |||
+ | | ||
+ | |||
+ | | ||
+ | |||
+ | | ||
+ | |||
+ | **O soluţie**: -alegem ca un sector să reprezinte o literă şi aceea să fie litera cu care încep toate titlurile intrărilor din acel sector. În realitate, sectoarele pot fi notate cu litere, dar, într-un limbaj de programare, le notăm cu numere pentru a lucra mai uşor. | ||
+ | |||
+ | * Functia index dă valorile **{0, | ||
+ | < | ||
+ | | ||
+ | </ | ||
+ | |||
+ | * Ignorând problema spaţiului, definim secvenţa pentru distribuirea intrărilor pe sectoare: | ||
+ | (presupunem structura **Carte** definită) | ||
+ | <file cpp> | ||
+ | Carte sector[26][n]; | ||
+ | int elemInSectorul[26] = {0}; // contor pentru nr. de elemente, 0 iniţial | ||
+ | for(int i = 0; i < nrCarti; | ||
+ | int indexCurent = index(intrare[i].titlu); | ||
+ | sector[indexCurent][elemInSectorul[indexCurent]] = intrare[i]; | ||
+ | elemInSectorul[indexCurent]++; | ||
+ | } //o variantă mai eficientă foloseşte 26 de liste în loc de 26 de vectori | ||
+ | </ | ||
+ | |||
+ | **Rezultatele**: | ||
+ | |||
+ | | ||
+ | | ||
+ | |||
+ | | ||
+ | |||
+ | |||
+ | ====1.2 Simplificare==== | ||
+ | |||
+ | Cum ar fi dacă, în loc de foarte multe cărţi, am avea 26 de cărţi şi, în plus, nu ar exista nicio pereche de cărţi pentru care titlurile lor să înceapă cu aceeaşi literă? | ||
+ | |||
+ | *În acest caz, indexarea este perfectă: fiecare sector conţine o carte. | ||
+ | | ||
+ | |||
+ | =====2. Conceptele Cheie-Valoare(Key-Value)===== | ||
+ | Atunci când reorganizăm o structură de date, aşezăm într-o ordine diferită **valorile** din structura de date, folosind o regulă bazată pe **cheile** acestora. | ||
+ | |||
+ | *În exemplul nostru, structura de date este biblioteca. Aceasta conţine mai multe **cărţi**(valori), | ||
+ | |||
+ | =====3. Funcţia de indexare şi sectoarele(buckets)===== | ||
+ | Sectoarele sunt stocate sub formă de elemente ale unui vector. Avem nevoie de o funcţie care să facă legătura dintre cheie şi indice(index) al vectorului. | ||
+ | |||
+ | *În exemplul nostru, funcţia **index** preia prima litera din **titlu**(cheie) şi calculează “diferenţa” dintre această literă şi prima literă din alfabet. | ||
+ | |||
+ | =====4. Funcţia de dispersie(hash function)===== | ||
+ | Când coincide cu funcţia de indexare? | ||
+ | |||
+ | În general, putem scrie | ||
+ | <file cpp> | ||
+ | index(cheie, | ||
+ | </ | ||
+ | unde hash = funcţia de dispersie. Cu alte cuvinte, funcţia de dispersie trebuie să genereze un întreg(**oricât de mare**), folosindu-se de cheie, iar funcţia de indexare obţine un **indice**(indicele sectorului în care vom reţine cheia respectivă şi valoarea ei). | ||
+ | |||
+ | | ||
+ | <file cpp> | ||
+ | hash(cheie) == hash(cheie) % nrSectoare | ||
+ | </ | ||
+ | adică atunci când valorile luate de **hash(cheie)** pot fi folosite ca **indici**(0, | ||
+ | |||
+ | |||
+ | *În exemplul nostru, funcţia index nu are nevoie de nrSectoare(am considerat această valoare **mereu** egală cu **26**) şi nu apare “%26” în formulă, deci putem considera funcţia de dispersie şi funcţia de indexare **identice**. | ||
+ | *Cele mai simple funcţii hash: | ||
+ | <file cpp> | ||
+ | hash(cheie) == cheie % nrSectoare, unde cheia = întreg | ||
+ | </ | ||
+ | |||
+ | |||
+ | =====5 Avantaje/ | ||
+ | |||
+ | ====5.1 Avantaje==== | ||
+ | *timp de acces(un **vector** cu sectoare) | ||
+ | *timp de inserare(fiecare sector = o **listă**) | ||
+ | |||
+ | ====5.2 Dezavantaje==== | ||
+ | *nu este mereu uşor de ales o funcţie pentru dispersia(**uniformă** a) cheilor | ||
+ | | ||
+ | |||
+ | ====5.3 Observaţii==== | ||
+ | *în general, un ansamblu de tipul (**structură de sectoare/ | ||
+ | | ||
+ | |