Zurückgestellt

Dieses PEP wurde zurückgestellt. Kopierbare Iteratoren sind eine nette Idee, aber nach vier Jahren ist keine Implementierung oder breites Interesse entstanden.

Zusammenfassung

Dieses PEP schlägt vor, dass einige Iteratortypen flache Kopien ihrer Instanzen unterstützen sollten, indem sie eine Methode __copy__ bereitstellen, die bestimmte Anforderungen erfüllt, und es zeigt, wie Code, der einen Iterator verwendet, eine solche __copy__-Methode, falls vorhanden, nutzen könnte.

Aktualisierung und Kommentare

Unterstützung für __copy__ wurde in Py2.4’s itertools.tee() aufgenommen.

Das Hinzufügen von __copy__-Methoden zu bestehenden Iteratoren ändert das Verhalten unter tee(). Derzeit bleiben die kopierten Iteratoren an den ursprünglichen Iterator gebunden. Wenn der ursprüngliche Iterator fortschreitet, tun dies auch alle Kopien. Gute Praxis ist es, das Original zu überschreiben, damit keine Anomalien auftreten: a,b=tee(a). Code, der diese Praxis nicht befolgt, könnte eine semantische Änderung feststellen, wenn eine __copy__-Methode zu einem Iterator hinzugefügt wird.

Motivation

In Python bis 2.3 erlauben die meisten integrierten Iteratortypen dem Benutzer nicht, ihre Instanzen zu kopieren. Vom Benutzer erstellte Iteratoren, die es ihren Clients erlauben, copy.copy auf ihren Instanzen aufzurufen, geben möglicherweise – oder auch nicht – als Ergebnis der Kopie ein separates Iteratorobjekt zurück, das unabhängig vom Original durchlaufen werden kann.

Derzeit ist die "Unterstützung" für copy.copy in einem vom Benutzer erstellten Iteratortyp fast immer "zufällig" – d.h. die Standardmechanismen der copy-Methode im copy-Modul der Python-Standardbibliothek erstellen und geben eine Kopie zurück. Die Kopie ist jedoch nur dann unabhängig durchlauffähig in Bezug auf das Original, wenn der Aufruf von .next() auf einer Instanz dieser Klasse zufällig den Instanzzustand ändert, indem nur Attribute an neue Werte gebunden werden und nicht bestehende Werte von Attributen mutiert werden.

Zum Beispiel wird ein Iterator, dessen "Index"-Zustand als Ganzzahlattribut gespeichert ist, wahrscheinlich brauchbare Kopien liefern, da (da ganze Zahlen unveränderlich sind) .next() dieses Attribut wahrscheinlich nur neu zuweist. Andererseits wird ein anderer Iterator, dessen "Index"-Zustand als Listenattribut gespeichert ist, wahrscheinlich dasselbe Listenobjekt mutieren, wenn .next() ausgeführt wird, und daher werden Kopien eines solchen Iterators nicht separat und unabhängig vom Original durchlauffähig sein.

Angesichts der aktuellen Situation ist copy.copy(it) auf einem Iteratorobjekt nicht sehr nützlich und wird daher auch nicht weit verbreitet verwendet. Es gibt jedoch viele Fälle, in denen es nützlich ist, einen "Schnappschuss" eines Iterators als "Lesezeichen" zu erhalten, um die Sequenz weiter zu verarbeiten und später von diesem Lesezeichen an erneut durch dieselbe Sequenz zu iterieren. Um solche "Lesezeichen" zu unterstützen, ist im Modul itertools in 2.4 eine Funktion 'tee' hinzugekommen, die wie folgt verwendet wird:

it, bookmark = itertools.tee(it)

Der vorherige Wert von 'it' darf nicht mehr verwendet werden, weshalb dieses typische idiomatische Muster den Namen neu zuweist. Nach diesem Aufruf sind 'it' und 'bookmark' unabhängig durchlauffähige Iteratoren auf derselben zugrunde liegenden Sequenz wie der ursprüngliche Wert von 'it': dies erfüllt die Anwendungsanforderungen für "Iterator-Kopien".

