Generatoren und Iteratoren

Einführung

Windkraft-Generatoren Ein Iterator bezeichnet einen Zeiger, der es einem erlaubt über die Elemente einer Liste oder allgemein durch die Elemente einer Menge von Objekten zu iterieren. Der Iterator ist eine Abstraktion, die es einem erlaubt auf alle Elemente einer Menge zuzugreifen, ohne dass man Kenntnis der Datenstruktur oder der Implementierung haben muss. In einigen objektorientierten Programmiersprachen wie beispielsweise Perl, Java und auch Python stehen Iteratoren implizit zur Verfügung und können in foreach-Schleifen (in Python entspricht dies der for-Schleife) benutzt werden.

Generatoren sind eine besondere Art von Funktionen, die es einem erlauben, Iteratoren zu implementieren bzw. zu generieren.

Iteratoren sind ein fundamentaler Bestandteil der Sprache Python.
Meist werden sie jedoch nur implizit benutzt, zum Beispiel in der For-Schleife, wie wir im folgenden Beispiel sehen: 

>>> towns = ["Paris","Berlin","London","Vienna"]
>>> for location in towns:
...     print("location: " + location)
... 
location: Paris
location: Berlin
location: London
location: Vienna
>>>
Die sequentiellen Basistypen sowie ein Großteil der Klassen der Standardbibliothek von Python unterstützen Iterationen. Auch der Datentyp Dictionary (dict) unterstützt die Iteration. In diesem Fall läuft die Iteration über die Schlüssel des Dictionarys: 
>>> capitals = { "France":"Paris", "Netherlands":"Amsterdam", "Germany":"Berlin", "Switzerland":"Bern" }>>> for country in capitals:
...     print("The capital city of " + country + " is " + capitals[country])
... 
The capital city of Switzerland is Bern
The capital city of Netherlands is Amsterdam
The capital city of Germany is Berlin
The capital city of France is Paris
>>>

Generatoren

Iteratoren kann man auch dadurch erzeugen, dass man eine spezielle Funktion benutzt, die als Generator bezeichnet wird. Diese kann, anstatt eine komplette Liste, Dictionary oder ähnliches Objeckt auf einmal zurückzuliefern, die Elemente in mehreren Schritten dem Benutzer zurückliefern. Generatoren speichern ihren lokalen Zustand (Variablenwerte usw.) zwischen den Funktionsaufrufen. Dadurch eignen sie sich bestens zur Erzeugung von komplexen zustandsorientierten Iteratoren, z.B. ein Generator, der die Zahlen einer Fibonacci-Folge erzeugt.
Rein äußerlich betrachtet gleichen sie Funktionen. Syntaktisch betrachtet gibt es nur einen Unterschied: Statt der return-Anweisung findet man in einem Generator eine oder mehrere yield-Anweisungen.

Alles, was man mit Generatoren machen kann, lässt sich auch mit klassenbasierten Iteratoren machen. Aber der entscheidende Vorteil der Generatoren liegt darin, dass die Methoden __iter__() und next() automatisch erzeugt werden.

Bevor wir uns die Generatoren im Detail anschauen, betrachten wir ein einfaches Beispiel zur Einführung: 
def abc_generator():
    yield("a")
    yield("b")
    yield("c")

gen1 = abc_generator()
gen2 = abc_generator()

letter = gen1.next()
print(letter)
letter = gen1.next()
print(letter)
letter = gen2.next()
print(letter)def
Im obigen Beispiel definieren wir einen Generator, der nacheinander die Buchstaben "a", "b" und "c" produiziert. Wir definieren im Beispiel zwei Iteratoren gen1 und gen2. Wir können im Ergebnisausdruck des obigen Beispiels sehen, dass die beiden Iteratoren unabhängig voneinander arbeiten. 
$ python abc.py 
a
b
a
Nach dem dritten next()-Aufruf erfolgt eine Fehlermeldung.
Oft wird die Frage gestellt, ob man einem Iterator einen Reset schicken kann, damit man wieder von vorne mit der Iteration beginnen kann. Es gibt kein Reset, stattdessen kann man sich einfach wieder einen neuen Generator generieren lassen, also im obigen Beispiel mit dem Aufruf "x = abc_generator()"

In den meisten Fällen wird aber in einem Python-Programm nicht mit der next()-Methode auf einen Iterator zugegriffen sondern man interiert mittels einer for-Schleife: 
def abc_generator():
    yield("a")
    yield("b")
    yield("c")

for el in abc_generator():
    print(el)
Die obige for-Schleife führt zu folgendem Ergebnis, wenn man das Script wieder in abc.py abspeichert und aufruft: 
$ python abc.py 
a
b
c

Zum Verständnis der yield-Anweisung:
Stünde statt den yield-Anweisungen im abc-generator() jeweils ein return, hätten wir eine Funktion, die bei jedem Aufruf immer nur ein "a", also kein "b" oder "c" lieferte. Bei der yield-Anweisung sieht es so aus, dass der Generator verlassen wird, aber es wird sich "gemerkt", wo die yield-Anweisung stand. Bei der nächsten Iteration, wird nach der letzten yield-Anweisung weiter gemacht.

Generatoren und ihre Arbeitsweise

