Zadaci za wannabe pythoniste

Ključevi moraju biti jedinstveni. Ne možeš imati dva unosa sa istim ključem. Kao što ti je Đoka već rekao Dictionary je u stvari heš tabela. Pogledaj prvo šta je heš tabela, npr. https://en.wikipedia.org/wiki/Hash_table ili https://www.youtube.com/watch?v=MfhjkfocRR0

Mogao bi pod ključem agent da čuvaš niz.

Panto ovaj tvoj mydic.get metod ne rešava problem koji imamo kad je više istih ključeva:

>>> mydic = {'agency' : 'agencija', 'court' : 'avlija', 'court' : 'dvorište'}
>>>mydyc.get('court')
dvorište

nema 'avlije'

Inače, položio si kolokvijum sa zadatkom broj dvanaest. Čestitam! :)
I tvoje i moje rešenje su ovde.

Ništa od interfejsa za sada. Stavljamo ga na ler.
Iskrsni problemi neviđeni oko heš tabele, ne mož raspetljati ni pod razno
Kao što je Đoka i predviđao. Zna čovek gde su nagazne mine.

Odoh da vidim šta su te heš tabele, pa ćemo onda na kanal da budžimo

I naravno, hvala za apdejtovani rečnik. Mada je to tek test verzija, sad je čista ko suza!

Nema zato što je nemaš ni u rečniku. Ne možeš da imaš dva istoimena ključa.

Hvala za link. Ovo sa Wiki je pisano za vanzemaljce. Ništa ne razumem.
Pa sam našao na Stackoverflow nešto svarljivije. Možda će još nekom trebati, pa prenosim ovde.
Naravno, ostaje pitanje, kako sve to tehnički implementirati, ali bar mi je malo jasniji princip rada. Koliko shvatam, to mu dođe nešto kao bar-kod.

Here's an explanation in layman's terms.

Let's assume you want to fill up a library with books and not just stuff them in there, but you want to be able to easily find them again when you need them.

So, you decide that if the person that wants to read a book knows the title of the book and the exact title to boot, then that's all it should take. With the title, the person, with the aid of the librarian, should be able to find the book easily and quickly.

So, how can you do that? Well, obviously you can keep some kind of list of where you put each book, but then you have the same problem as searching the library, you need to search the list. Granted, the list would be smaller and easier to search, but still you don't want to search sequentially from one end of the library (or list) to the other.

You want something that, with the title of the book, can give you the right spot at once, so all you have to do is just stroll over to the right shelf, and pick up the book.

But how can that be done? Well, with a bit of forethought when you fill up the library and a lot of work when you fill up the library.

Instead of just starting to fill up the library from one end to the other, you devise a clever little method. You take the title of the book, run it through a small computer program, which spits out a shelf number and a slot number on that shelf. This is where you place the book.

The beauty of this program is that later on, when a person comes back in to read the book, you feed the title through the program once more, and get back the same shelf number and slot number that you were originally given, and this is where the book is located.

The program, as others have already mentioned, is called a hash algorithm or hash computation and usually works by taking the data fed into it (the title of the book in this case) and calculates a number from it.

For simplicity, let's say that it just converts each letter and symbol into a number and sums them all up. In reality, it's a lot more complicated than that, but let's leave it at that for now.

The beauty of such an algorithm is that if you feed the same input into it again and again, it will keep spitting out the same number each time.

Ok, so that's basically how a hash table works.

Technical stuff follows.

First, there's the size of the number. Usually, the output of such a hash algorithm is inside a range of some large number, typically much larger than the space you have in your table. For instance, let's say that we have room for exactly one million books in the library. The output of the hash calculation could be in the range of 0 to one billion which is a lot higher.

So, what do we do? We use something called modulus calculation, which basically says that if you counted to the number you wanted (i.e. the one billion number) but wanted to stay inside a much smaller range, each time you hit the limit of that smaller range you started back at 0, but you have to keep track of how far in the big sequence you've come.

