python - Uso de lookahead con generadores.
generator (8)
He implementado un escáner basado en el generador en Python que tokeniza una cadena en tuplas del formulario (tipo de token, valor del token) :
for token in scan("a(b)"):
print token
imprimiría
("literal", "a")
("l_paren", "(")
...
La siguiente tarea implica analizar el flujo de token y para eso, necesito poder mirar un elemento hacia adelante desde el actual sin mover el puntero hacia adelante también. El hecho de que los iteradores y los generadores no proporcionen la secuencia completa de elementos a la vez, pero cada elemento según sea necesario hace que los __next__() un poco más complicados en comparación con las listas, ya que el siguiente elemento no se conoce a menos que se __next__() a __next__() .
¿Cómo podría ser una implementación sencilla de un lookahead basado en un generador? Actualmente estoy usando una solución que implica hacer una lista del generador:
token_list = [token for token in scan(string)]
El lookahead entonces es fácilmente implementado por algo así:
try:
next_token = token_list[index + 1]
except: IndexError:
next_token = None
Por supuesto, esto simplemente funciona bien. Pero pensando que otra vez, surge mi segunda pregunta: ¿hay realmente un punto de hacer que scan() un generador en primer lugar?
Aquí hay un ejemplo que permite que un solo artículo se envíe de vuelta al generador
def gen():
for i in range(100):
v=yield i # when you call next(), v will be set to None
if v:
yield None # this yields None to send() call
v=yield v # so this yield is for the first next() after send()
g=gen()
x=g.next()
print 0,x
x=g.next()
print 1,x
x=g.next()
print 2,x # oops push it back
x=g.send(x)
x=g.next()
print 3,x # x should be 2 again
x=g.next()
print 4,x
Cómo lo escribiría de forma concisa, si solo necesitara un elemento de lookahead:
SEQUENCE_END = object()
def lookahead(iterable):
iter = iter(iterable)
current = next(iter)
for ahead in iter:
yield current,ahead
current = ahead
yield current,SEQUENCE_END
Ejemplo:
>>> for x,ahead in lookahead(range(3)):
>>> print(x,ahead)
0, 1
1, 2
2, <object SEQUENCE_END>
Construya un envoltorio simple de búsqueda itertools.tee usando itertools.tee :
from itertools import tee, islice
class LookAhead:
''Wrap an iterator with lookahead indexing''
def __init__(self, iterator):
self.t = tee(iterator, 1)[0]
def __iter__(self):
return self
def next(self):
return next(self.t)
def __getitem__(self, i):
for value in islice(self.t.__copy__(), i, None):
return value
raise IndexError(i)
Utilice la clase para envolver un iterable o iterador existente. A continuación, puede iterar normalmente usando next o puede mirar hacia delante con búsquedas indexadas.
>>> it = LookAhead([10, 20, 30, 40, 50])
>>> next(it)
10
>>> it[0]
20
>>> next(it)
20
>>> it[0]
30
>>> list(it)
[30, 40, 50]
Para ejecutar este código en Python 3, simplemente cambie el siguiente método a __siguiente__ .
La de Paul es una buena respuesta. Un enfoque basado en clase con lookahead arbitrario podría ser algo como:
class lookahead(object):
def __init__(self, generator, lookahead_count=1):
self.gen = iter(generator)
self.look_count = lookahead_count
def __iter__(self):
self.lookahead = []
self.stopped = False
try:
for i in range(self.look_count):
self.lookahead.append(self.gen.next())
except StopIteration:
self.stopped = True
return self
def next(self):
if not self.stopped:
try:
self.lookahead.append(self.gen.next())
except StopIteration:
self.stopped = True
if self.lookahead != []:
return self.lookahead.pop(0)
else:
raise StopIteration
x = lookahead("abcdef", 3)
for i in x:
print i, x.lookahead
Muy buenas respuestas allí, pero mi enfoque favorito sería utilizar itertools.tee : dado un iterador, devuelve dos (o más si se solicita) que se pueden avanzar de forma independiente. Se almacena en la memoria tanto como sea necesario (es decir, no mucho, si los iteradores no se "salen del paso" el uno del otro). P.ej:
import itertools
import collections
class IteratorWithLookahead(collections.Iterator):
def __init__(self, it):
self.it, self.nextit = itertools.tee(iter(it))
self._advance()
def _advance(self):
self.lookahead = next(self.nextit, None)
def __next__(self):
self._advance()
return next(self.it)
Puede envolver cualquier iterador con esta clase y luego usar el atributo .lookahead del envoltorio para saber cuál será el próximo elemento que se devolverá en el futuro. Me gusta dejar toda la lógica real a itertools.tee y solo proporcionar este pegamento fino -)
No es bonito, pero esto puede hacer lo que quieras:
def paired_iter(it):
token = it.next()
for lookahead in it:
yield (token, lookahead)
token = lookahead
yield (token, None)
def scan(s):
for c in s:
yield c
for this_token, next_token in paired_iter(scan("ABCDEF")):
print "this:%s next:%s" % (this_token, next_token)
Huellas dactilares:
this:A next:B
this:B next:C
this:C next:D
this:D next:E
this:E next:F
this:F next:None
Puede escribir una envoltura que almacene un número de elementos del generador y proporcione una función lookahead () para mirar esos elementos almacenados:
class Lookahead:
def __init__(self, iter):
self.iter = iter
self.buffer = []
def __iter__(self):
return self
def next(self):
if self.buffer:
return self.buffer.pop(0)
else:
return self.iter.next()
def lookahead(self, n):
"""Return an item n entries ahead in the iteration."""
while n >= len(self.buffer):
try:
self.buffer.append(self.iter.next())
except StopIteration:
return None
return self.buffer[n]
Ya que dices que estás tokenizando una cadena y no una iterable general, sugiero la solución más simple de simplemente expandir tu tokenizador para devolver un 3-tuple: (token_type, token_value, token_index) , donde token_index es el índice del token en la cadena . Luego puedes mirar hacia adelante, hacia atrás o en cualquier otro lugar de la cadena. Simplemente no vayas más allá del final. La solución más simple y flexible, creo.
Además, no necesita utilizar una lista de comprensión para crear una lista a partir de un generador. Simplemente llame al constructor de la lista () en él:
token_list = list(scan(string))