Iterátory a generátory

Iterátory jsou v Pythonu používané velice často, přestože o tom v mnoha případech ani nevíme nebo nepřemýšlíme. Generátory se staly jedním se základních kamenů pro Python 3.

Základní použití iterátorů a generátorů

Nejprve se podíváme, jak se iterátory v Pythonu používají. Později se dozvíme, jak interně fungují. Jednoduše řečeno, iterátory slouží k postupnému procházení položek v nějakém objektu. Co jsou jednotlivé položky, závisí na daném objektu. Generátor je konkrétním typem iterátoru, který dynamicy vytváří (generuje) položky v závislosti na vnitřním stavu (typicky v závislosti na poslední iteraci). Položky tedy nejsou (resp. nemusí být) uloženy v paměti všechny najednou.

Mnoho objektů v Pythonu je iterabilních (lze z nich vytvořit iterátor), zejména pak

  • kontejnery: list, tuple, dict apod.
  • řetězce: str, unicode
  • objekty typu stream, tedy např. file

Poměrně přehledně to ukazuje článek Iterables vs. Iterators vs. Generators, ze kterého je i tento názorný obrázek.

In [1]:
from IPython.display import Image
Image(url='http://nvie.com/img/relationships.png', width=700)
Out[1]:

for smyčky

for funguje v Pythonu výhradně na základě iterátorů. Neexistuje zde "klasická" for smyčka jako počítadlo. Syntaxi si ukážeme na příkladu procházení seznamu.

In [2]:
# vytvoříme nějaký seznam
l = [10, "a", ("x", 1e-3)]
# projdeme položky pomocí for
for x in l:
    print(x)
10
a
('x', 0.001)

Můžeme také procházet (iterovat) slovník - v takovém případě dostáváme postupně jednotlivé klíče. (Ale pozor: pořadí prvků slovníku je náhodné.)

In [3]:
d = {"one": 1, "two": 2}
for k in d:
    print('%s -> %s' % (k, d[k]))
one -> 1
two -> 2

Pro procházení slovníku se hodí metoda items. Všimněte si použití dvou proměnných (ve skutečnosti to je tuple, jen je zde možná vynechat závorky) pro přiřazení, které slouží k dekompozici, stejně jako např. u volání funkcí.

In [4]:
d = {"one": 1, "two": 2}
for k, v in d.items():
    print('%s -> %s' % (k, v))
one -> 1
two -> 2

Pokud chceme udělat klasické for počítadlo, musíme vytvořit objekt, který bude postupně vracet požadovaná čísla. K tomu slouží funkce range. (V Pythonu 2 můžeme použít také xrange, který vrací generátor. V Pythonu 3 vrací range generátor a xrange neexistuje.) Použití počítadla by mělo být poslední volbou pro procházení číslovaných polí. Použijeme ho jen v případě, že opravdu potřebujeme čísla jako taková, nikoli pouze prvky nějakého seznamu.

In [5]:
help(range)
print('range(5) = %s' % range(5))
for x in range(5):
    print(x)
Help on class range in module builtins:

class range(object)
 |  range(stop) -> range object
 |  range(start, stop[, step]) -> range object
 |  
 |  Return an object that produces a sequence of integers from start (inclusive)
 |  to stop (exclusive) by step.  range(i, j) produces i, i+1, i+2, ..., j-1.
 |  start defaults to 0, and stop is omitted!  range(4) produces 0, 1, 2, 3.
 |  These are exactly the valid indices for a list of 4 elements.
 |  When step is given, it specifies the increment (or decrement).
 |  
 |  Methods defined here:
 |  
 |  __contains__(self, key, /)
 |      Return key in self.
 |  
 |  __eq__(self, value, /)
 |      Return self==value.
 |  
 |  __ge__(self, value, /)
 |      Return self>=value.
 |  
 |  __getattribute__(self, name, /)
 |      Return getattr(self, name).
 |  
 |  __getitem__(self, key, /)
 |      Return self[key].
 |  
 |  __gt__(self, value, /)
 |      Return self>value.
 |  
 |  __hash__(self, /)
 |      Return hash(self).
 |  
 |  __iter__(self, /)
 |      Implement iter(self).
 |  
 |  __le__(self, value, /)
 |      Return self<=value.
 |  
 |  __len__(self, /)
 |      Return len(self).
 |  
 |  __lt__(self, value, /)
 |      Return self<value.
 |  
 |  __ne__(self, value, /)
 |      Return self!=value.
 |  
 |  __new__(*args, **kwargs) from builtins.type
 |      Create and return a new object.  See help(type) for accurate signature.
 |  
 |  __reduce__(...)
 |      helper for pickle
 |  
 |  __repr__(self, /)
 |      Return repr(self).
 |  
 |  __reversed__(...)
 |      Return a reverse iterator.
 |  
 |  count(...)
 |      rangeobject.count(value) -> integer -- return number of occurrences of value
 |  
 |  index(...)
 |      rangeobject.index(value, [start, [stop]]) -> integer -- return index of value.
 |      Raise ValueError if the value is not present.
 |  
 |  ----------------------------------------------------------------------
 |  Data descriptors defined here:
 |  
 |  start
 |  
 |  step
 |  
 |  stop

