Računalništvo

Iteratorji

Iteratorje uporabljamo že vseskozi, ne da bi se tega sploh zavedali. Videli smo, da se lahko z zanko for "sprehodimo" preko seznama, niza, množice, slovarja, datoteke itn. Zgled:

>>> sadje = {'banana', 'sliva', 'hruška', 'jabolko', 'lubenica'}
>>> for s in sadje:
...     print(s)
... 
banana
lubenica
hruška
jabolko
sliva

Gotovo si mislite: "O, kako pametna je zanka for! Ona se lahko sprehodi po elementih katerekoli podatkovne strukture. Obvlada sezname, nize, slovarje, range in še in še." Kar zna zanka for, lahko počnemo tudi sami "na roke". Množica ima namreč metodo__iter__, ki vrne iterator. ("Sprehajanju" po podatkovni strukturi programerji pravijo iteriranje.)

>>> it = sadje.__iter__()
>>> it
<set_iterator object at 0x7fe996242c18>

Na množici sadje smo poklicali metodo __iter__ in dobili objekt razreda set_iterator. Na temu objektu - iteratorju - pa lahko kličemo metodo __next__:

>>> it.__next__()
'banana'
>>> it.__next__()
'lubenica'
>>> it.__next__()
'hruška'
>>> it.__next__()
'jabolko'
>>> it.__next__()
'sliva'
>>> it.__next__()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

Ko se iterator "izrabi", sproži izjemo StopIteration. V resnici ne gre za pravo napako, ampak za signal, da se je iterator izrabil. Zgornjo zanko for lahko ekvivalentno zapišemo z zanko while, takole:

it = sadje.__iter__()
while True:
    try:
        s = it.__next__()
    except StopIteration:
        break
    print(s)

Vidite? Ta koda naredi natanko isto, kot zgornja zanka for. Dognali smo, da zanka for ni nič posebej "pametna", saj počne natanko isto kot zgornja zanka while, le zapis z zanko for je bolj preprost. Vsaka podatkovna struktura je sama zase pametna, tj. sama pri sebi ve, kako se po njej iterira.

Nihče pri zdravi pameti ne bi namesto zanke for uporabljal zgornji (ekvivalentni) zapis z zanko while. Zanka for namreč namerno skrije tehnične podrobnosti, da lahko programer vso svojo pozornost posveti reševanju problema. Tudi vozniki avtobusa ne premišljujejo o tem, kaj se dogaja v notranjosti motorja, ko pritisnejo stopalko za plin. Svojo pozornost (upajmo!) usmerjajo na dogajanje na cesti.

Po svoji definiciji je iterator objekt, za katerega velja:

• vsebuje metodo __next__, ki vrača elemente zaporedja
  
• vsebuje metodo __iter__, ki vrne objekt, na katerem je metoda klicana (torej self)
  
• ko se iterator "izrabi", sproži izjemo StopIteration
  

Tako lahko sami napišemo iterator, ki vrača člene Collatzovega zaporedja:

class Collatz:

    def __init__(self, n):
        self.n = n
        self.konec = False
    
    def __iter__(self):
        return self
    
    def __next__(self):
        if self.konec:
            raise StopIteration
        ret = self.n
        if self.n % 2 == 0:
            self.n //= 2
        else:
            self.n = 3*self.n + 1
        if ret == 1:
            self.konec = True
        return ret

Objekt razreda Collatz je iterator, saj ustreza zgornji definiciji. Naš iterator lahko uporabimo v zanki for na čisto enak način kot iteratorje, ki so že vgrajeni v Python:

for x in Collatz(43):
    print(x)

Objektom, po katerih je mogoče iterirati, pravimo iterabilni objekti. Takšni objekti imajo metodo __iter__, ne pa nujno tudi metode __next__. Sami se lahko prepričate, da so množice v Pythonu iterabilne, niso pa iteratorji.

V resnici ni nujno, da iterator kadarkoli sproži izjemo StopIteration. Naredimo lahko tudi iteratorje po neskončnih zaporedjih.

Generatorji

Mazohisti lahko s tem, kar smo opisali zgoraj, povsem srečno živijo. Vsak iterator bodo namreč izdelali na zgoraj opisan način v potu lastnega obraza. To seveda ni v duhu Pythona, saj se ne bodo osredotočali na problem, ampak na tehnikalije.

Generator je strogo gledano funkcija, ki sestavi in vrne iterator. Python ima mehanizem, s katerim na preprost način izdelamo generatorje. Definicija generatorja zgleda čisto tako kot definicija funkcije, le da namesto stavka return vsebuje stavek yield.

Definirajmo generator collatz, ki bo vračal iteratorje po Collatzovem zaporedju s podanim začetnim členom n. Definicija generatorja:

def collatz(n):
    yield n
    while n != 1:
        if n % 2 == 0:
            n //= 2
        else:
            n = 3*n + 1
        yield n

Prepričajmo se, da je collatz funkcija:

>>> collatz
<function collatz at 0x7f03e5d34e18>
>>> g = collatz(13)
>>> g
<generator object collatz at 0x7f03e4febe58>

Res! Če pa funkcijo collatz pokličemo, le-ta sestavi in vrne objekt, ki mu Python pravi "generator object", v resnici pa to ni nič drugega kakor iterator, v kar se lahko prepričamo takole:

>>> g is g.__iter__()
True
>>> g.__next__()
13
>>> g.__next__()
40

Pri poimenovanju je nastala zmeda, saj nekateri z besedo generator poimenujejo objekte (iteratorje), ki jih vračajo generatorji. Dosledneži (npr. Sheldon iz nadaljevanke The Big Bang Theory) bodo z besedo generator imenovali zgolj in samo funkcijo, ki sestavi in vrne iterator. Torej funkcija collatz je generator, objektu g, ki ga vrne, pa bodo rekli le iterator.

Tega, da je generator v resnici funkcija, ki sestavi in vrne iterator, se nam ni treba zavedati, saj ga uporabljamo na enak način kot zgornji iterator, ki smo ga naredili "na roke". Zgled:

for x in collatz(43):
    print(x)

Vidite? Je kakšna razlika? (Razen seveda tega, da je v prejšnjem primeru Collatz zapisan z veliko, tukaj pa z malo.) Tudi navodila nalog se bodo glasila: "Napišite generator, ki vrača to in to." Če bi bili dosledni, bi se navodila nalog glasila: "Napišite generator, ki sestavi in vrne iterator, ki vrača to in to." Ta vmesni korak je namreč tehnikalija, ki jo Python skrije pred našimi očmi.

Range

Še nekaj dodatne zmede povzroči range. Pa si poglejmo en primer:

>>> g = collatz(5)   
>>> list(g)
[5, 16, 8, 4, 2, 1]
>>> list(g)
[]
>>> g = range(5)
>>> list(g)
[0, 1, 2, 3, 4]
>>> list(g)
[0, 1, 2, 3, 4]

Najprej smo naredili iterator, ki gre po členih Collatzovega zaporedja. Ker se je ta pri prvem klicu list(g) že "izrabil", drugi klic list(g) vrne prazen seznam. Pri range pa vidimo, da ni tako. Kako to, da se ni izrabil? To je zaradi tega, ker g v drugem primeru ni iterator, pač pa je tip! Torej, je nek iterabilen objekt. V to se enostavno prepričamo:

>>> g = range(5)
>>> type(g)
<class 'range'>
>>> g.__iter__() is g
False
>>> it = g.__iter__()
>>> type(it)
<class 'range_iterator'>

Se pravi, iz objekta g razreda range se je vsakič naredil nov iterator in se seveda tudi "izrabil".