Itera sobre las líneas de una cuerda

119

Tengo una cadena de varias líneas definida así:

foo = """
this is 
a multi-line string.
"""

Esta cadena la usamos como entrada de prueba para un analizador que estoy escribiendo. La función analizador recibe un objeto file-objeto como entrada y lo repite. También llama al next()método directamente para omitir líneas, por lo que realmente necesito un iterador como entrada, no un iterable. Necesito un iterador que recorra las líneas individuales de esa cadena como lo fileharía un objeto sobre las líneas de un archivo de texto. Por supuesto que podría hacerlo así:

lineiterator = iter(foo.splitlines())

¿Existe una forma más directa de hacer esto? En este escenario, la cadena tiene que atravesar una vez para la división y luego otra vez por el analizador. No importa en mi caso de prueba, ya que la cuerda es muy corta allí, solo pregunto por curiosidad. Python tiene muchos elementos integrados útiles y eficientes para tales cosas, pero no pude encontrar nada que se adapte a esta necesidad.

Björn Pollex
fuente
12
eres consciente de que puedes iterar, foo.splitlines()¿no?
SilentGhost
¿Qué quieres decir con "otra vez por el analizador"?
danben
4
@SilentGhost: Creo que el punto es no iterar la cadena dos veces. Una vez que se repite splitlines()y una segunda vez, se repite el resultado de este método.
Felix Kling
2
¿Hay alguna razón en particular por la que splitlines () no devuelve un iterador por defecto? Pensé que la tendencia era hacer eso en general para los iterables. ¿O es esto solo cierto para funciones específicas como dict.keys ()?
Cerno

Respuestas:

144

Aquí hay tres posibilidades:

foo = """
this is 
a multi-line string.
"""

def f1(foo=foo): return iter(foo.splitlines())

def f2(foo=foo):
    retval = ''
    for char in foo:
        retval += char if not char == '\n' else ''
        if char == '\n':
            yield retval
            retval = ''
    if retval:
        yield retval

def f3(foo=foo):
    prevnl = -1
    while True:
      nextnl = foo.find('\n', prevnl + 1)
      if nextnl < 0: break
      yield foo[prevnl + 1:nextnl]
      prevnl = nextnl

if __name__ == '__main__':
  for f in f1, f2, f3:
    print list(f())

Ejecutar esto como el script principal confirma que las tres funciones son equivalentes. Con timeit(y * 100para fooobtener cadenas sustanciales para una medición más precisa):

$ python -mtimeit -s'import asp' 'list(asp.f3())'
1000 loops, best of 3: 370 usec per loop
$ python -mtimeit -s'import asp' 'list(asp.f2())'
1000 loops, best of 3: 1.36 msec per loop
$ python -mtimeit -s'import asp' 'list(asp.f1())'
10000 loops, best of 3: 61.5 usec per loop

Tenga en cuenta que necesitamos la list()llamada para asegurarnos de que los iteradores se atraviesan, no solo se compilan.

IOW, la implementación ingenua es mucho más rápida que ni siquiera es divertida: 6 veces más rápido que mi intento con findllamadas, que a su vez es 4 veces más rápido que un enfoque de nivel inferior.

Lecciones para retener: la medición siempre es algo bueno (pero debe ser precisa); los métodos de cadena como splitlinesse implementan de manera muy rápida; juntar cadenas programando a un nivel muy bajo (especialmente mediante bucles de +=piezas muy pequeñas) puede ser bastante lento.

Editar : se agregó la propuesta de @ Jacob, ligeramente modificada para dar los mismos resultados que los demás (se mantienen los espacios en blanco al final de una línea), es decir:

from cStringIO import StringIO

def f4(foo=foo):
    stri = StringIO(foo)
    while True:
        nl = stri.readline()
        if nl != '':
            yield nl.strip('\n')
        else:
            raise StopIteration

La medición da:

$ python -mtimeit -s'import asp' 'list(asp.f4())'
1000 loops, best of 3: 406 usec per loop