range(5) = range(0, 5)
0
1
2
3
4

Pokud už číslovaní potřebujeme, obvykle potřebujeme také hodnoty s daným indexem. V takovém případě použijeme enumerate:

In [6]:
for i, x in enumerate(('egg', 'bacon', 'sausage', 'spam')):
    print('{}. {}'.format(i, x))
0. egg
1. bacon
2. sausage
3. spam

Generátorová notace

Pomocí generátorové notace se dají v Pythonu dělat (téměř) zázraky. Používá se pro zkrácený zápis tvorby nového objektu typu list, dict, set nebo generátoru pomocí závorek a klíčových slov for, in, případně if.

Generátorový výraz (Generator expression)

Kulaté závorky: (výraz for proměnná in iterable)

In [7]:
(x ** 2 for x in range(1, 11))  # generátor, tj. iterovatelný objekt
Out[7]:
<generator object <genexpr> at 0x7f2f906de620>

Generátory seznamů (List comprehension)

Hranaté závorky: [výraz for proměnná in iterable]

In [8]:
[x ** 2 for x in range(1, 11)]  # klasický seznam
Out[8]:
[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

Toto můžeme použít i na převod generátoru na seznam.

In [9]:
# vytvoříme generátor
gen = (x ** 2 for x in range(1, 11))
# a teprve z něj vytvoříme list
[x for x in gen]
Out[9]:
[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

Generátory množin (Set comprehension)

(Podporováno od Pythonu 2.7.)

Složené závorky: {výraz for proměnná in iterable}

In [10]:
jmena = ["Ester", "Eva", "Egon", "Marie", "Monika", "Richard"]
prvni_pismena = {jmeno[0] for jmeno in jmena}
print("Množina počátečních písmen jmen (každé jen jednou):\n{}".format(prvni_pismena))
Množina počátečních písmen jmen (každé jen jednou):
{'R', 'E', 'M'}

Generátory slovníků (Dictionary comprehension)

(Podporováno od Pythonu 2.7.)

Složené závorky: {klíč: hodnota for proměnná in iterable}. Od generátoru množit se liší přítomností dvojtečky ve výrazu klíč: hodnota.

In [11]:
jmena = ["Ester", "Eva", "Egon", "Marie", "Monika", "Richard"]
# Slovník s délkami jmen
{jmeno : len(jmeno) for jmeno in jmena}
Out[11]:
{'Egon': 4, 'Ester': 5, 'Eva': 3, 'Marie': 5, 'Monika': 6, 'Richard': 7}

Filtrování pomocí if

U generátorové notace můžeme použít if jako filtr. Jako příklad vybereme z mocnin dvou jen ty dvouciferné.

In [12]:
# vytvoříme generátor (horní mez jsme nějak odhadli)
gen = (2 ** n for n in range(1, 11))
[x for x in gen if 9 < x < 100]
Out[12]:
[16, 32, 64]

Vícenásobné for

V jednom generátorovém výrazu můžeme mít více for klíčových slov. Bude se pak iterovat postupně přes všechny prvky všech iterárátorů za for. Je to ekvivalentní vnořenému for cyklu.

In [13]:
# vytvoření dvojic ze dvou množin
m1 = {"a", "b", "c"}
m2 = {"a", "c", "e"}
{(x1, x2) for x1 in m1 for x2 in m2}
Out[13]:
{('a', 'a'),
 ('a', 'c'),
 ('a', 'e'),
 ('b', 'a'),
 ('b', 'c'),
 ('b', 'e'),
 ('c', 'a'),
 ('c', 'c'),
 ('c', 'e')}

Cvičení

  1. Pomocí for cyklu z čísel od 10ti do 30ti vyberte prvky dělitelné 3mi. Vypisujte je na obrazovku a zároveň ukládejte no nového seznamu.
  2. Pomocí generátorové notace vytvořte generátor dvouciferných čísel dělitelných 3mi.

Užitečné funkce a metody

zip

K procházení více iterovatelných objektů nám zlouží zip. Tato funkce spáruje prvky n objektů do n-tic, takže jdou pak procházet současně, bez použití indexování.

In [14]:
# vytvoříme seznamy a generátor
l1 = range(1,9)
l2 = (2 ** n for n in l1)
# nyní je chceme procházet současně
for x, y in zip(l1, l2):
    print("%i -> %i" % (x, y))
1 -> 2
2 -> 4
3 -> 8
4 -> 16
5 -> 32
6 -> 64
7 -> 128
8 -> 256

enumerate

Pokud potřebujeme znát číselný index prvku, je lepší použít enumerate, která postupně vrací (index, prvek).

In [15]:
for i, n in enumerate(range(1,10)):
    print("%i -> %i" % (i, n))
0 -> 1
1 -> 2
2 -> 3
3 -> 4
4 -> 5
5 -> 6
6 -> 7
7 -> 8
8 -> 9

dict.items

Některé třídy mají pomocné metody pro iterace. Např. dict.items vrací dvojice (klíč, hodnota).

In [16]:
# slovník s částí ascii tabulky
d = {i: chr(i) for i in range(40, 50)}
for k, v in d.items():
    print("{0} -> {1}".format(k, v))
48 -> 0
49 -> 1
40 -> (
41 -> )
42 -> *
43 -> +
44 -> ,
45 -> -
46 -> .
47 -> /

modul itertools

Tento modul obsahuje mnoho zajímavých a užitečných funkcí pro tvorbu iterátorů, často inspirovných funkcionálními jazyky (o funkcionálním programování v Pythonu ještě uslyšíme).

In [17]:
# vypíšeme si funkce v itertools
import itertools
sorted([f for f in itertools.__dict__ if not f.startswith("_")])
Out[17]:
['accumulate',
 'chain',
 'combinations',
 'combinations_with_replacement',
 'compress',
 'count',
 'cycle',
 'dropwhile',
 'filterfalse',
 'groupby',
 'islice',
 'permutations',
 'product',
 'repeat',
 'starmap',
 'takewhile',
 'tee',
 'zip_longest']

V dokumentaci naleznete také recepty, jak vytvořit další užitečné funkce pomocí itertools. Ukažme si například, jak získat n-tý prvek z iterátoru (který pochopitelně nemusí mít číselné indexování).

In [18]:
from itertools import islice
# definice funkce
def nth(iterable, n, default=None):
    "Returns the nth item or a default value"
    # všimněte si použití funkce next
    return next(islice(iterable, n, None), default)

# jednoduché použití
print(nth(range(100), 3))
3

Cvičení

  1. Pro slovníkovou reprezentaci polynomů implementujte násobení. Reprezentace $x^3-2x+1$ je {3: 1, 1:-2, 0: 1}.
  2. Naprogramujte ekvivalent funkce enumerate pomocí funkce zip (případně itertools.izip) a vhodné funkce z modulu itertools. Aplikujte na libovolně vytvořený seznam jmen a vytvořte slovník, který přiřazuje pořadová čísla.

Architektura iterátorů

Účelem iterátorů je postupně procházet (iterovat) prvky objektu. To, jakým způsobem jsou chápány a implementovány prvky je specifické pro daný objekt. Klíčem k pochopení iterátorů jsou dvě speciálně pojmenované metody __iter__ a __next__ (next v Pythonu 2). Ty se obvykle nevolají přímo, ale např. pomocí for cyklu nebo generátorové notace. Ukažme si to na příkladu jednoduchého počítadla.

In [20]:
class Counter(object):
    """Primitivní počítadlo"""
    
    def __init__(self, n):
        self.n = n
        
    def __iter__(self):
        self.i = 0
        return self
    
    def __next__(self):
        i = self.i
        self.i += 1
        if self.i > self.n:
            raise StopIteration
        return i
   
# použijeme iterátor Counter ve for smyčce
my_counter = Counter(4)

for a in my_counter:
    print(a)

# vytvoříme list pomocí generátorové notace
print([a for a in my_counter])
0
1
2
3
[0, 1, 2, 3]

Jak to celé funguje? Pomocí iterátorového protokolu, který si můžeme ukázat krok za krokem. Jako první se vytvoří objekt pomocí metody __iter__ (ta se zavolá při for cyklu i generátorové notaci)

In [21]:
# iter zavolá __iter__
it = iter(Counter(5))
print(it)
print(dir(it))
<__main__.Counter object at 0x7f2f90680e48>
['__class__', '__delattr__', '__dict__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__gt__', '__hash__', '__init__', '__iter__', '__le__', '__lt__', '__module__', '__ne__', '__new__', '__next__', '__reduce__', '__reduce_ex__', '__repr__', '__setattr__', '__sizeof__', '__str__', '__subclasshook__', '__weakref__', 'i', 'n']

Poté se volá metoda next (resp. __next__ v Python 3). Obojí je možné volat pomocí vestavěné funkce next:

In [22]:
print(next(it))
print(next(it))
0
1

Iterace končí vyhozením výjimky StopIteration. Funguje to tedy asi takto:

In [23]:
it = iter(Counter(4))
while True:
    try:
        print(next(it))
    except StopIteration:
        break
0
1
2
3

No a teď už konečně víme, jak funguje "klasický" for cyklus s počítáním pomocí funkce range, resp. xrange. (V Pythonu 2 vrací range list a xrange generátor. V Pythonu 3 existuje už jen range, který vrací generátor.)

In [24]:
for i in range(4):
    print(i)
0
1
2
3

V Pythonu jsou iterace základním (a vlastně jediným) mechanismem for smyček. Pokud chceme provést nějakou operaci na množině objektů, která je typicky uložena v nějakém kontejneru (list, tuple, dic, set spod.), použijeme k tomu iterace. Ukážeme si několik příkladů.

Architektura generátorů

Pro vytvoření generátoru, nebo lépe řečené generátorové funkce, služí klíčové slovo yield. Jakmile se při běhu funkce narazí na klíčové slovo yield, funkce se "zmrazí" (zachová se interní stav pomocí uzávěru nebo closure -- o tom si ještě povíme) a vrátí se výraz za yield. Spuštění generátorová funkce jako takové pak vrací iterátor, který řídí spouštění této funkce. Ukážeme si jednoduchý příklad, který počítá donekonečna.

In [25]:
def countup(value=0):
    print("Příkazy se spustí až po zavolání prvního next")
    while True:
        yield value
        value += 1
g = countup(2)
In [26]:
next(g)
Příkazy se spustí až po zavolání prvního next
Out[26]:
2
In [27]:
next(g)
Out[27]:
3
In [28]:
next(g)
Out[28]:
4

Takto bychom mohli pokračovat donekonečna. Pokud chceme, aby iterátor někde zastavil, musíme použít vyjímku.

In [29]:
def countupto(to_value, from_value=0):
    value = from_value
    while value < to_value:
        yield value
        value += 1
    # tuto výjimky můžeme vyhodit manuálně, v tomto případě to ale není nutné
    # raise StopIteration
g = countupto(2)
In [30]:
next(g)
Out[30]:
0
In [31]:
next(g)
Out[31]:
1
In [32]:
next(g)
---------------------------------------------------------------------------
StopIteration                             Traceback (most recent call last)
<ipython-input-32-5f315c5de15b> in <module>()
----> 1 next(g)

StopIteration: 

Výjimka StopIteration je odchycena ve for cyklech, generátorech seznamů apod. Můžeme tedy udělat např. toto:

In [33]:
[i for i in countupto(10, 1)]
Out[33]:
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Pokud toto zkusíte s countup, iterace nikdy neskončí, resp. skončí nějakou chybou nebo přehřátím počítače.

Ukázali jsme si základní tvorbu generátorů. Celý protokol je ale bohatší a umožňuje komunikovat s generátorovou funkcí pomocí posílání hodnot nebo výjimek, viz dokumentace.

Cvičení

  1. Vytvořte generátorovou funkci pro čísla, která jsou definována rekurentním vztahem $$F_{n}=F_{n-1}+F_{n-2},\ F_0 = 0,\ F_1 = 1$$

Komentáře

Comments powered by Disqus