Wenn jedoch itertools.tee keine Hypothesen über die Natur des übergebenen Iterators machen kann, muss es alle Elemente im Speicher speichern, durch die einer der beiden 'tee'-Iteratoren, aber noch nicht beide, fortgeschritten ist. Dies kann in Bezug auf den Speicher sehr kostspielig sein, wenn die beiden Iteratoren sich in ihrem Fortschritt sehr weit voneinander entfernen; tatsächlich kann es in einigen Fällen vorzuziehen sein, eine Liste aus dem Iterator zu erstellen, um die Teilsequenz wiederholt durchlaufen zu können, oder, wenn dies zu kostspielig ist, Elemente auf der Festplatte zu speichern, um sie wiederholt durchlaufen zu können.

Dieses PEP schlägt eine weitere Idee vor, die in einigen wichtigen Fällen itertools.tee mit minimalen Speicherkosten ermöglicht; Benutzercode kann die Idee gelegentlich auch nutzen, um zu entscheiden, ob ein Iterator kopiert, eine Liste daraus erstellt oder eine Hilfsplattendatei verwendet werden soll.

Der entscheidende Punkt ist, dass einige wichtige Iteratoren, wie diejenigen, über die die integrierte Funktion iter Sequenzen durchläuft, intrinsisch leicht zu kopieren wären: einfach ein weiterer Verweis auf dieselbe Sequenz und eine Kopie des ganzzahligen Index. In Python 2.3 geben diese Iteratoren den Zustand jedoch nicht preis und unterstützen copy.copy nicht.

Der Zweck dieses PEP ist es daher, dass diese Iteratortypen eine geeignete __copy__-Methode bereitstellen. Ebenso sollten vom Benutzer erstellte Iteratortypen, die Kopien ihrer Instanzen liefern können, die für separate und unabhängige Iteration mit begrenzten Zeit- und Kostenaufwand geeignet sind, ebenfalls eine geeignete __copy__-Methode bereitstellen. Während copy.copy auch andere Wege unterstützt, um einem Typ die Kontrolle darüber zu geben, wie seine Instanzen kopiert werden, wird vorgeschlagen, der Einfachheit halber, dass Iteratortypen, die das Kopieren unterstützen, dies immer durch die Bereitstellung einer __copy__-Methode tun und nicht auf die anderen von copy.copy unterstützten Wege.

Wenn Iteratoren eine geeignete __copy__-Methode bereitstellen, wenn dies machbar ist, wird dies eine einfache Optimierung von itertools.tee und ähnlichem Benutzercode ermöglichen, wie z.B.:

def tee(it):
    it = iter(it)
    try: copier = it.__copy__
    except AttributeError:
        # non-copyable iterator, do all the needed hard work
        # [snipped!]
    else:
        return it, copier()

Beachten Sie, dass diese Funktion NICHT "copy.copy(it)" aufruft, was (auch nach der Implementierung dieses PEP) immer noch "zufällig erfolgreich sein" könnte. für einen Iteratortyp, der als vom Benutzer erstellte Klasse implementiert ist, ohne wirklich ein angemessenes "unabhängig durchlauffähiges" Kopierobjekt als Ergebnis zu liefern.

Spezifikation

Jeder Iteratortyp X kann eine Methode __copy__ bereitstellen, die auf jeder Instanz x von X ohne Argumente aufgerufen werden kann. Die Methode sollte genau dann bereitgestellt werden, wenn der Iteratortyp Kopierbarkeit mit einem vernünftigerweise geringen Rechen- und Speicheraufwand bieten kann. Darüber hinaus sollte das von der Methode __copy__ zurückgegebene neue Objekt y eine neue Instanz von X sein, die unabhängig und separat von x durchlauffähig ist und entlang derselben "zugrunde liegenden Sequenz" von Elementen schreitet.

Nehmen wir zum Beispiel an, eine Klasse Iter hätte im Wesentlichen die Funktionalität des integrierten iter für die Iteration über eine Sequenz dupliziert.

class Iter(object):

    def __init__(self, sequence):
        self.sequence = sequence
        self.index = 0

    def __iter__(self):
        return self

    def next(self):
        try: result = self.sequence[self.index]
        except IndexError: raise StopIteration
        self.index += 1
        return result

Um diese Klasse Iter mit diesem PEP konform zu machen, würde die folgende Ergänzung zum Körper der Klasse Iter ausreichen:

def __copy__(self):
    result = self.__class__(self.sequence)
    result.index = self.index
    return result

