Generatorji

Generatorski izrazi

Generatorje načelno poznamo. Sintaktično so podobni izpeljanim seznamom in množicam - oziroma, še bolj, neobstoječim izpeljanim terkam. Tole je generator, ki generira (= sproti sestavlja!) kvadrate števil do 10

kvadrati = (x ** 2 for x in range(5))

in tole je generator, ki generira (vsa) praštevila

from itertools import count

prastevila = (x for x in count(2) if all(x % k != 0 for k in range(2, x)))

Pognati ga je seveda potrebno previdno, saj sam od sebe nikoli ne bo jenjal generirati.

for p in prastevila:
    if p > 20:
        break
    print(p)
2
3
5
7
11
13
17
19

Mimogrede se spomnimo še, kaj generator pravzaprav počne: generira nov element vsakič, ko pokličemo next.

prastevila = (x for x in count(2) if all(x % k != 0 for k in range(2, x)))
next(prastevila)
2
next(prastevila)
3
next(prastevila)
5

Kaj pa počne generator med dvema klicema next? Neumno vprašanje. Kaj počne... nič. Pač, vsakič, ko pokličemo next vzame naslednjo vrednost, ki jo vrne zanke ter jo kvadrira in jo vrne. Oziroma preveri, ali je praštevilo, in če ni, vzame naslednjo in naslednjo, dokler ne naleti na praštevilo. Tega vrne in to je to. Ob naslednjem next-u pa naprej. Pri tem seveda na nek način shranjuje "stanje" - zanka for, ki se skriva v generatorju, ve, do kod je prišla. (To sem napisal nekoliko poenostavljeno; v resnici je (še) preprosteje.)

Seznam rekordov

Omejitev takšnega generatorja je, da ga smejo sestavljati le izraz, zanka in pogoj. Edino "stanje", ki ga vzdržuje generator, je stanje zanke. Težko si beleži, kaj se je dogajalo v preteklosti, vedno vidi le trenutni korak. Kako omejujoče je to, uvidimo, če poskusimo sestaviti generator rekordi, ki za podani seznam (terko, datoteko, ...) vrača zaporedne rekorde: za vsak element preverimo, ali je večji od elementov, ki smo jih generirali doslej - za kar seveda zadošča preveriti, da je večji od zadnjega generiranega elementa. Če imamo seznam

s = [3, 5, 8, 4, 2, 8, 3, 10, 11, 5, 13, 4]

mora generator rekordi(s) izgenerirati 3, 5, 8, 10, 11, 13.

def rekordi(s):
    r = []
    for x in s:
        if not r or x > r[-1]:
            r.append(x)
    return r
rekordi(s)
[3, 5, 8, 10, 11, 13]

Da nam bo kasneje lažje razmišljati, rešimo še malo drugače: izognimo se škiljenju v r, temveč vanj le dodajamo, zadnji element pa shranjujmo ločeno.

def rekordi(s):
    prejsnji = None
    r = []
    for x in s:
        if prejsnji is None or x > prejsnji:
            r.append(x)
            prejsnji = x
    return r
rekordi(s)
[3, 5, 8, 10, 11, 13]

Funkcija, ki vrne generator

Z gornjo funkcijo ni nič narobe, dokler so seznami kratki in nas ne moti, da so shranjeni v pomnilniku. In dokler je argument, s v resnici seznam in ne generator, ki elemente vrača, kadar pridejo (na primer po omrežni povezavi, ali pa jih sproti vnaša uporabnik) in bi jih radi tudi generirali sproti.

Zanka v gornji funkciji ni "čista" (v smislu, v kateri so nekatere funkcije čiste funkcije, pure function): poleg tega, da preverja nek pogoj in dodaja v seznam, tudi spreminja vrednost prejsnji. V generatorskih izrazih vsak x pričakata enak pogoj in enak izraz - če je x enak 13, ga generator, ki sestavlja praštevila bodisi sprejme bodisi zavrne, ne glede na to, kaj se je dogajalo pred njim. Pythonovi generatorski izrazi sicer ne zahtevajo čistoče -- posebej walrus jo zlahka povozi --, jo pa ljubijo. Z nekaj zvijanja rok lahko stlačimo rekordi v generatorski izraz, vendar bo grd.

