Wie kann man ein Element (Peek) in einem Python-Generator nach vorne schauen?

78

Ich kann nicht herausfinden, wie ich ein Element in einem Python-Generator vorausschauen kann. Sobald ich hinschaue, ist es weg.

Folgendes meine ich:

gen = iter([1,2,3])
next_value = gen.next()  # okay, I looked forward and see that next_value = 1
# but now:
list(gen)  # is [2, 3]  -- the first value is gone!

Hier ist ein realeres Beispiel:

gen = element_generator()
if gen.next_value() == 'STOP':
  quit_application()
else:
  process(gen.next())

Kann mir jemand helfen, einen Generator zu schreiben, mit dem Sie ein Element nach vorne schauen können?

bodacydo
quelle
1
Können Sie genauer beschreiben, was Sie tun möchten? Codebeispiel vielleicht?
Tim Pietzcker
Was brauchen Sie noch, wenn Sie eine Liste haben? Es scheint auch, dass Sie den ersten Wert speichern als next_value, nein?
SilentGhost
SilentGhost war ein Beispiel, um zu veranschaulichen, was gonebedeutet. Ich habe keine Liste und keinen next_value. Es war nur ein Beispiel, um zu zeigen, was es bedeutet, wenn ein Element aus einem Generator verschwindet.
Bodacydo
@ Bodacydo: Ich verstehe immer noch nicht. Wie ist es dann gelaufen? Warum haben Sie keinen Zugriff auf diesen Wert?
SilentGhost
Tim hat die Frage mit einem besseren Beispiel aktualisiert.
Bodacydo

Antworten:

60

Die Python-Generator-API ist eine Möglichkeit: Sie können gelesene Elemente nicht zurückschieben. Sie können jedoch mit dem Modul itertools einen neuen Iterator erstellen und das Element voranstellen:

import itertools

gen = iter([1,2,3])
peek = gen.next()
print list(itertools.chain([peek], gen))
Aaron Digulla
quelle
5
Sie können sendeinen zuvor ermittelten Wert zurück in einen Generator schieben, wenn er den nächsten Wert ergibt.
Dansalmo
2
@dansalmo: Ja, aber Sie müssen den Generatorcode dafür ändern. Siehe die Antwort von Andrew Hare.
Aaron Digulla
6
Ich habe diese Lösung schon oft verwendet, aber ich denke, es sollte wahrscheinlich darauf hingewiesen werden, dass Sie grundsätzlich itertools.chain.__next__ nZeiten für jedes Element aufrufen , das Sie aus der nIterable herausholen (wo ist die Häufigkeit, mit der Sie einen Blick darauf geworfen haben). Dies funktioniert gut für ein oder zwei Peeks, aber wenn Sie einen Blick auf jedes Element werfen müssen, ist dies nicht die beste Lösung :-)
mgilson
9
Ich würde erwähnen, dass dies im more-itertoolsPaket als implementiert ist spy. Um nicht zu sagen, dass es sich lohnt, ein ganz neues Paket für nur diese eine Funktionalität einzuführen, aber einige Leute finden eine vorhandene Implementierung möglicherweise nützlich.
David Z
@mgilson Ja, das sollte definitiv mit einer Warnung kommen. Die Leute könnten sehr gut versuchen, dies in einer Schleife zu tun, indem sie jedes Element betrachten, und dann dauert die gesamte Iteration quadratisch.
Kelly Bundy
79

Der Vollständigkeit halber enthält das more-itertoolsPaket (das wahrscheinlich Teil der Toolbox eines Python-Programmierers sein sollte) einen peekableWrapper, der dieses Verhalten implementiert. Wie das Codebeispiel in der Dokumentation zeigt:

>>> p = peekable(['a', 'b'])
>>> p.peek()
'a'
>>> next(p)
'a'

Es ist jedoch häufig möglich, Code, der diese Funktionalität verwendet, so umzuschreiben, dass er tatsächlich nicht benötigt wird. Zum Beispiel könnte Ihr realistisches Codebeispiel aus der Frage folgendermaßen geschrieben werden:

