Galileo Computing < openbook > Galileo Computing - Professionelle Bücher. Auch für Einsteiger.

...powered by haas.homelinux.net...

Inhaltsverzeichnis
1 Einleitung
2 Überblick über Python
3 Die Arbeit mit Python
4 Der interaktive Modus
5 Grundlegendes zu Python-Programmen
6 Kontrollstrukturen
7 Das Laufzeitmodell
8 Basisdatentypen
9 Benutzerinteraktion und Dateizugriff
10 Funktionen
11 Modularisierung
12 Objektorientierung
13 Weitere Spracheigenschaften
14 Mathematik
15 Strings
16 Datum und Zeit
17 Schnittstelle zum Betriebssystem
18 Parallele Programmierung
19 Datenspeicherung
20 Netzwerkkommunikation
21 Debugging
22 Distribution von Python-Projekten
23 Optimierung
24 Grafische Benutzeroberflächen
25 Python als serverseitige Programmiersprache im WWW mit Django
26 Anbindung an andere Programmiersprachen
27 Insiderwissen
28 Zukunft von Python
A Anhang
Stichwort

Download:
- ZIP, ca. 4,8 MB
Buch bestellen
Ihre Meinung?

Spacer
 <<   zurück
Python von Peter Kaiser, Johannes Ernesti
Das umfassende Handbuch - Aktuell zu Python 2.5
Buch: Python

Python
gebunden, mit CD
819 S., 39,90 Euro
Galileo Computing
ISBN 978-3-8362-1110-9
Pfeil 13 Weitere Spracheigenschaften
  Pfeil 13.1 Exception Handling
    Pfeil 13.1.1 Eingebaute Exceptions
    Pfeil 13.1.2 Werfen einer Exception
    Pfeil 13.1.3 Abfangen einer Exception
    Pfeil 13.1.4 Eigene Exceptions
    Pfeil 13.1.5 Erneutes Werfen einer Exception
  Pfeil 13.2 List Comprehensions
  Pfeil 13.3 Docstrings
  Pfeil 13.4 Generatoren
  Pfeil 13.5 Iteratoren
  Pfeil 13.6 Interpreter im Interpreter
  Pfeil 13.7 Geplante Sprachelemente
  Pfeil 13.8 Die with-Anweisung
  Pfeil 13.9 Function Decorator
  Pfeil 13.10 assert
  Pfeil 13.11 Weitere Aspekte der Syntax
    Pfeil 13.11.1 Umbrechen langer Zeilen
    Pfeil 13.11.2 Zusammenfügen mehrerer Zeilen
    Pfeil 13.11.3 String conversions


Galileo Computing - Zum Seitenanfang

13.5 Iteratoren  topZur vorigen Überschrift

Sie sind bei der Lektüre dieses Buchs schon oft mit dem Begriff »iterierbares Objekt« konfrontiert worden, wobei Ihnen bisher nur gesagt wurde, dass Sie solche Instanzen beispielsweise mit einer for-Schleife durchlaufen oder bestimmten Funktionen, wie list, als Parameter übergeben konnten. In diesem Kapitel werden wir uns nun endlich mit den Hintergründen und Funktionsweisen dieser Objekte befassen.

Ein sogenannter Iterator ist eine Abstraktionsschicht, die es ermöglicht, auf die Elemente einer Sequenz über eine standardisierte Schnittstelle zuzugreifen. Bisher mussten Sie für den Zugriff auf die Elemente einer Sequenz oder eines Dictionarys immer eine Referenz auf den Container, also die list- oder dict-Instanz, sowie den Index des jeweiligen Elements benutzen. Dies hatte den Nachteil, dass man dafür immer die Art der Indizes kennen musste, die die Datenstruktur anbot, weshalb man den Code für jeden Datentyp anpassen musste. Nun ist aber insbesondere das Durchlaufen aller Elemente einer Sequenz oder eines anderen Objekts, das mehrere Elemente speichert, eine Operation, die unabhängig von dem jeweiligen Datentyp immer auf das Gleiche hinausläuft. Um beispielsweise alle Elemente einer Sequenz auszugeben, benötige ich nacheinander Zugriff auf die Elemente, wobei es mir egal sein kann, ob dieser nun über numerische Indizes oder irgendeine andere Art von Schlüsseln bereitgestellt wird.

Deshalb wurden Iteratoren eingeführt, mit denen der jeweilige Datentyp sich selbst um die Bereitstellung der Elemente kümmert und die konkrete Implementation hinter einer einheitlichen Schnittstelle versteckt. Die dazu festgelegte Schnittstelle heißt Iterator-Protokoll und ist folgendermaßen definiert:

