Generatoren

Einführung

Windkraft-Generatoren Generatoren sind eine einfache und mächtige Möglichkeit, Iteratoren zu kreieren.
Äußerlich 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")
Mit diesem Generator kann man einen Iterator generieren, der die drei Buchstaben "a", "b" und "c" der Reihe nach liefert. 
>>> from abc_generator import abc_generator
>>> x = abc_generator()
>>> print x.next()
a
>>> print x.next()
b
>>> print x.next()
c
>>> print x.next()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration
Mit dem obigen Aufruf in der interaktiven Python-Shell haben wir einen Iterator x erzeugt. Die next()-Methode liefert uns mit jedem Aufruf einen weiteren Buchstaben. Nachdem alle drei Buchstaben iteriert worden sind, liefert ein weiterer Aufruf von next() einen Fehler.
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()"
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:
    print x,
print
Der obige Generator liefert einen Iterator mit den ersten n Fibonacci-Zahlen (genaugenommen n+1, da 0-te Zahl auch dabei ist). 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,
    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)
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

>>> 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 python
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 g.next()

print list(firstn(fibonacci(), 10))