From 236001ec7563804f87a40c924681461bc8b2d764 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Martin=20Mo=C5=BEina?= Date: Mon, 5 Dec 2016 11:51:58 +0100 Subject: Added a new set of exercises (regular expressions). --- .../problems/comprehensions/comprehensions_sl.html | 572 +++++++++++++++++++++ 1 file changed, 572 insertions(+) create mode 100644 python/problems/comprehensions/comprehensions_sl.html (limited to 'python/problems/comprehensions') diff --git a/python/problems/comprehensions/comprehensions_sl.html b/python/problems/comprehensions/comprehensions_sl.html new file mode 100644 index 0000000..4ebea98 --- /dev/null +++ b/python/problems/comprehensions/comprehensions_sl.html @@ -0,0 +1,572 @@ + + + + + + + + + + +

Matematiki si lahko privoščijo opisati množico dvakratnikov vseh naravnih + števil, katerih kvadrat je manjši od 120, takole: + \(S=\{\,2\cdot x\mid x \in \mathbb{N},\ x^2<120\,\}\). Mi tudi.

+ +

Seznami

+ +

Vendar pojdimo lepo počasi. Začnimo s tistim, kar najbolj poznamo: s seznami. + Doslej smo jih zapisali tako, da smo v oglatih oklepajih naštevali njihove + elemente,

+ +
k = [9, 16, 81, 25, 196]
+ +

Oglate oklepaje bomo uporabljali tudi poslej, le da znotraj njih ne bomo + našteli elementov, temveč napisali izraz, ki jih sestavi. Recimo, da bi + hotel seznam korenov števil iz gornjega seznama (po nekem čednem naključju + gornji seznam vsebuje ravno same kvadrate). Naredil bi tako:

+ +
>>> [sqrt(x) for x in k]
+[3.0, 4.0, 9.0, 5.0, 14.0]
+ +

Torej: napisal sem oglate oklepaje, kot vedno, kadar definiram seznam, a + namesto, da bi naštel elemente, sem povedal, kakšni naj bodo. Rekel sem, + naj bodo elementi mojega novega seznama koren iz x, pri čemer so + x elementi seznama k. Kaj pa, če bi hotel + namesto tega imeti kvadrate števil? Isti šmorn:

+ +
>>> [x**2 for x in k]
+[81, 256, 6561, 625, 38416]
+ +

