23.4    Spezielle Generatoren – itertools 

An dieser Stelle stellen wir Ihnen das Modul itertools der Standardbibliothek vor, das Generatorfunktionen enthält, die im Programmieralltag immer wieder benötigt werden. So ist es mit itertools beispielsweise möglich, über alle Kombinationen oder Permutationen aus Elementen einer gegebenen Liste zu iterieren.

Tabelle 23.2 listet die im Modul itertools enthaltenen Generatoren auf und erklärt diese kurz. Detaillierte Beschreibungen folgen in den anschließenden Abschnitten.

Tabelle 23.2    Funktionen des Moduls itertools

Zur Veranschaulichung werden in den folgenden Beispielen die von den Generatorfunktionen zurückgegebenen Iteratoren in Listen überführt und ausgegeben. Um die Beispiele nachvollziehen zu können, müssen Sie zuvor das Modul itertools importiert haben:

>>> import itertools

 

23.4.1    accumulate(iterable, [func]) 

Die Funktion accumulate erzeugt einen Iterator, der die Partialsummen der Elemente von iterable durchläuft. Dies wird durch das folgende Beispiel veranschaulicht:

>>> list(itertools.accumulate([1,2,3,4]))
[1, 3, 6, 10]

Der erzeugte Iterator durchläuft die Elemente 1, 1+2, 1+2+3 und 1+2+3+4.

Für den optionalen Parameter func kann ein selbst definierter Operator übergeben werden, der anstelle der Addition benutzt werden soll. Es muss sich dabei um ein Funktionsobjekt handeln, das zwei Parameter erwartet und daraus einen Rückgabewert berechnet.

 

23.4.2    chain([*iterables]) 

Die Funktion chain (dt. »verketten«) erzeugt einen Iterator, der der Reihe nach alle Elemente der übergebenen iterierbaren Objekte durchläuft:

>>> list(itertools.chain("ABC", "DEF"))
['A', 'B', 'C', 'D', 'E', 'F']

Sie sehen, dass zuerst die Elemente des ersten und dann die Elemente des zweiten übergebenen Strings durchlaufen werden.

In einigen Fällen ist es ungünstig, die iterierbaren Objekte einzeln als Parameter zu übergeben. Dafür gibt es die Funktion chain.from_iterable, die eine Sequenz von iterierbaren Objekten als einzigen Parameter erwartet:

>>> list(itertools.chain.from_iterable(["ABC", "DEF", "GHI"]))
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']

Abgesehen von der Parameterfrage sind die beiden Funktionen äquivalent.

 

23.4.3    combinations(iterable, r) 

Die Funktion combinations durchläuft alle r-elementigen Kombinationen aus iterable. Bei einer Kombination wird nicht auf die Reihenfolge der zusammengestellten Elemente geachtet. Das Vertauschen von Elementen einer Kombination führt also nicht zu einer neuen Kombination. Im folgenden Beispiel werden alle vierstelligen Kombinationen aus den Zahlen von 0 bis 4 durchlaufen:

>>> list(itertools.combinations(range(5), 4))
[(0, 1, 2, 3), (0, 1, 2, 4), (0, 1, 3, 4), (0, 2, 3, 4), (1, 2, 3, 4)]

Sie sehen, dass die Anordnung (4, 1, 0, 2) nicht aufgeführt ist, da sie sich nur durch Vertauschung der Elemente aus der Kombination (0, 1, 2, 4) ergibt.

Anhand des nächsten Beispiels sehen Sie, dass die erzeugten Kombinationen von der Reihenfolge der Elemente in iterable abhängen:

>>> list(itertools.combinations("ABC", 2))
[('A', 'B'), ('A', 'C'), ('B', 'C')]
>>> list(itertools.combinations("CBA", 2))
[('C', 'B'), ('C', 'A'), ('B', 'A')]

Wenn Sie an einem Generator interessiert sind, der auf die Reihenfolge der Elemente achtet, möchten Sie alle Permutationen durchlaufen. In diesem Fall ist die Funktion permutations eine bessere Wahl.

 

23.4.4    combinations_with_replacement(iterable, r) 

Die Funktion combinations_with_replacement durchläuft wie combinations alle r-elementigen Kombinationen aus iterable, allerdings mit Zurücklegen. Das bedeutet, dass ein Element aus iterable mehrfach in einer Kombination vorkommen darf.

