Rečnici, torke, skupovi

Rečnici (dictionary)

Rečnici su generalizovana verzija liste. Sledi lista koja sadrži broj dana u mesecima godine:

dana = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]

Ako hoćemo broj dana u januaru, koristimo izraz dana[0]. Decembar ima dana[11] ili dana[-1].

Sledi rečnik dana u mesecima godine:

dani = {'Januar':31, 'Februar':28, 'Mart':31, 'April':30,
        'Maj':31, 'Jun':30, 'Jul':31, 'Avgust':31,
        'Septembar':30, 'Oktobar':31, 'Novembar':30, 'Decembar':31}

Da dobijemo broj dana u Januaru pišemo dani[‘Januar’]. Jedna korist od korišćenja rečnika u ovom slučaju je da je kod mnogo čitljiviji, i da ne treba da razmišljamo koji je indeks za traženi mesec. Rečnici, kao što ćemo videti, imaju veliki broj primena.

Osnovne operacije sa rečnicima

Kreiranje rečnika

Sledi jedan prost rečnik:

d = {'A':100, 'B':200}

Da označimo da je nešto rečnik koristimo zagrade {}. Svaki element u rečniku je par podataka razdvojen sa dve tačke. Prvi deo u paru se naziva kljič (key) a drugi je vrednost (value). Ključ igra ulogu sličnu indeksu. Tako je u prvom paru našeg primera, ‘A’:100, ključ jednak ‘A’, a vrednost je jednaka 100, pa d[‘A’] daje 100. Ključevi su često stringovi, ali mogu biti i celi i decimalni brojevi, kao i mnogo drugih stvari. U istom rečniku mogu se naći ključevi različitog tipa.

Promena rečnika

Počnimo sa sledećim rečnikom:

d = {'A':100, 'B':200}

Da promenimo d[‘A’] na 400 (umesto 100) pišemo:

d['A']=400

Da dodamo novi element u rečnik, prosto dodelimo novom ključu neku vrednost kao u primeru:

d['C']=500

Setite se da ovo nije moguće sa listama. Ako napišemo L[2]=500 za listu L koja ima samo dva elementa (L[0] i L[1]) dobićemo „index out of range“ grešku. Za razliku, kod rečnika je to moguće.

Da izbrišemo element iz rečnika koristimo operator del

del d['A']

Prazan rečnik

Prazan rečnik je {}, čemu je analogno [] za praznuu listu, ili ‘’ za prazan string.

Važna napomena

Redosled elemenata u rečniku ne mora biti isti sa redosldeom kojim su stavljani u rečnik. Interno, Python rearanžira elemente u cilju optimizacije performansi.

Primeri rečnika

Primer 1

Rečnik se može koristiti kao stvarni rečnik definisanja pojmova kao u sledećem primeru:

d = {'pas' : 'ima dugačak rep i laje!',
     'mačka' : 'kaže mjau',
     'miš' : 'love ga mačke'}

Evo i primera kako se taj rečnik može koristiti:

reč = input('Unesite reč: ')
print('Definicija reči:', d[reč])

Unesite reč: miš
Definicija reči: love ga mačke

Primer 2

Sledeći rečnik je koristan za rad sa Rimskim brojevima:

rimski = {‘I’:1, ‘V’:5, ‘X’:10, ‘L’:50, ‘C’:100, ‘D’:500, ‘M’:1000}

Primer 3

U igri Scrabble, svakom slovu je pridružena vrednost. Možemo koristiti sledeći rečnik za vrednost slova u njemu:

points = {'A':1, 'B':3, 'C':3, 'D':2, 'E':1, 'F':4, 'G':2,
          'H':4, 'I':1, 'J':8, 'K':5, 'L':1, 'M':3, 'N':1,
          'O':1, 'P':3, 'Q':10, 'R':1, 'S':1, 'T':1, 'U':1,
          'V':4, 'W':4, 'X':8, 'Y':4, 'Z':10}

Da izračunamo skor za neku reč koristimo kod:

skor = sum([points[c] for c in word])

Ili ako više volite dužu varijantu:

score = 0
for c in word:
    score += points[c]

Primer 4

Rečnik omogućava lepu varijantu za prikaz špila karata:

špil = [{'vrednost':i, 'boja':c}
        for c in ['pik', 'tref', 'herc', 'karo']
        for i in range(2,15)]

Špil je zapravo lista sa 52 rečnika. Metod shuffle se može iskoristiti za mešanje špila:

shuffle(špil)

Prva karta u špilu je špil[0]. Da dobijemo boju i vrednost karte koristimo sledeće naredbe:

špil[0]['vrednost']
špil[0]['boja']

Rad sa rečnicima

Kopiranje rečnika

Kao i kod liste kopiranje rečnika je malo problematično, o čemu ćemo govoriti kasnije. Da kopiramo rečnik koristimo copy metodu. Evo primera:

d2 = d.copy()

Operator in

Operator in se koristi da nam kaže da li je neki ključ u rečniku ili nije. Na primer, recimo da imamo sledeći rečnik:

d = {'A':100, 'B':200}

Ako pokušamo da dobijemo vrednost nekog ključa koji nije u rečniku dobićemo grešku. Na primer print(d[‘C’]) će javiti grešku. Da to sprečimo, možemo da iskoristimo operator in da proverimo da li je neki ključ u rečniku pre nego što upotrebimo taj ključ. Evo primera:

slovo = input('Unesite slovo: ')
if slovo in d:
    print('Vrednost je', d[slovo])
else:
    print('Nije u rečniku')

Možete takođe koristiti i not in da proverite da kljuć nije u rečniku.

Petlje

Može se napraviti petlja kroz rečnik na sličan način kao i kod liste. Evo jedan primer koji štampa sve ključeve iz rečnika:

for kljuc in d:
    print(kljuc)

A evo i primera koji štampa vrednosti iz rečnika:

for kljuc in d:
    print(d[kljuc])

Liste ključeva i vrednosti

Sledeća tabela ilustruje načine da se dobiju liste kljuceva i vrednosti iz rečnika. Za primere smo koristili rečnik d={‘A’:1, ‘B’:3}.

Naredba Rezultat Opis
list(d) [‘A’,’B’] Ključevi iz rečnika d
list(d.values()) [1,3] Vrednosti iz rečnika d
list(d.items()) [(‘A’,1),(‘B’,3)] (kljuc,vrednost) parovi iz d

Parovi koje daje d.items nazivaju se torke (tuples). Torke su slične listama. O njima će biti reči kasnije.

Ovde koristimo d.items da pronađemo sve ključeve rečnika d kojima odgovara vrednost 100:

d = {'A':100, 'B':200, 'C':100}
L = [x[0] for x in d.items() if x[1]==100]

['A', 'C']

Funkcija dict

Funkcija dict je još jedan način kako se kreira rečnik. To se radi kao u sledećem primeru:

d = dict([('A',100),('B',300)])

Gornjom narednom će biti kreiran rečnik {‘A’:100, ‘B’:300}.

Sastavljanje rečnika (Dictionary comprehensions)

Sastavljanje rečnika je slično sastavljanju liste. Sledeći jednostavan primer kreira rečnik od liste reči u kojem će vrednosti u rečniku biti dužine odgovarajućih reči:

reči=['jabuka','banana','jagoda']
d = {s : len(s) for s in reči}

Prebrojavanje reči

Možemo iskoristiti rečnik za izračunavanje frekvencije pojavljivanja reči u tekstovima.

U sledećem poglavlju naučićemo kako se čita tekst iz nekog fajla. Za sada, dajemo liniju koda koja čita ceo tekst pripovetke Ive Andrića i učitani tekst smešta u varijablu tekst:

tekst = open(‘svetknjige.txt’).read() Da dobijemo pojedinačne reči, koristićemo metod split da string pretvorimo u listu reči. Takođe, pošto su neke možda reči sa velikim slovima, konvertovaćemo sve reču u mala slova. Takođe ćemo ukloniti i sve znake interpunkcije.

from string import punctuation

tekst = tekst.lower()
for p in punctuation:
    tekst = tekst.replace(p, '';)
reči = tekst.split()

Sada sledi kod kojim se vrši prebrojavanje pojavljivanja reči. Rečnik koji kreiramo sadržaće reči iz teksta kao ključeve, dok će vrednosti biti broj pojavljivanja reči u tekstu. Počinjemo sa praznim rečnikom. Zatim za svaku reč u već napravljenoj listi reči iz teksta, ako je reč već viđena dodajemo jedan na vrednost koja odgovara toj reči. Ako se reč pojavljuje prvi puta vrednost postaje 1. Evo kako izgleda kod:

d = {}
for r in reči:
    if r in d:
        d[r] = d[r] + 1
    else:
        d[r] = 1