gen = element_generator()
command = gen.next_value()
if command == 'STOP':
  quit_application()
else:
  process(command)

(Anmerkung des Lesers: Ich habe die Syntax im Beispiel aus der Frage zum Zeitpunkt des Schreibens beibehalten, obwohl sie sich auf eine veraltete Version von Python bezieht.)

David Z.
quelle
25

Ok - zwei Jahre zu spät - aber ich bin auf diese Frage gestoßen und habe keine der Antworten zu meiner Zufriedenheit gefunden. Kam mit diesem Meta-Generator:

class Peekorator(object):

    def __init__(self, generator):
        self.empty = False
        self.peek = None
        self.generator = generator
        try:
            self.peek = self.generator.next()
        except StopIteration:
            self.empty = True

    def __iter__(self):
        return self

    def next(self):
        """
        Return the self.peek element, or raise StopIteration
        if empty
        """
        if self.empty:
            raise StopIteration()
        to_return = self.peek
        try:
            self.peek = self.generator.next()
        except StopIteration:
            self.peek = None
            self.empty = True
        return to_return

def simple_iterator():
    for x in range(10):
        yield x*3

pkr = Peekorator(simple_iterator())
for i in pkr:
    print i, pkr.peek, pkr.empty

Ergebnisse in:

0 3 False
3 6 False
6 9 False
9 12 False    
...
24 27 False
27 None False

Das heißt, Sie haben jederzeit während der Iteration Zugriff auf das nächste Element in der Liste.

plof
quelle
1
Ich fühle mich ein bisschen gemein, das zu sagen, aber ich finde diese Lösung schrecklich und ziemlich fehleranfällig. Zu jedem Zeitpunkt benötigen Sie Zugriff auf zwei Elemente des Generators: die Elemente 'i' und 'i + 1'. Warum codieren Sie Ihren Algorithmus nicht so, dass er den aktuellen und den vorherigen Wert anstelle des nächsten und des aktuellen Werts verwendet? Es scheint absolut identisch und viel einfacher zu sein.
Jonathan Hartley
1
auf jeden Fall - sei so gemein wie du musst :)
plof
6
@ Jonathan Dies ist in nicht trivialen Beispielen möglicherweise nicht immer möglich, z. B. wenn der Iterator an eine Funktion übergeben wird.
Florian Ledermann
3
Jemand sollte darauf hinweisen, dass ab Python2.6 der bevorzugte Weg, um den nächsten Wert eines Generators zu erhalten, next(generator)eher als ist generator.next(). IIRC, generator.next()geht in python3.x weg. __next__ = nextFügen Sie aus Gründen der besten Vorwärtskompatibilität dem Hauptteil der Klasse hinzu, damit sie in python3.x weiterhin funktioniert. Das heißt, gute Antwort.
mgilson
Nach @mgilson funktioniert dies in Python 3 nicht, wenn der Generator ein String-Iterator ist. Dafür müssen Sie unbedingt verwendennext()
jpyams
16

Sie können itertools.tee verwenden, um eine einfache Kopie des Generators zu erstellen. Ein Blick auf eine Kopie wirkt sich dann nicht auf die zweite Kopie aus:

import itertools

def process(seq):
    peeker, items = itertools.tee(seq)

    # initial peek ahead
    # so that peeker is one ahead of items
    if next(peeker) == 'STOP':
        return

    for item in items:

        # peek ahead
        if next(peeker) == "STOP":
            return

        # process items
        print(item)

Der Generator "Gegenstände" bleibt davon unberührt, dass Sie "Peeker" belästigen. Beachten Sie, dass Sie nach dem Aufruf von "tee" nicht die ursprüngliche "seq" verwenden sollten, da dies zu Problemen führen kann.

FWIW, dies ist der falsche Weg, um dieses Problem zu lösen. Jeder Algorithmus, bei dem Sie 1 Element in einem Generator vorausschauen müssen, kann alternativ so geschrieben werden, dass das aktuelle Generatorelement und das vorherige Element verwendet werden. Dann müssen Sie die Verwendung von Generatoren nicht mehr stören, und Ihr Code wird viel einfacher. Siehe meine andere Antwort auf diese Frage.