>>> list(itertools.combinations_with_replacement(range(3), 2))
[(0, 0), (0, 1), (0, 2), (1, 1), (1, 2), (2, 2)]

Wie bei combinations kommt es auch hier nicht auf die Reihenfolge der Elemente an.

 

23.4.5    compress(data, selectors) 

Die Funktion compress erzeugt einen Iterator, der diejenigen Elemente des iterierbaren Objekts data durchläuft, deren korrespondierendes Element in selectors den Wert True hat. Das wird an folgendem Beispiel deutlich:

>>> list(itertools.compress("ABCDEFGH", [1,1,1,0,0,1,0,1]))
['A', 'B', 'C', 'F', 'H'] 

Die für selectors übergebene Liste gibt an, dass die ersten drei sowie das sechste und achte Element von data durchlaufen werden sollen.

 

23.4.6    count([start, step]) 

Die Funktion count erzeugt einen Iterator, der die Werte start+n⋅step für alle n≥0 durchläuft, beginnend bei 0. Sowohl für start als auch für step können Gleitkommazahlen übergeben werden, wobei standardmäßig bei 0 begonnen und die Schrittweite 1 gewählt wird. Beachten Sie, dass dieser Iterator von selbst nicht aufhört zu zählen.

>>> for i in itertools.count(-5):
...     print(i)
...     if i >= 0:
...         break
...
-5
-4
-3
-2
-1
0

Interessant ist count auch in Verbindung mit der Built-in Function map (Abschnitt 19.8.30). Dies wird anhand des folgenden Beispiels demonstriert, das die Quadratzahlen zwischen 0 und 30 ausgibt:

>>> m = map(lambda x: x**2, itertools.count())
>>> for i in m:
...     if i > 30:
...         break
...     print(i)
...
0
1
4
9
16
25

 

23.4.7    cycle(iterable) 

Die Funktion cycle durchläuft alle Elemente des iterierbaren Objekts iterable und fängt danach wieder von vorn an. Der von cycle erzeugte Iterator läuft in einer Endlosschleife. Beachten Sie, dass sich die Funktion cycle intern eine Kopie jedes Elements von iterable anlegt und diese beim erneuten Durchlaufen verwendet. Das hat je nach Länge von iterable einen signifikanten Speicherverbrauch zur Folge.

 

23.4.8    dropwhile(predicate, iterable) 

Die Funktion dropwhile bekommt ein iterierbares Objekt iterable und eine Funktion predicate übergeben. Sie ruft zunächst für alle Elemente von iterable die Funktion predicate auf und übergeht jedes Element, für das predicate den Wert True zurückgegeben hat. Nachdem predicate zum ersten Mal den Wert False zurückgegeben hat, wird jedes nachfolgende Element von iterable durchlaufen, unabhängig davon, was predicate für diese Elemente zurückgibt. Sie können sich die Funktion predicate also als ein Startsignal vorstellen.

>>> p = lambda x: x.islower()
>>> list(itertools.dropwhile(p, "abcdefgHIJKLMnopQRStuvWXYz"))
['H', 'I', 'J', 'K', 'L', 'M', 'n', 'o', 'p', 'Q', 'R', 'S', 't', 'u', 'v', 'W', 'X', 'Y', 'z']

Im Beispiel werden alle Buchstaben nach den Kleinbuchstaben am Anfang in die Ergebnisliste aufgenommen. Sie sehen, dass auch Kleinbuchstaben im Ergebnis enthalten sind, nachdem die Prädikatfunktion p zum ersten Mal True zurückgegeben hat.

 

23.4.9    filterfalse(predicate, iterable) 

Die Funktion filterfalse durchläuft alle Elemente von iterable, für die die Funktion predicate den Wert False zurückgibt. Ein Aufruf von filterfalse ist damit äquivalent zur folgenden Generator Expression:

(x for x in iterable if not predicate(x))

Im folgenden Beispiel werden nur die Großbuchstaben eines Strings durchlaufen:

>>> p = lambda x: x.islower()
>>> list(itertools.filterfalse(p, "abcDEFghiJKLmnoP"))
['D', 'E', 'F', 'J', 'K', 'L', 'P']
>>> list((x for x in "abcDEFghiJKLmnoP" if not p(x)))
['D', 'E', 'F', 'J', 'K', 'L', 'P']

 