Kada smo kreirali rečnik, možemo da koristimo sledeći kod da štampamo rezultat sortiran alfabetski:

podaci = list(d.items())
podaci.sort()
for p in podaci:
    print(p)

Ovaj program koristi malo lukavstvo. Setite se da d.items() vraća listu parova (koje zovemo torke) koji su slični listama. Kada sortiramo listu torki, sortiranje se vrši po prvom elementu torke, što je u našem slučaju reč. Zato se sortiranje vrši u alfabetskom redosledu reči.

Ako umesto toga želimo da sortiranje bude po frekvencijama pojavljivanja reči, možemo zameniti mesta u torkama pre sortiranja, kako je dole pokazano:

podaci = list(d.items())
podaci = [(p[1], p[0]) for p in podaci]  # zamena mesta u torki
podaci.sort()
for p in podaci:
    print(p)

Evo sada celog programa:

from string import punctuation

# citanje iz fajla, uklanjanje znakova interpunkcije, a razbijanje (split) teksta u pojedinacne reci
tekst = open('svetknjige.txt').read()
tekst = tekst.lower()
for p in punctuation:
    tekst = tekst.replace(p, '';)
reči = tekst.split()

# Kreiranje recnika frekvencija
d = {}
for w in reči:
    if w in d:
        d[w] = d[w] + 1
    else:
        d[w] = 1

# stampanje u alfabetskom redosledu
parovi = list(d.items())
parovi.sort()
for p in parovi:
    print(p)

# stampanje od najmanjeg do najvećeg
parovi = list(d.items())
parovi = [(i[1], i[0]) for i in parovi]
parovi.sort()
for p in parovi:
    print(p)

Torke (Tuples)

Torka je zapravo nepromenljiva lista. Dole je prikazana jedna lista sa tri elementa i torka sa ista tri elementa:

L = [1,2,3]
t = (1,2,3)

Torke se stavljaju unutar malih zagrada, iako su zagrade u stvari samo opcione (može se i bez njih). Indeksiranje i segmentacija su isti kao i kod liste. Kao i kod liste funkcijom len možete dobiti dužinu torke, a torke imaju kao i liste count i index metode. Međutim, pošto su torke nepromenljive, torke nemaju neke metode koje imaju liste, kao što su sort ili reverse.

Već smo se susretali sa torkama. Metoda items kod rečnika je zapravo vraćala listu torki. Takođe kada smo koristili sledeće skraćeno pisanje za zamenu vrednosti dve ili više varijabli, zapravo smo koristili torke:

a,b = b,a

Jedan od razloga zašto postoje i liste i torke je što nam u nekim situacijama trebaju nepromeljive liste. Na primer lista ne može da bude ključ u rečniku, jer se lista može menjati, pa bi za Python to predstavljalo problem kako da prati takve promene ključa. Torke, međutim, mogu da igraju ulogu ključa u rečnicima. Evo primera kako se mogu pridružiti ocene parovima studenata:

ocene = {(‘Petar’, ‘Ana’): 95, (‘Milovan’, ‘Igor’): 87} Takođe, u situacijama kada je brzina važna, torke rade brže od lista. Fleksibilnost koju imaju liste plaća se dodatnom cenom u brzini.

Funkcija tuple

Za konverziju nekog objekta u torku koristimo funkciju tuple. Sledeći primer pokazuje kako se konvertuju lista i string u torku:

t1 = tuple([1,2,3]) t2 = tuple(‘abcde’)

Napomena

Prazna torka je (). Način da dobijemo torku sa jednim elementom je ovako: (1,). Ako bi napisali (1) jer se (1) interpretira kao matematički izraz sa zagradom koji ima vrednost 1. Na primer u formuli2+(3*4), mi ne želimo da (3*4) bude torka već želimo da to bude neki izračunati broj.

Skupovi (Sets)

Python ima i strukturu koja se zove set (skup). Set struktura radi slično matematičkim skupovima. Skupovi su slični listama, ali bez ponavljanja elemenata. Skupovi se označavaju vitičastim zagradama, {}, kao ovaj dole prikazani:

S = {1,2,3,4,5}

Setimo se da se vitičaste zagrade koriste za rečnike, a da je {} prazan rečnik. Da dobijemo prazan skup koristimo funkciju set bez argumenata, kao što je prikazano:

S = set()

Funkcija set se može koristiti i za konverziju objekata u skupove. Evo dva primera:

set([1,4,4,4,5,1,2,1,3])
set('this is a test')
{1, 2, 3, 4, 5}
{'a', ' ', 'e', 'i', 'h', 's', 't'}

Uočite da Python smešta podatke u skup u proizvoljnom redolsedu, i ne uvek u redosledu koji ste vi postavili. Kod skupova nije važan redosled, več samo podaci koji ga čine. To znači da indeksiranje kod skupova nema smisla. Zato se ne može , ma primer, tražiti s[0], za set s.

Rad sa skupovima

Postoji nekoliko operacija koje se mogu obavljati sa skupovima.

Operator Opis Primer
| Unija (union) {1,2,3}|{3,4} -> {1,2,3,4}
& Presek (intersection) {1,2,3}&{3,4} -> {3}
- Razlika (difference) {1,2,3}-{3,4} -> {1,2}
^ Simetrična razlika {1,2,3}^{3,4} -> {1,2,4}
in Jeste u skupu 3 in {1,2,3} -> True

Simetrična razlika daje elemente koji su u jednom ili drugom skupu ali ne u oba.

Evo i nekoliko korisnih metoda sa skupovima:

Metoda Opis
S.add(x) Dodaje x u skup
S.remove(x) Sklanja x iz skupa
S.issubset(A) Vraća True ako je S ⊂ A, a False ako nije .
S.issuperset(A) Vraća True ako je A ⊂ S, a False ako nije.

Na kraju, možemo slično kao i kod liste sastavljati skupove na skraćeni način:

s = {i**2 for i in range(12)}

{0, 1, 4, 100, 81, 64, 9, 16, 49, 121, 25, 36}

Napomena: Ovo nije moguće u Python 2 verzijama.

Primer: Brisanje duplih elemenata iz liste

Možemo iskoristiti činjenicu da skupovi ne mogu imati ponovljene elemente. Evo primera

L = [1,4,4,4,5,1,2,1,3]  # lista sa ponavljanjem elemenata
L = list(set(L))         # konvertujemo listu u skup, pa nazad u listu

Nakon toga lista će biti [1,2,3,4,5].

Vežbe

11.1 Napišite program koji uzastopno traži od korisnika da unese proizvod i njegovu cenu. Smestite sve unete vrednosti u rečnik čiji je ključ naziv proizvoda a vrednost cena proizvoda. Kada korisnik završi sa unosom podataka za rečnik, dajte mu mogućnost da uzastopno unosi ime proizvoda pa štampajte njegovu cenu ili poruku da proizvod nije u rečniku.

11.2 Koristeći rečnik kreiran u prethodnom problemu dajte mogućnost korisniku da unese neku vrednost pa štampajte sve proizvode čija je cena manja od unete vrednosti.

11.3 Za ovaj zadatak koristićemo rečnik sa početka ovog poglavlja koji je kao kljuc imao naziv meseca a kao vrednost broj dana u mesecu. Tražite od korisnika da unese naziv meseca, pa korišćenjem rečnika kažite mu koliko dana ima taj mesec (Vodite računa da korsinik može uneti nepostojeći mesec – greškom ili namerno )

  • Štampajte sve ključeve iz rečnika u alfabetskom redolsedu.
  • Štampajte sve mesece koji imaju 31 dan.
  • Štampajte (kljuc,vrednost) parove sortirane po broju dana u mesecu.
  • Modifikujte program tako da korisnik može da unese samo prva tri znaka iz naziva meseca.

11.4 Napišite program koji koristi rečnik u kojem se nalazi deset imena korisnika i njihovih pasvorda. Program treba da traži od korisnika da unesu ime i pasvord. Ako ime nije u rečniku program treba da obavesti korisnika da nije registrovan u sistemu. Ako je uneto ime u recniku ali korisnik nije uneo ispravan pasvord, program treba da ga obavesti da je uneti pasvord neispravan. Ako je pasvord ispravan program treba da saopšti korisniku da se ulogovao u sistem.

11.5 Tražite uzastopno od korisnika da unese ime tima kao i koliko je utakmica tim dobio i izgubio. Smestite ove informacije u rečnik u kojem će ključ biti ime tima a vrednost lista u formi [broj pobeda, broj poraza] .

  • Tražite od korisnika da unese naziv tima, pa korišćenjem rečnika izračunajte i štampajte procenat pobeda koje je taj tim ostvario.
  • Korišćenjem rečnika, kreirajte listu čiji su elementi brojevi pobeda svih timova.
  • Korišćenjem rečnika kreirajte listu svih timova koji imaju više pobeda nego poraza.

