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 povpreč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 povpreč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