Jede iterierbare Instanz muss eine parameterlose __iter__-Methode implementieren, die ein Iterator-Objekt zurückgibt. Das Iterator-Objekt muss ebenfalls eine __iter__-Methode besitzen, die einfach eine Referenz auf das Objekt selbst zurückgibt. Außerdem muss es eine next-Methode aufweisen, die bei jedem Aufruf das nächste Element des zu durchlaufenden Containers zurückgibt. Ist das Ende der Iteration erreicht, muss die next-Methode die StopIteration-Exception mittels raise werfen.

Auf der anderen Seite, also da, wo die Iteration selbst stattfindet, muss, um das Durchleufen zu beginnen, mittels der Built-in Function iter eine Referenz auf den Iterator ermittelt werden. iter(objekt) ruft dabei die __iter__-Methode der Instanz objekt auf und reicht das Ergebnis als Rückgabewert an die aufrufende Ebene weiter. Von der zurückgegebenen Iterator-Instanz kann dann so lange die next-Methode aufgerufen werden, bis diese die StopIteration-Exception wirft.

Um mehr Licht in diese abstrakte Beschreibung zu bringen, werden wir eine Klasse entwickeln, die uns über die Fibonacci-Folge iterieren lässt. Die Fibonacci-Folge ist eine Folge aus ganzen Zahlen, wobei jedes Element f(n) durch die Summe seiner beiden Vorgänger f(n-2) + f(n-1) berechnet werden kann. Die beiden ersten Elemente werden per Definition auf f(1) = f(2) = 1 gesetzt. Der Anfang der unendlichen Folge ist in der nachstehenden Tabelle gezeigt:


Tabelle 13.1  Die ersten 14 Elemente der Fibonacci-Folge
n

1

2

3

4

5

6

7

8

9

10

11

12

13

14

f(n)

1

1

2

3

5

8

13

21

34

55

89

144

233

377


Die Folge kann unter anderem dazu verwendet werden, die idealisierte Entwicklung von Kaninchenpopulationen zu berechnen. Außerdem konvergiert der Quotient von aufeinanderfolgenden Elementen für große n gegen den goldenen Schnitt ( = 1,618…), einem Verhältnis, das sich sehr oft in der Natur findet.

class Fibonacci(object): 
    def __init__(self, max_n): 
        self.MaxN = max_n 
        self.N = 0 
        self.A = 0 
        self.B = 0 
 
    def __iter__(self): 
        self.N = 0 
        self.A = 0 
        self.B = 1 
        return self 
 
    def next(self): 
        if self.N < self.MaxN: 
            self.N += 1 
            self.A, self.B = self.B, self.A + self.B 
            return self.A 
        else: 
            raise StopIteration

Unsere Klasse Fibonacci erwartet als Parameter für ihren Konstruktor die Nummer des Elements, nach dem die Iteration stoppen soll. Diese Nummer speichern wir in dem privaten Attribut MaxN und zählen dann mit dem Attribut N, wie viele Elemente bereits zurückgegeben wurden. Um uns zwischen den next-Aufrufen die aktuelle Position in der Folge zu merken und um das nächste Element berechnen zu können, speichern wir das zuletzt zurückgegebene Element und seinen Nachfolger in den Attributen A und B der Fibonacci-Klasse. Wir werden keine separate Iterator-Klasse definieren und lassen deshalb die __iter__-Methode eine Referenz auf die Fibonacci-Instanz selbst, also self, zurückgeben. Außerdem müssen beim Beginn des Durchlaufens die Speicher für das letzte nächste Element mit ihren Anfangswerten 0 bzw. 1 belegt und der N-Zähler auf 0 gesetzt werden. Die next-Methode kümmert sich um die Berechnung des aktuellen Elements der Folge und aktualisiert die Zwischenspeicher und den Zähler. Ist das Ende der gewünschten Teilfolge erreicht, wird StopIteration geworfen.

Die Klasse lässt sich nun mit allen Konstrukten verarbeiten, die das Iterator-Protokoll unterstützen, wie beispielsweise die for-Schleife und die Built-in Functions list oder sum:

>>> for f in Fibonacci(14): 
        print f, 
1 1 2 3 5 8 13 21 34 55 89 144 233 377 
>>> list(Fibonacci(16)) 
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987] 
>>> sum(Fibonacci(60)) 
4052739537880L

