Nächstes Kapitel: Anonyme Funktionen: Lambda-Operator, map- filter- und reduce
Generatoren und Iteratoren
Einführung
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ürichDie 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 aNach 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:
- Ein Generator wird wie eine Funktion aufgerufen. Er liefert als Rückgabewert ein Iterator-Objekt zurück. Dabei wird der Code des Generators noch nicht ausgeführt.
- Wird nun der zurückgelieferte Iterator benutzt, dann wird jedes mal, wenn ein neues Objekt des Iterators benötigt wird (next-Methode), der Code innerhalb des Generators so lange ausgeführt, bis er bei einer yield-Anweisung angelangt.
- yield wirkt dann wie ein return einer Funktion, d.h. der Wert des Ausdrucks oder Objektes hinter yield wird zurückgegeben. Allerdings wird der Generator dabei nicht wie eine Funktion beendet, sondern er wird nur unterbrochen und wartet nun auf den nächsten Aufruf, um hinter dem yield weiterzumachen. Sein gesamter Zustand wird bis zum nächsten Aufruf zwischengespeichert.
- Der Generator wird erst beendet, wenn entweder der Funktionskörper vollständig abgearbeitet wurde oder der Programmablauf auf eine return-Anweisung (ohne Wert) stößt.
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 aWir 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
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 * 1Der 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
- 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)- Schreiben Sie eine Version "rtrange" des vorigen Generators, welcher eine Nachricht empfangen kann um den Start-Wert zurückzusetzen.
- 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- 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.
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 1Voriges Kapitel: Difference between interators und Iterables
Nächstes Kapitel: Anonyme Funktionen: Lambda-Operator, map- filter- und reduce