Jonathan Hartley
quelle
3
"Jeder Algorithmus, bei dem Sie 1 Element in einem Generator vorausschauen müssen, kann alternativ so geschrieben werden, dass das aktuelle Generatorelement und das vorherige Element verwendet werden." Das Verstümmeln der Verwendung von Generatoren kann manchmal zu eleganterem und lesbarerem Code führen, insbesondere bei Parsern, die Lookahead erfordern.
Rufflewind
Hey da, Rufflewind. Ich verstehe den Punkt über das Parsen, der Lookahead erfordert, aber ich verstehe nicht, warum Sie dies nicht erreichen können, indem Sie einfach das vorherige Element aus Ihrem Generator speichern und das neueste Element aus Ihrem Generator als Lookahead verwenden. Dann erhalten Sie das Beste aus beiden Welten: einen nicht verwickelten Generator und einen einfachen Parser.
Jonathan Hartley
Deshalb wickeln Sie den Generator in eine benutzerdefinierte Klasse ein, um dies automatisch zu tun.
Rufflewind
Hey Ruffelwind. Ich bin mir nicht mehr sicher, ob ich verstehe, was Sie befürworten. Tut mir leid, dass ich die Handlung verloren habe.
Jonathan Hartley
1
FWIW, Code ist jetzt behoben, @Eric \ Mays Kommentar, dass der gesamte Iterator gepuffert ist, ist nicht mehr wahr.
Jonathan Hartley
5
>>> gen = iter(range(10))
>>> peek = next(gen)
>>> peek
0
>>> gen = (value for g in ([peek], gen) for value in g)
>>> list(gen)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Robert King
quelle
Haben Sie etwas dagegen, eine Erklärung darüber zu geben, was hier passiert
Kristof Pal
Wir werfen einen Blick auf Gen. Wir erstellen dann einen iterierbaren [Peek] und kombinieren ihn mit dem Rest des Gens, um ein neues Gen zu erstellen. Dies erfolgt durch Iteration durch die Abflachung der beiden Generatoren, die zusammen das Original ergeben. Siehe Wohnung: stackoverflow.com/questions/952914/…
King
Dies ist dieselbe, aber expliziter als die Lösung itertools.chain.
Theo Belaire
5

Nur zum Spaß habe ich eine Implementierung einer Lookahead-Klasse erstellt, basierend auf dem Vorschlag von Aaron:

import itertools

class lookahead_chain(object):
    def __init__(self, it):
        self._it = iter(it)

    def __iter__(self):
        return self

    def next(self):
        return next(self._it)

    def peek(self, default=None, _chain=itertools.chain):
        it = self._it
        try:
            v = self._it.next()
            self._it = _chain((v,), it)
            return v
        except StopIteration:
            return default

lookahead = lookahead_chain

Damit funktioniert folgendes:

>>> t = lookahead(xrange(8))
>>> list(itertools.islice(t, 3))
[0, 1, 2]
>>> t.peek()
3
>>> list(itertools.islice(t, 3))
[3, 4, 5]

Bei dieser Implementierung ist es eine schlechte Idee, peek mehrmals hintereinander aufzurufen ...

Beim Betrachten des CPython-Quellcodes habe ich gerade einen besseren Weg gefunden, der sowohl kürzer als auch effizienter ist:

class lookahead_tee(object):
    def __init__(self, it):
        self._it, = itertools.tee(it, 1)

    def __iter__(self):
        return self._it

    def peek(self, default=None):
        try:
            return self._it.__copy__().next()
        except StopIteration:
            return default

lookahead = lookahead_tee

Die Verwendung ist die gleiche wie oben, aber Sie zahlen hier keinen Preis, um Peek mehrmals hintereinander zu verwenden. Mit ein paar Zeilen mehr können Sie auch mehr als ein Element im Iterator (bis zum verfügbaren RAM) nach vorne schauen.

Bluehorn
quelle
4

