Iterieren Sie über die Zeilen einer Zeichenfolge

119

Ich habe eine mehrzeilige Zeichenfolge wie folgt definiert:

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

Diese Zeichenfolge haben wir als Testeingabe für einen Parser verwendet, den ich schreibe. Die Parser-Funktion empfängt ein file-Objekt als Eingabe und iteriert darüber. Es ruft die next()Methode auch direkt auf, um Zeilen zu überspringen, daher brauche ich wirklich einen Iterator als Eingabe, keinen iterierbaren. Ich brauche einen Iterator, der über die einzelnen Zeilen dieser Zeichenfolge iteriert, wie ein fileObjekt über die Zeilen einer Textdatei. Ich könnte es natürlich so machen:

lineiterator = iter(foo.splitlines())

Gibt es einen direkteren Weg, dies zu tun? In diesem Szenario muss die Zeichenfolge einmal für die Aufteilung und dann erneut vom Parser durchlaufen werden. In meinem Testfall spielt es keine Rolle, da die Saite dort sehr kurz ist, frage ich nur aus Neugier. Python hat so viele nützliche und effiziente integrierte Funktionen für solche Dinge, aber ich konnte nichts finden, das diesem Bedarf entspricht.

Björn Pollex
quelle
12
Sie wissen, dass Sie über iterieren können, foo.splitlines()oder?
SilentGhost
Was meinst du mit "wieder vom Parser"?
Danben
4
@ SilentGhost: Ich denke, es geht darum, die Zeichenfolge nicht zweimal zu wiederholen. Sobald es durch splitlines()und ein zweites Mal durch Iteration über das Ergebnis dieser Methode iteriert wird .
Felix Kling
2
Gibt es einen bestimmten Grund, warum splitlines () standardmäßig keinen Iterator zurückgibt? Ich dachte, der Trend geht dahin, dies generell für iterables zu tun. Oder gilt dies nur für bestimmte Funktionen wie dict.keys ()?
Cerno

Antworten:

144

Hier sind drei Möglichkeiten:

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())

Wenn Sie dies als Hauptskript ausführen, wird bestätigt, dass die drei Funktionen gleichwertig sind. Mit timeit(und einem * 100für foo, um wesentliche Zeichenfolgen für eine genauere Messung zu erhalten):

$ 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

Beachten Sie, dass wir den list()Aufruf benötigen , um sicherzustellen, dass die Iteratoren durchlaufen und nicht nur erstellt werden.

IOW, die naive Implementierung ist so viel schneller, dass es nicht einmal lustig ist: 6-mal schneller als mein Versuch mit findAnrufen, was wiederum 4-mal schneller ist als ein Ansatz auf niedrigerer Ebene.

Zu behaltende Lektionen: Messung ist immer eine gute Sache (muss aber genau sein); String-Methoden wie splitlineswerden sehr schnell implementiert; Das Zusammensetzen von Saiten durch Programmieren auf einer sehr niedrigen Ebene (insbesondere durch Schleifen +=sehr kleiner Stücke) kann sehr langsam sein.

Bearbeiten : @ Jacobs Vorschlag hinzugefügt, leicht modifiziert, um die gleichen Ergebnisse wie die anderen zu erzielen (nachgestellte Leerzeichen in einer Zeile bleiben erhalten), dh:

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

Messen ergibt:

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