Oblika tega, kar pišemo, je vedno + [izraz for spremenljivka in nekaj], +kjer je spremenljivka ime neke spremenljivke (npr. x, +izraz nek izraz, ki (običajno, ne pa čisto nujno) vsebuje to +spremenljivko (npr. sqrt(x) ali 2*x, nekaj +pa je nekaj, čez kar je možno spustiti zanko for, torej seznam, slovar, +množica, datoteka ali kaj, česar še ne poznamo, vendar bomo spoznali še danes. +

+ +

Imam seznam imen, recimo,

+
l = ["Ana", "Berta", "Cilka", "Dani", "Ema"]
+ +

Kako bi izračunal poprečno dolžino imena? Imam funkcijo sum, + ki zna sešteti števila v seznamu. Potrebujem torej le še seznam dolžin + (namesto seznama imen). Tega pač preprosto dobim: izračunati želim dolžino + niza ime za vsako ime v seznamu + imena.

+ +
>>> [len(ime) for ime in imena]
+[3, 5, 5, 4, 3]
+ +

Zdaj pa tole le še seštejem in delim z dolžino seznama.

+ +
>>> sum([len(ime) for ime in imena]) / len(imena)
+4.0
+ +

Poprečna dolžina imena ni nič posebej zanimivega. Računajmo raje poprečno +težo in, da nam ne bo dolgčas, jo bomo računali iz teh podatkov:

+ +
podatki = [
+    (74, "Anže", False),
+    (82, "Benjamin", False),
+    (58, "Cilka", True),
+    (66, "Dani", False),
+    (61, "Eva", True),
+    (84, "Franc", False),
+]
+ +

Takole nam je storiti: z zanko se zapeljemo čez podatke, izračunamo vsoto +prvih elementov in jo delimo z dolžino seznama.

+ +

Lepo prosim, ne tako:

+ +
vsota = 0
+for i in range(len(podatki)):
+    vsota += podatki[i][0]
+print(vsota / len(podatki))
+ +

Tole je že boljše:

+ +
vsota = 0
+for podatek in podatki:
+    vsota += podatek[0]
+print(vsota / len(podatki))
+ +

In še malo bolje:

+ +
vsota = 0
+for teza, ime, zenska in podatki:
+    vsota += teza
+print(vsota / len(podatki))
+ +

Zdaj pa naredimo tako, kot smo se naučili danes. Naredimo lahko + +

vsota = sum([podatek[0] for podatek in podatki])
+ +

ali, po zadnji različici

+ +
vsota = sum([teza for teza, ime, zenska in podatki])
+ +

Pri izpeljevanju seznamov lahko dodamo še pogoj, s katerim izbiramo +elemente, ki naj se dodajo.

+ +

Kako bi sestavili seznam kvadratov vseh lihih +števil do 100? Seznam kvadratov vseh števil do 100 je trivialen, napisati +nam je treba le:

+ +
s = [x**2 for x in range(100)]
+ +

Če želimo pobrati samo liha števila, lahko v izpeljavo seznama dodamo še +pogoj.

+ +
s = [x**2 for x in range(100) if x % 2 == 1]
+ +

Tole pravzaprav ni čisto potrebno, lahko bi rekli preprosto

+ +
s = [x**2 for x in range(1, 100, 2)]
+ +

Kaj pa, če bi hoteli seznam kvadratov vseh števil do 100, ki niso deljiva s + 7 in ne vsebujejo števke 7?

+ +
[x**2 for x in range(100) if (x % 7 != 0) and ("7" not in str(x))]
+ +

V pogoju smo zaradi preglednosti uporabili oklepaje, čeprav sicer niso +potrebni). Prvi del poskrbi, da število ni deljivo s 7 (ostanek po deljenju s +7 mora biti različni od 0). Drugi del poskrbi, da število ne vsebuje števke 7: +število preprosto pretvorimo v niz in preverimo, da ne vsebuje sedemke.

+ +

Kako bi izračunali vsoto tež moških v gornjem seznamu? Za zanko dodamo +pogoj. Za začetek sestavimo le seznam imen vseh moških.

+ +
[ime for teza, ime, zenska in podatki if not zenska]
+ +

V definicijo našega seznama lepo na konec, za for, dodamo še +if in pogoj, ki mu mora zadoščati element, da nas zanima.

+ +

Z vsoto je podobno.

+ +
vsota = sum([teza for teza, ime, zenska in podatki if not zenska])
+ +

Zdaj veste, zakaj sem tako utrujal, da ne uporabljajte +for i in range(len(s)): zato, ker z njim namesto lepega, kratkega +preglednega [ime for teza, ime, zenska in podatki if not zenska] +dobimo +[podatki[i][1] for i in range(len(podatki)) if not podatki[i][2]]. +Seveda lahko delate tudi na ta, drugi način. Svobodni ljudje ste in noben zakon +ne prepoveduje mazohizma.

+ +

Sestavimo seznam vseh deliteljev danega števila n. Vzemimo, + recimo n = 60. Seznam deliteljev je tedaj seznam vseh + x, pri čemer x prihaja z intervala + 1 ≤ x ≤ n, za katere velja, da je ostanek po deljenju + n z x enak 0 (torej x deli + n).

+ +
def delitelji(n):
+    return [x for x in range(1, n+1) if n % x == 0]
+ +

Zdaj lahko hitro ugotovimo, ali je dano število popolno: popolna +števila so (se še spomnimo?) števila, ki so enaka vsoti svojih +deliteljev (brez sebe samega). + +

def popolno(n):
+    return n == sum(delitelji(n))
+

+ +

Še bolj imenitna števila so praštevila, števila brez deliteljev. Se pravi + tista, pri katerih je seznam deliteljev med 2 in tem številom prazen.

+ +
def prastevilo(n):
+    return not delitelji(n)
+ +

Če funkcije delitelji še ne bi imeli - nič hudega. Ali je + število praštevilo, bi še vedno dognali v eni sami vrstici.

+ +
def prastevilo(n):
+    return not [x for x in range(2, n) if n % x == 0])
+ +

