Python stazaCjelina 5 · Strukture podataka (napredno)Lekcija 31

Brojanje i traženje: Counter, defaultdict i bisect

Tri gotova alata koja skraćuju programe iz lekcija 24 i 27: brojanje bez if-a, rječnik koji sam stvara vrijednosti i binarno pretraživanje u jednom retku.

Pythonoko 45 minuta4 zadatka za evaluator

1Brojanje bez if-a: Counter

U lekciji 24 brojali smo pojave rječnikom: ako ključ postoji, povećaj ga, a inače ga postavi na 1. Toliko je čest posao da Python ima gotov alat: Counter iz modula collections. Dobije listu (ili tekst) i sam prebroji sve elemente.

Program
from collections import Counter
glasovi = Counter(["Ana", "Ivo", "Ana", "Mia", "Ana", "Ivo"])
print(glasovi["Ana"])
print(glasovi["Marko"])
print(glasovi.most_common(2))
Ispis
3 0 [('Ana', 3), ('Ivo', 2)]
NaredbaŠto radi
Counter(lista)prebroji elemente liste (ili slova teksta)
cnt[x]koliko puta se pojavio x; za x kojeg nema vraća 0 (bez greške!)
cnt[x] += 1povećaj, i kad x još ne postoji
cnt.most_common(k)k najčešćih, kao lista parova (element, broj)
Pazi

Kad više elemenata ima jednako pojava, most_common ih daje redom kojim su se prvi put pojavili, a ne po abecedi. Ako zadatak traži abecedu, nađi najveći broj pojava (max(cnt.values())), pa među elementima s tim brojem uzmi najmanji.

2Rječnik s početnom vrijednošću: defaultdict

Ponekad za svaki ključ želimo skupljati listu. defaultdict(list) je rječnik koji za ključ kojeg još nema sam stvori praznu listu. Tako odmah možemo pisati d[k].append(x).

Program
from collections import defaultdict
po_slovu = defaultdict(list)
for rijec in ["mama", "tata", "more", "trava", "sunce"]:
    po_slovu[rijec[0]].append(rijec)
for slovo in sorted(po_slovu):
    print(slovo, po_slovu[slovo])
Ispis
m ['mama', 'more'] s ['sunce'] t ['tata', 'trava']
Ključna ideja

defaultdict(int) radi isto što i Counter za brojanje: za novi ključ počinje od 0.

3Binarno pretraživanje gotovom funkcijom: bisect

U lekciji 27 binarno pretraživanje smo pisali sami. Modul bisect ima gotove funkcije za sortiranu listu:

FunkcijaVraća
bisect_left(a, x)prvo mjesto na koje bi se x mogao umetnuti: broj elemenata manjih od x
bisect_right(a, x)zadnje takvo mjesto: broj elemenata manjih ili jednakih x
Program
from bisect import bisect_left, bisect_right
a = [2, 4, 4, 4, 7, 9]
print(bisect_left(a, 4))
print(bisect_right(a, 4))
print(bisect_right(a, 4) - bisect_left(a, 4))
print(bisect_right(a, 8) - bisect_left(a, 3))
Ispis
1 4 3 4

Zadnja dva retka su najčešća primjena: koliko puta se x pojavljuje, i koliko je elemenata između 3 i 8. Svaka funkcija radi oko log N koraka.

Pazi

Lista mora biti sortirana. Na nesortiranoj listi bisect vraća besmislene rezultate i ne javlja grešku.

4Provjeri se

Prije zadataka provjeri jesi li razumio gradivo. Klikni na odgovor za koji misliš da je točan.

Pitanje

Što vraća Counter("banana")["a"]?

Pitanje

Što vraća cnt[x] za x kojeg nema u Counteru?

Pitanje

Za a = [1, 3, 3, 5], koliko je bisect_right(a, 3) - bisect_left(a, 3)?

5Zadaci

Najčešća riječ

★☆☆ lagano

Učitaj N riječi. Koja se pojavljuje najviše puta i koliko puta? Ako ih je više, ispiši onu koja je prva po abecedi.

Ulaz
U prvom retku N. Zatim N redaka s po jednom riječi od malih slova.
Izlaz
Riječ i broj pojavljivanja, odvojeni razmakom.
Ograničenja
1 ≤ N ≤ 100 000
Ulaz
5 mama tata mama baka tata
Izlaz
mama 2
Treba ti pomoć?

Counter prebroji sve odjednom. Najveći broj je max(cnt.values()), a među riječima s tim brojem traži najmanju po abecedi.

Riješi u evaluatoru

Po početnom slovu

★★☆ srednje

Učitaj N riječi i razvrstaj ih po početnom slovu. Za svako slovo koje se pojavljuje ispiši redak: slovo, dvotočku, pa riječi koje njime počinju, poredane po abecedi (ponavljanja ostaju).

Ulaz
U prvom retku N. Zatim N redaka s po jednom riječi.
Izlaz
Po jedan redak za svako početno slovo, slova po abecedi.
Ograničenja
1 ≤ N ≤ 50 000
Ulaz
5 more auto mama maca auto
Izlaz
a: auto auto m: maca mama more
Treba ti pomoć?

defaultdict(list): ključ je prvo slovo, a vrijednost lista riječi. Na kraju sortiraj i ključeve i svaku listu.

Riješi u evaluatoru

Skupine anagrama

★★☆ srednje

Dvije riječi su anagrami ako imaju ista slova, možda drukčijim redom (npr. tabla i balta). Riječi koje su međusobno anagrami čine skupinu. Koliko je skupina i koliko riječi ima najveća?

Ulaz
U prvom retku N. Zatim N redaka s po jednom riječi.
Izlaz
Broj skupina i veličina najveće, odvojeni razmakom.
Ograničenja
1 ≤ N ≤ 100 000, riječi do 10 slova
Ulaz
5 lisa sila mama slia maam
Izlaz
2 3
Treba ti pomoć?

Anagrami imaju istu sortiranu riječ: "".join(sorted(rijec)). Neka to bude ključ rječnika.

Riješi u evaluatoru

Koliko ih je u rasponu

★★☆ srednje

Zadan je niz od N brojeva i Q pitanja. Za svako pitanje (x, y) ispiši koliko je brojeva niza između x i y, uključujući x i y.

Ulaz
U prvom retku N i Q. U drugom retku N brojeva. Zatim Q redaka s x i y (x ≤ y).
Izlaz
Q redaka s odgovorima.
Ograničenja
1 ≤ N, Q ≤ 100 000, brojevi do 10⁹
Ulaz
6 3 4 9 2 4 7 4 3 7 10 20 4 4
Izlaz
4 0 3
Treba ti pomoć?

Sortiraj niz jednom. Odgovor je bisect_right(a, y) − bisect_left(a, x).

Riješi u evaluatoru
Vježbaj dalje: zadaci s natjecanja

Ovi zadaci s Infokupa traže upravo ovo gradivo. Kreni od prvoga.

  1. Igra Infokup 2014 · županijsko · 8. r. OŠ
  2. Imendan Infokup 2013 · županijsko · 8. r. OŠ
  3. Kripto Infokup 2017 · županijsko · 8. r. OŠ

6Što smo naučili

  • Counter(lista) prebroji elemente; za nepostojeći ključ vraća 0.
  • defaultdict(list) za novi ključ sam stvori praznu listu.
  • bisect_left i bisect_right rade binarno pretraživanje na sortiranoj listi.
  • Broj elemenata u rasponu [x, y]: bisect_right(a, y) − bisect_left(a, x).
Najčešće greške

most_common kod jednakih ne sortira po abecedi · bisect na nesortiranoj listi · zaboravljen import