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.