Beachten Sie, dass __copy__ in diesem Fall nicht einmal versucht, die Sequenz zu kopieren; wenn die Sequenz geändert wird, während einer oder beide der ursprünglichen und kopierten Iteratoren noch auf ihr schreiten, ist das Iterationsverhalten wahrscheinlich fehlerhaft – es liegt nicht in der Verantwortung von __copy__, dieses normale Python-Verhalten für Iteratoren, die auf veränderliche Sequenzen iterieren, zu ändern (das wäre vielleicht die Spezifikation für eine __deepcopy__-Methode von Iteratoren, mit der sich dieses PEP jedoch nicht befasst).

Betrachten Sie auch einen "zufälligen Iterator", der eine nicht endende Sequenz von Ergebnissen einer Methode einer zufälligen Instanz liefert, die mit gegebenen Argumenten aufgerufen wird.

class RandomIterator(object):

    def __init__(self, bound_method, *args):
        self.call = bound_method
        self.args = args

    def __iter__(self):
        return self

    def next(self):
        return self.call(*self.args)

    def __copy__(self):
        import copy, new
        im_self = copy.copy(self.call.im_self)
        method = new.instancemethod(self.call.im_func, im_self)
        return self.__class__(method, *self.args)

Dieser Iteratortyp ist etwas allgemeiner, als sein Name vermuten lässt, da er Aufrufe an jede gebundene Methode (oder andere aufrufbare Elemente) unterstützt, aber wenn das aufrufbare Element keine gebundene Methode ist, schlägt die Methode __copy__ fehl. Aber der Anwendungsfall ist für die Generierung zufälliger Ströme, wie in:

import random

def show5(it):
    for i, result in enumerate(it):
        print '%6.3f'%result,
        if i==4: break
    print

normit = RandomIterator(random.Random().gauss, 0, 1)
show5(normit)
copit = normit.__copy__()
show5(normit)
show5(copit)

Dies zeigt eine Ausgabe wie:

-0.536  1.936 -1.182 -1.690 -1.184
 0.666 -0.701  1.214  0.348  1.373
 0.666 -0.701  1.214  0.348  1.373

Der entscheidende Punkt ist, dass die zweite und dritte Zeile gleich sind, da die Iteratoren 'normit' und 'copit' entlang derselben "zugrunde liegenden Sequenz" schreiten werden. (Nebenbei bemerkt, um eine Kopie von self.call.im_self zu erhalten, müssen wir copy.copy verwenden und NICHT versuchen, direkt auf eine __copy__-Methode zuzugreifen, da zum Beispiel Instanzen von random.Random das Kopieren über __getstate__ und __setstate__ unterstützen, NICHT über __copy__; tatsächlich ist die Verwendung von copy.copy der normale Weg, um eine flache Kopie jedes Objekts zu erhalten – kopierbare Iteratoren sind anders wegen der bereits erwähnten Unsicherheit über das Ergebnis von copy.copy, das diese "kopierbaren Iterator"-Spezifikationen unterstützt).

Details

Neben der Aufnahme einer Empfehlung in die Python-Dokumentation, dass vom Benutzer erstellte Iteratortypen eine __copy__-Methode unterstützen sollten (falls und nur wenn sie mit geringen Speicher- und Laufzeitkosten implementiert werden kann und eine unabhängig durchlauffähige Kopie eines Iteratorobjekts liefert), wird die Implementierung dieses PEP speziell die Aufnahme der Kopierbarkeit in die Iteratoren über Sequenzen, die das integrierte iter zurückgibt, sowie in die Iteratoren über ein Wörterbuch, das von den Methoden __iter__, iterkeys, itervalues und iteritems des integrierten Typs dict zurückgegeben wird, enthalten.

Iteratoren, die von Generatorfunktionen erzeugt werden, werden nicht kopierbar sein. Iteratoren, die von den neuen "Generatorausdrücken" von Python 2.4 (PEP 289) erzeugt werden, sollten jedoch kopierbar sein, wenn ihre zugrunde liegenden Iteratoren dies sind; die strengen Beschränkungen dessen, was in einem Generatorausdruck möglich ist, im Vergleich zur viel größeren Allgemeinheit eines Generators, sollten dies machbar machen. Ebenso sollten die von der integrierten Funktion enumerate erzeugten Iteratoren und bestimmte vom Modul itertools bereitgestellte Funktionen kopierbar sein, wenn die zugrunde liegenden Iteratoren dies sind.