Die Generatoren bieten eine komfortable Möglichkeit Iteratoren zu "generieren", daher der Name Generator, und diese zu verarbeiten.
Funktionsweise eines Generators:

Betrachten wir als Beispiel den Fibonacci-Generator, ein Generator, der die Fibonacci-Zahlen erzeugt, also die Folge der Zahlen 0,1,1,2,3,5,8,13 (fib(n) = fib(n-1) + fib(n-2) für n >= 2) 
def fibonacci(n):
    """Ein Fibonacci-Zahlen-Generator"""
    a, b, counter = 0, 1, 0
    while True:
        if (counter > n): return
        yield a
        a, b = b, a + b
        counter += 1
f = fibonacci(5)
for x in f:
	 # no linefeed is enforced by  end="":
    print(x, " ", end="") # 
print()
Der obige Generator liefert einen Iterator mit den ersten n Fibonacci-Zahlen (genaugenommen n+1, da 0-te Zahl auch dabei ist). Durch die Verwendung des Schlüsselwort-Argumentes end="" wird erzwungen, dass nach dem Aufruf der print()-Funktion kein Zeilenvorschub erfolgt.

Man kann auch einen endlosen Iterator liefern, indem man den Generator ohne Abbruchbedingung und ohne Argument umbaut, dann muss man bei der Benutzung des Iterators darauf achten, dass man ein Endekriterium einbaut: 
def fibonacci():
    """Ein Fibonacci-Zahlen-Generator, unendlich"""
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

f = fibonacci()

counter = 0
for x in f:
    print(x, " ", end="")
    counter += 1
    if (counter > 10): break 
print()

Rekursiver Generator

Permutationen Auch Generatoren können genau wie Funktionen Rekursionen enthalten. Wir wollen die Rekursion in Generatoren an einem weiteren Beispiel verdeutlichen. Im folgenden Beispiel wird ein Generator für Permutationen implementiert.

Da sicherlich nicht alle Besucher und Besucherinnen dieser Einführung in Python wissen, was eine Permutation ist, wollen wir diese kurz vorstellen.

Formale Definition:
Jede mögliche Anordnung von n Elementen, in der alle Elemente verwendet werden, nennt man Permutation dieser Elemente.

In den folgenden Zeilen sehen wir beispielsweise alle möglichen Permutationen der Buchstaben a, b und c:
a b c
a c b
b a c
b c a
c a b
c b a

Für die Anzahl der Permutationen von n Elementen gilt:
n! = n*(n-1)*(n-2) ... 2 * 1 Der Permutations-Generator wird mit einer beliebigen Liste von Objekten aufgerufen, aus der dann ein Iterator mit allen möglichen Permutationen zur Verfügung gestellt wird: 

def permutations(items):
    n = len(items)
    if n==0: yield []
    else:
        for i in range(len(items)):
            for cc in permutations(items[:i]+items[i+1:]):
                yield [items[i]]+cc

for p in permutations(['r','e','d']): print(''.join(p))
for p in permutations(list("game")): print(''.join(p) + ", ", end="")
Das vorige Beispiel ist sicherlich nicht ganz einfach zu verstehen für Programmieranfänger. Wie so häufig bietet Python auch hierfür ein komplexes Problem eine bequeme Lösung. Dafür benötigen wir das Modul itertools. Dies ist ein hilfreiches Tool zur Erzeugung und Bearbeitung von Iteratoren.

Erzeugung von Permutationen mit itertools: 
>>> import itertools
>>> perms = itertools.permutations(['r','e','d'])
>>> perms
<itertools.permutations object at 0x7fb0da3e4a70>
>>> list(perms)
[('r', 'e', 'd'), ('r', 'd', 'e'), ('e', 'r', 'd'), ('e', 'd', 'r'), ('d', 'r', 'e'), ('d', 'e', 'r')]
>>>

Ein Generator für Generatoren

Der zweite Generator für die Fibonacci-Folge produziert Iteratoren, die alle alle Fibonacci liefern, d.h. unendlich viele. Damit bieten Generatoren eine einfache Möglichkeit unendliche Mengen zu erzeugen. Allerdings sollte man nie versuchen sich die Liste der Fibonacci-Zahlen wirklich erzeugen zu lassen. Ein Aufruf der Form 

list(fibonacci())
zeigt einem sehr schnell die Grenzen des eigenen Rechners!
Im obigen Beispiel iterierten wir zwar über die Menge der Fibonacci-Zahlen, hatten aber mit der Variablen counter ein Abbruchkriterium formuliert.
Sehr häufig hat man bei Generatoren das Problem, dass man nur eine bestimmte Anzahl von Elementen der unendlichen Folge des Iterators haben will. Zur Erzeugung der ersten n Elemente eine Generators g kann man sich folgenden Generator definieren: 
def firstn(g, n):
	for i in range(n):
		yield g.next()
Das folgende Skript liefert die ersten 10 Fibonacci-Zahlen: 
#!/usr/bin/env python3
def fibonacci():
    """Ein Fibonacci-Zahlen-Generator"""
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

def firstn(g, n):
	for i in range(n):
		yield next(g)

print(list(firstn(fibonacci(), 10)))
Dies liefert folgende Ausgabe: 
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]