Say that the output of the hash algorithm is in the range of 0 to 20 and you get the value 17 from a particular title. If the size of the library is only 7 books, you count 1, 2, 3, 4, 5, 6, and when you get to 7, you start back at 0. Since we need to count 17 times, we have 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, and the final number is 3.

Of course modulus calculation isn't done like that, it's done with division and a remainder. The remainder of dividing 17 by 7 is 3 (7 goes 2 times into 17 at 14 and the difference between 17 and 14 is 3).

Thus, you put the book in slot number 3.

This leads to the next problem. Collisions. Since the algorithm has no way to space out the books so that they fill the library exactly (or the hash table if you will), it will invariably end up calculating a number that has been used before. In the library sense, when you get to the shelf and the slot number you wish to put a book in, there's already a book there.

Various collision handling methods exist, including running the data into yet another calculation to get another spot in the table (double hashing), or simply to find a space close to the one you were given (i.e. right next to the previous book assuming the slot was available also known as linear probing). This would mean that you have some digging to do when you try to find the book later, but it's still better than simply starting at one end of the library.

Finally, at some point, you might want to put more books into the library than the library allows. In other words, you need to build a bigger library. Since the exact spot in the library was calculated using the exact and current size of the library, it goes to follow that if you resize the library you might end up having to find new spots for all the books since the calculation done to find their spots has changed.

I hope this explanation was a bit more down to earth than buckets and functions :)

Sada si me podsetio na one dve legendarne scene iz filma Karate Kid - prve, kao i one kasnije u filmu, druge ... gde ucitelj objasnjava klincu kako je sve u zivotu Kung Fu. A sto rece profesor Edsger Dijkstra: "Programiranje je jedna od najtezih oblasti primenjene matematike. Losim matematicarima bi bilo najbolje da se drze ciste matematike".

Matematicki problemi u pocetnickim zbirkama iz programiranja su vojnicki dril za buduceg programera. Svrha tih zadataka je da te nauce da razmisljas kao programer, sto tebi u ovom trenutku prilicno nedostaje i to se recimo videlo na onom zadatku s bacanjem novcica. Lepo si iskoristio funkciju random.randint(0,1) da dobijes uniformno raspodeljene slucajne ishode nule ili jedinice, a onda si napisao:

    if random.randint(0, 1) == 0:

        baci = '1glava'

    else:

        baci = '0pismo'

    print(baci[0], end='')

Znaci, ako ti je rezultat 0 ti to tumacis kao '1glava', a ako ti je rezultat 1 tebi je to '0pismo', da bi kasnije 'pismo' i 'glavu' odsekao i ispisao samo 0 i 1. Nazivi 'glava' i 'pismo' su cist visak. Takodje, nema potrebe da obrces rezultat funkcije randint(), ako imas u vidu da je verovatnoca ishoda 0 i 1 fifty-fifty, zar ne? Prema tome, zasto ne odmah:

    print (random.randint(0,1), end='')

Slicno si uradio i sa ovim recnikom - napravio si strukturu u kojoj su ti kljucevi engleske reci, a vrednosti srpske, da bi onda vrsio obrnuto prevodjenje.

Nemoj da me shvatis pogresno, ovo sto radis je sjajna stvar. Ucis! I to je super! Zapravo, trenutno samo opipavas teren, ali sada je vec vreme da malcice naucis neke temelje struke, kako bi ti se kockice slozile na pravi nacin. Recimo, na netu ces naci gomilu kurseva posveceih uvodu u programiranje i strukturama podataka. Moj favorit je ovaj uvodni Python kurs sa MIT - pokriva sve aspekte Pythona, veoma lep, akademski, metodican, imas video snimke profesora koji pricaju, mozes da skines slajdove da ih listas dok slusas predavanja, sve besplatno dostupno, mozes sve i da downloadujes. I nije namenjen samo buducim programerima, vec studentima svih inzenjerskih disciplina koje se tamo izucavaju, jer je na MIT Python neka vrsta programerskog bukvara za sve studente ... kasnije oni koji rade number crunching uce SciPy/SymPy, a programeri napredne algoritme itd. Mislim da bi ti ovaj kurs pomogao da popunis rupe u znanju. Oni imaju i zadatke za vezbu itd. A mozes i paralelno da nastavis da eksperimentises, naravno. Jednom kada odslusas kurs videces kako ovi zadaci koje postujes ovde pocinju da ti imaju vise smisla.