Rešitev bomo našli v generatorskih funkcijah. A preden jih napišemo zares, se vrnimo k začetnima generatorjema. Zgoraj smo pisali

kvadrati = (x ** 2 for x in range(5))

Če bi človek pogosto potreboval generatorje kvadratov (dasiravno si ne predsavljam, kakšen človek bi to mogel biti), bi si morda pripravil kar funkcijo, ki mu vrne takšen generator.

def f_kvadrati():
    return  (x ** 2 for x in range(5))

Še več, dotični bi nemara potreboval različno dolge sezname kvadratov in bi funkciji dodal še argument.

def f_kvadrati(n):
    return (x ** 2 for x in range(n))

Da to uporabi, mora poklicati funkcijo. Če je poprej pisal

for x in kvadrati:
    print(x)
0
1
4
9
16

Bo zdaj pač poklical funkcijo

for x in f_kvadrati(5):
    print(x)
0
1
4
9
16

Ali, če bo ravno hotel

kvadrati = f_kvadrati(5)
for x in kvadrati:
    print(x)
0
1
4
9
16

Podobno bi lahko sestavil funkcijo, ki vrne generator praštevil in jih, spet, če bi hotel, omejil.

def f_prastevila(n):
    return (x for x in range(2, n) if all(x % k != 0 for k in range(2, x)))
for p in f_prastevila(10):
    print(p)
2
3
5
7

Generatorske funkcija

Funkciji, ki vrača generator, rečemo generatorska funkcija. Ne brez razloga: vračati generator ni kar tako, kot vračati, recimo, terko, pa da bi potem takšnim funkcijam rekli "terčne funkcije", onim, ki vračajo slovarje, pa slovarske. Ne, ne, generatorske funkcije so čisto posebna vrsta funkcij. Imajo jih mnogi spodobni jeziki (pa tudi nekateri drugi).

Gornji generatorski funkciji sta vrnili generator, ki sta ga sestavili z generatorskim izrazom. V Pythonu, Javascriptu, C# (pa tudi v Php) bo funkcija vrnila generator, če namesto return-a vrača rezultat(e) z yield. Spodnji funkciji sta ekvivalentni gornjim:

def f_kvadrati(n):
    for x in range(n):
        yield x ** 2

def f_prastevila(n):
    for x in range(2, n):
        if all(x % k != 0 for k in range(2, x)):
            yield x

Detajli sledijo spodaj, ne skrbi. Za zdaj se le prepričajmo, da funkciji res vrneta generator:

prastevila = f_prastevila(10)
prastevila
<generator object f_prastevila at 0x106317010>
for x in prastevila:
    print(x)
2
3
5
7

In, da bomo še bolj prepričani, poskusimo počasi, ročno:

prastevila = f_prastevila(10)
next(prastevila)
2
next(prastevila)
3
next(prastevila)
5

Za podrobnejši uvid, napišimo še en, še preprostejši generator.

def endvatri():
    print("Pa začnimo!")
    yield 1
    print("Pa nadaljujmo.")
    yield 2
    print("Še malo, pa bo konec!")
    yield 3
    print("Pa smo končali.")

Pokličimo funkcijo, pridobimo generator.

g = endvatri()

Tole je pomembna opazka: nič se ni zgodilo. Nič od kode, ki je zapisana v funkciji, se ni izvedlo. Klic funkcije je zgolj vrnil generator.

Pokličimo next.

next(g)
Pa začnimo!
1

Zdaj se je koda generatorja začne izvajati: izvedel se je print, yield pa je vrnil vrednost - podobno, kot bi jo return. Generator tu vrne vrednost in s tem se njegovo izvajanje seveda ustavi.

Nadaljevalo se bo z novim klicem next.

next(g)
Pa nadaljujmo.
2

Potem se reč spet ustavi in nadaljuje ob naslednjem next.

