Sebastian Schmid bio photo

Sebastian Schmid

Student der angewandten Informatik an der HTW Berlin.
Interessen sind Linux, Latex und Python.

Github Stackoverflow

Die faule Methode um speichersparend große Daten vorzuhalten

Da sich Python besonders eignet um mit (auch mal größeren) Daten zu hantieren, stellt sich häufig das Problem, dass die Daten einen solchen Umfang erreichen, dass das Vorhalten der gesamten Werte in Datenstrukturen jedweder Art im RAM zu Problemen führen kann. Neben dem Vorhalten ist dies der Zeitpunkt, an dem man sich auch Gedanken machen sollte, welche Werkzeuge man wirklich braucht um die Daten zu bearbeiten. Denn warum braucht man Werkzeuge wie slicing oder Einzelauswahl, wenn man die Liste nur einmal durchiterieren möchte und dann je nach Einzelwert bestimmte Entscheidungen oder Berechnungen ausführen möchte.

Zu diesem Zweck gibt es in Python bereits seit Version 2.2 die so genannten Generatoren.

Iterationen abseits der gewohnten for-Schleife

Folgende Schreibweise für das Iterieren eines Datensatzes dürfte jedem bekannt sein.

for char in 'word':
    print(char)
w
o
r
d

Genau das selbe kann aber auch als sogenanntes Iterator-Statement ausgedrückt werden.

word = iter('word')
while True:
    print(next(iterator_word))
w
o
r
d

---------------------------------------------------------------------------
StopIteration                             Traceback (most recent call last)
<ipython-input-3-72068b206a0e> in <module>()
      1 word = iter('word')
      2 while True:
----> 3     print(next(word))

StopIteration:

So wird das Objekt so lange iteriert, bis man am Ende des Datensatzes angelangt ist und mit einer Exception beendet. Hier kann man sehr gut sehen, dass Ausnahmebehandlungen anders als in anderen Sprachen sehr wohl als normales Sprachelement verwendet werden. Auf diese Weise ist es einfach möglich relativ simple Datensätze wie Strings iterierbar zu machen, ohne dass man die Länge der Datenstruktur mitführen muss.

So kann man das Verhalten der for-Schleife auch folgendermaßen nachstellen.

word = iter('word')
while True:
    try:
        print(next(word))
    except StopIteration:
        break
w
o
r
d

Natürlich ist es einfacher mit einer normalen for-Schleife über einen Datensatz zu iterieren. Das man sich Iteratorobjekte erstellt, wird auch wirklich nur in wenigen Ausnamefällen interessant sein. Doch ist es wichtig, sich zu vergewissern, was unter der Haube passiert, wenn man ein iterierbares Objekt in Python mit einer for-Schleife durchläuft.

word = iter('word')

Durch diesen Ausdruck wird der gesamte Datensatz in den Hauptspeicher des Computers kopiert. Das mag bei solch kleinen Datensätzen noch kein Problem darstellen. Doch wenn man zum Beispiel 1 Million Zahlen von einem Würfelexperiment aus einer Datei auslesen möchte um sie zu untersuchen, kann das auf Computern mit eher wenig Hauptspeicher schon zu Problemen führen. Zumindest wird der RAM sich ziemlich füllen. Hier werden auch immer alle der Ziffern vorgehalten, obwohl wir in unserer for-Schleife ja immer nur eine einzige untersuchen.

def diggit_list():
    infile = open('onemillion.txt')
    lst = []
    for line in infile.readlines():
        for diggit in line.strip().split(" "):
            lst.append(int(diggit))
    infile.close()
    return lst

Man sieht sehr schön, dass alle Werte aus der Datei herausgenommen werden und nach und nach an die Liste angehängt werden, die dann als Ganzes als Rückgabewert der Methode an den Aufrufer zurückgegeben wird.

Ein Aufrufer, der herausfinden möchte, wie viele der Zahlen ungerade sind, muss also zuerst alle der Zahlen in den Arbeitsspeicher kopieren um sie darin zu untersuchen.

odds = 0
for diggit in diggit_list():
    if not diggit % 2 == 0:
        odds += 1
print(odds)
499878

Dabei wäre es doch viel effizienter, immer nur genau das Datum im Speicher zu haben, das man gerade untersucht. Wenn man weiss, dass man die Daten sowieso nur iteriert, verschwenden zu jedem Zeitpunkt die 999999 Werte, die gerade nicht gebraucht werden, nur Platz. Genau dieses Problem wird durch Generatoren gelöst. Durch folgende Schreibweise erhält man einen Generator, der wie oben die Datei einliest und jeweils die nach int konvertierten Werte aus der Datei zurückgibt.