Mit einer kleinen Subklasse von Fibonacci können wir auch einen Iterator erzeugen, der uns die Verhältnisse zweier aufeinanderfolgender Fibonacci-Zahlen durchlaufen lässt. Dabei sieht man sehr schnell, dass sich die Quotienten dem goldenen Schnitt nähern. Die Subklasse muss nur die next-Methode der Fibonacci-Klasse überschreiben und dann anstatt der Folgenelemente die Quotienten zurückgeben. Dabei kommt es uns zugute, dass wir in dem Attribut B bereits den Wert des nächsten Elements im Voraus berechnen. Die Implementation sieht dann folgendermaßen aus:

class GoldenerSchnitt(Fibonacci): 
    def next(self): 
        Fibonacci.next(self) 
        return float(self.B) / self.A

Die Konvertierung von self.B in eine Gleitkommazahl ist deshalb notwendig, damit keine Ganzzahldivision durchgeführt wird und die Nachkommastellen nicht verloren gehen. Schon die ersten vierzehn Elemente dieser Folge lassen die Konvergenz erkennen. (Der goldene Schnitt, bis auf sechs Nachkommastellen gerundet, lautet 1,618034.)

>>> for g in GoldenerSchnitt(14): 
    print "%.6f" % g, 
1.000000 2.000000 1.500000 1.666667 1.600000 1.625000 1.615385  
1.619048 1.617647 1.618182 1.617978 1.618056 1.618026 1.618037

Es ist durchaus üblich, die __iter__-Methode eines iterierbaren Objekts als Generator zu implementieren. Im Falle unserer Fibonacci-Folge läuft diese Technik auf wesentlich eleganteren Code hinaus, weil wir uns nun nicht mehr den Status des Iterators zwischen den next-Aufrufen merken müssen und auch die explizite Definition von next entfällt:

class Fibonacci2(object): 
    def __init__(self, max_n): 
        self.MaxN = max_n 
 
    def __iter__(self): 
        n = 0 
        a, b = 0, 1 
        for n in xrange(self.MaxN): 
            a, b = b, a + b 
            yield a

Instanzen der Klasse Fibonacci2 würden sich bei der Iteration genau wie die Lösung ohne Generator-Ansatz verhalten:

>>> list(Fibonacci2(10)) 
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

Allerdings ließe sich die Klasse GoldenerSchnitt nicht mehr so einfach als Subklasse von Fibonacci2 implementieren, da die Zwischenspeicherung der Werte und auch die next-Methode nun in dem Generator gekapselt sind.

Benutzung von Iteratoren

Nun haben Sie gelernt, wie Sie eine gültige Iterator-Schnittstelle in ihren eigenen Klassen definieren können. Wir werden diese Thematik nun von der anderen Seite betrachten und uns damit beschäftigen, wie die Benutzung dieser Iterator-Schnittstelle aussieht, damit Sie auch Funktionen schreiben können, die nicht Listen oder andere Sequenzen, sondern beliebige iterierbare Instanzen verarbeiten können.

Wir betrachten zu diesem Zweck eine einfache for-Schleife und werden dann hinter die Kulissen schauen, indem wir eine äquivalente Schleife ohne for programmieren werden, die das Iterator-Protokoll explizit benutzt:

>>> for i in xrange(10): 
        print i, 
0 1 2 3 4 5 6 7 8 9

Wie Sie bereits wissen, benötigen wir zum Durchlaufen einer Sequenz das dazugehörige Iterator-Objekt. Dieses liefert uns die Built-in Function iter, die, wie schon in der Einleitung erklärt, die __iter__-Methode des übergebenen Objekts aufruft:

>>> iter(xrange(10)) 
<rangeiterator object at 0x01446608>

Über die next-Methode das Iterator-Objekts können wir nun der Reihe nach alle Elemente ermitteln:

>>> i = iter(xrange(3)) 
>>> i.next() 
0 
>>> i.next() 
1 
>>> i.next() 
2 
>>> i.next() 
Traceback (most recent call last): 
  File "<pyshell#41>", line 1, in <module> 
    i.next() 
StopIteration

Wird i.next nach dem Zurückgeben des letzten Elements erneut aufgerufen, wirft die Methode erwartungsgemäß die StopIteration-Exception. Wenn wir diese Exception mit einer try/except-Anweisung abfangen, können wir die for-Schleife folgendermaßen nachbauen:

>>> i = iter(xrange(10)) 
>>> while True: 
        try: 
            print i.next(), 
        except StopIteration: 
            break 
0 1 2 3 4 5 6 7 8 9

Natürlich soll dieses Beispiel keine Aufforderung sein, in Zukunft keine for-Schleifen mehr zu benutzen. Das Ziel unserer Bemühungen war es, Ihnen ein besseres Verständnis für die Benutzung von Iteratoren zu geben. Die for-Schleife in Python ist natürlich nicht wie in dem Beispiel implementiert, sondern in eine optimierte Routine des Python-Interpreters ausgelagert. Dadurch erlaubt der Iterator-Ansatz auch eine Geschwindigkeitssteigerung, weil die Iteration durch eine maschinennahe C-Schleife übernommen werden kann.