no es tan bueno como el .findenfoque basado; aún así, vale la pena tenerlo en cuenta porque podría ser menos propenso a pequeños errores uno por uno (cualquier bucle en el que vea apariciones de +1 y -1, como el f3anterior, debería automáticamente desencadenar sospechas de uno en uno, y también deberían hacerlo muchos bucles que carecen de tales ajustes y deberían tenerlos, aunque creo que mi código también es correcto ya que pude verificar su salida con otras funciones ').

Pero el enfoque basado en la división aún prevalece.

Un aparte: posiblemente un mejor estilo para f4sería:

from cStringIO import StringIO

def f4(foo=foo):
    stri = StringIO(foo)
    while True:
        nl = stri.readline()
        if nl == '': break
        yield nl.strip('\n')

al menos, es un poco menos detallado. La necesidad de eliminar los trailing \ns desafortunadamente prohíbe el reemplazo más claro y rápido del whilebucle con return iter(stri)(la iterparte de la cual es redundante en las versiones modernas de Python, creo que desde 2.3 o 2.4, pero también es inocuo). Quizás valga la pena intentarlo, también:

    return itertools.imap(lambda s: s.strip('\n'), stri)

o variaciones de los mismos, pero me detengo aquí, ya que es más o menos un ejercicio teórico que es el stripmás simple y rápido.

Alex Martelli
fuente
Además, (line[:-1] for line in cStringIO.StringIO(foo))es bastante rápido; casi tan rápido como la implementación ingenua, pero no del todo.
Matt Anderson
Gracias por esta gran respuesta. Supongo que la lección principal aquí (ya que soy nuevo en Python) es convertir el uso en timeitun hábito.
Björn Pollex
@Space, sí, el tiempo es bueno, siempre que te preocupes por el rendimiento (asegúrate de usarlo con cuidado, por ejemplo, en este caso, mira mi nota sobre la necesidad de una listllamada para cronometrar todas las partes relevantes).
Alex Martelli
6
¿Qué pasa con el consumo de memoria? split()claramente intercambia memoria por rendimiento, manteniendo una copia de todas las secciones además de las estructuras de la lista.
ivan_pozdeev
3
Sus comentarios me confundieron mucho al principio porque enumeró los resultados de tiempo en el orden opuesto a su implementación y numeración. = P
jamesdlin
53

No estoy seguro de lo que quiere decir con "luego otra vez por el analizador". Una vez que se ha realizado la división, no hay más recorrido de la cadena , solo un recorrido de la lista de cadenas divididas. Esta será probablemente la forma más rápida de lograrlo, siempre que el tamaño de su cuerda no sea absolutamente enorme. El hecho de que Python use cadenas inmutables significa que siempre debes crear una nueva cadena, por lo que esto debe hacerse en algún momento de todos modos.

Si su cadena es muy grande, la desventaja está en el uso de la memoria: tendrá la cadena original y una lista de cadenas divididas en la memoria al mismo tiempo, duplicando la memoria requerida. Un enfoque de iterador puede ahorrarle esto, construyendo una cadena según sea necesario, aunque todavía paga la penalización de "división". Sin embargo, si la cadena es tan grande, por lo general, quiere evitar incluso la flor sin dividir cadena esté en la memoria. Sería mejor simplemente leer la cadena de un archivo, que ya le permite iterar a través de él como líneas.

Sin embargo, si ya tiene una cadena enorme en la memoria, un enfoque sería usar StringIO, que presenta una interfaz similar a un archivo para una cadena, lo que incluye permitir la iteración por línea (usando internamente .find para encontrar la siguiente nueva línea). Entonces obtienes:

import StringIO
s = StringIO.StringIO(myString)
for line in s:
    do_something_with(line)
Brian
fuente
5
Nota: para python 3, debe usar el iopaquete para esto, por ejemplo, use en io.StringIOlugar de StringIO.StringIO. Ver docs.python.org/3/library/io.html
Attila123
El uso StringIOtambién es una buena manera de obtener un manejo de nueva línea universal de alto rendimiento.
Martineau
3

Si leo Modules/cStringIO.ccorrectamente, esto debería ser bastante eficiente (aunque algo detallado):

from cStringIO import StringIO

def iterbuf(buf):
    stri = StringIO(buf)
    while True:
        nl = stri.readline()
        if nl != '':
            yield nl.strip()
        else:
            raise StopIteration
Jacob Oscarson
fuente
3

La búsqueda basada en expresiones regulares es a veces más rápida que el enfoque del generador:

RRR = re.compile(r'(.*)\n')
def f4(arg):
    return (i.group(1) for i in RRR.finditer(arg))
par
fuente
2
Esta pregunta se trata de un escenario específico, por lo que sería útil mostrar un punto de referencia simple, como lo ha hecho la respuesta de mayor puntuación.
Björn Pollex
1

Supongo que podrías rodar el tuyo:

def parse(string):
    retval = ''
    for char in string:
        retval += char if not char == '\n' else ''
        if char == '\n':
            yield retval
            retval = ''
    if retval:
        yield retval

No estoy seguro de cuán eficiente es esta implementación, pero solo iterará sobre su cadena una vez.

Mmm, generadores.

Editar:

Por supuesto, también querrá agregar cualquier tipo de acciones de análisis que desee realizar, pero eso es bastante simple.

Wayne Werner
fuente
Bastante ineficiente para líneas largas (la +=parte tiene el peor O(N squared)rendimiento de los casos , aunque varios trucos de implementación intentan reducirlo cuando sea posible).
Alex Martelli
Sí, acabo de aprender sobre eso recientemente. ¿Sería más rápido agregar a una lista de caracteres y luego '' .unirlos (caracteres)? ¿O es un experimento que debería realizar yo mismo? ;)
Wayne Werner
por favor, mídete, es instructivo, ¡y asegúrate de probar tanto líneas cortas como en el ejemplo del OP como largas! -)
Alex Martelli
Para cadenas cortas (<~ 40 caracteres), + = es en realidad más rápido, pero llega al peor de los casos rápidamente. Para cadenas más largas, el .joinmétodo en realidad parece una complejidad O (N). Como todavía no pude encontrar la comparación particular hecha en SO, comencé una pregunta stackoverflow.com/questions/3055477/… (¡que sorprendentemente recibió más respuestas que las mías!)
Wayne Werner
0

Puede iterar sobre "un archivo", lo que produce líneas, incluido el carácter de nueva línea final. Para hacer un "archivo virtual" a partir de una cadena, puede usar StringIO:

import io  # for Py2.7 that would be import cStringIO as io

for line in io.StringIO(foo):
    print(repr(line))
Tomasz Gandor
fuente