def diggit_generator():
    infile = open('onemillion.txt') 
    for line in infile:
        for diggit in line.strip().split(" "):
            yield int(diggit)
    infile.close()

yield, das return der Generatoren

Wie man oben sehen kann, werden die Werte nicht erst in einer Liste gesammelt und zurückgegeben, sondern einzeln mit dem yield Statement zurückgegeben.

Die Verarbeitung der Methode ist dann wie gehabt.

odds = 0
for diggit in diggit_generator():
    if not diggit % 2 == 0:
        odds += 1
print(odds)
499878

Nur das jetzt an jedem Punkt der Iteration nur der eine Wert vorgehalten wird, der auch gerade untersucht wird. Auf diese Weise lässt sich also der Speicherverbrauch des Programms drastisch reduzieren.

Wer genau aufgepasst hat, wird auch gesehen haben, dass sich in den Funktionen das Auslesen der Zeilen aus der Datei unterschieden haben.

Wärend

for line in infile.readlines():
	pass

die Datei als Iterationsobjekt, also als Liste behandelt. Ist folgendes ein eingebauter Generator in open.

for line in infile:
	pass

Denn was bringt es, in der letzten Abstraktionsebene sauber mit speichersparenden Methoden zu arbeiten, wenn davor Speicher ohne Ende verschwendet wird?

Generatoren als Expressions

Wie auch bei List-/Dict-Comprehensions lassen sich Generatoren sehr elegant und einfach als Expressions ausdrücken.

infile = open('onemillion.txt')
# Tief verschachtelte Ausdrücke werden in der selben Reihenfolge geschrieben
# wie in 'normalen' Schleifenkonstruktionen, geführt von dem Rückgabewert.
dig_gen = (int(diggit)
            for line in infile 
            for diggit in line.strip().split(" "))
# (...)
# Erst schließen, wenn der Zugriff auf die Daten abgeschlossen ist.
infile.close()

Auch wenn diese Schreibweise am Anfang etwas ungewohnt scheint, so ist sie, hat man sich mal an den Ausdruck gewöhnt, sehr intuitiv und durch die kompakte Schreibweise viel einfacher lesbar als tief verschachtelte Ausdrücke.

Zum Vergleich hier noch die Schreibweise wenn man die Daten als Liste vorhalten möchte.

infile = open('onemillion.txt')
dig_lst = [int(diggit)
            for line in infile.readlines() 
            for diggit in line.strip().split(" ")]
# Daten wurden kopiert, deswegen kann die Datei sofort geschlossen werden.
infile.close()

Als Unterschied im Syntax ist eigentlich nur die Art der Klammern ersichtlich. wärend List-Comprehensions mit [ x for x in … ] arbeiten, sind es bei Generatoren folgende Klammern ( x for x in … ). Zur Erinnerung, wenn mit dict-Comprehensions gearbeitet wird, ist folgende Schreibweise die gewünschte { k,v for k,v in … }.

Sind Generatoren immer schneller als Listen?

Der Umstand dass Generatoren weniger Speicher verbrauchen, lässt die Vermutung aufkommen, die Verarbeitung von Datensätzen sei in jedem Fall schneller als die Verarbeitung von Listen. Dies stimmt aber nur bedingt und kommt auf die jeweiligen Fälle und Daten an.

So war bei mir die Überraschung groß als ich die Zeiten des hier untersuchten einemillion-Datei-Problems untersucht hatte. So war die Verarbeitung mittels Expressions/Comprehension zwar in jedem Fall schneller als über Funktionen. Aber anders als erwartet, war die Verarbeitung mittels Listen schneller als über Generatoren. Dazu muss aber auch gesagt werden, dass ich mit 8GB relativ schnellem RAM recht gut bestellt bin und dass das Eregebniss in einer VM mit wenig Hauptspeicher schon anders ausgesehen hätte.

Es sei aber festzuhalten, dass Generatoren zwar ein Garant für speichersparende, aber nicht in jedem Fall für schnellere Programme sind. Gerade wenn, wie in diesem Fall, Dateien geöffnet und Cast, sowie String-Operationen ausgeführt werden, kann es sein, dass bei genügend RAM die Verarbeitung durch list-Comprehensions schneller ist, als über Generatoren.

Wenn dies wichtig ist, sollte das je nach Anwendungsfall getestet und je nachdem was effizienter ist, so umgesetzt werden.