Die for-Schleife kann im Übrigen auch über einen Iterator selbst iterieren und muss diesen nicht selbst erzeugen. Die folgenden beiden Schleifen sind also äqivalent:

>>> for i in xrange(3): 
        print i, 
0 1 2 
>>> for i in iter(xrange(3)): 
        print i, 
0 1 2

Dass for dabei, wie in der alternativen while-Schleife verdeutlicht, noch einmal selbst iter aufruft, ist insofern kein Problem, als die __iter__-Methode eines Iterator-Objekts eine Referenz auf das Objekt selbst zurückgeben muss. Ist a ein Iterator-Objekt, so gilt immer a == iter(a), wie das folgende Beispiel noch einmal verdeutlicht:

>>> a = iter(xrange(10))  # einen xrange-Iterator erzeugen 
>>> a == iter(a) 
True

Im Gegensatz dazu muss die __iter__-Methode eines iterierbaren Objekts weder eine Referenz auf sich selbst noch immer dieselbe Iterator-Instanz zurückgeben:

>>> a = xrange(10)  # ein iterierbares Objekt erzeugen 
>>> iter(a) == iter(a) 
False

Im Umkehrschluss bedeutet dies, dass die Built-in Function iter bei Aufrufen für dasselbe iterierbare Objekt verschiedene Iteratoren zurückgeben kann.

Dieses Verhalten kann zu relativ schwierig auffindbaren Fehlern führen. Stellen Sie sich einmal vor, Sie lesen eine Textdatei ein, die eine bestimmte Schlüsselzeile enthält. Alles, was vor dieser Schlüsselzeile steht, ist für Ihr Programm vollkommen uninteressant, denn Sie interessieren sich nur für den dahinterstehenden Teil. Da Sie bereits wissen, dass man über die Zeilen einer Datei mittels einer eleganten for-Schleife iterieren kann, könnten Sie auf folgende Scheinlösung kommen:

datei = open("textdatei.txt", "r") 
for zeile in datei: 
    if zeile.strip() == "Schlüsselzeile": 
        break
for zeile in datei: print zeile

Der Grund, warum mit diesem Miniprogramm nicht nur die interessanten Zeilen hinter der "Schlüsselzeile", sondern alle Zeilen der Datei ausgegeben werden, liegt darin, dass beide Schleifen jeweils ihren eigenen Iterator für die Datei erzeugt haben. Deshalb wurde zu Beginn der zweiten for-Schleife die Leseposition innehalb der Datei wieder an den Anfang gesetzt und somit alles ausgegeben. Mit ein paar kleinen Änderungen können wir die Schleifen aber dazu zwingen, sich einen Iterator zu teilen, und erreichen damit das gewünschte Verhalten:

datei = open("textdatei.txt", "r") 
datei_iterator = iter(datei) 
for zeile in datei_iterator: 
    if zeile.strip() == "Schlüsselzeile": 
        break
for zeile in datei_iterator: print zeile

Dadurch, dass die impliziten iter-Aufrufe am Anfang der beiden for-Schleifen nun Referenzen auf denselben Iterator zurückgeben, erscheinen nur die interessanten Informationen auf dem Bildschirm. Es kann also in manchen Fällen durchaus sinnvoll sein, explizit Iteratoren zu erzeugen und mit diesen zu arbeiten.

Nachteile von Iteratoren gegenüber dem direkten Zugriff über Indizes

Neben den schon angesprochenen Vorteilen, dass einmal geschriebener Code für alle Datentypen, die das Iterator-Interface implementieren, gilt und dass durch die maschinennahe Implementation der Schnittstelle die Ausführung der Programme beschleunigt werden kann, gibt es auch Nachteile.

Iteratoren eignen sich hervorragend, um alle Elemente einer Sequenz zu durchlaufen und dies einheitlich für alle Container-Datentypen umzusetzen. Mit Indizes ist aber auch möglich, in beliebiger Reihenfolge auf die Elemente zuzugreifen und ihre Werte zu verändern, was mit dem Iterator-Ansatz nicht möglich ist.

Insofern lassen sich die Indizes nicht vollständig durch Iteratoren ersetzen, sondern werden für Spezialfälle durch sie ergänzt.

Alternative Definition für iterierbare Objekte

