From 236001ec7563804f87a40c924681461bc8b2d764 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Martin=20Mo=C5=BEina?= 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. 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, 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: 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
+ Oblika tega, kar pišemo, je vedno
+ Imam seznam imen, recimo, Kako bi izračunal poprečno dolžino imena? Imam funkcijo Zdaj pa tole le še seštejem in delim z dolžino seznama. 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: 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: Tole je že boljše: In še malo bolje: Zdaj pa naredimo tako, kot smo se naučili danes. Naredimo lahko
+
+ ali, po zadnji različici 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: Če želimo pobrati samo liha števila, lahko v izpeljavo seznama dodamo še
+pogoj. Tole pravzaprav ni čisto potrebno, lahko bi rekli preprosto Kaj pa, če bi hoteli seznam kvadratov vseh števil do 100, ki niso deljiva s
+ 7 in ne vsebujejo števke 7? 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. V definicijo našega seznama lepo na konec, za Z vsoto je podobno. Zdaj veste, zakaj sem tako utrujal, da ne uporabljajte
+ Sestavimo seznam vseh deliteljev danega števila 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).
+
+Seznami
+
+k = [9, 16, 81, 25, 196]
+
+>>> [sqrt(x) for x in k]
+[3.0, 4.0, 9.0, 5.0, 14.0]
+
+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]
+
+[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.
+l = ["Ana", "Berta", "Cilka", "Dani", "Ema"]
+
+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]
+
+>>> sum([len(ime) for ime in imena]) / len(imena)
+4.0
+
+podatki = [
+ (74, "Anže", False),
+ (82, "Benjamin", False),
+ (58, "Cilka", True),
+ (66, "Dani", False),
+ (61, "Eva", True),
+ (84, "Franc", False),
+]
+
+vsota = 0
+for i in range(len(podatki)):
+ vsota += podatki[i][0]
+print(vsota / len(podatki))
+
+vsota = 0
+for podatek in podatki:
+ vsota += podatek[0]
+print(vsota / len(podatki))
+
+vsota = 0
+for teza, ime, zenska in podatki:
+ vsota += teza
+print(vsota / len(podatki))
+
+vsota = sum([podatek[0] for podatek in podatki])
+
+vsota = sum([teza for teza, ime, zenska in podatki])
+
+s = [x**2 for x in range(100)]
+
+s = [x**2 for x in range(100) if x % 2 == 1]
+
+s = [x**2 for x in range(1, 100, 2)]
+
+[x**2 for x in range(100) if (x % 7 != 0) and ("7" not in str(x))]
+
+[ime for teza, ime, zenska in podatki if not zenska]
+
+for
, dodamo še
+if
in pogoj, ki mu mora zadoščati element, da nas zanima.vsota = sum([teza for teza, ime, zenska in podatki if not zenska])
+
+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.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]
+
+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 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}+ + +
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)}+ +
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.
Š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 return
u. No, v resnici naredimo
+ natanko tako, le namesto return
a 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.
+ +Š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 yield
a. 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 yield
a, 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 insert
u 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