Vorlesungsskript 24

Operationen auf Iterables

Ein Iterable ist ein Objekt, das andere Objekte als Elemente enthält und es erlaubt, auf diese Elemente eins nach dem anderen zuzugreifen. Anders gesagt: Alles, worüber man mit Hilfe einer for-Schleife iterieren kann, ist ein Iterable.

Typische Iterables sind Datenstrukturen, bei denen sich die Elemente im Arbeitsspeicher befinden: Listen, Dictionarys, Sets, Tupel, Strings. Aber auch ein Dateiobjekt ist ein Iterable. Seine Elemente sind die Zeilen. Und wenn man beginnt, über ein Dateiobjekt zu iterieren, sind noch nicht unbedingt alle Zeilen von der Festplatte in den Arbeitsspeicher geladen.

Welcher Art die Iterables auch immer sind, Operationen auf Iterables spielen beim Programmieren eine extrem wichtige Rolle. Dabei geht es um das (nicht-destruktive) Erzeugen von neuen Iterables (Output-Iterables), oft auf Grundlage von bestehenden Iterables (Input-Iterables). Zwei der wichtigsten Operationen auf Iterables sind das Zuordnen (engl. mapping) und das Filtern.

Beim Zuordnen wird dieselbe Operation auf alle Elemente des Input-Iterables angewendet. Das Output-Iterable enthält die Ergebnisse. Das folgende Beispiel zeigt eine Funktion, die eine Zuordnung vornimmt. Sie nimmt eine Liste von Strings als Argument und gibt eine Liste zurück mit den gleichen Strings, aber in Kleinbuchstaben umgewandelt:

def map_lower(strings):
    result = []
    for string in strings:
        result.append(string.lower())
    return result

Beim Filtern wird auf jedes Element des Input-Iterables ein Test angewendet. Besteht es den Test, wird es in das Output-Iterable aufgenommen. Wenn nicht, dann nicht. Ein Beispiel für eine Funktion, die filtert, ist unsere alte Bekannte remove_stopwords:

def remove_stopwords(words, stopwords):
    result = []
    for word in words:
        if word not in stopwords:
            result.append(word)
    return result

Die obigen Funktionen stellen Operationen auf Iterables dar, weil sie Listen zurückgeben, und Listen sind Iterables. Operationen auf Iterables können aber eleganter, flexibler und effizienter bewerkstelligt werden. Hierfür stellt Python zwei spezielle Werkzeuge zur Verfügung: Generator-Funktionen und Comprehensions.

Generator-Funktionen

In den obigen Funktionen (map_lower und remove_stopwords) legen wir zunächst eine neue Liste an (result), füllen diese und geben sie am Ende mit return zurück. Mit Generator-Funktionen (engl. generator functions) können wir uns das Anlegen und Zurückgeben der Liste sparen und stattdessen jedes Element einzeln zurückgeben, und zwar mit dem Schlüsselwort yield. Python sorgt dann automatisch dafür, dass ein Iterable zurückgegeben wird, das diese Elemente enthält. So sieht die erste Funktion aus, jetzt als Generator-Funktion definiert:

def map_lower(strings):
    for string in strings:
        yield string.lower()

Und so die zweite Funktion:

def remove_stopwords(words, stopwords):
    for word in words:
        if word not in stopwords:
            yield word

Das ist deutlich kürzer und daher angenehmer zu schreiben und zu lesen. Man muss nur beachten, dass Generator-Funktionen keine Listen zurückgeben, sondern einen anderen Typ von Iterable, nämlich einen Generator. Über Generatoren kann man iterieren, aber sonst kann man nicht viel mit ihnen machen, man kann z.B. nicht direkt auf ein Element an einem bestimmten Index zugreifen, und gibt man einen Generator aus, enthält man nur einen kryptischen String. Man kann Generatoren aber mit der Funktion list (oder auch set) leicht in den gewünschten Sammeldatentyp umwandeln:

>>> words = ['The', 'company', 'was', 'sold', 'to', 'Google']
>>> stopwords = {'the', 'a', 'an', 'am', 'are', 'is', 'was', 'were', 'to'}
>>> words_lower = map_lower(words)
>>> words_lower
<generator object map_lower at 0x7f10b415d728>
>>> words_lower[1]
Traceback (most recent call last):
  File "", line 1, in 
TypeError: 'generator' object is not subscriptable
>>> words_lower = list(words_lower)
>>> words_lower
['the', 'company', 'was', 'sold', 'to', 'google']
>>> words_lower[1]
'company'
>>> content_words = list(remove_stopwords(words_lower, stopwords))
>>> content_words
['company', 'sold', 'google']

Dass Generator-Funktionen keine Listen zurückgeben, ist tatsächlich ein weiterer ihrer Vorteile. Will man nämlich mehrere Zuordnungs- und Filteroperationen hintereinander vornehmen, wäre das Anlegen immer neuer Listen nämlich ineffizient. Es reicht, wenn man das einmal am Ende macht. Hier wenden wir zum Beispiel unsere zwei Generator-Funktionen direkt hintereinander an:

>>> list(remove_stopwords(map_lower(words), stopwords))
['company', 'sold', 'google']

Komplexere Operationen mit Generator-Funktionen

Generator-Funktionen können mehr als nur zuordnen und filtern: Man kann damit gegenüber dem Input-Iterable neue Elemente ins Output-Iterable hinzufügen, mehrere Elemente zusammenfassen oder ein Element in mehrere aufteilen. Hier einige Beispiele:

Anstandsdame