Die Implementierung dieses PEP wird auch die Optimierung der neuen itertools.tee-Funktion enthalten, die im Abschnitt Motivation erwähnt wird.

Begründung

Der Hauptanwendungsfall für (flache) Kopien eines Iterators ist derselbe wie für die Funktion itertools.tee (neu in 2.4). Benutzercode wird nicht direkt versuchen, einen Iterator zu kopieren, da er separat mit nicht kopierbaren Fällen umgehen müsste; der Aufruf von itertools.tee wird intern die Kopie durchführen, wenn angebracht, und implizit auf eine maximal effiziente nicht-kopierende Strategie für Iteratoren zurückfallen, die nicht kopierbar sind. (Gelegentlich möchte Benutzercode mehr direkte Kontrolle, insbesondere um mit nicht kopierbaren Iteratoren durch andere Strategien umzugehen, wie z.B. das Erstellen einer Liste oder das Speichern der Sequenz auf Festplatte).

Ein "tee'-d" Iterator kann als "Referenzpunkt" dienen und es ermöglichen, die Verarbeitung einer Sequenz von einem bekannten Punkt aus fortzusetzen oder wieder aufzunehmen, während der andere unabhängige Iterator frei fortgeschritten werden kann, um bei Bedarf einen weiteren Teil der Sequenz zu "erkunden". Ein einfaches Beispiel: eine Generatorfunktion, die, gegeben einen Iterator von Zahlen (angenommen, es sind positive), einen entsprechenden Iterator zurückgibt, dessen Elemente die Fraktion des Gesamten sind, die jedem entsprechenden Element des Eingabeiterators entspricht. Der Aufrufer kann den Gesamtwert als Wert übergeben, wenn er im Voraus bekannt ist; andernfalls berechnet der von einem Aufruf dieser Generatorfunktion zurückgegebene Iterator zuerst den Gesamtwert.

def fractions(numbers, total=None):
    if total is None:
        numbers, aux = itertools.tee(numbers)
        total = sum(aux)
    total = float(total)
    for item in numbers:
        yield item / total

Die Fähigkeit, den Zahleniterator zu "tee'-n", ermöglicht es diesem Generator, den Gesamtwert bei Bedarf vorab zu berechnen, ohne zwangsläufig O(N) Hilfsspeicher zu benötigen, wenn der Zahleniterator kopierbar ist.

Als weiteres Beispiel für "Iterator-Lesezeichen" betrachten wir einen Strom von Zahlen mit einer gelegentlichen Zeichenkette als "Postfix-Operator". Der mit Abstand häufigste solcher Operator ist ein '+', woraufhin wir alle vorherigen Zahlen (seit dem letzten vorherigen Operator, falls vorhanden, ansonsten seit dem Anfang) summieren und das Ergebnis liefern müssen. Manchmal finden wir stattdessen ein '*', was dasselbe ist, nur dass die vorherigen Zahlen stattdessen multipliziert, nicht summiert werden müssen.

def filter_weird_stream(stream):
    it = iter(stream)
    while True:
        it, bookmark = itertools.tee(it)
        total = 0
        for item in it:
            if item=='+':
                yield total
                break
            elif item=='*':
                product = 1
                for item in bookmark:
                    if item=='*':
                        yield product
                        break
                    else:
                        product *= item
           else:
               total += item

Ähnliche Anwendungsfälle von itertools.tee können Aufgaben wie "Rückgängig" bei einem Strom von Befehlen, die durch einen Iterator repräsentiert werden, "Backtracking" beim Parsen eines Stroms von Token usw. unterstützen. (Natürlich sollte in jedem Fall auch einfachere Möglichkeiten in Betracht gezogen werden, wie z.B. das Speichern relevanter Teile der Sequenz in Listen, während man mit nur einem Iterator durch die Sequenz geht, abhängig von den Details der jeweiligen Aufgabe).

Hier ist ein Beispiel, in reinem Python, wie die integrierte Funktion 'enumerate' erweitert werden könnte, um __copy__ zu unterstützen, wenn ihr zugrunde liegender Iterator ebenfalls __copy__ unterstützt:

class enumerate(object):

    def __init__(self, it):
        self.it = iter(it)
        self.i = -1

    def __iter__(self):
        return self

    def next(self):
        self.i += 1
        return self.i, self.it.next()

    def __copy__(self):
        result = self.__class__.__new__()
        result.it = self.it.__copy__()
        result.i = self.i
        return result