Anstatt Elemente (i, i + 1) zu verwenden, wobei 'i' das aktuelle Element und i + 1 die 'Peek Ahead'-Version ist, sollten Sie (i-1, i) verwenden, wobei' i-1 ' ist die vorherige Version vom Generator.

Wenn Sie Ihren Algorithmus auf diese Weise optimieren, wird etwas erzeugt, das mit dem identisch ist, was Sie derzeit haben, abgesehen von der zusätzlichen unnötigen Komplexität des Versuchs, einen Blick nach vorne zu werfen.

Ein Blick nach vorne ist ein Fehler, und Sie sollten es nicht tun.

Jonathan Hartley
quelle
Sie müssen einen Gegenstand aus einem Generator nehmen, bevor Sie wissen, ob Sie ihn möchten. Angenommen, eine Funktion nimmt einen Gegenstand von einem Generator und entscheidet bei der Inspektion, dass er ihn nicht will. Der nächste Benutzer des Generators sieht dieses Element nur, wenn Sie es zurückschieben können. Durch das Spähen müssen Elemente zurückgeschoben werden.
Isaac Turner
@IsaacTurner Nein, das musst du nicht tun. Beispielsweise könnten Sie zwei verschachtelte Generatoren haben. Der Innere nimmt einen Gegenstand, entscheidet, dass er nichts damit anfangen will, und gibt ihn dann trotzdem zurück. Der Äußere sieht immer noch alles in der Sequenz. Es gibt äquivalente, sehr einfache Möglichkeiten, dasselbe ohne verschachtelte Generatoren zu tun. Denken Sie einfach an das 'vorherige Element' in einer Variablen, und Sie können alles tun, was von dieser Frage verlangt wird. VIEL einfacher als zu versuchen, die Dinge zurückzudrängen.
Jonathan Hartley
4

Eine einfache Lösung besteht darin, eine Funktion wie die folgende zu verwenden:

def peek(it):
    first = next(it)
    return first, itertools.chain([first], it)

Dann können Sie tun:

>>> it = iter(range(10))
>>> x, it = peek(it)
>>> x
0
>>> next(it)
0
>>> next(it)
1
Thomas Ahle
quelle
3

Dies funktioniert - es puffert ein Element und ruft mit jedem Element und dem nächsten Element in der Sequenz eine Funktion auf.

Ihre Anforderungen an das, was am Ende der Sequenz passiert, sind trübe. Was bedeutet "nach vorne schauen", wenn Sie am letzten sind?

def process_with_lookahead( iterable, aFunction ):
    prev= iterable.next()
    for item in iterable:
        aFunction( prev, item )
        prev= item
    aFunction( item, None )

def someLookaheadFunction( item, next_item ):
    print item, next_item
S.Lott
quelle
3

Wenn jemand interessiert ist, und bitte korrigieren Sie mich, wenn ich falsch liege, aber ich glaube, es ist ziemlich einfach, jedem Iterator einige Push-Back-Funktionen hinzuzufügen.

class Back_pushable_iterator:
    """Class whose constructor takes an iterator as its only parameter, and
    returns an iterator that behaves in the same way, with added push back
    functionality.

    The idea is to be able to push back elements that need to be retrieved once
    more with the iterator semantics. This is particularly useful to implement
    LL(k) parsers that need k tokens of lookahead. Lookahead or push back is
    really a matter of perspective. The pushing back strategy allows a clean
    parser implementation based on recursive parser functions.

    The invoker of this class takes care of storing the elements that should be
    pushed back. A consequence of this is that any elements can be "pushed
    back", even elements that have never been retrieved from the iterator.
    The elements that are pushed back are then retrieved through the iterator
    interface in a LIFO-manner (as should logically be expected).

    This class works for any iterator but is especially meaningful for a
    generator iterator, which offers no obvious push back ability.

    In the LL(k) case mentioned above, the tokenizer can be implemented by a
    standard generator function (clean and simple), that is completed by this
    class for the needs of the actual parser.
    """
    def __init__(self, iterator):
        self.iterator = iterator
        self.pushed_back = []

    def __iter__(self):
        return self

    def __next__(self):
        if self.pushed_back:
            return self.pushed_back.pop()
        else:
            return next(self.iterator)

    def push_back(self, element):
        self.pushed_back.append(element)
