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.
Iteratoren werden auch in for-Schleifen genutzt. Im folgenden Beispiel durchlaufen wir die Elemente der Liste ,,cities''. 

>>> cities = ["Hamburg", "Berlin", "München", "Stuttgart", "Zürich"]
>>> for city in cities:
...     print("Stadt: " + city)
... 
Stadt: Hamburg
Stadt: Berlin
Stadt: München
Stadt: Stuttgart
Stadt: Zürich
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: 
>>> hauptstaedte = { "Österreich":"Wien", "Niederlande":"Amsterdam", "Deutschland":"Berlin", "Schweiz":"Bern" }
>>> for land in hauptstaedte:
...     print("Die Hauptstadt von " + land + " ist " + hauptstaedte[land]) 
... 
Die Hauptstadt von Österreich ist Wien
Die Hauptstadt von Niederlande ist Amsterdam
Die Hauptstadt von Deutschland ist Berlin
Die Hauptstadt von Schweiz ist Bern


Man kann die Iteration der for-Schleife durch folgenden Code simulieren: 
cities = ["Hamburg", "Berlin", "München", "Stuttgart", "Zürich"]
iterator = iter(cities)
while True:
    try:
        city = next(iterator)
    except StopIteration:
        break
    print(city)


Generatoren

Iteratoren kann man auch dadurch erzeugen, dass man eine spezielle Funktion benutzt, die als Generator bezeichnet wird. Diese kann, anstatt eine komplette Liste, ein Dictionary oder ähnliches Objekt 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 = next(gen1)
>>> print(letter)
a
>>> letter = next(gen1)
>>> print(letter)
b
>>> letter = next(gen2)
>>> print(letter)
a
>>> letter = next(gen2)
>>> print(letter)
b
>>>
Im obigen Beispiel definieren wir einen Generator, der nacheinander die Buchstaben "a", "b" und "c" produziert. 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 (genau genommen 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()

send Methode

Generatoren sind nicht nur in der Lage Objekte zu senden, sondern auch zu empfangen. Eine Nachricht, d.h. ein Objekt, an einen Generator zu senden, können wir die send-Methode einem Generator-Objekt zuweisen. Sind Sie sich der Tatsache bewusst, das "send" einen Wert sowohl an den Generator sendet, als auch den ergebenen Wert zurückliefert. Was wir bis jetzt nicht erwähnt haben: Der nächte Aufruf sendet und empfängt. Es sendet immer ein None-Objekt. Die Werte, die durch "next" und "send" gesendet werden, werden einer Variable innerhalb des Generators zugewiesen: Diese Variable wird im folgenden Beispiel "message" genannt. 
def abc():
    s = "abcdefg"
    count = 0
    while True:
        if count >= len(s):
            count = 0
        message = yield s[count]
        if message != None:
            count = 0 if message < 0 else message
        else:
            count += 1
            
            
x = abc()      
print(next(x))
print(next(x))
print(x.send(5))
print(next(x))
print(next(x))
Wir erhalten folgende Ausgabe: 
a
b
f
g
a
Wir sehen, dass der definierte Generator in unserem Beispiel für immer die Zeichen "a", "b", "c", "d", "e", "f", "a", "b" usw. zurückgibt wenn wir nur die next-Funktion verwenden. Es ist möglich die Sequenz zu ändern indem ein Index-Wert an den Generator gesendet wird mit der send-Methode des Generator-Objekts.

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')]
>>>


Als nächstes Beispiel für einen rekursiven Generator präsentieren wir einen Generator, der Variationen ohne Wiederholungen erzeugt. Bei einer Variation ohne Wiederholung werden k von n Objekten (wobei k<=n gilt) so auf k Plätze verteilt, dass jedes Objekt nur höchstens einen Platz einnimmt. Für den ersten Platz gibt es n Möglichkeiten, für den zweiten n-1, für den dritten n-2 bis zum k-ten Platz für den des dann noch n-k+1 Plätze gibt. Allgemein gibt es also
n! / (n-k)!
mögliche Anordnungen.

Im folgenden sehen wir alle 3-Variationen von {"a","b","c","d"}: 
['a', 'b', 'c']
['a', 'b', 'd']
['a', 'c', 'b']
['a', 'c', 'd']
['a', 'd', 'b']
['a', 'd', 'c']
['b', 'a', 'c']
['b', 'a', 'd']
['b', 'c', 'a']
['b', 'c', 'd']
['b', 'd', 'a']
['b', 'd', 'c']
['c', 'a', 'b']
['c', 'a', 'd']
['c', 'b', 'a']
['c', 'b', 'd']
['c', 'd', 'a']
['c', 'd', 'b']
['d', 'a', 'b']
['d', 'a', 'c']
['d', 'b', 'a']
['d', 'b', 'c']
['d', 'c', 'a']
['d', 'c', 'b']



Im folgenden Proramm haben wir einen Generator implementiert, der die k-Variationen von n berechnet. 

def k_variations(items, n):
    if n==0: 
        yield []
    else:
        for item in items:
            for kp in k_variations(items, n-1):
                if item not in kp:
                    yield [item] + kp
                    
for kp in k_variations("abcd", 3):
    print(kp)



The above program returns the following k-variationen:




['a', 'b', 'c']
['a', 'b', 'd']
['a', 'c', 'b']
['a', 'c', 'd']
['a', 'd', 'b']
['a', 'd', 'c']
['b', 'a', 'c']
['b', 'a', 'd']
['b', 'c', 'a']
['b', 'c', 'd']
['b', 'd', 'a']
['b', 'd', 'c']
['c', 'a', 'b']
['c', 'a', 'd']
['c', 'b', 'a']
['c', 'b', 'd']
['c', 'd', 'a']
['c', 'd', 'b']
['d', 'a', 'b']
['d', 'a', 'c']
['d', 'b', 'a']
['d', 'b', 'c']
['d', 'c', 'a']
['d', 'c', 'b']
{'c', 'd', 'e'}
{'a', 'd', 'e'}
{'f', 'd', 'e'}
{'b', 'd', 'e'}
{'f', 'c', 'd'}
{'c', 'a', 'd'}
{'b', 'c', 'd'}
{'f', 'a', 'd'}
{'b', 'a', 'd'}
{'b', 'd', 'f'}
{'c', 'a', 'e'}
{'f', 'a', 'e'}
{'b', 'a', 'e'}
{'f', 'c', 'a'}
{'b', 'c', 'a'}
{'b', 'a', 'f'}
{'f', 'c', 'e'}
{'b', 'c', 'e'}
{'b', 'c', 'f'}
{'b', 'f', 'e'}












Ein Generator für Generatoren



Der zweite Generator für die Fibonacci-Folge produziert Iteratoren, die alle 
Fibonacci-Zahlen 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 eines Generators g kann man sich folgenden Generator definieren: 

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


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]