Hier ist ein Beispiel für die Art von "Zerbrechlichkeit", die durch "zufällige Kopierbarkeit" eines Iterators entsteht – der Grund, warum man copy.copy NICHT verwenden sollte und erwarten, dass man, wenn es erfolgreich ist, ein Ergebnis erhält, das unabhängig vom Original durchlauffähig ist. Hier ist eine Iteratorklasse, die auf "Bäumen" iteriert (in Preorder), die der Einfachheit halber nur verschachtelte Listen sind – jedes Element, das eine Liste ist, wird als Unterbaum behandelt, jedes andere Element als Blatt.

class ListreeIter(object):

    def __init__(self, tree):
        self.tree = [tree]
        self.indx = [-1]

    def __iter__(self):
        return self

    def next(self):
        if not self.indx:
            raise StopIteration
        self.indx[-1] += 1
        try:
            result = self.tree[-1][self.indx[-1]]
        except IndexError:
            self.tree.pop()
            self.indx.pop()
            return self.next()
        if type(result) is not list:
            return result
        self.tree.append(result)
        self.indx.append(-1)
        return self.next()

Nun zum Beispiel der folgende Code:

import copy
x = [ [1,2,3], [4, 5, [6, 7, 8], 9], 10, 11, [12] ]

print 'showing all items:',
it = ListreeIter(x)
for i in it:
    print i,
    if i==6: cop = copy.copy(it)
print

print 'showing items >6 again:'
for i in cop: print i,
print

funktioniert NICHT wie beabsichtigt – der "cop"-Iterator wird Schritt für Schritt konsumiert und erschöpft, wie der ursprüngliche "it"-Iterator, weil das zufällige (statt absichtliche) Kopieren, das von copy.copy durchgeführt wird, die "index"-Liste teilt und nicht dupliziert, welche das veränderliche Attribut it.indx (eine Liste von numerischen Indizes) ist. Daher ist dieser "Client-Code" des Iterators, der versucht, zweimal über einen Teil der Sequenz mittels eines copy.copy auf dem Iterator zu iterieren, NICHT korrekt.

Einige korrekte Lösungen beinhalten die Verwendung von itertools.tee, d.h. die Änderung der ersten for-Schleife in:

for i in it:
    print i,
    if i==6:
        it, cop = itertools.tee(it)
        break
for i in it: print i,

(beachten Sie, dass wir die Schleife in zwei Teile aufteilen MÜSSEN, sonst würden wir immer noch auf dem URSPRÜNGLICHEN Wert von it iterieren, der nach dem Aufruf von tee NICHT mehr verwendet werden darf!); oder das Erstellen einer Liste, d.h.:

for i in it:
    print i,
    if i==6:
        cop = lit = list(it)
        break
for i in lit: print i,

(auch hier muss die Schleife in zwei Teile aufgeteilt werden, da der Iterator 'it' durch den Aufruf list(it) erschöpft wird).

Schließlich würden alle diese Lösungen funktionieren, wenn Listiter eine geeignete __copy__-Methode bereitstellen würde, wie dieses PEP empfiehlt:

def __copy__(self):
    result = self.__class__.new()
    result.tree = copy.copy(self.tree)
    result.indx = copy.copy(self.indx)
    return result

Es ist nicht nötig, "tiefer" in die Kopie zu gehen, aber die beiden veränderlichen "Zustandsattribute" müssen tatsächlich kopiert werden, um eine "korrekte" (unabhängig durchlauffähige) Iterator-Kopie zu erzielen.

Die empfohlene Lösung ist, dass die Klasse Listiter diese __copy__-Methode bereitstellt UND dass der Client-Code itertools.tee verwendet (mit der oben gezeigten zweigeteilten Schleife). Dies macht den Client-Code maximal tolerant gegenüber verschiedenen Iteratortypen, die er möglicherweise verwendet, und erzielt gleichzeitig eine gute Leistung für das "tee"-en dieses spezifischen Iteratortyps.

Referenzen

[1] Diskussion auf python-dev ab dem Beitrag: https://mail.python.org/pipermail/python-dev/2003-October/038969.html

[2] Online-Dokumentation für das copy-Modul der Standardbibliothek: https://docs.pythonlang.de/release/2.6/library/copy.html

Urheberrecht

Dieses Dokument wurde gemeinfrei erklärt.