54. Iteratoren und Generatoren

Warnung: Die folgenden Geschichten sind relativ neu. In der Regel wollt ihr Python 2.3 haben, um damit zu spielen. Siehe aber unten zu __future__, Iteratoren selbst gibts seit Python 2.2.

Die Callbacks in der letzten Folie sind häufig eher umständlich. Wäre es nicht einfacher, wenn man über einen Baum wie über eine Liste iterieren könnte: for node in tree:?

Hier hilft das Iterator-Pattern. In Python: Iteratoren implementieren eine Methode next, die das „nächste” Objekt zurückgeben oder eine StopIteration-Exception auslösen. Aus technischen Gründen müssen Iteratoren auch noch die Methode __iter__ unterstützen – diese gibt einfach das Objekt selbst zurück (return self). Man spricht dann auch davon, dass ein Objekt das Iterator-Protokoll implementiert.

Analog kann ein Objekt auch das Sequenzen-Protokoll und damit mindestens mal __len__ und __getitem__ implementieren – Python kann über ein solches Objekt „aus dem Stand” iterieren, so dass quasi automatisch

for item in ob:
  ...bla...

in

for index in range(len(ob)):
  item = ob[index]
  ...bla...

verwandelt wird.

Richtige Iteratoren sind aber meistens schneller und fast immer eleganter.

Ein Beispiel, das eine Iteration über die ersten seqLen Werte der Fakultätsfunktion iteriert:

class FacIterManual:
  def __init__(self, seqLen):
    self.seqLen = seqLen
    self.curFac = 1
    self.curInd = 0

  def __iter__(self):
    return self

  def next(self):
    if self.curInd>=self.seqLen:
      raise StopIteration
    self.curFac = max(1, self.curInd*self.curFac)
    self.curInd += 1
    return self.curFac

Schreibt man for v in ob, versucht Python die __iter__-Methode von ob auszuführen und iteriert über das Ergebnis. Die eingebaute Funktion iter liefert einen Iterator über ihr Argument. Letzteres klappt natürlich nur, wenn das Argument tatsächlich eine __iter__-Methode hat oder das Sequenzenprotokoll implementiert. iter ist vor allem dann nützlich, wenn man einen schon bestehenden Iterator recyclen will. Vgl. auch FacIterCheat in iterobs.py (Anhang).

Generatoren

Im letzten Beispiel mussten wir curFac und curInd als Zustand im Objekt mitschleppen. Bei komplizierteren Problemen ist das lästig.

Abhilfe: Generatoren. Ein Generator sieht aus wie eine Funktion, nur, dass statt return das Schlüsselwort yield steht (es ist erst seit Python 2.3 ein Schlüsselwort, in Python 2.2 muss man es noch mit from __future__ import generators „freischalten”, vorher gab es keine Generatoren). Ruft man einen Generator auf, bekommt man einen Iterator als Ergebnis. Lest den letzten Satz nochmal. Ja, ihr solltet ein wenig verwirrt sein. Dieser Iterator sorgt quasi dafür, dass als würde bei jeder Ausführung eines yield-Statements die Funktion „eingefroren” und der Ausdruck hinter yield als Ergebnis von next verwendet wird. Wenn das nächste Element der Iteration angefragt wird (also next aufgerufen wird), wird die Funktion „aufgetaut” und läuft weiter, als wäre nichts geschehen, bis das nächste yield-Statement kommt.

Unser Beispiel mit den Fakultäten mit einem Generator:

class FacIterGenerator(FacIterator):
  def __iter__(self):
    curFac = 1
    yield curFac # 0! = 1
    for i in range(1, self.seqLen):
      curFac = curFac*i
      yield curFac

Es ist ohne Probleme möglich, Iteratoren aus Methoden zurückzugeben. Beispiel Dictionaries: Es gibt itervalues, iterkeys, iteritems. iter(dict) ist iterkeys.

Ein weiteres Beispiel für die Nützlichkeit von Generatoren ist enumerate. Diese Funktion ist ab Python 2.3 eingebaut und liefert aus einer Sequenz (oder überhaupt etwas Iterablem) einen Iterator über Tupel von (index, element) für alle Elemente der Sequenz. Es ist natürlich nicht schwer, sowas ohne Iteratoren nachzurüsten:

def enumerate(seq):
  return [(i, seq[i]) for i in range(len(seq))]

– wenn wir das so machen, müssen wir aber eine, potenziell lange, Liste erzeugen, nur, um über sie zu iterieren. Das braucht Zeit und vor allem Speicherplatz.

Eleganter geht das so (gleich mit Code, der dafür sorgt, dass, wenn enumerate schon definiert ist, wir diese Definition – hinter der sich hoffentlich schnellerer Code verbirgt – nicht überschreiben):

from __future__ import generators
try:
  enumerate(range(2))
except NameError:
  def enumerate(seq):
    ind = 0
    for el in seq:
      yield ind, el
      ind += 1

Leute, die Iteratoren mögen, sollten sich weiter unbedingt das sehr schöne Modul itertools (ab Python 2.3) ansehen.

Übungen zu diesem Abschnitt

Ihr solltet euch wenigstens an den rötlich unterlegten Aufgaben versuchen

(1)

Studiert das angehängte Modul iterobs.py und macht euch klar, wo die Vor- und Nachteile der verschiedenen verwendeten Techniken liegen.

(2)

Erweitert BinaryTree so, dass ihr einfach etwas wie

for node in someTree:
  print node.getValue()

schreiben könnt und danach die Knoten in preorder ausgegeben werden. Das ist hier etwas tricky, weil ihr dazu rekursive Iteratoren braucht. Ihr solltet __iter__ als Generator implementieren, der zunächst den Node selbst yieldet und dann das yieldet, was die Iteratoren der Kinder zurückgeben.

(3)

Baut BinaryTree noch so um, dass sie Methoden iterPreorder, iterPostorder und iterInorder haben, die jeweils Iteratoren zurückgeben, die in der entsprechenden Traversierung über den Baum gehen.

(4)

Im os-Modul gibt es seit 2.3 die Funktion walk, die ebenfalls ein Generator ist (d.h. einen Iterator zurückgibt – in diesem Fall über alle Dateien und Verzeichnisse unterhalb eines Verzeichnisses). Schreibt z.B. ein Programm, das die Namen aller Dateien unterhalb des augenblicklichen Verzeichnisses ausgibt, in denen etwas vorkommt, was auf einen bestimmten regulären Ausdruck passt.

Vergleicht das mit der Vorgehensweise, die beim älteren os.path.walk aus dem os.path-Modul nötig ist.

(5)

Für Leute, die sich itertools angesehen haben: Baut einen enumerate-Generator mit itertools.

Dateien zu diesem Abschnitt


Markus Demleitner

Copyright Notice