Metoda clasică

Un vector de frecvență este un vector în care memorăm de câte ori apare fiecare valoare într-o colecție de numere. Ideea este simplă: indicele reprezintă valoarea, iar elementul aflat la acel indice reprezintă numărul de apariții ale valorii respective.

Să considerăm lista:

v = [2, 5, 2, 3, 5, 2, 7]

Valoarea 2 apare de 3 ori, valoarea 3 apare o dată, valoarea 5 apare de 2 ori, iar valoarea 7 apare o dată. În vectorul de frecvență vom avea, așadar, f[2] = 3, f[3] = 1, f[5] = 2 și f[7] = 1.

Dacă știm că toate valorile sunt numere naturale cuprinse între 0 și 100, construim un vector cu 101 elemente, inițial egale cu 0:

v = [2, 5, 2, 3, 5, 2, 7]

f = [0] * 101

for x in v:
    f[x] += 1

La fiecare apariție a unei valori x, incrementăm elementul f[x]. De exemplu, de fiecare dată când întâlnim valoarea 2, executăm f[2] += 1. După parcurgerea întregii liste, f[2] va avea valoarea 3.

▶️ Analizează simularea de mai jos: Observație 💡 Vectorul de frecvență nu memorează valorile în ordinea în care apar. El memorează câte apariții are fiecare valoare posibilă.

Pentru a afișa numai valorile care apar în listă și frecvențele lor, putem scrie:

for i in range(len(f)):
    if f[i] > 0:
        print(i, "apare de", f[i], "ori")

Vectorii de frecvență sunt utilizați frecvent pentru a determina valorile distincte, valorile care apar o singură dată, valorile care se repetă sau elementul cu frecvența maximă.

De ce este eficient?

Pentru construirea vectorului de frecvență parcurgem lista o singură dată. Pentru fiecare element efectuăm doar operația f[x] += 1, astfel încât complexitatea algoritmului este O(n).

În plus, după construirea vectorului, frecvența unei valori poate fi aflată direct. Dacă vrem să știm de câte ori apare valoarea 7, este suficient să accesăm:

print(f[7])

Există însă și limitări. Metoda clasică este potrivită atunci când valorile sunt numere naturale dintr-un interval relativ mic și cunoscut. Dacă lista conține valori precum 1.000.000 sau 7.000.000, ar trebui să rezervăm un vector uriaș doar pentru câteva valori folosite efectiv.

În plus, valorile negative nu pot fi folosite direct ca indici cu semnificația dorită. Pentru astfel de situații, în Python avem o soluție mult mai flexibilă: dicționarele.

Vector de frecvență cu dicționar

Într-un dicționar putem folosi cheia pentru valoarea întâlnită și valoarea asociată cheii pentru frecvența acesteia. Avantajul este că memorăm numai elementele care apar efectiv.

v = [2, 5, 2, 3, 5, 2, 7]

f = {}

for x in v:
    if x in f:
        f[x] += 1
    else:
        f[x] = 1

Dicționarul obținut va fi:

{2: 3, 5: 2, 3: 1, 7: 1}

Algoritmul este ușor de urmărit: dacă x există deja în dicționar, îi mărim frecvența; dacă apare pentru prima dată, îl introducem cu frecvența 1.

Varianta cu get()

Python ne permite să scriem aceeași idee mult mai compact folosind metoda get() a dicționarelor:

f = {}

for x in v:
    f[x] = f.get(x, 0) + 1

Expresia f.get(x, 0) returnează valoarea asociată cheii x dacă aceasta există în dicționar. Dacă cheia nu există încă, returnează valoarea 0.

Astfel, instrucțiunea f[x] = f.get(x, 0) + 1 poate fi citită foarte natural: frecvența lui x devine frecvența sa anterioară plus 1; dacă x nu exista, pornim de la 0.

Și această metodă are, în medie, complexitatea O(n).

Hack cu dictionary comprehension

În Python, dicționarele pot fi construite și prin dictionary comprehension, folosind o sintaxă asemănătoare cu list comprehension:

{cheie: valoare for element in colectie}

Pentru frecvențe am putea scrie foarte elegant:

v = [2, 5, 2, 3, 5, 2, 7]

f = {x: v.count(x) for x in set(v)}

set(v) păstrează valorile distincte, iar pentru fiecare valoare x, expresia v.count(x) determină numărul ei de apariții.

💡 Codul este scurt și foarte ușor de citit, dar există un detaliu important: count() parcurge lista de fiecare dată când este apelat. Pentru multe valori distincte, lista va fi parcursă în mod repetat, iar complexitatea poate ajunge foarte ușor la O(n²).

Prin urmare, o soluție mai scurtă nu este automat și o soluție mai eficientă.

Counter – varianta Python

Python oferă în modulul collections o structură specializată exact pentru această operație: Counter.

from collections import Counter

v = [2, 5, 2, 3, 5, 2, 7]

f = Counter(v)
print(f)

Rezultatul va fi:

Counter({2: 3, 5: 2, 3: 1, 7: 1})

Dacă avem nevoie de un dicționar obișnuit, îl putem obține direct:

f = dict(Counter(v))

Important ⚠️ Pentru problemele clasice de algoritmică este important să înțelegem mai întâi metoda cu vectorul de frecvență și apoi implementarea cu dicționar. Counter este soluția oferită direct de Python atunci când scopul nostru este pur și simplu să numărăm aparițiile.

🧠 Rețineți ideea de bază: indiferent dacă folosim un vector, un dicționar sau Counter, construim aceeași asociere — fiecărei valori îi asociem numărul său de apariții.

1

O parte dintre manualele și culegerile de probleme se găsește și [în format electronic] securizat sub formă de fișier *.pdf.
"O cameră fără cărţi este ca un corp fără suflet." (G. K. Chesterton)

[vezi lista completă a cărților]

home

list  LECȚII

perm_identity

arrow_upward