Na kraju, da se nadovezem na ovo sto je Djole lepo rekao:

A onda kada budes shvatio da je tocak i vatru vec izmislio neko drugi ... i da je vecinu standardnih programerskih zadataka neko vec resio i napravio i Python modul za to ... i da je tvoje samo da proucis dokumentaciju za taj modul, vidis koje su ti funkcije potrebne i opalis jedan 'import modul_taj_i_taj' na pocetku programa (prethodno ces morati da radis 'pip install', doduse ...) - videces da se mnogi problemi resavaju i sa 10 linija, umesto 10000 linija koda. E tada postajes vec medior programer, koji uspesno koristi ono sto vec postoji i ne izmislja toplu vodu svaki put iznova i iznova. A senior ces postati onda kada i sam budes uspeo da napises svoje module. Otprilike tako.

P.S. Ja nisam programer, niti mi je softverski inzenjering ikada bio core business. Kodiranje mi je sporedna stvar u poslu. Bavim se mrezama (IP/MPLS), a Python koristim samo za scripting / network automation ... za sta sam do sada koristio Perl, ponekad bash/awk ...

Koncept heš tabele je jednostavan. Da bi razumeo heš tabelu, odnosno Dictionary potrebno je prvo da razumeš nizove. Elementima niza pristupaš na osnovu indeksa. Takav pristup je direktan (brz) i vreme pristupa je konstantno. Na primer:



Ako imaš gomilu podataka kojima treba da pristupiš na osnovu ključa, a želiš da vreme pristupa ne zavisi od broja elemenata, onda koristiš heš tabelu. Heš tabela ima funkciju koja za svaki ključ generiše indeks i pod tim indeksom čuva vrednost u nizu. Ako ovo razumeš i ne planiraš da implementiraš svoju heš funkciju/tabelu mislim da za sada tu možeš da se zaustaviš i nastaviš da koristiš Dictionary.

(Stvari su malo komplikovanije od onoga što sam napisao. Kada bi imali beskonačno memorije radilo bi odlično, međutim pošto je to nemoguće, onda su neophodni neki kompromisi i zato je bitno pametno osmisliti strategiju heširanja i smeštanja podataka u slučaju da heš funkcija generiše isti indeks za različite ključeve...)

Mali test, da li je Dictionary (heš tabela) dobar izbor ako želimo da u okviru for petlje prođemo kroz sve unose i zašto?

Beri:"E tada postajes vec medior programer, koji uspesno koristi ono sto vec postoji i ne izmislja toplu vodu svaki put iznova i iznova. "

Ima i kategorija koja se zove skript kidi :P

Zurg, prvo hvala na konstruktivnom doprinosom u ovoj temi. Drugo, nisam pogrešio kada sam rekao da je kompleksnost pretrage hash tabele O(n). Pogledaj i sam link na wiki koji si ostavio
Doduše, ta kompleksnost je "worst case" scenario, ali ga je vrlo lako isprogramirati izborom lošeg hash algoritma i "štimovanjem" podataka da postigneš worst case.

Drugo, postavljaču teme predlažem da pokuša da piše FUNKCIONALNE SPECIFIKACIJE.
Ne zato da ga obeshrabrim, nego da ga usmerim na pravi put.

Funkcionalnu specifikaciju možeš da posmatraš, sa jedne strane, kao niz obećanja klijentu šta ćeš da uradiš, a sa druge strane, kada programiraš za svoju dušu, podsetnik šta treba da se uradi. To je okvirni plan rada. Kaže se: plan nije ništa, planiranje je sve. Kako drugačije da proceniš da li napreduješ, ako nisi zacrtao ciljeve koje želiš da postigneš?
Ja uvek imam običaj da pravim funkcionalnu specifikaciju za svaki program za koji mi je potrebno više od jednog dana da ga napišem.