Übungen



    

  1. Schreiben Sie einen Generator "trange", der eine Sequenz aus Zeit-Tupeln generiert 
von start bis stop in Stufen von step. Ein Zeit-Tupel ist ein 3er-Tupel aus Integer-Werten: 
(Stunden, Minuten, Sekunden).
Beispiel:

    for time in trange((10, 10, 10), (13, 50, 15), (0, 15, 12) ):
        print(time)

    
Liefert zurück:

    (10, 10, 10)
(10, 25, 22)
(10, 40, 34)
(10, 55, 46)
(11, 10, 58)
(11, 26, 10)
(11, 41, 22)
(11, 56, 34)
(12, 11, 46)
(12, 26, 58)
(12, 42, 10)
(12, 57, 22)
(13, 12, 34)
(13, 27, 46)
(13, 42, 58)

    

    2. 


  2. 
Schreiben Sie eine Version "rtrange" des vorigen Generators, welcher eine Nachricht empfangen kann um den Start-Wert zurückzusetzen.

    3. 


  3. 
Schreiben Sie ein Programm, welches den gerade geschriebenen Generator "trange" verwendet, 
um eine Datei "times_and_temperatures.txt" zu erstellen.
Die Zeilen der Datei bestehen aus einer Zeitangabe im Format hh::mm::ss und einer zufälligen Temperatur zwischen 10.0 und 25.0 Grad Celsius.
Die Zeiten sollten bei 06:00:00 beginnen und in 90-Sekunden-Schritten aufsteigen.


    
Beispiel:

    06:00:00 20.1