next(g)
Še malo, pa bo konec!
3

Ob naslednjem next se izvede print, nove vrednosti pa ni in generator to sporoči tako, da sproži izjemo StopIteration.

next(g)
Pa smo končali.
---------------------------------------------------------------------------
StopIteration                             Traceback (most recent call last)
Cell In[34], line 1
----> 1 next(g)

StopIteration: 

Spomnimo se, kako sta videti naša generatorja kvadratov in praštevil:

def f_kvadrati(n):
    for x in range(n):
        yield x ** 2

def f_prastevila(n):
    for x in range(2, n):
        if all(x % k != 0 for k in range(2, x)):
            yield x

Isto, samo da je yield v zanki namesto na prostem.

yield je seveda podoben return-u. Naivna - in skoraj pravilna - razlaga yield-a je, da "zamrzne" izvajanje funkcije, in da se bo izvajanje ob "naslednjem klicu funkcije" nadaljevalo od yield-a naprej. Zgolj skoraj pravilna je zato, ker ne gre za klice funkcije: funkcijo smo poklicali le v začetku in vrnila je generator. Gre torej za "klice" generatorja, prek next.

Generator rekordov

V čem je prednost generatorskih funkcij pred generatorskimi izrazi? Mar nismo kar vzdihovali od sreče in navdušenja, ko smo odkrili, da lahko namesto

t = []
for x in s:
    if x % 2 == 0:
        t.append(x)

pišemo

t = [x for x in s if x % 2 == 0]

Nismo zdaj naredili ravno koraka v nasprotno smer, ko namesto enega samega generatorskega izraza, (x ** 2 for x in range(n)) pišemo celo funkcijo, v več vrsticah, z zanko?

Ne nujno. Saj vemo: ne da se vsega v eni vrstici. Generatorske funkcije nam bodo rešile problem s stanjem pri rekordih.

Funkcija, ki smo si jo napisali za prepoznavanje rekordov, je bila takšna:

def rekordi(s):
    prejsnji = None
    r = []
    for x in s:
        if prejsnji is None or x > prejsnji:
            r.append(x)
            prejsnji = x
    return r

Tole pa je generatorska funkcija:

def rekordi(s):
    prejsnji = None
    for x in s:
        if prejsnji is None or x > prejsnji:
            yield x
            prejsnji = x
r = rekordi(s)
next(r)
3
next(r)
5
next(r)
8
next(r)
10

Vrednost prejsnji, ki je prej nismo mogli stlačiti v eno vrstico, je brez težav našla mesto v generatorski funkciji.

Ne spreglejte: tale rekordi še ni generator: rekordi je generatorska funkcija, ki jo moramo poklicati in njen rezultat, r je generator.

Terminološka zagata

Obstajajo generatorji in iteratorji. Tule uporabljamo le prvi izraz, drugemu pa se izogibam, ker bi potem moral razložiti razliko. Za to pa bi morali zariniti še globlje in pokazati, kako definirati razred, ki se vede kot generator ali kot iterator (ali kot oboje).

Še dva primera

Navrzimo še dva primera.

Generator unikati bo vsako vrednost izgeneriral le enkrat, ponovitve pa preskočil.

def unikati(s):
    past = set()
    for x in s:
        if x not in past:
            yield x
            past.add(x)
s
[3, 5, 8, 4, 2, 8, 3, 10, 11, 5, 13, 4]
list(unikati(s))
[3, 5, 8, 4, 2, 10, 11, 13]

Manjša, s temo nepovezana, a pomembna pripomba: tole deluje le, če s vrača stvari, ki jih je mogoče zlagati v množico. Če bi bil med njimi kakšen seznam ... Ne bo šlo.

Še en generator iz obveznega programa: Fibonačijeva števila (ker vedno pozabim, s koliko c-ji se piše Fibonac(c)i, sem se ga odločil pisati kar po domače).

def fibonači():
    a = b = 1
    while True:
        yield a
        a, b = b, a + b

To je to.

for x in fibonači():
    if x > 20:
        break
    print(x)
1
1
2
3
5
8
13