it = Back_pushable_iterator(x for x in range(10))

x = next(it) # 0
print(x)
it.push_back(x)
x = next(it) # 0
print(x)
x = next(it) # 1
print(x)
x = next(it) # 2
y = next(it) # 3
print(x)
print(y)
it.push_back(y)
it.push_back(x)
x = next(it) # 2
y = next(it) # 3
print(x)
print(y)

for x in it:
    print(x) # 4-9
Nilo
quelle
1

Python3-Snippet für @ jonathan-hartley Antwort:

def peek(iterator, eoi=None):
    iterator = iter(iterator)

    try:
        prev = next(iterator)
    except StopIteration:
        return iterator

    for elm in iterator:
        yield prev, elm
        prev = elm

    yield prev, eoi


for curr, nxt in peek(range(10)):
    print((curr, nxt))

# (0, 1)
# (1, 2)
# (2, 3)
# (3, 4)
# (4, 5)
# (5, 6)
# (6, 7)
# (7, 8)
# (8, 9)
# (9, None)

Es wäre unkompliziert, eine Klasse zu erstellen, die dies tut __iter__und nur das prevElement liefert und das elmin ein Attribut einfügt.

endlich
quelle
1

In @David Zs Beitrag kann das neuere seekableTool einen umschlossenen Iterator auf eine vorherige Position zurücksetzen.

>>> s = mit.seekable(range(3))
>>> s.next()
# 0

>>> s.seek(0)                                              # reset iterator
>>> s.next()
# 0

>>> s.next()
# 1

>>> s.seek(1)
>>> s.next()
# 1

>>> next(s)
# 2
Pylang
quelle
1

Cytoolz hat eine Peek- Funktion.

>> from cytoolz import peek
>> gen = iter([1,2,3])
>> first, continuation = peek(gen)
>> first
1
>> list(continuation)
[1, 2, 3]
WP McNeill
quelle
1

Ein Iterator, der es ermöglicht, auf das nächste Element und auch weiter vorne zu schauen. Es liest nach Bedarf voraus und merkt sich die Werte in a deque.

from collections import deque

class PeekIterator:

    def __init__(self, iterable):
        self.iterator = iter(iterable)
        self.peeked = deque()

    def __iter__(self):
        return self

    def __next__(self):
        if self.peeked:
            return self.peeked.popleft()
        return next(self.iterator)

    def peek(self, ahead=0):
        while len(self.peeked) <= ahead:
            self.peeked.append(next(self.iterator))
        return self.peeked[ahead]

Demo:

>>> it = PeekIterator(range(10))
>>> it.peek()
0
>>> it.peek(5)
5
>>> it.peek(13)
Traceback (most recent call last):
  File "<pyshell#68>", line 1, in <module>
    it.peek(13)
  File "[...]", line 15, in peek
    self.peeked.append(next(self.iterator))
StopIteration
>>> it.peek(2)
2
>>> next(it)
0
>>> it.peek(2)
3
>>> list(it)
[1, 2, 3, 4, 5, 6, 7, 8, 9]
>>>
Stefan Pochmann
quelle
0

Obwohl dies itertools.chain()das natürliche Werkzeug für diesen Job ist, sollten Sie sich vor solchen Schleifen hüten:

for elem in gen:
    ...
    peek = next(gen)
    gen = itertools.chain([peek], gen)

... weil dies eine linear wachsende Menge an Speicher verbraucht und schließlich zum Stillstand kommt. (Dieser Code scheint im Wesentlichen eine verknüpfte Liste zu erstellen, einen Knoten pro chain () -Aufruf.) Ich weiß das nicht, weil ich die Bibliotheken überprüft habe, sondern weil dies nur zu einer erheblichen Verlangsamung meines Programms geführt hat - das Entfernen der gen = itertools.chain([peek], gen)Zeile hat es beschleunigt nochmal. (Python 3.3)

Jacob Eliosoff
quelle