23.4.10    groupby(iterable, [key]) 

Die Funktion groupby erzeugt einen Iterator, der die Elemente aus iterable gruppiert durchläuft. Die Gruppierung wird dabei anhand der für key übergebenen Schlüsselfunktion durchgeführt. Wenn der Parameter key nicht angegeben wird, werden die Elemente anhand ihres Wertes gruppiert.

Der von groupby erzeugte Iterator durchläuft Tupel, die den jeweiligen Gruppenschlüssel und einen Iterator über die Gruppenelemente enthalten. Das folgende Beispiel demonstriert die Funktionsweise von groupby:

>>> for l in list(itertools.groupby("AAABBBCCC")):
...     print(list(l))
...
['A', <itertools._grouper object at 0x7f4784b6c310>]
['B', <itertools._grouper object at 0x7f4784b6c5d0>]
['C', <itertools._grouper object at 0x7f4784b6c390>]
>>> [list(g) for k, g in itertools.groupby('AAABBBCCC')]
[['A', 'A', 'A'], ['B', 'B', 'B'], ['C', 'C', 'C']] 

Mithilfe einer eigenen Schlüsselfunktion können die Elemente nach anderen Gesichtspunkten gruppiert werden. Im folgenden Beispiel wird eine Schlüsselfunktion eingesetzt, um eine Gruppierung nach der Wortlänge durchzuführen.

>>> def f(x):
...     return len(x)
...
>>> words = ["for", "while", "and", "or", "if", "elif", "else"]
>>> [list(g) for k, g in itertools.groupby(words, f)]
[['for'], ['while'], ['and'], ['or', 'if'], ['elif', 'else']] 

Hier zeigt sich eine wichtige Anforderung an die Reihenfolge der Elemente in iterable. Obwohl die Wörter »for« und »and« gleich lang sind, wurden sie nicht zu einer Gruppe zusammengefasst. Damit das Gruppieren mit groupby funktioniert, müssen die in iterable enthaltenen Objekte im Hinblick auf die eingesetzte Schlüsselfunktion vorsortiert werden.

 

23.4.11    islice(iterable, [start], stop, [step]) 

Die Funktion islice bildet das Slicing, das Sie von den sequenziellen Datentypen her kennen, auf beliebige iterierbare Objekte ab. Die Funktion erzeugt einen Iterator, der bei dem Element mit der laufenden Nummer start beginnt, vor dem Element mit der Nummer stop aufhört und in jedem Schritt um step Elemente weiterspringt:

>>> list(itertools.islice("ABCDEFGHIJKL", 2, 8, 2))
['C', 'E', 'G']
>>> "ABCDEFGHIJKL"[2:8:2]
'CEG'

 

23.4.12    permutations(iterable, [r]) 

Die Funktion permutations erzeugt einen Iterator über alle r-stelligen Permutationen aus Elementen des iterierbaren Objekts iterable.

>>> list(itertools.permutations(range(3), 2))
[(0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1)]

Wie Sie sehen, sind die Anordnungen (0,1) und (1,0) beide in der Ergebnisliste enthalten. Bei Permutationen kommt es im Gegensatz zu den Kombinationen auf die Reihenfolge der Anordnung an.