Kako bi izgledala funkcionalna specifikacija za rečnik:

1. pretraga rečnika, za reč iz jezika J1 naći reči u jeziku J2.
2. obezbediti pretragu rečnika iz komandne linije
3. obezbediti grafički interfejs za pretragu rečnika (ovo može i kasnije)
4. unos nove odrednice
5. unos novog pevoda
6. postojanje više od dva jezika u rečniku (ako nije suviše teško)
7. snimanje izmena rečnika u fajl
8. korišćenje baze podataka za smeštanje reči

itd.

Onda kreneš da planiraš da uradiš one delove koji su ti lakši da prvo isprogramiraš, a one teže ostaviš za kraj.

U nekom trenutku, uporediš svoju funkcionalnu specifikaciju, ako treba izmeniš ili dodaš novu funkcionalnost i napraviš plan kako da tu funkcionalnost da uradiš.

Recimo, želim grafički interfejs, da li da interfejs napravim kao desktop aplikaciju, ili kao web aplikaciju? Podsetnik: proveri koje grafičke biblioteke mogu da iskoristim za desktop aplikaciju, a koje za web? Ako idem na web, šta mi je od dodatnog softvera potrebno da instaliram? Koliko vremena mi je potrebno da naučim da napravim jednostavnu desktop aplikaciju? Recimo da odredim dve nedelje, pa ako procenim posle nedelju dana da nije dovoljno, menjam plan...

Još neke napomene uz projekat rečnik:

Šta raditi u slučaju, recimo gramatičkih oblika koje imaju isti koren?
Na primer, play može biti imenica igra ili glagol u infinitivu igrati.
Ali play kao glagol može da se pojavi i u oblicima plays kada se koristi uz imenicu ili zamenicu trećeg lice jednine, ili u obliku playing.
Takođe, odrednice u srpskom mogu da budu i igram, igraš, igra, igramo, igrate igraju, igrajući, igrao, igralii i slično.

Šta raditi sa imenicama? Da li treba čuvati imenicu samo u nominativu jednine ili u svim padežima?
Da li treba čuvati rod imenice? U engleskom je to jednostavno, ali u srpskom i nemačkom nema strogog pravila...
Šta raditi sa rečima koje se isto pišu ortografski, ali imaju različito značenje. Na primer "da" može biti afirmacija "yes" ili predlog "to"
Da li ima smisla označavati neke reči kao sinonime ili antonime drugih reči (dakle veza između reči može biti između reči u istom jeziku, a ne samo između reči u različitim jezicima).

Dakle, ti si samo zagrebao vrh teme, a da nisi ozbiljno razmislio...

"Drugo, nisam pogrešio kada sam rekao da je kompleksnost pretrage hash tabele O(n)."

Jesi. Nemo sad da se vadis ;)

"Doduše, ta kompleksnost je "worst case" scenario,"

worst case svakako, ali to ti je i worst case za stablo.

Kako i stablo biva balanasirano, tako i hash funkcija ne mapira sve kljuceve na jedan broj,
tako da je to teorijski moguce, prakticno nemoguce.

Recimo, da je hash tabela realizovana kao niz od k ulaza a svaki ulaz je lista parova key value za key koji daje istu hash vrednost.
Tada je prosečna dužina liste za svaku hash vrednost n/k a prosečno vreme pretrage n/2k, što daje kompleksnost od O(n). Ne treba da se posebno trudiš da postigneš worst case.
Mogu da se naprave i bolji algoritmi za razrešenje kolizije, ali sve je to linearna ili nešto malo bolja kompleksnost...

Tacno, sa time da hash tabela raste kako se dodaju novi elementi tako da to n/k tezi jedinici. To je poenta hash tabele.

Evo prema Đokinom odličnom predlogu, pribeležih ono što mi je palo na pamet u vezi sa projektom rečnik.
Sigurno sam nešto zaboravio, pa dodajte ako imate ideju.