Die folgende Generator-Funktion nimmt ein Iterable von Strings, die Jungen und Mädchen repräsentieren. Immer, wenn ein Junge neben einem Mädchen sitzt, wird dazwischen eine Anstandsdame (engl. chaperone) eingefügt:

def chaperonize(people):
    last_person = None
    for person in people:
        if {last_person, person} == {'boy', 'girl'}:
            yield 'chaperone'
	yield person
        last_person = person

>>> list(chaperonize(['boy', 'boy', 'girl', 'boy', 'girl']))
['boy', 'boy', 'chaperone', 'girl', 'chaperone', 'boy', 'chaperone', 'girl'

Paare addieren

Die folgende Generator-Funktion nimmt eine Liste mit einer geraden Anzahl von Zahlen und addiert immer zwei nebeneinander stehende:

def add_pairs(numbers):
    for i in range(0, len(numbers), 2):
        yield numbers[i] + numbers[i + 1]

>>> list(add_pairs([2, 3, 5, 7, 11, 13, 17, 19]))
[5, 12, 24, 36]

flatten

Hier ist die Funktion flatten, die verschachtelte Listen in eine flache Liste umwandelt, als Generator-Funktion geschrieben:

def flatten(L):
    for element in L:
         if isinstance(element, list):
              for subelement in flatten(element):
                  yield subelement
         else:
             yield element

>>> nested = [2, [3, 5, [7, 11]], [13], 17]
>>> flat = list(flatten(nested))
>>> flat
[2, 3, 5, 7, 11, 13, 17]

Die Funktion iteriert über die Listenelemente. Elemente, die nicht selbst Listen sind, werden einfach „geyieldet“. Ist ein Element selbst eine Liste, wird flatten rekursiv aufgerufen und dann jedes Element des Ergebnisses „geyieldet“.

for subelement in flatten(element):
    yield subelement

yield from flatten(element)

Comprehensions

Wenn wir beim Verarbeiten von Iterables nur zuordnen und filtern, können wir das noch kürzer schreiben, nämlich in einem einzigen Ausdruck. Wollen wir zum Beispiel jedem String seine Kleinbuchstaben-Version zuordnen, können wir das so tun:

>>> words = ['The', 'company', 'was', 'bought', 'by', 'Google']
>>> words_lower = [w.lower() for w in words]
>>> words_lower
['the', 'company', 'was', 'sold', 'to', 'google']

Und so können wir Stopwörter herausfiltern:

>>> content_words = [w for w in words_lower if w not in stopwords]
>>> content_words
['company', 'sold', 'google']

Die Ausdrücke in eckigen Klammern, die an eine Mischung aus Listen-Literalen und for-Schleifen erinnern, sind Listen-Comprehensions (manchmal auch Listen-Abstraktionen genannt). Ihre allgemeine Form ist die folgende:

[AUSDRUCK for ITERATIONSVARIABLE in INPUTSEQUENZ if BEDINGUNG]

INPUTSEQUENZ ist ein Iterable, über das die Comprehension iteriert, wie bei for-Schleifen. Bei jedem Durchlauf wird das nächste Element in der Variablen ITERATIONSVARIABLE gespeichert. Falls dann BEDINGUNG wahr ist (oder fehlt), wird der Ausdruck AUSDRUCK ausgewertet und das Ergebnis in die Output-Liste übernommen. Die Comprehension gibt eine Liste mit allen übernommenen Elementen zurück.

Im ersten Beispiel haben wir nur zugeordnet und nicht gefiltert, weil wir keinen if-Teil verwendet haben. Im zweiten Beispiel haben wir nur gefiltert und nicht zugeordnet, weil AUSDRUCK mit ITERATIONSVARIABLE, also Input-Elemente mit Output-Elementen identisch waren. Wir können das Filtern und Zuordnen auch in einer Comprehension kombinieren. Um zum Beispiel gleichzeitig Stopwörter herauszufiltern und Wörter in Kleinbuchstaben umzuwandeln:

>>> content_words = [w.lower() for w in words if w.lower() not in stopwords]
>>> content_words
['company', 'sold', 'google']

Neben Listen-Comprehensions gibt es noch drei weitere Arten von Comprehensions. Hier eine Übersicht über ihre Formen:

Die Formen der verschiedenen Comprehensions unterscheiden sich vor allem durch die Klammern, die sie umschließen. Dictionary-Comprehensions haben außerdem statt dem einfachen AUSDRUCK ein SCHLÜSSEL: WERT-Paar.

Set-Comprehensions geben als Output-Iterable keine Liste, sondern ein Set zurück, wodurch natürlich die Reihenfolge und Duplikate verloren gehen. Für Dictionary-Comprehensions gilt Ähnliches, wobei hier sowohl Schlüssel als auch Werte generiert werden. Generator-Comprehensions sind nützlich, wenn das Output-Iterable zur Weiterverarbeitung in einer for-Schleife, einer weiteren Comprehension oder einer Generator-Funktion gedacht ist und das überflüssige Erzeugen einer Liste mit dem Zwischenergebnis vermieden werden soll.

Das folgende Beispiel illustriert die Unterschiede zwischen den verschiedenen Comprehensions:

>>> [x % 3 for x in range(10)]
[0, 1, 2, 0, 1, 2, 0, 1, 2, 0]
>>> {x % 3 for x in range(10)}
{0, 1, 2}
>>> {x: x % 3 for x in range(10)}
{0: 0, 1: 1, 2: 2, 3: 0, 4: 1, 5: 2, 6: 0, 7: 1, 8: 2, 9: 0}
>>> (x % 3 for x in range(10))
<generator object <genexpr> at 0x7f10b21c3830>