S to funkcijo hitro sestavimo seznam vseh praštevil med 2 in 100:

+ +
>>> [n for n in range(2, 101) if prastevilo(n)]
+[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
+ +

Znamo pa, jasno, tudi brez funkcije; tisto, kar dela funkcija, pač kar +prepišemo v pogoj.

+ +
>>> [n for n in range(2, 101) if not [x for x in range(2, n) if n % x == 0])]
+[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
+ +

Takšnih reči sicer raje ne pišemo, saj hitro postanejo nepregledne.

+ +

Kdor je gledal stare naloge, je opazil nalogo z vislicami. V eni od nalog + je bilo potrebno napisati funkcijo pokazi_crke(beseda, crka), + ki kot argument dobi besedo in množico črk, vrniti pa mora besedo, v kateri + so "vidne" vse črke, ki so v množici, tiste, ki jih ni, pa je potrebno + zamenjati s piko. Tako mora, recimo, + pokazi_crke("BESEDA", {"E", "D"}) vrniti .E.ED.. +

+ +

Nalogo rešimo lepo po korakih. Vzemimo neko množico črk in neko besedo.

+ +
>>> crke = {"E", "D"}
+>>> beseda = "BESEDA"
+ +

Zdaj razsekajmo besedo na črke.

+ +
>>> [b for b in beseda]
+['B', 'E', 'S', 'E', 'D', 'A']
+ +

Zdaj pa naj seznam vsebuje b le, če je b v množici + crke, sicer pa piko.

+ +
>>> [b if b in crke else "." for b in beseda]
+['.', 'E', '.', 'E', 'D', '.']
+ +

Da združimo črke v niz, potrebujemo le še večno zeleni join.

+ +
>>> "".join([b if b in crke else "." for b in beseda])
+'.E.ED.'
+ +

Celotna rešitev naloge je torej

+ +
def pokazi_crke(beseda, crke):
+    print "".join((c if c in crke else ".") for c in beseda)
+
+ +

V splošnem: vsak kos kode, ki izgleda takole

+ +
r = []
+for e in s:
+    if pogoj(e):
+        r.append(funkcija(e))
+ +

lahko prepišemo v

+ +
r = [funkcija(e) for e in s if pogoj(e)]
+ +

Kdor želi še kakšen primer, si bo ogledal + rešitev + kronogramov in + napadalnih kraljic. +

+ +

Množice

+ +

Množice sestavljamo natančno tako kot sezname, le da namesto oglatih + oklepajev uporabimo zavite. Takole dobimo vse delitelje 60

+ +
>>> {i for i in range(1, 61) if 60 % i == 0}
+{1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 60, 30}
+ + +

Slovarji

+ +

Ista reč. Če hočemo narediti slovar, ki bo kot ključe vseboval števila do + 10, kot vrednosti pa njihove kvadrate, napišemo

+ +
{i: i**2 for i in range(11)}
+ +

Generatorji

+ +

Tule bi pričakovali nekaj drugega: terke. Lahko tako kot sezname, množice in + slovarje naredimo tudi terke in nize? Ne. Na takšen način določeni nizi + očitno ne bi imeli nobenega smisla, pa tudi terke ne bi bile preveč + uporabne. Pač pa nas čaka - in bo pogosto v okroglih oklepajih - še nekaj + bolj nenavadnega in imenitnejšega: generatorji.

+ +
>>> g = (x**2 for x in range(10))
+ +

Tale g, kot se hitro prepričamo, ni terka, temveč nekaj + drugega.

+ +
>>> g
+ at 0x667bc0>
+ +

Kaj je generator, čemu služi in kako ga uporabljamo? Na prvi dve vprašanji + lahko odgovorimo naenkrat: generator je nekaj, kar generira objekte. + Vsakič, ko bomo od njega zahtevali nov objekt, bo vrnil novo število - + najprej 0, potem 1, potem 4, potem 9 ... pač kvadrate naravnih števil do + 10. Na tretje vprašanje, kako ga uporabljamo, nam skoraj ni potrebno + odgovarjati, saj generatorje (in njim podobne reči) že dolgo uporabljamo. + Generatorje najpreprosteje uporabimo z zanko for. Še več, zanka for deluje + na tistih rečeh - in samo tistih rečeh - ki se znajo obnašati kot + generatorji (torej: v resnici so generatorji ali pa podpirajo osnovne + funkcije generatorjev).

+ +
>>> for i in g:
+...     print(i, end=" ")
+...
+0 1 4 9 16 25 36 49 64 81
+ +

Če poskusimo ponoviti, ne gre: generator je že "iztrošen". Kar je imel + zgenerirati, je zgeneriral.

+ +
>>> for i in g:
+...     print(i, end=" ")
+...
+>>>
+ +

Generator je torej videti kot izpeljani seznam, le da namesto oglatih + oklepajev uporabimo okrogle. Kadar ga pošljemo kot edini argument funkciji, + smemo oklepaje celo izpustiti. Napišimo funkcijo, ki kot argument dobi + seznam števil in vrne prvo število, ki je večje od 50.

+ +
def nad50(s):
+    for e in s:
+        if e > 50:
+            return e
+ +

Preskusimo jo, trikrat:

+ +
>>> nad50([5, 1, 40, 1, 82, 12, 6])
+82
+>>> nad50([x**2 for x in range(10)])
+64
+>>> nad50(x**2 for x in range(10))
+64
+ +

V prvem primeru je dobila najobičajnejši seznam. Tako smo si predstavljali, + ko smo jo pisali. V drugem primeru smo ji dali seznam kvadratov števil do + 10 in vrnila je prvi kvadrat, ki je večji od 50. V tretjem klicu pa ji + sploh nismo dali seznama, temveč generator, ki je dajal kvadrate - + natančno isto reč kot gornji g. Funkcija je čez generator + pognala zanko for natančno tako, kot jo sicer poganja čez + sezname.

+ +

V čem je prednost generatorjev pred seznami? V tem, da ne sestavijo seznama. + Če želimo izračunati vsoto kvadratov prvih stotih števil in za to uporabimo + generator, na ta način ne sestavimo seznama teh števil (kot bi ga, če bi + rekli sum([x**2 for x in range(100)]), temveč števila, namreč + kvadrate, generiramo sproti (tako, da pokličemo + sum([x**2 for x in range(100)]). Hm, pa to v resnici deluje? + No, seveda. Funkcija sum bi lahko bila napisana takole

+ + 
def sum(s):
+     vsota = 0
+     for e in s:
+         vsota += e
+     return vsota
+ +

Zanka for lahko gre prek generatorja (in v resnici vedno gre prek + generatorja), torej ona reč deluje.

+ +

Že, že, poreče pozornejši študent: kaj pa range(100)? Mar ta + ne sestavi seznama stotih števil? Smo res kaj dosti pridobili - namesto + seznama kvadratov števil do 100 imamo pač števila do 100 - je to res tak + napredek? Tu lahko študenta pohvalimo za budnost, vendar se moti.

+ + 
>>> range(100)
+ range(0, 100)
+ +

V resnici range ne sestavi seznama, temveč generator. Res se + nam ni predstavil kot kak "generator object" temveč kot "range(0, 100)", + vendar v resnici ni ničesar sestavil. Nobenega seznama s stotimi števili + ni. Kako vem? Preprosto:

+ + 
>>> range(1000000000000)
+ range(0, 1000000000000)
+ +

Če bi range sestavljal sezname, bi bil to seznam z bilijon + elementi. Če bi vsak od njih zavzel samo en bajt (pa jih v resnici najbrž + vsaj 20, verjetneje pa 32), bi shranjevanje takšnega seznama zahtevalo + pomnilnik velik en terabajt.

+ +

Tako smo torej generatorje uporabljali že, odkar vemo za range. + (Morda se kdo spomni, da sem vam takrat, na onem davnem predavanju, ko sem + povedal za funkcijo range, le-to pokazal na Pythonu 2.7? Tako + je bilo lažje, saj je takrat še vračal sezname. To je ena od sprememb od + različice 3.0 naprej: po novem vrača generatorji.)

+ +

Podobno je s slovarji: metode __keys__, __values__ + in __items__ vračajo generatorje, ne seznamov.

+ +

Funkcije, ki generirajo

+ +

Še nekoliko naprednejša snov: Bi znali napisati generator Fibonaccijevih + števil, tako kot smo napisali generator kvadratov? Da, vendar bo + preprostejša nekoliko drugačna pot. Napisali bomo funkcijo, ki ne vrača le + enega rezultata temveč "generira" rezultate. Torej, nekaj takšnega:

+ +
def fibonacci(n):
+    a = b = 1
+    for i in range(n):
+        return a    # Tole ne deluje!
+        a, b = b, a+b
+ +

Tale funkcija ne deluje, napisali smo jo le, da ilustriramo idejo: radi bi + naredili zanko. Ko funkcijo prvič pokličemo, bi return vrnil + prvo Fibonaccijevo število. Ko jo pokličemo naslednjič, se funkcija ne bi + izvajala od začetka, temveč od tam, kjer smo nazadnje vrnili rezultat, se + pravi z vrstico, ki sledi returnu. No, v resnici naredimo + natanko tako, le namesto returna moramo uporabiti + yield:

+ +
def fibonacci(n):
+    a = b = 1
+    for i in range(n):
+        yield a
+        a, b = b, a+b
+ +

Preskusimo.

+ +
>>> for i in fibonacci(5):
+...    print(i)
+1
+1
+2
+3
+5
+ +

Napišemo lahko celo funkcijo, ki vrne (no, generira) vsa + Fibonaccijeva števila.

+ +
def fibonacci():
+    a = b = 1
+    while True:
+        yield a
+        a, b = b, a+b
+ +

Neskončno zanko, while True, smo že videli, vendar je bil v + njej vedno break, ki jo je nekoč prekinil. Kdo pa prekine to + zanko? Če nismo previdni, nihče. Če rečemo

+ +
>>> for i in fibonacci():
+...    print(i)
+ +

bo program izpisoval v nedogled. Pač pa lahko poiščemo, recimo, prvo + Fibonaccijevo število, ki je večje od 50.

+ +
>>> for i in fibonacci():
+...    if i > 50:
+...        print(i)
+...        break
+55
+ +

Ali pa, ah, saj imamo za to že funkcijo, nad50. Naj kar ta +pove, katero je prvo Fibonaccijevo število večje od 50!

+ +
>>> nad50(fibonacci())
+55
+ +

V zvezi z vsemi temi rečmi bi bilo mogoče povedati še zelo veliko. Tole je + ena najbolj kul tem v Pythonu. Pravzaprav treba priznati, da to niti ni + tema iz Pythona. V ozadju tega, kar počnemo tule, je poseben slog + programiranja, + funkcijsko + programiranje. Python ga omogoča in med "normalnimi" jeziki je za + takšen slog pravzaprav eden boljših. Obstajajo pa jeziki, ki so posebej + narejeni za takšno programiranje. Če je bilo komu tole, kar smo počeli + doslej, všeč naj si nujno ogleda kak + SML ali + + Haskell, morda pa ga bo zabaval tudi + + Racket (dialekt Lispa).

+ +

V Pythonu pa si bo ta, ki so mu bile te reči všeč, dobro ogledal module +functools, +iterools in +operator.

+ +

Generator deliteljev

+ +

Še en zanimiv primer je generator, ki vrne vse delitelje podanega števila. +

+ +
def delitelji(n):
+    for i in range(1, n + 1):
+        if n % i == 0:
+            yield i
+ +

Opazimo lahko, da z enim deliteljem dobimo dva: če je i delitelj +n-ja, je tudi n // i delitelj n-ja. +Če je tako, zadošča, da gremo do korena iz n in vrnemo po dva +delitelja.

+ +
from math import sqrt
+
+def delitelji(n):
+    for i in range(1, int(sqrt(n) + 1)):
+        if n % i == 0:
+            yield i
+            yield n // i
+ +

Koren iz n moramo spremeniti v celo število, ker range +ne mara necelih.

+ +

Pazite, tole sta dva yielda. Funkcija se izvaja tako, ad vrne +najprej eno število, in ko zahtevamo naslednje, se izvede naslednji +yield.

+ +

Funkcija je zdaj bistveno hitrejša (pri velikih številih bi se to utegnilo +kar poznati - namesto, da gre do milijona, bo šla le do 1000. Vendar žal ne +dela pravilno. Če je n, recimo, 25, bo funkcija +dvakrat vrnila 5. A tega se znamo hitro znebiti.

+ +
from math import sqrt
+
+def delitelji(n):
+    for i in range(1, int(sqrt(n) + 1)):
+        if n % i == 0:
+            yield i
+            if i ** 2 != n:
+                yield n // i
+ +

Zdaj nas morda moti le še to, da števila ne prihajajo v pravem vrstnem redu. +Kot delitelje 42 bi namesto 1, 2, 3, 6, 7, 14, 21, 42 dobili 1, 42, 2, 21, 3, +14, 6, 7. To lahko popravimo tako, da n // i ne vračamo sproti, +temveč jih le shranjujemo in jih vračamo kasneje.

+ +
from math import sqrt
+
+def delitelji(n):
+    for i in range(1, int(sqrt(n) + 1)):
+        if n % i == 0:
+            yield i
+            if i ** 2 != n:
+                ostali.append(n // i)
+    for e in ostali:
+        yield e
+ +

Nismo še čisto zmagali. Zdaj imamo 1, 2, 3, 6, 41, 21, 14, 7 - prva polovica +je iz prvega yielda, druga (od 41 naprej) iz drugega. Te, druge, +vrača v enakem vrstnem redu, v katerem jih je vstavljal v seznam, saj +append pač vstavlja na konec.

+ +

Pa vstavljajmo raje na začetek! Uporabimo insert.

+ +
from math import sqrt
+
+def delitelji(n):
+    for i in range(1, int(sqrt(n) + 1)):
+        if n % i == 0:
+            yield i
+            if i ** 2 != n:
+                ostali.insert(0, n // i)
+    for e in ostali:
+        yield e
+ +

Žal se je insertu modro izogibati. Za to, da vstavi element +na prvo mesto, mora enega za drugim premakniti vse ostale. V teoriji (ki se jo +boste učili drugo leto) je ta program enako počasen kot bi bil, če bi prvo +zanko spustili prek range(1, n + 1). S tem, ko smo zamenjali +append z insert, smo, vsaj v teoriji, zapravili ves +prihranek.

+ +

To je preprosto urediti. Vstavljali bomo na konec, z append. +Pač pa bomo seznam nato prehodili v obratnem vrstnem redu. To se da narediti +z indeksiranjem (for i in range(-1, -n - n, -1): yield ostali[i], +vendar si bomo raje pomagali s priročno funkcijo reversed, ki +obrne seznam.

+ +
def delitelji(n):
+    ostali = []
+    for i in range(1, int(sqrt(n)) + 1):
+        if n % i == 0:
+            yield i
+            if i ** 2 != n:
+                ostali.append(n // i)
+    for e in reversed(ostali):
+        yield e
+ + -- cgit v1.2.1