-
Notifications
You must be signed in to change notification settings - Fork 0
/
README
70 lines (50 loc) · 2.97 KB
/
README
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
********************************************************************************
README
TEMA 2 SD
BUF SORINA-ANAMARIA
********************************************************************************
Cele trei taskuri sunt implementate in functiile freq.c, hash.c, hll.c.
TASK I
Primul task este implementat integral in functia main si a constat in creearea
unui vector de frecventa pe care la inceput il aloc si initializez cu 0. Pe
masura ce numerele sunt citite, pe pozitia din vector aferenta valorii
numarului citit maresc cu o unitate numarul de aparitii stocat in bucketul
respectiv. La final, afisez perechile valoare - numar de aparitii.
TASK II
Al doilea task a constat in calcularea numarului de aparitii al mai multor
siruri de caractere, folosind un Hashtable cu politica de rezolvare a
conflictelor de tip open addressing prin linear probing, care presupune faptul
ca, in momentul in care bucketul unde trebuie realizata insertia este ocupat,
se cauta prima pozitie libera dupa bucketul respectiv. Daca se ajunge la finalul
hashtable-ului, cautarea se reia de la inceputul structurii.
Taskul este implementat in urmatoarele functii:
-unsigned int hash_function_string(char key[LENGTH])
functia folosita pentru calcularea hash-ului stringurilor
-void collision_same_word(struct Hashtable *ht, unsigned int index,
char word[LENGTH])
functia folosita pentru rezolvarea coliziunilor in cazul in care bucketul
unde trebuie realizata insertia contine deja un string identic
-void collision_different_word(struct Hashtable *ht, unsigned int index,
char word[LENGTH])
functia folosita pentru rezolvarea coliziunilor in cazul in care bucketul
unde trebuie realizata insertia contine un string diferit
void print_words(struct Hashtable *ht)
functia folosita pentru printarea perechilor cuvant - numar de aparitii
De asemenea, functiile implementate mai sus sunt apelate in functia main, care
initializeaza hashtable-ul, citeste cuvintele si calculeaza numarul de aparitii
al fiecarui string.
TASK III
Al treilea task a constat in implementarea algoritmului HyperLogLog folosit
pentru calcularea numarului de aparitii distincte al unui sir de numere.
Taskul este implementat in urmatoarele functii:
-unsigned int hash_integer(void *a)
functia folosita pentru calcularea hash-ului inturilor
-double power(int x)
functia folosita pentru calcularea puterilor lui 2
De asemenea, functiile implementate mai sus sunt apelate in functia main,
care citeste numerele si urmeaza pasii algoritmului HyperLogLog: initializarea
unui vector M de marimea 2048; pentru fiecarea numar calcularea hash-ului,
calcularea indexului bucketului corespunzator, calcularea numarului de
biti 0 initiali; agregarea valorilor din toate bucketurile si determinarea
numarului de elemente distincte intalnite.
********************************************************************************