Neben der oben beschriebenen Definition für iterierbare Objekte gibt es noch eine weitere Möglichkeit, eine Klasse iterierbar zu machen. Da es bei sehr vielen Folgen und Containern möglich ist, die Elemente einfach durchzunummerieren und über ganzzahlige Indizes anzusprechen, haben sich die Python-Entwickler dazu entschlossen, dass ein Objekt schon dann iterierbar ist, wenn man seine Elemente über die __getitem__-Methode, also den []-Operator, ansprechen kann. Ruft man die Built-in Function iter mit einer solchen Instanz als Parameter auf, kümmert Python sich um die Erzeugung des Iterators. Bei jedem Aufruf der next-Methode des erzeugten Iterators wird die __getitem__-Methode der iterierbaren Instanz aufgerufen, wobei immer eine Ganzzahl als Parameter übergeben wird. Die Zählung der übergebenen Indizes beginnt bei 0 und endet erst, wenn die __getitem__-Methode einen IndexError produziert, sobald ein ungültiger Index übergeben wurde.

Beispielsweise könnte eine Klasse zum Iterieren über die ersten max_n Quadratzahlen folgendermaßen aussehen, wenn sie zudem noch das Bestimmen ihrer Länge mittels len unterstützt:

class Quadrate(object): 
    def __init__(self, max_n): 
        self.MaxN = max_n 
 
    def __getitem__(self, index): 
        index += 1 # 0*0 ist nicht sehr interessant... 
        if index > len(self) or index < 1: 
            raise IndexError 
        return index*index 
 
    def __len__(self): 
        return self.MaxN

Zur Demonstration dieses versteckten Iterators lassen wir uns eine Liste mit den ersten zwanzig Quadratzahlen ausgeben:

>>> list(Quadrate(20)) 
[1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400]

Es bleibt noch zu sagen, dass diese Art von Iterator-Definition nur in seltenen Fällen benutzt werden sollte, da sie einerseits wenig elegant und andererseits meistens langsamer als eine explizite Implementation des Iterator-Protokolls ist.

Funktionsiteratoren

Die letzte Möglichkeit, in Python auf Iteratoren zurückzugreifen, stellen sogenannte Funktionsiteratoren dar. Funktionsiteratoren sind Objekte, die eine bestimmte Funktion so lange aufrufen, bis diese einen bestimmten Wert, den Terminator der Folge, zurückgibt. Einen Funktionsiterator kann man mit der Built-in Function iter erzeugen, wobei als erster Parameter eine Referenz auf die Funktion, über die man iterieren möchte, und als zweiter Parameter der Wert des Terminators übergeben wird.

iter(funktion, terminator)

Ein gutes Beispiel ist die Methode readline des file-Objekts, die so lange den Wert der nächsten Zeile zurückgibt, bis das Ende der Datei erreicht wurde. Wenn sich keine weiteren Daten mehr hinter der aktuellen Leseposition der file-Instanz befinden, gibt readline einen leeren String zurück. Läge eine Datei namens freunde.txt, die die vier Namen "Lucas", "Florian", "Lars" und "John" in je einer separaten Zeile enthält, so könnten wir folgendermaßen über sie iterieren und würden die nachstehende Ausgabe erhalten:

>>> datei = open("freunde.txt") 
>>> for zeile in iter(datei.readline, ""): 
        print zeile.strip(), 
Lucas Florian Lars John

Anmerkung
Dieses Beispiel dient nur der Veranschaulichung von Funktionsiteratoren. Über die Zeilen einer Datei können Sie natürlich auch weiterhin direkt mit

>>> for zeile in datei: 
...     print zeile.strip(),
iterieren.




Ihr Kommentar

Wie hat Ihnen das <openbook> gefallen? Wir freuen uns immer über Ihre freundlichen und kritischen Rückmeldungen.






 <<   zurück
  
  Zum Katalog
Zum Katalog: Python






Python
bestellen
 Ihre Meinung?
Wie hat Ihnen das <openbook> gefallen?
Ihre Meinung

 Buchtipps
Zum Katalog: Linux






 Linux


Zum Katalog: Ubuntu GNU/Linux






 Ubuntu GNU/Linux


Zum Katalog: Praxisbuch Web 2.0






 Praxisbuch Web 2.0


Zum Katalog: UML 2.0






 UML 2.0


Zum Katalog: Praxisbuch Objektorientierung






 Praxisbuch Objektorientierung


Zum Katalog: Einstieg in SQL






 Einstieg in SQL


Zum Katalog: IT-Handbuch für Fachinformatiker






 IT-Handbuch für Fachinformatiker


 Shopping
Versandkostenfrei bestellen in Deutschland und Österreich
InfoInfo