Nicht ganz so gut wie der .findbasierte Ansatz - dennoch sollte man bedenken, dass er möglicherweise weniger anfällig für kleine Fehler ist (jede Schleife, in der Sie Vorkommen von +1 und -1 sehen, wie f3oben, sollte automatisch erfolgen Auslösen von Verdachtsmomenten - und auch viele Schleifen, denen solche Optimierungen fehlen und die sie haben sollten - obwohl ich glaube, dass mein Code auch richtig ist, da ich seine Ausgabe mit anderen Funktionen überprüfen konnte ').

Der Split-basierte Ansatz regiert jedoch weiterhin.

Nebenbei: Möglicherweise wäre ein besserer Stil für f4:

from cStringIO import StringIO

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

Zumindest ist es etwas weniger ausführlich. Die Notwendigkeit, nachgestellte \ns zu entfernen, verhindert leider das klarere und schnellere Ersetzen der whileSchleife durch return iter(stri)(der iterTeil davon ist in modernen Versionen von Python überflüssig, glaube ich seit 2.3 oder 2.4, aber es ist auch harmlos). Vielleicht auch einen Versuch wert:

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

oder Variationen davon - aber ich höre hier auf, da es so ziemlich eine theoretische Übung für die stripbasierte, einfachste und schnellste ist.

Alex Martelli
quelle
Auch (line[:-1] for line in cStringIO.StringIO(foo))ist ziemlich schnell; fast so schnell wie die naive Umsetzung, aber nicht ganz.
Matt Anderson
Vielen Dank für diese tolle Antwort. Ich denke, die wichtigste Lektion hier (da ich neu in Python bin) ist es, timeiteine Gewohnheit zu verwenden.
Björn Pollex
@Space, yep, timeit ist immer gut, wenn Sie sich für die Leistung interessieren (achten Sie darauf, dass Sie es sorgfältig verwenden, z. B. in diesem Fall meinen Hinweis, dass Sie einen listAnruf benötigen , um alle relevanten Teile tatsächlich zeitlich zu steuern ! -).
Alex Martelli
6
Was ist mit dem Speicherverbrauch? split()Tauschen Sie Speicher eindeutig gegen Leistung aus und halten Sie zusätzlich zu den Listenstrukturen eine Kopie aller Abschnitte bereit.
ivan_pozdeev
3
Ihre Bemerkungen haben mich zunächst wirklich verwirrt, weil Sie die Timing-Ergebnisse in der entgegengesetzten Reihenfolge ihrer Implementierung und Nummerierung aufgelistet haben. = P
Jamesdlin
53

Ich bin mir nicht sicher, was du mit "dann wieder mit dem Parser" meinst. Nachdem die Aufteilung durchgeführt wurde, erfolgt keine weitere Durchquerung der Zeichenfolge , sondern nur eine Durchquerung der Liste der geteilten Zeichenfolgen. Dies ist wahrscheinlich der schnellste Weg, um dies zu erreichen, solange die Größe Ihrer Zeichenfolge nicht absolut groß ist. Die Tatsache, dass Python unveränderliche Zeichenfolgen verwendet, bedeutet, dass Sie immer eine neue Zeichenfolge erstellen müssen , sodass dies ohnehin irgendwann erfolgen muss.

Wenn Ihre Zeichenfolge sehr groß ist, liegt der Nachteil in der Speichernutzung: Sie haben gleichzeitig die ursprüngliche Zeichenfolge und eine Liste der geteilten Zeichenfolgen im Speicher, wodurch sich der erforderliche Speicher verdoppelt. Ein Iterator-Ansatz kann Ihnen dies ersparen und nach Bedarf eine Zeichenfolge erstellen, obwohl die Strafe für das "Aufteilen" immer noch gezahlt wird. Wenn Ihre Zeichenfolge jedoch so groß ist, möchten Sie im Allgemeinen vermeiden, dass sich auch die nicht aufgeteilte Zeichenfolge im Speicher befindet. Es ist besser, nur die Zeichenfolge aus einer Datei zu lesen, damit Sie sie bereits als Zeilen durchlaufen können.

Wenn Sie jedoch bereits eine große Zeichenfolge im Speicher haben, besteht ein Ansatz darin, StringIO zu verwenden, das eine dateiähnliche Schnittstelle zu einer Zeichenfolge darstellt, einschließlich des Erlaubens einer zeilenweisen Iteration (intern mit .find, um die nächste neue Zeile zu finden). Sie erhalten dann:

import StringIO
s = StringIO.StringIO(myString)
for line in s:
    do_something_with(line)
Brian
quelle
5
Hinweis: Für Python 3 müssen Sie hierfür das ioPaket verwenden, z . B. io.StringIOanstelle von StringIO.StringIO. Siehe docs.python.org/3/library/io.html
Attila123
Die Verwendung StringIOist auch ein guter Weg, um ein universelles Newline-Handling mit hoher Leistung zu erhalten.
Martineau
3

Wenn ich Modules/cStringIO.crichtig lese , sollte dies ziemlich effizient sein (obwohl etwas ausführlich):

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
quelle
3

Die Regex-basierte Suche ist manchmal schneller als der Generator-Ansatz:

RRR = re.compile(r'(.*)\n')
def f4(arg):
    return (i.group(1) for i in RRR.finditer(arg))
Steckdosenpaar
quelle
2
Diese Frage bezieht sich auf ein bestimmtes Szenario, daher wäre es hilfreich, einen einfachen Benchmark zu zeigen, wie es die Antwort mit der höchsten Punktzahl getan hat.
Björn Pollex
1

Ich nehme an, Sie könnten Ihre eigenen rollen:

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

Ich bin mir nicht sicher, wie effizient diese Implementierung ist, aber das wird Ihre Zeichenfolge nur einmal durchlaufen.

Mmm, Generatoren.

Bearbeiten:

Natürlich möchten Sie auch jede Art von Parsing-Aktionen hinzufügen, die Sie ausführen möchten, aber das ist ziemlich einfach.

Wayne Werner
quelle
Ziemlich ineffizient für lange Leitungen (das +=Teil weist die schlechteste O(N squared)Leistung auf, obwohl mehrere Implementierungstricks versuchen, diese zu senken, wenn dies möglich ist).
Alex Martelli
Ja - das habe ich erst kürzlich erfahren. Wäre es schneller, an eine Liste von Zeichen anzuhängen und sie dann zu verbinden? Oder ist das ein Experiment, das ich selbst durchführen sollte? ;)
Wayne Werner
Bitte messen Sie sich selbst, es ist lehrreich - und probieren Sie sowohl kurze als auch lange Zeilen aus! -)
Alex Martelli
Bei kurzen Saiten (<~ 40 Zeichen) ist das + = tatsächlich schneller, trifft aber schnell den schlimmsten Fall. Bei längeren Zeichenfolgen .joinsieht die Methode tatsächlich nach O (N) -Komplexität aus. Da ich den speziellen Vergleich, der auf SO gemacht wurde, noch nicht finden konnte, startete ich eine Frage stackoverflow.com/questions/3055477/… (die überraschenderweise mehr Antworten erhielt als nur meine eigene!)
Wayne Werner
0

Sie können über "eine Datei" iterieren, wodurch Zeilen einschließlich des nachgestellten Zeilenumbruchs erzeugt werden. Um eine "virtuelle Datei" aus einer Zeichenfolge zu erstellen, können Sie Folgendes verwenden StringIO:

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

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