Englesko-srpski rečnik - specifikacija

A. Softver:
1. pretraživanje značenja prema unetoj reči (ili prvim slovima reči u desktop verziji - dropdaun lista)
2.1. preko konzole
2.1. kasnije napraviti desktop aplikaciju
2.2. još kasnije napraviti onlajn izdanje, gde bi korisnici mogli i sami da predlažu nove reči ili njihova značenja (crowdsourcing)
3. mogućnost unošenja novih reči za oba jezika i snimanje izmena
4. mogućnost popravljanja već unetih reči za oba jezika i snimanje izmena
5. mogućnost brisanja već unetih reči za oba jezika i snimanje izmena
6. veličina: do 100.000 reči u svakom od jezika.
7. operativni sistem: windows

B: Sadržaj:
1. Svaka engleska reč ima oznaku za vrstu (n = noun, v = verb, adj = adjective, pre = preposition itd.)
2. Na taj način se pravi razlika između onih koje imaju isti oblik:
play n. = 1. igra, zabava; 2. drama, pozorišna predstava
play v. = 1. igrati (se); 2. svirati; 3. glumiti
3. Različita polja značenja iste reči se odvajaju arapskim brojevima (vidi gornji primer).
4. Fraze u kojima se javlja neka reč idu na kraj značenja te reči i iza kose crte (/). Tako za play:
play v. = 1. igrati (se); 2. svirati; 3. glumiti / to bring into play = staviti u pogon, pokrenuti
5. Oblik imenica je uvek u prvom licu jednine (play, a ne plays)
6. Oblik glagola je uvek u infinitivu bez "to" (work, a ne working ili worked, sem naravno u frazama)

Đoko, priznaj lepo da nisi u pravu da ne smetamo čoveku dok uči.

Nego da ti odgovorim na ovo:
"Mali test, da li je Dictionary (heš tabela) dobar izbor ako želimo da u okviru for petlje prođemo kroz sve unose i zašto?"

Ukoliko zelimo sortiran prolaz nije, zato sto hash tabela za razliku od stabla nije sortirana. No u svakom drugom slucaju je hash tabela bolja od stabla.
Znaci uzmi najprostije recimo brojanje reci u nekom vecem tekstu i svako ce videti razliku O(1) hash tabela vs O(log n) stablo.

Evo ovde je dobro objašnjena ideja hash tabele.

To ko bibli uoteci knjige i katalog, pa ne tražiš knjigu redom na polici, već u katalogu vidiš njenu signaturu, tj, mesto u magacinu.
E sad vidim ima kao neke kolizije. To kao kad staviš knjigu na pogrešno mesto, pa kad na to isto mesto hoćeš posle da staviš pravu, cvrc, ne može. :)

"E sad vidim ima kao neke kolizije"

Kolizija je kada dva razlicita kljuca gadjaju isti slot u tabeli. To je ili zato sto hash funkcija nije savrsena ili zato sto ima vise kljuceva nego sto moze da stane.
U slucaju da je ovo drugo onda se poveca velicina i uradi rehashing posle nekog tresholda.
Inace hash tabela je obicno implementirana kao niz listi gde u liste idu kolizije.

Počeli smo da mešamo babe i žabe, pa ću napraviti novu temu za englesko-srpski rečnik, a ovde nastaviti da postavljam samo zadatke za ambiciozne početnike.

Evo ga novi, zadatak broj 14:

Napiši program koji će uporediti tri varijable: x, y, z
i ispisati najveći neparni broj među njima. Ako nijedna od varijabli nije
neparan broj, trebalo bi da ispiše odgovarajuću poruku.

Za pravljenje funkcije moguće koristiti jedino dve alatke:
1. if-elif-else petlju i
2. modulo, za proveru je li broj neparan.

Uživajte! :)

Zasto samo tri broja? Hajde da malo napravimo zadatak tezim. Neka to bude matrica N x M i da nadjes najveci neparan broj, ali da uz to ispises i koordinate (vrstu i kolonu) gde se taj broj nalazi.