>>> list(itertools.permutations("ABC", 2))
[('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]
>>> list(itertools.permutations("CBA", 2))
[('C', 'B'), ('C', 'A'), ('B', 'C'), ('B', 'A'), ('A', 'C'), ('A', 'B')]

Dieses Beispiel zeigt, dass auch hier die Reihenfolge der Permutationen in der Ergebnisliste von der Reihenfolge der zu permutierenden Elemente in iterable abhängt.

 

23.4.13    product([*iterables], [repeat]) 

Die Funktion product erzeugt einen Iterator, der das kartesische Produkt der übergebenen iterierbaren Objekte durchläuft. Das Ergebnis sind alle Tupel, die aus je einem Element eines jeden übergebenen iterierbaren Objekts gebildet werden können. Dabei steht ein Element in dem Tupel genau an der Stelle, an der auch das iterierbare Objekt in der Parameterliste steht, aus dem es stammt. Dies veranschaulicht das folgende Beispiel:

>>> list(itertools.product("ABC", [1,2]))
[('A', 1), ('A', 2), ('B', 1), ('B', 2), ('C', 1), ('C', 2)]

Hier wurde jedes Zeichen aus dem String "ABC" einmal mit allen Elementen der Liste [1,2] in Verbindung gebracht.

Über den optionalen Schlüsselwortparameter repeat kann ein iterierbares Objekt beispielsweise mehrmals mit sich selbst »multipliziert« werden, ohne dass es der Funktion mehrfach übergeben werden muss:

>>> list(itertools.product("AB", "AB", "AB"))
[('A', 'A', 'A'), ('A', 'A', 'B'), ('A', 'B', 'A'), ('A', 'B', 'B'),  
('B', 'A', 'A'), ('B', 'A', 'B'), ('B', 'B', 'A'), ('B', 'B', 'B')]
>>> list(itertools.product("AB", repeat=3))
[('A', 'A', 'A'), ('A', 'A', 'B'), ('A', 'B', 'A'), ('A', 'B', 'B'),  
('B', 'A', 'A'), ('B', 'A', 'B'), ('B', 'B', 'A'), ('B', 'B', 'B')]

 

23.4.14    repeat(object, [times]) 

Die Funktion repeat erzeugt einen Iterator, der nur das Objekt object zurückgibt, dies aber fortwährend. Optional können Sie über den Parameter times festlegen, wie viele Iterationsschritte durchgeführt werden sollen:

>>> list(itertools.repeat("A", 10))
['A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A']

Wenn der Parameter times nicht angegeben wird, läuft der von repeat zurückgegebene Iterator endlos.

 

23.4.15    starmap(function, iterable) 

Die Funktion starmap arbeitet ähnlich wie die Built-in Function map. Die Funktion function wird für jede in iterable enthaltene Parameterliste aufgerufen. Der von starmap erzeugte Iterator durchläuft die Ergebnisse dieser Funktionsaufrufe.

>>> list(itertools.starmap(max, [(1,2), (4,4,3,6), [2,3,9]]))
[2, 6, 9]

Im Beispiel wurde die Funktion starmap gemeinsam mit der Built-in Function max eingesetzt, um die jeweils größten Elemente der Tupel zu durchlaufen.

 

23.4.16    takewhile(predicate, iterable) 

Die Funktion takewhile ist das Gegenstück zu dropwhile. Sie erzeugt einen Iterator, der so lange die Elemente von iterable durchläuft, wie die Funktion predicate für die Elemente den Wert True zurückgibt. Sobald ein predicate-Aufruf den Wert False ergeben hat, bricht der Iterator ab.

>>> p = lambda x: x.islower()
>>> list(itertools.takewhile(p, "abcdefGHIjklMNOp"))
['a', 'b', 'c', 'd', 'e', 'f']

In diesem Fall wurde takewhile verwendet, um nur die Kleinbuchstaben am Anfang des übergebenen Strings zu durchlaufen.

 

23.4.17    tee(iterable, [n]) 

Die Funktion tee erzeugt n voneinander unabhängige Iteratoren über die Elemente von iterable. Standardmäßig werden n=2 Iteratoren erzeugt.

>>> list(itertools.tee([1,2,3,4]))
[<itertools._tee object at 0x7f26a9e69e48>, <itertools._tee object at 0x7f26a9e69f08>]
>>> [list(x) for x in itertools.tee([1,2,3,4])]
[[1, 2, 3, 4], [1, 2, 3, 4]]

Nach dem Aufruf von tee sollten nur noch die von tee zurückgegebenen Iteratoren verwendet werden und nicht mehr der als Parameter übergebene.

 

23.4.18    zip_longest([*iterables], [fillvalue]) 

Die Funktion zip_longest arbeitet ähnlich wie die Built-in Function zip. Der Unterschied ist, dass bei zip_longest stets das längste der übergebenen iterierbaren Objekte ausschlaggebend ist und fehlende Elemente bei den anderen Objekten mit fillvalue aufgefüllt werden.

>>> list(zip("ABC", "abcde"))
[('A', 'a'), ('B', 'b'), ('C', 'c')]
>>> list(itertools.zip_longest("ABC", "abcde"))
[('A', 'a'), ('B', 'b'), ('C', 'c'), (None, 'd'), (None, 'e')] 
>>> list(itertools.zip_longest("ABC", "abcde", fillvalue="-"))
[('A', 'a'), ('B', 'b'), ('C', 'c'), ('-', 'd'), ('-', 'e')