11.6 Uzastopno trašite od korisnika da unese rezultate utakmica dva tima u formi tim1 golova1 - tim2 golova2. Smestite ove informacije u rečnik kod kojeg je kljuc naziv tima a vrednost lisa oblika [broj pobeda, broj poraza].

11.7 Kreirajte jednu 5 x 5 listu slučajnih brojeva od 1 do 5. Zatim napišite program koji kreira rečnik čiji su ključevi brojevi iz 5 x 5 liste, a vrednosti brojevi njihovih pojavljivanja u listi. Zatim štampajte tri broja sa najvećim brojem pojavljivanja.

11.8 Korišćenjem rečnika za špil karata ( rečnik sa početka poglavlja) kreirajte jednu prostu igru u kojoj dvojica igrača dobijaju po tri karte. Igrač sa najačom kartom pobeđuje. Ako oba igrača imaju istu najaču kartu pobeđuje onaj koji ima drugu najaču kartu, ako je i tada nerešeno upoređuju se treće karte. Ako su kod oba igrača sve tri karte iste „jačine“ partija je nerešena.

11.9 Korišćenjem rečnika za špil karata ( rečnik sa početka poglavlja), podelite tri karte. Odredite sledeće:

  • Da li su sve tri karte iste boje (fleš).
  • Da li su sve tri karte iste vrste (triling)
  • Da li postoji par istih (ali ne i triling)
  • Da li tri karte čine liniju (kao recimo 2,3,4 ili (10, Žandar, Dama)

11.10 Korišćenjem rečnika za špil karata ( rečnik sa početka poglavlja) i Monte Karlo simulacije procenite verovatnoću da se dobije fleš kada se podeli pet karata.

11.11 U nekom od ranijih poglavlja sreli smo se sa šifriranjem teksta. Kod šifriranja se svako slovo teksta zamenjuje sa nekim drugim slovom. Na primer svako a zamenjujemo sa e, svako b sa a itd. Napišite program koji traži od korisnika da unese dva stringa. Zatim utvrdite da li drugi string može da bude šifrirana verzija prvog stringa kod kojeg je izvršena zamena slova kako je gore navedeno. Na primer string CXYZ ne može biti šifiran string BOOK jer se O pojavljuje sa dva različita slova u šifriranim string CXYZ. Takođe, CXXK nije šifrirana verzija od BOOK jer se K zamenilo sa samim sobom. S druge strane CXXZ može biti širiran string BOOK. Problem može biti rešen sa ili bez rečnika.13.

11.12 Pretpostavimo da vam je data sledeća lista stringova

L = ['aabaabac', 'cabaabca', 'aaabbcba', 'aabacbab', 'acababba']

Ovakvi nizovi se pojavljuju na raznim mestima uključujući DNA kodove. Korisnik ima string sa samo nekim od slova a ostala mesta su popunjena sa zvezdicama. Na primer a**a****. Korisnik bi želeo da zna koji string iz liste odgovara njegovom parcijalnom stringu. U primeru koji je dat, a**a****, ovoj mustri bi moglao da odgovara prvi i treći član liste. Jedan način da se reši ovaj problem je da se kreira rečnik čiji ključevi bi bili indeksi za ona slova iz korisnikovog stringa koja nisu zvezdice, a vrednosti u rečniku bi bila sama ta slova. Napišite program koji koristi ovaj način (ili neki drugi načina ) za pronalaženje stringova koji odgovaraju stringu koji unese korisnik ( mustri)

11.13 Rečnici predstavljaju pogodan način za smeštanje (pamćenje) struktuiranih podataka. Evo jednog takvog primera

d=[{'ime':'Janko', 'telefon':'555-1414', 'email':'janko@mail.net'},
   {'ime':'Marko', 'telefon':'555-1618', 'email':'marko@mail.net'},
   {'ime':'Ana', 'telefon':'555-3141', 'email':'';},
   {'ime':'Jovana', 'telefon':'555-2718', 'email':'jovana@mail.net'}]

Napišite program koji čita ovaj rečnik i štampa sledeće:

  • Sve korisnike čiji telefonski broj se završava sa 8.
  • Sve korisnike koji nemaju email adresu.

11.14 Napišite program kojim se nalazi unija i presek sledećih skupova

A = {1, 2, 3, 4, 5}
B = {4, 5, 6, 7, 8}