06:01:30 16.1
06:03:00 16.9
06:04:30 13.4
06:06:00 23.7
06:07:30 23.6
06:09:00 17.5
06:10:30 11.0

    4. 

  4. 
Schreiben Sie einen Generator mit dem Namen "random_ones_and_zeroes", der 
einen Bit-Strom zurückliefert, d.h. eine eins oder eine null in jedem Durchlauf (Iteration).
Die Wahrscheinlichkeit p, dass eine eins geliefert wird, wird über die Variable p festgelegt.
Der Generator initialisiert die Variable mit 0.5.
Das bedeutet, dass 1-en und 0-en mit der gleichen Wahrscheinlichkeit auftreten.

    5. 





Lösungen zu den Übungen



def trange(start, stop, step):
    """ 
    trange(stop) -> time as a 3-tuple (hours, minutes, seconds)
    trange(start, stop[, step]) -> time tuple

    start: time tuple (hours, minutes, seconds)
    stop: time tuple
    step: time tuple

    returns a sequence of time tuples from start to stop incremented by step
    """        

    current = list(start)
    while current < list(stop):
        yield tuple(current)
        seconds = step[2] + current[2]
        min_borrow = 0
        hours_borrow = 0
        if seconds < 60:
            current[2] = seconds
        else:
            current[2] = seconds - 60
            min_borrow = 1
        minutes = step[1] + current[1] + min_borrow
        if minutes < 60:
            current[1] = minutes 
        else:
            current[1] = minutes - 60
            hours_borrow = 1
        hours = step[0] + current[0] + hours_borrow
        if hours < 24:
            current[0] = hours 
        else:
            current[0] = hours -24

if __name__ == "__main__":           
    for time in trange((10, 10, 10), (13, 50, 15), (0, 15, 12) ):
        print(time)




def rtrange(start, stop, step):
    """ 
    trange(stop) -> time as a 3-tuple (hours, minutes, seconds)
    trange(start, stop[, step]) -> time tuple

    start: time tuple (hours, minutes, seconds)
    stop: time tuple
    step: time tuple

    returns a sequence of time tuples from start to stop incremented by step
    
    The generator can be reset by sending a new "start" value.
    """        

    current = list(start)
    while current < list(stop):
        new_start = yield tuple(current)
        if new_start != None:
            current = list(new_start)
            continue
        seconds = step[2] + current[2]
        min_borrow = 0
        hours_borrow = 0
        if seconds < 60:
            current[2] = seconds
        else:
            current[2] = seconds - 60
            min_borrow = 1
        minutes = step[1] + current[1] + min_borrow
        if minutes < 60:
            current[1] = minutes 
        else:
            current[1] = minutes - 60
            hours_borrow = 1
        hours = step[0] + current[0] + hours_borrow
        if hours < 24:
            current[0] = hours 
        else:
            current[0] = hours -24

if __name__ == "__main__":           
    ts = rtrange((10, 10, 10), (13, 50, 15), (0, 15, 12) )  
    for _ in range(3):
        print(next(ts))
        
    print(ts.send((8, 5, 50)))
    for _ in range(3):
        print(next(ts))
        
Die Ausführung des Programms liefert folgende Ausgabe:

(10, 10, 10)
(10, 25, 22)
(10, 40, 34)
(8, 5, 50)
(8, 21, 2)
(8, 36, 14)
(8, 51, 26)




from timerange import trange
import random

fh = open("times_and_temperatures.txt", "w")

for time in trange((6, 0, 0), (23, 0, 0), (0, 1, 30) ):
    random_number = random.randint(100, 250) / 10
    lst = time + (random_number,)
    output = "{:02d}:{:02d}:{:02d} {:4.1f}\n".format(*lst)
    fh.write(output)




import random

def random_ones_and_zeros():
    p = 0.5
    while True:
        x = random.random()
        message = yield 1 if x < p else 0
        if message != None:
            p = message
        
x = random_ones_and_zeros()
next(x)  # we are not interested in the return value
for p in [0.2, 0.8]:
    x.send(p)
    print("\nprobabiliy: " + str(p))    
    for i in range(15):
        print(next(x), end=" ")

Wir erhalten folgende Ausgabe:
probabiliy: 0.2
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 
probabiliy: 0.8
1 1 1 1 1 0 1 0 0 1 1 0 1 1 1