Iterátory a generátory

Komentáře

Zdroj

Dostupné také v

English

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.

V této lekci:

  • Se dozvíte co jsou iterátory a generátory.
  • Naučíte se jak používat for.
  • Dozvíte se že kontejnery, které už znáte, jsou iterabilní.
  • Pochopítě užitečnost generátorové notace.

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(f'x = {x}')

x = 10
x = a
x = ('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 key in d:
    print(f'{key} -> {d[key]}')

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 key, value in d.items():
    print(f'{key} -> {value}')

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. 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)

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:
 |  
 |  __bool__(self, /)
 |      True if self else False
 |  
 |  __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.
 |  
 |  __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) -> integer -- return index of value.
 |      Raise ValueError if the value is not present.
 |  
 |  ----------------------------------------------------------------------
 |  Static methods defined here:
 |  
 |  __new__(*args, **kwargs) from builtins.type
 |      Create and return a new object.  See help(type) for accurate signature.
 |  
 |  ----------------------------------------------------------------------
 |  Data descriptors defined here:
 |  
 |  start
 |  
 |  step
 |  
 |  stop
In [6]:
range(5)
Out[6]:
range(0, 5)
In [7]:
for x in range(5):
    print(x)

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 [8]:
for i, x in enumerate(('egg', 'bacon', 'sausage', 'spam')):
    print(f'{i}. {x}')

0. egg
1. bacon
2. sausage
3. spam

Cvičení

Pomocí for a enumerate naprogramujte funkci find(where, what), která vrací pole indexů prvků what v iterabilním objektu where. Ověřte pomocí assert testů.

In [9]:
def find(where, what):
    ???
    return indexes

Pokud assert nevyhodí výjimku, funkce je napsaná (velice pravděpodobně) správně.

In [ ]:
assert list(find(['FJFI', 2018, 2019], 2018)) == [1]
assert list(find((), 'whatever')) == []
assert list(find('Mississippi', 's')) == [2, 3, 5, 6]
print('Funkce find pracuje správně')

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 [10]:
(x ** 2 for x in range(1, 11))  # generátor, tj. iterovatelný objekt
Out[10]:
<generator object <genexpr> at 0x10655d660>

Generátory seznamů (List comprehension)

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

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

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

In [12]:
# 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[12]:
[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

Generátory množin (Set comprehension)

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

In [13]:
jmena = ["Ester", "Eva", "Egon", "Marie", "Monika", "Richard"]
prvni_pismena = {jmeno[0] for jmeno in jmena}
print(f"Množina počátečních písmen jmen (každé jen jednou):\n{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 [14]:
jmena = ["Ester", "Eva", "Egon", "Marie", "Monika", "Richard"]
# Slovník s délkami jmen
{jmeno : len(jmeno) for jmeno in jmena}
Out[14]:
{'Ester': 5, 'Eva': 3, 'Egon': 4, '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 [15]:
# 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[15]:
[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 [16]:
# 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[16]:
{('a', 'a'),
 ('a', 'c'),
 ('a', 'e'),
 ('b', 'a'),
 ('b', 'c'),
 ('b', 'e'),
 ('c', 'a'),
 ('c', 'c'),
 ('c', 'e')}

Cvičení

Přepište funkci find pomocí jednoho genráorového výrazu.

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 [18]:
# 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(f"{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 [21]:
for i, n in enumerate("ABCDE"):
    print(f"{i} -> {n}")

0 -> A
1 -> B
2 -> C
3 -> D
4 -> E

dict.items

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

In [22]:
# slovník s částí ascii tabulky
d = {i: chr(i) for i in range(40, 50)}
for k, v in d.items():
    print(f"{k} -> {v}")

40 -> (
41 -> )
42 -> *
43 -> +
44 -> ,
45 -> -
46 -> .
47 -> /
48 -> 0
49 -> 1

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 [23]:
# vypíšeme si funkce v itertools
import itertools
sorted([f for f in itertools.__dict__ if not f.startswith("_")])
Out[23]:
['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 [24]:
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 funkci pro násobení polynomů polydot(polynom1, polynom2). Slovníková reprezentace polynomu má jako klíče exponenty a jako hodnoty koeficienty u daných polynomů. Např. reprezentace $x^3 - 2x + 1$ je {3: 1, 1:-2, 0: 1}. Využijte dict metodu get nebo collections.defaultdict.
  2. Naprogramujte ekvivalent funkce enumerate pomocí funkce zip (případně itertools.izip) a vhodné funkce z modulu itertools, která bude sloužit jako počítadlo. Aplikujte na libovolně vytvořený seznam jmen a vytvořte slovník, který přiřazuje pořadová čísla.
In [ ]:
# Test pro cvičení 1

poly1 = {3: 1, 1: -2, 0: 1}
poly2 = {1: -1, 0: 2}

assert polydot(poly1, poly2) == {4: -1, 3: 2, 2: 2, 1: -5, 0: 2}
print('Funkce polydot pracuje správně')

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 [25]:
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 [26]:
# iter zavolá __iter__
it = iter(Counter(5))
print(it)
print(dir(it))

<__main__.Counter object at 0x1065b3130>
['__class__', '__delattr__', '__dict__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__gt__', '__hash__', '__init__', '__init_subclass__', '__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 [27]:
print(next(it))
print(next(it))

0
1

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

In [28]:
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 [29]:
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 [31]:
def countup(value=0):
    print("Příkazy se spustí až po zavolání prvního next")
    while True:
        yield value
        value += 1
In [33]:
g = countup(2)
In [34]:
next(g)

Příkazy se spustí až po zavolání prvního next
Out[34]:
2
In [35]:
next(g)
Out[35]:
3
In [36]:
next(g)
Out[36]:
4

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

In [37]:
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
In [38]:
g = countupto(2)
In [39]:
next(g)
Out[39]:
0
In [40]:
next(g)
Out[40]:
1
In [41]:
next(g)

---------------------------------------------------------------------------
StopIteration                             Traceback (most recent call last)
Cell In[41], line 1
----> 1 next(g)

StopIteration:

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

In [42]:
[i for i in countupto(10, 1)]
Out[42]:
[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